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 language | English |
---|---|
Title of host publication | Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling |
Publisher | AAAI Press |
Pages | 97-105 |
Number of pages | 9 |
ISBN (Print) | 9781577357575 |
Publication status | Published - 2016 |
Event | 26th International Conference on Automated Planning and Scheduling ICAPS 2016 - London, London, United Kingdom Duration: 12 Jun 2016 → 17 Jun 2016 http://icaps16.icaps-conference.org/ |
Conference
Conference | 26th International Conference on Automated Planning and Scheduling ICAPS 2016 |
---|---|
Abbreviated title | ICAPS 2016 |
Country/Territory | United Kingdom |
City | London |
Period | 12/06/2016 → 17/06/2016 |
Internet address |
Keywords
- Artificial intelligence planning