Problem Domains for Generalized Planning

This is a compilation of some test problems from the generalized planning literature. The selection features problems that generalize in a well-defined manner and permit reasonably simple expressions of plan preconditions. The objective is to be able to find plans for these problems that fair well along all of the evaluation measures. To the best of our knowledge, no existing approach can do so for all of these problems.

• In all the problems, the variables N and M are unknown, and unbounded.
• Most actions are from standard benchmark PDDL domains and are expected to have similar preconditions.
• Problems are described at a high-level; the exact action representations and predicate vocabularies are up to the implementation.
• In order to have a meaningful exchange of ideas, we encourage researchers to discuss any extra actions or predicates used, as a part of their results.
• If any of the problem descriptions needs clarification, contact me.

1. Accumulator (Levesque, 2005)
   

   Initial states	Two accumulators set to zero, unknown integer input N.
   Actions	incr_acc(i): increments accumulator i; test_acc(): tests if first accumulator has the same value as input.
   Goal	Second accumulator must have value 2N-1.








2. Unit Delivery (Srivastava et al., 2008)
   

   Initial states	Transport map with a dock, N delivery locations, a truck of capacity one, M packages at the dock, each marked with its destination location. All destinations are connected directly to the dock.
   Actions	mvTo(l): move truck to l; findDest(p): sense destination of package p; load(p): load package p on to the truck. p must be at truck's current location; unload(): unload the package currently in the truck.
   Goal	All packages must be at their destinations.

   
   
   
   
   
   
   
   
   
   
   
   
3. Green Block (Bonet et al., 2009)
   

   Initial states	Tower with N blocks. At any stage, the color of only the topmost block is known.
   Actions	Unstack: puts the topmost block in the gripper; Drop: discards the block being held; Collect: collects the block being held.
   Goal	Collect a green block. This is achievable only if the tower had a green block.

   
   
   
   
   
   
   
   
   
   
4. N Good Eggs (Bonet and Geffner, 2001; Levesque, 2005)
   

   Initial states	An unbounded quantity of good and bad eggs; input parameter N.
   Actions	break(): picks an egg from the supply and breaks it into a dish; discard(): discards the contents of the dish; sniff_dish(): returns an observation reflecting whether the last egg to be broken was good or bad.
   Goal	Dish must have N good eggs.

   
   
   
   
   
   
   
   
   
   
5. Recycling (Srivastava et al., 2010)
   

   Initial states	N bins with objects of type paper and glass.
   Actions	mvToNext(): moves agent to next non-empty bin; pickObj(o,b): picks an object from bin b (agent must be at bin b); senseType(o): sense type of picked object o (paper, glass); collectPaper(o): collect object o in paper container; collectGlass(o): collect object o in glass container.
   Goal	All bins must be empty; all paper objects must be in the paper container and glass objects must be in the glass container.

   
   
   
   
   
   
   
   
   
   
   
   
6. Searching an Unbounded Binary Tree (Levesque, 2005)
   

   Initial states	An unbounded full binary tree (every non-leaf node has exactly two children).
   Actions	check_node_type(): sense if the current node is a target node, non-target leaf node, or non-target internal node; push_down_to(x): x is L or R; moves down to the left or right child from an internal node; pop_up_from(): move to the parent node.
   Goal	Reach the target node, if present.

   
   
   
   
   
   
   
   
   
   The push_down_to and pop_up_from actions in this problem use an internal stack to keep track of the direction in which the descent was made.
   
   
7. Striped Tower (Srivastava et al., 2008)
   

   Initial states	A tower of blocks with N blue blocks above M red blocks. The bottom most, red block of the tower satisfies the predicate "base".
   Actions	mv(b,c): place block b on block c (both b and c must be clear); mvToTable(b): place block b on the table (b must be clear).
   Goal	A striped tower of blocks of alternating colors, starting with the "base" block at the bottom.

   
   
   
   
   
   
   
   
   
8. Y-Transport (Srivastava et al., 2008)
   

   Initial states	A Y-shaped tranport graph with locations L1, L2, L3 at the end points and D at the center. N monitors are present at L1 and M servers at L2. Trucks T1 and T2 of capacities 1 and 2 are initially at L1 and L2 respectively.
   Actions	loadTi(o): load object o onto Ti (o and Ti must be at the same location); mv(Ti, Li): move truck Ti to Li (possible only along the edges of the Y-shaped transport graph.); unloadTi(o): unload object o from truck Ti. At l3, objects can be unloaded only in pairs consisting of a monitor and a server.
   Goal	Deliver all objects at L3. This is possible only if N=M.

   
   
   
   
   
   
   
   
   
   
   
   
   

Grid Problems

1. Corner (Bonet et al., 2009)
   

   Initial states	N x M grid with an agent at the southwest corner.
   Actions	mvE(), mvW(), mvN(), mvS(): move the agent along the cardinal directions.
   Goal	Agent must reach the northeast corner.

   
   
   
   
   
   
   
   
2. Diagonal Return (Srivastava et al., 2009)
   

   Initial states	N x M rectangular grid with a single agent whose initial position is unknown.
   Actions	mvE(), mvW(), mvN(), mvS(): move the agent along the cardinal directions.
   Goal	Agent must reach the northeast corner and then return diagonally to the southwest corner. The problem is solvable only if N=M.

   
   
   
   
   
   
   
   
   
3. Hall (Bonet et al., 2009)
   

   Initial states	A quadrilateral arrangement of 4 rows of rooms. The number of rooms in each wing of the arrangement is unknown; an agent is present at the southwest corner.
   Actions	mvE(), mvW(), mvN(), mvS(): move the agent along the cardinal directions.
   Goal	Visit the three other corner rooms of the quadrilateral and return to the starting point.

   
   
   
   
   
   
   
   
   
   
4. Prize (Bonet et al., 2009)
   

   Initial states	N x M grid with an agent at the northwest corner.
   Actions	mvE(), mvW(), mvN(), mvS(): move the agent along the cardinal directions.
   Goal	Visit every grid square.