International Planning Competition 2014

Competition Domains

This page contains the description of the competition domains for the satisfying, agile, optimal and multi-core tracks.

Barman

From the original domain description (here). In this domain there is a robot barman that manipulates drink dispensers, glasses and a shaker. The goal is to find a plan of the robot's actions that serves a desired set of drinks. In this domain deletes of actions encode relevant knowledge given that robot hands can only grasp one object at a time and given that glasses need to be empty and clean to be filled.

Cave Diving

Author: Nathan Robinson,Christian Muise, and Charles Gretton.
There are a set of divers, each of who can carry 4 tanks of air. These divers must be hired to go into an underwater cave and either take photos or prepare the way for other divers by dropping full tanks of air. The cave is too narrow for more than one diver to enter at a time.
The cave system is represented by an undirected acyclic graph. Divers have a single point of entry. Certain leaf nodes of the cave branches are objectives that the divers must photograph. Swimming and photographing both consume air tanks. Divers must exit the cave and decompress at the end. They can therefore only make a single trip into the cave.
Certain divers have no confidence in other divers and will refuse to work if someone they have no confidence in has already worked. Divers have hiring costs inversely proportional to how hard they are to work with.

Child-Snack

Authors: Raquel Fuentetaja, Tomás de la Rosa Turbides.
This domain is to plan how to make and serve sandwiches for a group of children in which some are allergic to gluten. There are two actions for making sandwiches from their ingredients. The first one makes a sandwich and the second one makes a sandwich taking into account that all ingredients are gluten-free. There are also actions to put a sandwich on a tray and to serve sandwiches.
Problems in this domain define the ingredients to make sandwiches at the initial state. Goals consist of having all kids served with a sandwich to which they are not allergic.

CityCar

Author: Mauro Vallati.
This model aims to simulate the impact of road building / demolition on traffic flows. A city is represented as an acyclic graph, in which each node is a junction and edges are "potential" roads. Some cars start from different positions and have to reach their final destination as soon as possible. The agent has a finite number of roads available, which can be built for connecting two junctions and allowing a car to move between them. Roads can also be removed, and placed somewhere else, if needed. In order to place roads or to move cars, the destination junction must be clear, i.e., no cars should be in there.

Floortile

From the original domain description (here). A set of robots use different colors to paint patterns in floor tiles. The robots can move around the floor tiles in four directions (up, down, left and right). Robots paint with one color at a time, but can change their spray guns to any available color. However, robots can only paint the tile that is in front (up) and behind (down) them, and once a tile has been painted no robot can stand on it.
For the IPC set, robots need to paint a grid with black and white, where the cell color is alternated always. This particular configuration makes the domain hard because robots should only paint tiles in front of them, since painting tiles behind make the search to reach a dead-end.

Genome Edit Distances

Author: Patrik Haslum.
The GED problem is to find a min-cost sequence of operations that transforms one genome (signed permutation of genes) into another. The purpose of this is to use this cost as a measure of the distance between the two genomes, which is used to construct hypotheses about the evolutionary relationship between the organisms.
Further information: here.

Hiking

Author: Lee McCluskey.
Imagine you want to walk with your partner a long clockwise circular route over several days (e.g. in the "Lake District" in NW England), and you do one "leg" each day. You want to start at a certain point and do the walk in one direction, without ever walking backwards. You have two cars which you must use to carry your tent/luggage and to carry you and your partner to the start/end of a leg, if necessary. Driving a car between any two points is allowed, but walking must be done with your partner and must start from the place where you left off. As you will be tired when you've walked to the end of a leg, you must have your tent up ready there so you can sleep the night before you set off to do the next leg the morning.

Maintenance

Author: Jussi Rintanen.
This is a simple planning/scheduling problem. There are mechanics/equipment who on any day may work at one of several airports (hubs) where the maintenance facilities are present. There are airplanes each of which has to be checked or repaired during the given time period. The airplanes are guaranteed to visit some of the airports on given days. The problem is to schedule the presence of the mechanics/equipment so that each plane will get maintenance once during the time period.

Openstacks

From the original domain description (here). This domain was first used at IPC-2006. The openstacks domain is based on the "minimum maximum simultaneous open stacks" combinatorial optimization problem, which can be stated as follows: A manufacturer has a number of orders, each for a combination of different products, and can only make one product at a time.
The total required quantity of each product is made at the same time (because changing from making one product to making another requires a production stop). From the time that the first product included in an order is made to the time that all products included in the order have been made, the order is said to be "open" and during this time it requires a "stack" (a temporary storage space). The problem is to order the making of the different products so that the maximum number of stacks that are in use simultaneously, or equivalently the number of orders that are in simultaneous production, is minimized (because each stack takes up space in the production area).
The problem is NP-hard and known to be equivalent to several other problems. It was recently posed as a challenge problem for the constraint programming community (see here).
Note that this is an optimization problem: for any instance of the problem every ordering of the making of products is a solution, which at worst uses as many simultaneously open stacks as there are orders. Thus, finding a plan is quite trivial (in the sense that there exists a domain-specific linear-time algorithm that solves the problem), but finding a plan of high quality is hard (even for a domain-specific algorithm).

Parking

This domain is original from the learning part of IPC2008. The domain involves parking cars on a street with N curb locations, and where cars can be double-parked but not triple-parked. The goal is to find a plan to move from one configuration of parked cars to another configuration, by driving cars from one curb location to another. The problems in the competition contain 2*(N-1) cars, which allows one free curb space and guarantees solvability.

Tetris

Author: Mauro Vallati.
This is a simplified version of the well-known Tetris. All the pieces (1x1, 2x1, L) are randomly distributed on a NxN grid. The goal is to move them in order to free the upper half of the grid. The pieces can be rotated or translated. Each movement action has a different cost, accordingly to the size of the piece.

Thoughtful

This domain is original from the learning part of IPC2008. The domain represents a well-known solitaire card game.

Tidybot

From the original domain description (here). The Tidybot domain models a household cleaning task, in which one or more robots must pick up a set of objects and put them into goal locations. The world is structured as a 2d grid, divided into navigable locations and surfaces on which objects may lie. Robots have a gripper, which moves relative to the robot, up to some maximum radius. Existing objects block the gripper, so that it may be necessary to move one object out of the way to put another one down. Robots can carry one object at a time in the gripper, but may also make use of a cart, that can hold multiple objects. The instance generator creates worlds that contain rectangular surfaces ("tables"), as well as U-shaped enclosures ("cupboards"), which are the goal locations of objects.
In many real-world problems, the difficulty is due to the large state space and number of objects, rather than due to complex, "puzzle-like" combinatorial constraints. Humans are able to quickly find feasible solutions in such domains, because they seem to be able to decompose the problem into separate parts and make use of the geometrical structure. This domain is thus intended to exercise the ability of planners to find and exploit structure in large but mostly unconstrained problems.
Optimal reasoning in such problems is challenging for humans as well, and a secondary motivation for the domain is to test the ability to do optimal reasoning in geometrically structured worlds. The presence of the carts adds another combinatorial decision: it might be worthwhile to spend some time fetching the cart to avoid later having to go back and forth with each object.

Transport

This domain is original from the IPC2008. There is no description of this domain, but it seems to be a kind of logistics one. Each vehicle can transport some packages depending on its capacity and moving has a cost depending on the length of the road. Picking up or dropping a package costs 1.

Visitall

From the original domain description (here). The heuristics used in state-of-the-art (satisficing) planners are a decade old and are based on the delete-relaxation. Several heuristics that take deletes into account have been formulated but they haven’t been shown to be cost-effective. One problem with delete-relaxation heuristics that aproximate h+, appears in instances with multiple conflicting goals. In these cases, that are very common, progress towards one goal means moving away from other goals. Such instances produce large plateaus where the heuristic is almost useless. Indeed, in some cases, state-of-the-art heuristics are no better than heuristics that ignore the problem structure completely and just count, for example, the number of unachievable goals. As an illustration of this, consider the Visit-All domain where an agent in the middle of a square grid nxn must visit all the cells in the grid. Solving optimally the delete relaxation h+ gives the exact goal distance as long as there exists a hamiltonian path visiting every cell. Recall that in a 1xn grid, no hamiltonian path exists.
The use of delete-relaxation heuristics to appraise the cost of achieving all goals together runs into a situation resembling Buridan’s ass: where a hungry and thirsty donkey, placed between a bundle of hay and a pail of water, dies of hunger and thirst for not finding a reason to choose one over the other.