Competition Domains

The competition was run with a series of domains, divided into three broad collections: transportation related domains, space-applications related domains and a collection of odds-and-ends. The first collection contained the domains called Depots, DriverLog and ZenoTravel, the second contained Satellite and Rovers and the third contained FreeCell, Settlers and UMTranslog-2. Apart from the third set, in each case a domain was represented by several variants, including STRIPS, numeric, simple-timed, timed and, in some cases, more complex problems (usually combining time and numbers in more interesting ways).

Simple-timed problems used durative actions in which durations were fixed for all instances of an action schema, being given as domain constants. Timed versions were more complex, since the durations could depend on problem-specific data. Only in more complex versions could the values on which these durations depended be fluents, since this requires of a planner the capability for managing both durative actions and numeric-valued fluents.

Variants of the domains changed the nature of the problems very significantly, so each domain variant can be seen as a separate domain in its own right. The following sections detail the domains we used in all their variations.

The Archive

The entire archive of domains and. problem sets used in the competition, together with the generators used to produce the problems, are available here. This archive is 17Mb. Generator executables are compiled for Linux (C++ source is also supplied). The domains are organised in a hierarchy of sub-directories. Within each domain variant sub-directory can be found the typed domain description and problem sets for automatic and for hand-coded planners. The untyped problems are identical sets, but without types.

A much smaller archive, containing scripts that allow the problems to be regenerated using the generators is available here. To use this, unpack it (gunzip and untar) and then, in IPC3, run the script "buildall" which will automatically invoke the makefiles to build the generators from source and then construct all the problem sets. This archive is only 150Kb, but requires you to have a C++ compiler, make and, to run the scripts, bash.

If you would like to get hold of the problem files in some other form, please contact us.

Depots

This domain was devised in order to see what would happen if two previously well-researched domains were joined together. These were the logistics and blocks domains. They are combined to form a domain in which trucks can transport crates around and then the crates must be stacked onto pallets at their destinations. The stacking is achieved using hoists, so the stacking problem is like a blocks-world problem with hands. Trucks can behave like "tables", since the pallets on which crates are stacked are limited.

• Strips: This is the basic combined domain.
• Numeric: Trucks are equipped with load capacities and consume fuel as they move. Crates have weights and hoists consume fuel as they lift packages. The task is always to achieve the goals at least fuel cost.
• Simple-time: durations vary from 10 for driving to 1 for dropping a crate onto a stack. There is considerable scope for concurrency in the use of trucks and hoists.
• Time: Durations now depend on distances between locations and the speeds of different trucks. Hoists take different times to load or unload according to their power and the weights of the crates. This makes the concurrency issue more subtle, since faster trucks might be available, but somewhere other than the location they are needed, so a better plan might involve coordinating concurrent positioning of trucks and use of hoists.

DriverLog

This domain involves driving trucks around delivering packages between locations. The complication is that the trucks require drivers who must walk between trucks in order to drive them. The paths for walking and the roads for driving form different maps on the locations.

• Strips: The basic version.
• Numeric: Walking and driving are each allocated a cost proportional to the distance travelled by a moving object. Plans must minimize some linear combination of these values. The linear combination is problem instance specific, making it harder for hand-coders to predetermine a strategy for optimising whether drivers walk between trucks or simply drive everywhere.
• Hard-Numeric: In this case the fuel consumption of a trucks is proportional to the square of its load. This makes the problem of efficiently using trucks much harder, since it might be better to make multiple trips with smaller loads than to make a single trip with a heavy load.
• Simple time: Action durations vary from 20 for walking to 1 for simple boarding and disembarking. Concurrency is possible by using drivers and trucks in parallel, including both movement and loading or unloading activity.
• Time: Distances between locations are now used to compute the times taken to travel between locations. This makes the management of concurrent activity rather trickier.

ZenoTravel

The final transportation domain involves transporting people around in planes, using different modes of movement: fast and slow. The key to this domain is that, where the expressive power of the numeric tracks is used, the fast movement consumes fuel faster than slow movement, making the search for a good quality plan (one using less fuel) much harder.

• Strips: This version was not particularly challenging, since the domain failed to offer any advantage for using the faster flight method, but still extracted a penalty. The main opportunity for interesting behaviour in this case was to automatically avoid using the inefficient operator altogether. Otherwise, this was a typical transportation problem.
• Numeric: In this version aircraft consume fuel at different rates according to the mode of travel. One mode is restricted to planes that are carrying fewer than a treshold number of people, dependent on the plane concerned. Each plane has a separately generated fuel consumption rate in each travel mode.
• Simple-time: Using a small set of symbolic fuel levels, this version manages to combine the benefits of fast travel (shorter journey times) with the associated costs (higher fuel consumption) that must be balanced with the cost of refuelling to arrive at time-efficient plans.
• Time: In this form the domain uses numbers to encode fuel consumptions, dependent on distances, and speeds to calculate travel times in each travel mode. This version is essentially the domain used to illustrate the Zeno planning system developed by Penberthy and Weld.

Satellite

The first of the domains inspired by space-applications is a first step towards the "Ambitious Spacecraft" described by David Smith at AIPS'00. It involves planning and scheduling a collection of observation tasks between multiple satellites, each equipped in slightly different ways.

• Strips: In its Strips version this domain is reasonably straightforward, although it still represents a new benchmark domain.
• Numeric: The numeric version introduces fuel costs for satellites to slew between targets and the satellites have a finite (and non-replenishable) fuel source. In addition, data takes up space in a finite capacity data store. The over all effect of this is to create a constrained bin-packing problem (the constraints being determined partly by the equipment on the different satellites and partly by the fuel limits; the bins being the data stores and the objects to be packed being the observations). Plans are expected to acquire all the necessary data at minimum fuel cost.
• Simple-time: This version allows for concurrent use of different satellites, so that the data can be acquired more quickly if they are used efficiently.
• Time: Concurrency is complicated by the introduction of different slew times between targets and of callibration times for different instruments paired with different possible callibration targets.
• Complex: The Satellite domain offers a complex version, in which the timed version (with varying slew times and callibration times) is combined with the finite data capacities of the numeric-version satellites. The result is a constrained bin-packing problem with the additional requirement that observations be efficiently scheduled (makespan is the quality metric).
• Hard Numeric: A final variant used for the Satellite domain is an interesting exploitation of the opportunity to specify a plan quality metric in PDDL2.1. All these problems have no logical goals at all, but the metric judges plans that acquire more data to be better. Therefore, the obvious null plan is of no value, even though it satisfies the (null) goals.

Rovers

Inspired by planetary rovers problems, this domain requires that a collection of rovers navigate a planet surface, finding samples and communicating them back to a lander.

• Strips: The Strips version is an interesting challenge in its own right. In addition, a minor subtlety in the encoding is used to prevent parallel communication between rovers and the lander: communication actions precondition on the channel to the lander being free, and then both add and delete this fact. Because deletes occur before adds this has the over all effect of leaving the channel free, but it makes the fact a "moving target" which prevents a concurrent action from using the fact. Some planners find this mechanism difficult to handle.
• Numeric: In the numeric version, rovers consume energy in their various activities. They can recharge, but only at locations that are in the sun (they use solar rechargers). This makes the challenge to manage energy efficiently. Plan quality is judged by the number of recharges required, rather than the plan length.
• Simple-time: Concurrent use of the rovers must be coordinated with the bottleneck of communication with the lander over the single communication channel. This makes it a challenge to find efficient makespans.
• Time: This variant combined the demands of the simple time durations of activities with the complexities of managing energy levels as in the numeric version. Recharging time depends on the level of charge to be replenished. Plan quality is measured by makespan, but since this reflects the amount of time spent recharging, efficient energy use is also important.

FreeCell

In order to confirm that STRIPS planning is still advancing, we chose this domain from IPC2. It is the familiar solitaire game found on many computers, involving moving cards from an initial tableau, constrained by tight restrictions, to achieve a final suit-sorted collection of stacks.

Settlers

This one was for the numeric track and proved to be a very tough resource management domain. Several interesting issues in encoding arise as well as the subsequent problem of planning with the domain. In particular, resources can be combined to construct vehicles of various kinds. Since these vehicles are not available initially, this is an example of a problem in which new objects are created. PDDL does not conveniently support this concept at present, so it is necessary to name "potential" vehicles at the outset, which can be realised through construction. A very high degree of redundant symmetry exists between these "potential" vehicles, since it does not matter which vehicle names are actually used for the vehicles that are realised in a plan. Planners that begin by grounding all actions can be swamped by the large numbers of potential actions involving these potential vehicles, which could be realised as one of several different types of actual vehicles.

Plan quality is judged by a linear combination of labour use, pollution creation and resource consumption. There is scope for constructing very hard metrics that involve maximising housing construction subject to an increasing pollution penalty (say), to ensure that optimal plan quality is bounded.

UMTranslog-2

This is a numeric domain, but was only used for the hand-coding planners in the competition. It is a large domain with 23 types of objects, 38 predicates, 24 functions and 38 action schemas. Plan quality was measured by plan length (both allowing for concurrent activity and also simply counting steps). More complex metrics would be possible.

Thanks go to Dan Wu for her great efforts in encoding this domain and writing the automatic problem generator for it.