Lab Assignment #1
Wire routing
Temporal ASP
Introduction
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
|
What to do
Encode the problem in telingo,
treating each wire as a moving robot that leaves a wire
portion behind. You will need a preprocessing step for
transforming the input into facts and a post-processing
step for decoding your problem representation and printing
the final map. These two steps can be programmed in any
standard programming language (java, C, python, etc).
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
The maximum grade for this exercise is 0,95
points = 9,5% of the course. The deadline for
delivery is Friday, April 26th,
2019 using the MOODLE assignment. When
grouping by pairs of students, the same group
configuration of assignment 1 must be repeated. If so,
only one student is required to deliver the files in
moodle, but all source files must contain the names of the
two group members.
Delivery: upload all files in a .zip including a
README.txt describing how to compile and execute the code.
Regardless of the programming language you choose,
avoid using non-standard libraries.
|
|
|