Application Developers

Planning Researchers

(wiki admin)
(edit sidebar)

Real and Realistic Planning Domains

This page collects information about real (or close enough to real to be called realistic) planning problems that have been formulated in (some version of) PDDL. If you're looking to try your planner on a real problem, this is the place to look. Of course, this is not a complete list of all real problems that have been solved with planning technology - some just can't be expressed in (any version of) PDDL. There is perhaps also some bias towards problems that can be solved by some planner: people rarely publicise PDDL encodings of application problems if no planner was good enough to successfully solve the application.

Cell Assembly Planning Problem

The Problem: A cell assembly system is a system in which each worker (robot or human) assembles complex products in a relatively small "cell" where parts and equipment is quickly accessible with minimum motion. Compared to large automated production lines, cell assembly systems suit the demands of assembling relatively small numbers (~100) of products, particularly experimental or custom-made products, because of the flexibility of the system. The planning problem arises when the assembly plan changes: to maximize productivity, efficient motion plans are required.
Related Publication: Asai, M. and Fukunaga, A. "Fully Automated Cyclic Planning for Large-Scale Manufacturing Domains." In Proceedings of the 24th International Conference on Automated Planning and Scheduling, 2014. PDF
PDDL Features: Two version of the problem are provided. The sequential ("ACP") version uses STRIPS, with negated preconditions, action costs and a hierarchy of object types. The temporal version uses simple temporal STRIPS (i.e., actions with durations, but only the "conservative" fragment of temporal planning). It uses static numeric functions to define action durations.
Objective: The objective is to minimize plan makespan. The temporal version encodes this objective directly, using the (total-time) metric. In the sequential version, sum of action costs is used as an (approximate) proxy for makespan, but a temporal plan must be produced by post-scheduling the sequential solution plan.
Simplifications and omissions: The planning domain is focused on the efficient motion of arms. Job dependencies (e.g. attaching X should be done before painting Y) are already encoded in the problem.

Also, the domain models components as instantly available to be picked up from trays. In some cell assembly systems, parts may be carried in by something like a conveyor. If components take a significant length of time to be supplied, this could cause a difference between plan execution times in the real and modelled system. However, the domain allows some customization so this could be fixed.

Home Theatre Assembly Task

(local copy -- try the URL provided first, to ensure you obtain the latest version)
The Problem: A user assistance system interactively guides a user through performing a complex (to the user) task, here exemplified by the task of assembling a home theatre system from components such as a TV, bluray player, etc., and cables of different kinds. The planning domain models this assembly task.
Related Publication: Bercher, P., Biundo, S., Geier, T., Hoernle, T., Richter, F., Schattenberg, B. and Nothdurft, F. "Plan, Repair, Execute, Explain -- How Planning Helps to Assemble Your Home Theater." In Proceedings of the 24th International Conference on Automated Planning and Scheduling, 2014.
PDDL Features: The domain is formulated in a hybrid hierarchical and causal link planning formalism (written in an XML-based format), but a translation to PDDL is also provided. The generated PDDL formulation uses typing and negative preconditions.
Objective: No metric is specified. However, since the plan is meant to be carried out by the user, one can assume shorter plans are preferred.
Simplifications and omissions: Plan generation is only one small part of the user assistance system, which must also be able to explain the plan to the user, monitor its execution, and repair plan failures. These aspects are not explicitly included in the planning domain model (original or PDDL).

Liner Shipping Fleet Repositioning Problem

The Problem: Liner shipping vessels travel the world on fixed routes, visiting ports at fixed times, carrying container cargo. The fleet repositioning problem arises when ships need to be moved from one route to another (due to changes in demand for transport capacity), and is the problem of moving ships out of one route and into another at minimum cost.
Related Publications: Kevin Tierney, Amanda Coles, Andrew Coles, Christian Kroer, Adam Britt, and Rune Møller Jensen. "Automated Planning for Liner Shipping Fleet Repositioning." In Proceedings of the 22nd International Conference on Automated Planning and Scheduling, pp. 279-287, 2012. A technical report describing the domain is also included in the download.
PDDL Features: Durative actions (with duration inequalities); timed initial literals and processes; numeric fluents; conditional effects (with numeric conditions).
Objective: Minimise cost. Cost is captured by a (total-cost) fluent as usual, but some actions' costs are not constant (they depend on duration).
Simplifications and omissions: Some parts of the problem have been changed to protect confidentiality.

Machine Tool Calibration Problem

The Problem: Machine tools contain many error sources that require measuring during calibration. Each measurement consists of instrumentation selection, installation and measurement. While the measurements take place, the machine tool is not available for manufacturing purposes, so minimising machine down-time is essential for maximising production.
Related Publications: Simon Parkinson, Andrew P. Longstaff, Andrew Crampton and Peter Gregory. "The Application of Automated Planning to Machine Tool Calibration." In: Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS'12), Atibaia, São Paulo, Brazil, 2012.
PDDL Features: Durative actions; static fluents; non-static fluents (max importance version); timed initial literals (version with workday constraint).
Objective: Two objectives are used, in different instances (both using the same domain). In one version ("time"), the set of goals (errors to measure) is given and the objective is to minimise makespan. In the other ("importance"), each error has a given importance and the objective is to maximise the total (summed) importance of the errors measured within a given time limit.
Simplifications and omissions: The domain captures the full problem, but instances can omit some constraints. In particular, the "workday" constraint, that each measurement be done during one of a given number of working days, can be enforced or not by setting timed initial literals for the (workday) predicate.

Genome Rearrangement (Edit Distance Computation)

The Problem: The edit distance between genomes is a similarity measure, and is one of the many tools used in reconstructing the history of life on Earth. It is defined as the cost of the cheapest sequence of edit operations that transforms one genome into the other. Genomes are represented as permutations of signed elements (genes), and the usual edit operations are inversion, transposition, and transversion (combined transposition and inversion of the transposed segment).
Related Publications: The idea of formulating genome rearrangement as a planning problem is due to E. Erdem and E. Tillier, "Genome Rearrangement and Planning", Proc. AAAI 2005. The formulation in PDDL is by P. Haslum, "Computing Genome Edit Distances using Domain-Independent Planning", SPARK 2011.
PDDL Features: The domain exists in different formulations. The simplest uses only STRIPS with action costs. Other formulations use ADL (quantified conditional effects) and derived predicates.
Objective: Minimise sum of action costs, which equals the edit distance. Most important is consistency, preserving the relative difference in distance between different pairs of genomes. The simplest way to achieve that is to find only optimal plans.
Simplifications and omissions: Essentially none. There are many versions of the genome rearrangement problem, depending on which edit operations are considered, but for the inversion, transposition and transversion set, comparing only genomes with equal content, the problem can be fully modelled in PDDL.