Automated planning through abstractions in dynamic and stochastic environments

• Autores: Moisés Martínez Muñoz
• Directores de la Tesis: Daniel Borrajo Millán (dir. tes.) , Fernando Fernández Rebollo (codir. tes.)
• Lectura: En la Universidad Carlos III de Madrid ( España ) en 2016
• Idioma: español
• Tribunal Calificador de la Tesis: María Manuela Veloso (presid.) , María Araceli Sanchís de Miguel (secret.) , Eva Onaindia de la Rivaherrera (voc.)
• Enlaces
  • Tesis en acceso abierto en: e-Archivo
• Resumen

  • Generating sequences of actions -- plans -- for an automatic system, like a robot, using Automated Planning is particularly difficult in stochastic and/or dynamic environments. These plans are composed of actions whose execution, in certain scenarios, might fail, which in turn prevents the execution of the rest of the actions in the plan. Also, in some environments, plans must be generated fast, both at the start of the execution and after every execution failure. These problems have contributed to generate new Automated Planning models (Planning under uncertainty) to tackle these situations. These models include changes in the representation of the information to manage the dynamics of the environment (action outcomes, observability of the environment, etc). In spite of the initial advantages of these models, there are some important disadvantages that increase the cost of generating a plan. These models require an accurate definition of the environment's dynamics. Frequently, it is extremely difficult to define such accurate models, and in some environments the amount of information needed is huge. The most common solution to avoid these problems consists on repairing or re-planning when a failure in execution is detected due to the lack of information. Therefore, at each planning (re-planning) step, a new plan of actions is generated including the possible changes in the environment.

    The main objective of this thesis consists on developing a new planning-execution approach that reduces the computational effort of the planning task in dynamic and stochastic scenarios. These scenarios present some challenges that increase the complexity of the planning-execution process: (i) new information about the environment can be discovered during action execution, modifying the structure of the planning task; (ii) actions' execution can fail which in turn prevents the execution of the rest of the plan; (iii) the execution of the actions in the plan can generate states from which the rest of the plan cannot be successfully executed (dead-ends); (iv) plans may need to be generated quickly to offer a real time interaction between the automated planning system and the environment; and (v) planning tasks present scalability problems. For these reasons, the process of generating and executing a plan of actions can be prohibitively expensive in real world environments.

    In the first part of this thesis, we detail novel methods for generating predicate abstractions from planning tasks. We then propose a way of using these predicate abstractions during search to generate partial abstract plans, while considering the far future information with a different level of detail, by selectively removing predicates of the planning task. This approach generates partial abstract solution plans where the (horizon) k-first actions in the plan are guaranteed to be applicable as long as the information about the environment does not change or the actions' execution is correct. Meanwhile, the rest of the plan might not necessarily be applicable due to the level of the details of the predicate abstraction. In the second part of this thesis, we focus on improving the technique developed on the first part to implement different methods to generate predicate abstraction automatically. Finally in the third part of this thesis, we focus on increasing the coverage (the number of tasks solved) and the solution quality conducting a detailed study about the horizon to define a new method to modify the value of the horizon dynamically during the planning-execution process.

    Finally, we provide an outlook on possible extensions of our work by investigating more complex ways to deploy abstractions during search using different level of abstractions or deploying predicate abstractions to generate partial plans which can be used to guide the search.