Eine Plattform für die Wissenschaft: Bauingenieurwesen, Architektur und Urbanistik
Eine Plattform für die Wissenschaft: Bauingenieurwesen, Architektur und Urbanistik
Have I Been Here Before?:State Memoization in Temporal Planning
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.
Have I Been Here Before?:State Memoization in Temporal Planning
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.
Have I Been Here Before?:State Memoization in Temporal Planning
Coles, Amanda Jane (Autor:in) / Coles, Andrew Ian (Autor:in)
01.01.2016
Coles , A J & Coles , A I 2016 , Have I Been Here Before? State Memoization in Temporal Planning . in Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling . , 12884 , pp. 97-105 , 26th International Conference on Automated Planning and Scheduling ICAPS 2016 , London , United Kingdom , 12/06/2016 . < http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13187 >
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
British Library Online Contents | 2007
| British Library Online Contents | 2005
In the west you have landscape, here we have
| Online Contents | 2014
‘In the west you have landscape, here we have … ’
| Taylor & Francis Verlag | 2014
In the west you have landscape, here we have
| British Library Online Contents | 2014