Wire routing

In this second assignment we will use telingo  to solve a variant of the wire routing problem as a multi-robot planning problem. Given a rectangular grid, the problem consists in joining pairs of points (named with the same letter {a,b,c,...} ) with a continuous line that does not intersect with lines for other pairs. Some of the grid cells are marked as obstacles.

The input will be given as a text file where the two first lines respectively contain the number of rows and columns of the grid. We use "." to represent an (initially) empty cell, "#" to represent an obstacle and letters {a,b,c,...} to mark pairs of points to be joined. The output is a text file where each "wire" is traced using the corresponding letter. As an example:

6 7 .a....b ....... ..b..## .##..## .##...a .....##	.a..bbb aa..b.. a.bbb## a##..## a##.aaa aaaaa##
Initial configuration: two wires, a and b, are needed	A possible solution

• To read the input files and transform them into telingo facts you can use the python program encodew.py as follows
  
  

  python3 encodew.py < grid1.txt > grid1.lp

• The input uses predicate end(W,c(X,Y)) meaning that one of the two ends of wire W is at cell c(X,Y). It also uses predicate obs(X,Y) meaning that there is an obstacle at X,Y
• Telingo output can be displayed as an ASCII map using the program decodew.py. This requires the predicates dim(N,M) with the dimensions of the board (N = rows, M=columns), the predicate obs(X,Y) and a predicate fill(X,Y,W) meaning that cell X,Y has wire W. As an example of use
• 
  

  python3 decodew.py wire.lp grid1.lp

File examples-wire.zip will contain a set of benchmarks of different sizes. Solutions are not included: several minimal solutions can be obtained.

Assessment & delivery