Skip navigation
Skip navigation
Open Research will be down for maintenance between 8:00 and 8:15 am on Tuesday, December 1 2020.

Engineering benchmarks for planning: The domains used in the deterministic part of IPC-4

Thiebaux, Sylvie M; Hoffmann, Joerg; Edelkamp, Stefan; Englert, Roman; dos Santos Liporace; Trueg, Sebastian

Description

In a field of research about general reasoning mechanisms, it is essential to have appropriate benchmarks. Ideally, the benchmarks should reflect possible applications of the developed technology. In AI Planning, researchers more and more tend to draw their testing examples from the benchmark collections used in the International Planning Competition (IPC). In the organization of (the deterministic part of) the fourth IPC, IPC-4, the authors therefore invested significant effort to create a...[Show more]

dc.contributor.authorThiebaux, Sylvie M
dc.contributor.authorHoffmann, Joerg
dc.contributor.authorEdelkamp, Stefan
dc.contributor.authorEnglert, Roman
dc.contributor.authordos Santos Liporace
dc.contributor.authorTrueg, Sebastian
dc.date.accessioned2009-04-16T02:21:10Z
dc.date.accessioned2010-12-20T06:02:40Z
dc.date.available2009-04-16T02:21:10Z
dc.date.available2010-12-20T06:02:40Z
dc.identifier.citationJournal of Artificial Intelligence Research 26 (2006): 453-541
dc.identifier.issn1076-9757
dc.identifier.urihttp://hdl.handle.net/10440/34
dc.identifier.urihttp://digitalcollections.anu.edu.au/handle/10440/34
dc.description.abstractIn a field of research about general reasoning mechanisms, it is essential to have appropriate benchmarks. Ideally, the benchmarks should reflect possible applications of the developed technology. In AI Planning, researchers more and more tend to draw their testing examples from the benchmark collections used in the International Planning Competition (IPC). In the organization of (the deterministic part of) the fourth IPC, IPC-4, the authors therefore invested significant effort to create a useful set of benchmarks. They come from five different (potential) real-world applications of planning: airport ground traffic control, oil derivative transportation in pipeline networks, model-checking safety properties, power supply restoration, and UMTS call setup. Adapting and preparing such an application for use as a benchmark in the IPC involves, at the time, inevitable (often drastic) simplifications, as well as careful choice between, and engineering of, domain encodings. For the first time in the IPC, we used compilations to formulate complex domain features in simple languages such as STRIPS, rather than just dropping the more interesting problem constraints in the simpler language subsets. The article explains and discusses the five application domains and their adaptation to form the PDDL test suites used in IPC-4. We summarize known theoretical results on structural properties of the domains, regarding their computational complexity and provable properties of their topology under the h+ function (an idealized version of the relaxed plan heuristic). We present new (empirical) results illuminating properties such as the quality of the most wide-spread heuristic functions (planning graph, serial planning graph, and relaxed plan), the growth of propositional representations over instance size, and the number of actions available to achieve each fact; we discuss these data in conjunction with the best results achieved by the different kinds of planners participating in IPC-4.
dc.format89 pages
dc.publisherMorgan Kauffman Publishers
dc.sourceJournal of Artificial Intelligence Research
dc.source.urihttp://www.jair.org/papers/paper1982.html
dc.subjectKeywords: Airport vehicular traffic; Benchmarking; Competition; Computational complexity; Problem solving; Safety factor; Pipeline networks; Power supply restoration; Safety properties; Structural properties; Learning algorithms
dc.titleEngineering benchmarks for planning: The domains used in the deterministic part of IPC-4
dc.typeJournal article
local.identifier.citationvolume26
dc.date.issued2006
local.identifier.absfor080199
local.identifier.ariespublicationu8803936xPUB11
local.type.statusPublished Version
local.contributor.affiliationThiebaux, Sylvie M, Research School of Information Sciences and Engineering, Computer Sciences Laboratory
local.contributor.affiliationHoffmann, Joerg, Max Planck Institute for Informatics
local.contributor.affiliationEdelkamp, Stefan, Dortmund University of Technology
local.contributor.affiliationEnglert, Roman, Deutsche Telekom Laboratories
local.contributor.affiliationdos Santos Liporace, Frederico, Pontifical Catholic University of Rio de Janeiro
local.contributor.affiliationTrueg, Sebastian, University of Freiburg
local.bibliographicCitation.startpage453
local.bibliographicCitation.lastpage541
dc.date.updated2015-12-08T02:59:46Z
local.identifier.scopusID2-s2.0-33748987920
CollectionsANU Research Publications

Download

File Description SizeFormat Image
Thiebaux_Engineering2006.pdf822.19 kBAdobe PDFThumbnail


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator