Lab Assignment #2

Vacuum cleaner

ASP planning


In this exercise, we will use ASP to solve a planning problem. We have a vacuum cleaner robot that must cover the whole open surface of a room, represented as a grid of floor tiles, going from a starting position to a final goal position.

What to do

To describe the scenario, we will use a text file to represent the grid, using a format like the one below:


with the following meaning

= empty floor tile

= empty floor tile, initial robot's position

= empty floor tile, goal position

= obstacle

Several benchmarks will be available here. You will have to create a filter program (C, python, java, etc) that transforms this input into ASP facts describing the scenario, using the predicates you decide for representing the problem. These files with input facts will be named roomN.txt. The main ASP file, cleaner.txt, will contain an encoding of the generic planning problem to be solved into ASP. The main call will look like:

clingo cleaner.txt room1.txt

We will use incremental solving, so clingo will go trying different path lengths until a minimal plan is found. The solutions must be expressed in terms of predicate move(D,T) meaning that the robot moved in some direction D={u,d,l,r} (up, down, left, right) at each time T=1,...,n, where n is the plan length.

Assessment & delivery

The maximum grade for this exercise is 0,65 points =0,65% of the course. The deadline for delivery is Friday, April 20th, 2018 using the MOODLE assignment. Exercises can be made by groups of 2 students at most: you will have to repeat the same group configuration of exercise 1. Only one student per group 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 the filter program for the input files. Regardless of the programming language you choose, avoid using non-standard libraries.

Maintained by Pedro Cabalar. Last update 1/3/2018