AAAI Publications, Sixth European Conference on Planning

Font Size: 
On the Complexity of Planning in Transportation Domains
Malte Helmert

Last modified: 2014-05-21


The efficiency of AI planning systems is usually evaluated empirically. The planning domains used in the competitions of the 1998 and 2000 AIPS conferences are of particular importance in this context. Many of these domains share a common theme of transporting portables, making use of mobiles traversing a map of locations and roads. In this contribution, we embed these benchmarks into a well-structured hierarchy of transportation problems and study the computational complexity of optimal and non-optimal planning in this domain family. We identify the key features that make transportation tasks hard and try to shed some light on the recent success of planning systems based on heuristic local search, as observed in the AIPS 2000 competition.

Full Text: PDF