Have I Been Here Before? State Memoization in Temporal Planning

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

11 Citations (Scopus)
71 Downloads (Pure)

Abstract

State memoization is critical to the good performance of heuristic forward search planners, which represent a significant proportion of the current state-of-the-art planning approaches. In non-temporal planning it is sufficient to discard any state that has been generated before, regardless of the path taken to reach that state, with the only side-constraint being plan cost. We begin this paper by demonstrating that the use of this technique in temporal planning can lead to loss of optimality with respect to metrics involving makespan and that in the case of more expressive domains can lead to loss of completeness. We identify the specific conditions under which this occurs: states where actions are currently executing. Following from this we introduce new memoization techniques for expressive temporal planning problems that are both completeness and optimality preserving, solving the challenging problem of determining when two states in temporal planning can be considered equivalent. Finally, we demonstrate that these have significant impact on improving the planning performance across a wide range of temporal planning benchmarks in the POPF planning framework.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling
PublisherAAAI Press
Pages97-105
Number of pages9
ISBN (Print)9781577357575
Publication statusPublished - 2016
Event26th International Conference on Automated Planning and Scheduling ICAPS 2016 - London, London, United Kingdom
Duration: 12 Jun 201617 Jun 2016
http://icaps16.icaps-conference.org/

Conference

Conference26th International Conference on Automated Planning and Scheduling ICAPS 2016
Abbreviated titleICAPS 2016
Country/TerritoryUnited Kingdom
CityLondon
Period12/06/201617/06/2016
Internet address

Keywords

  • Artificial intelligence planning

Cite this