LOLLIPOP: Generating and using an operator graph and negative refinements for online partial order planning


Antoine Gréa, Samir Aknine, Laetitia Matignon: LOLLIPOP: Generating and using an operator graph and negative refinements for online partial order planning. In: Journées Francophones sur la Planification, la Décision et l'Apprentissage pour la conduite de systèmes, 2016, (Creative Commons Attribution-NonCommercial-ShareAlike License).

Abstract

In recent years, the field of automatic planning has mainly focused on performances and advances in state space planning to improve scalability. That orientation shadows other less efficient ways of planning like Partial Order Planning (POP) that has the advantage to be much more flexible.
This flexibility allows these planners to take incomplete plans as input and to refine them into an optimized solution for the problem. This paper presents a set of mechanisms, called aLternative Optimization with partiaL pLan Injection Partial Ordered Planning (LOLLIPOP), that adapts the classical POP algorithm. The aim is to obtain a high plan quality while allowing fast online re-planning. Our algorithm builds an operator graph from the domain compilation that gives information on the possible behavior of operators. A safe operator graph is generated at initialization and used as LOLLIPOP's input to reduce the overhead of the initial subgoal backchaining. We prove that the use of these new mechanisms keeps POP sound and complete.

BibTeX (Download)

@inproceedings{grea_lollipop_2016,
title = {LOLLIPOP: Generating and using an operator graph and negative refinements for online partial order planning},
author = {Antoine Gréa and Samir Aknine and Laetitia Matignon},
url = {https://antoine.grea.me/wp-content/uploads/publications/lollipop/documents/article-jfpda16.pdf
http://jfpda2016.imag.fr/},
year  = {2016},
date = {2016-07-08},
publisher = {Journées Francophones sur la Planification, la Décision et l'Apprentissage pour la conduite de systèmes},
abstract = {In recent years, the field of automatic planning has mainly focused on performances and advances in state space planning to improve scalability. That orientation shadows other less efficient ways of planning like Partial Order Planning (POP) that has the advantage to be much more flexible.
    This flexibility allows these planners to take incomplete plans as input and to refine them into an optimized solution for the problem. This paper presents a set of mechanisms, called aLternative Optimization with partiaL pLan Injection Partial Ordered Planning (LOLLIPOP), that adapts the classical POP algorithm. The aim is to obtain a high plan quality while allowing fast online re-planning. Our algorithm builds an operator graph from the domain compilation that gives information on the possible behavior of operators. A safe operator graph is generated at initialization and used as LOLLIPOP's input to reduce the overhead of the initial subgoal backchaining. We prove that the use of these new mechanisms keeps POP sound and complete.},
note = {Creative Commons Attribution-NonCommercial-ShareAlike  License},
keywords = {automated planning, negative refinements, Partial Order Causal Link, Partial Order Planning, partial plan, planning, POCL, POP, PSP Plan-Space Planning},
pubstate = {published},
tppubtype = {inproceedings}
}

Antoine Gréa

About Antoine Gréa

Passionné de sciences et d'informatique depuis toujours, je cherche à lier l'élégance à l'utilité en poussant toujours plus loin l’innovation. Je suis ingénieur en embarqué et réseau et je poursuit une carrière académique en intelligence artificielle et robotique afin de peut-être un jour créer une intelligence artificielle générale.