welcome: please sign in

Please enter your password of your account at the remote wiki below.
/!\ You should trust both wikis because the password could be read by the particular administrators.

Clear message
location: VisitAll

VisitAll

Problem Description

This domain was created by Nir Lipovetzky and Héctor Geffner for the IPC 2011, to evaluate the performance of planners in problems with multiple conflicting goals. It is somehow inspired by the Dispose domain created by Héctor Palacios and Héctor Geffner for the conformant subtrack of the uncertainty part of the International Planning Competition celebrated in 2008 [1]. In the Visitall domain a robot in the middle of a $n\times n$ square grid must visit all the cells in the grid. There is only one action in this domain, which moves the robot from one cell to another one. From a planning community perspective, in this kind of problem, progress toward one goal means moving away from other goals. Such problems typically produce large plateaus in planners based on delete-relaxation heuristics, where this heuristic is almost useless. Similarly, the specific features of this domain cause ASP solvers to visit a large search tree with few or no possibility of early pruning. In the ASP Comp 2013 version, some unreachable grid cells were added in the grid, while the original problem was defined over plain square grids.

The objective is to minimize the number of moves. The number of goals is the number of cells, except for the sequential optimal subtrack where there are problems where only half of the cells have to be visited. In addition to be challenging to the delete-relaxation heuristics, this domain has a high number of goals, up to 2,500 in the most complex problem.

Predicates

Input format

The grid consists of a square matrix of NxN locations. While most of them can be occupied by a robot, a few are unreachable. Thus, to describe the geometry of the grid, the predicate connected/2 explicitly describes what positions are reachable from the other (so that unreachable locations are just ignored):

connected(l1,l2): l2 is reachable from l1 (i.e. the robot can step from l1 to l2).

There is a single robot. The original position of the robot is described with:

at(l): the robot is located at location l

The goal of this problem is to find the optimal path that takes the robot from its current location to a number of given cells. The goal locations are identified with the predicate visit/1:

visit(l): l is a goal location

On the other hand, since the solution consists of a sequence of steps, these are identified by the following input predicate:

step(s): s is a step, for s a positive integer.

Output format

A witness should consist of a sequence of moves of the robot that fulfills the goals of the problem. That is, it should find a path (not necessarily acyclic!) that starts at the location specified by at/1 and visits all the locations specified by visit/1. These movements are just represented by the predicate move/2:

move(l1,l2,s): move the robot from l1 to l2 at time step s

Example(s)

+--+--+--+
|  |  |  |
+--+--+--+
|XX|RR|  |
+--+--+--+
|  |  |XX|
+--+--+--+

The previous figure shows a small grid with 3 rows and 3 columns. Those marked with XX are unreachable and the goal consists of visiting all reachable locations from the initial position of the robot, located at (2,2).

The geometry of the problem is described with:

connected(x1y1,x2y1). connected(x2y1,x1y1). 
connected(x2y1,x3y1). connected(x3y1,x2y1).

connected(x2y2,x3y2). connected(x3y2,x2y2).

connected(x1y3,x2y3). connected(x2y3,x1y3). 
connected(x2y3,x3y3). connected(x3y3,x2y3).

connected(x2y1,x2y2). connected(x2y2,x2y1).
connected(x2y2,x2y3). connected(x2y3,x2y2).

connected(x3y1,x3y2). connected(x3y2,x3y1).
connected(x3y2,x3y3). connected(x3y3,x3y2).

The initial location of the robot is specified with:

at(x2y2).

Assume that in this particular problem it is required to visit all locations of the grid ---including the current location of the robot. This requirement appears described as:

visit(x1y1). visit(x2y1). visit(x3y1).
visit(x2y2). visit(x3y2).
visit(x1y3). visit(x2y3).

Finally, a sufficiently large sequence of time-steps is provided as well in the input:

step(1). step(2). step(3).
step(4). step(5). step(6).
step(7). step(8).

The output shown below contains a description of an optimal solution:

move(x2y2,x3y2,1). move(x3y2,x3y1,2).
move(x3y1,x2y1,3). move(x2y1,x1y1,4).
move(x1y1,x2y1,5). move(x2y1,x2y2,6).
move(x2y2,x2y3,7). move(x2y3,x1y3,8).

Problem Peculiarities

Type: Search Competition: System Track

Notes and Updates

Author(s)

References

[1] Daniel Bryce and Olivier Buffet. 6th International Planning Competition: Uncertainty Part. 2008