Publication: Automated planning through abstractions in dynamic and stochastic environments
Loading...
Identifiers
Publication date
2016-09
Defense date
2016-09-27
Authors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
Generating sequences of actions - plans - for an automatic system, like a robot, using Automated Planning is particularly diflicult in stochastic and/or dynamic environments. These plans are composed of actions whose execution, in certain scenarios, might fail, which in tum prevents the execution of the rest of the actions in the plan. Also, in some environments, plans must he generated fast, hoth at the start of the execution and after every execution failure. These problems have contrihuted to generate new Automated Planning models (Planning under Uncertainty) to tackle these situations. These models indude changes in the representation of the information to manage the dynamics of the environment ( action outcomes, observahility 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 defutition of the environment's dynamics. Frequently, it is extremely diflicult 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 induding the possihle changes in the environment.
The main ohjective 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 ahout the environment can be discovered during action excecution, modifying the structure of the planning task; (ii) actions' excecution can fail which in turn prevents the execution of the rest of the plan; (iii) the execution of the actions in the plan can generated states from which there is no solution (dead-ends); (iv) plans may need to he generated quickly to offer a real time interaction hetween the automated planning system and the environment; and (v) planning tasks present scalahility problems. For these reasons, the process of generating and executing a plan of actions can he prohibitively a-pensive 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 ahstract solution plans where the k-first actions in the plan are guaranteed to he applicahle as long as the information ahout the environment dloes not change or the actions' execution is correct. Meanwhile, the rest of the plan might not necessarily he applicahle 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 a method to generate predicate abstraction automatically using different extrraction methods (Landmark hased and Relaxed Plan Based). Finally in the third part of this thesis, we compare the performance of both extraction methods conducting a detailed study ahout the generation time and the type of predicate chosen in order to analyze their effect in the planning-execution process.
Finally, we provide an outlook on possible extensions of our work in different directions: (1) investigating more complex ways to deploy ahstractions during search using different level of abstractions; (2) deploying predicate abstractions to generate partial plans which can he used to guide the search; and (3) modifying the value of k dynamically in order to improve the quality of the partial plans generated for our approach.
Generar secuencias de acciones - planes - para un sistema automático, como un robot, mediante la utilización de Planificación Automática es particularmente dificil en entornos estocásticos y/ o dinámicos. Estos planes están compuestos por acciones cuya ejecución puede fallar en algunas ocasiones, evitando que se puedan ejecutar el resto de acciones que componen el plan. Además, en algunos entornos, los planes dehen ser generados rápidamente, tanto al comienzo de la ejecución, como cuando un fallo es detectado durante ésta. Estos problemas han contribuido a que aparezcan nuevos modelos de Planificación Automática (Planificación con Incertidumhre) capaces de manejar estos problemas. Estos modelos induyen cambios en la representación de la información para gestionar las dinámicas del entono (resultados de las acciones, observabilidad del entono, etc). A pesar de la ventajas iniciales de estos modelos, existen algunas importantes desventajas que producen un incremento en el coste de generación de los planes de acciones. Esto es debido a que es necesario tener una representación precisa de la dinámica del entomo y frecuentemente es extremadamente complicado obtenerla o es demasiado grande para manejarla. La solución más común para evitar estos problemas consiste en reparar o re-planificar cuando se detecta un fallo durante la ejecución debido a la falta de información. Por lo tanto, en cada proceso de planificación (re-planificación), se genera un nuevo plan de acciones induyendo los posibles cambios detectados en el entorno. El objetivo principal de esta tesis consiste en definir un nuevo enfoque de planificación-ejecución basado en abstracciones que permita reducir el coste computacional de la tarea de planificación en escenarios dinámicos y estocásticos. Estos escenarios presentan algunos desafíos que aumentan la complejidad del proceso de planificación-ejecución: (i) nueva información sobre el entono puede ser descubierta durante la ejecución de las acciones, modificando la estructura de la tarea de planificación; (ii) la ejecución de las acciones puede fallar impidiendo la ejecución del resto del plan; (iii) la ejecución de las acciones puede generar estados a partir de los cuales no hay solución ( caminos sin salida); (iv) los planes de acciones pueden necesitar ser generados rápidamente para ofrecer una interacción más realista entre el sistema de planificación automática y el entomo; y (v) este tipo i de entomos presentan problemas de escalabilidad dehido a la explosión combinatoria Por estas razones, el proceso de generar y ejecutar un plan de acciones puede ser prohibitivamente costoso en entonos del mundo real. En la primera parte de esta tesis, vamos a describir de forma detallada el método desarrollados para generar abstracciones basadas en predicados para tareas de planificación. A continuación, proponemos una forma de utilizar abstracciones basadas en predicados durante la búsqueda para generar planes parciales, considerando la información futura con diferentes niveles de detalle, mediante la eliminación de forma selectiva de predicados de la tarea de planificación. Este enfoque generará. planes parciales abstractos, donde las k-primeras acciones del plan (horizonte) podrán ser ejecutadas siempre y cuando la información sobre el entorno sea completa y no varíe, mientras que el resto del plan podría no ser necesariamente aplicable. En la segunda parte de esta tesis, nos centramos en la mejora de la técnica descrita en la primera parte mediante la implementación de diferentes técnicas para generar abstractiones basadas en predicados de forma automática utilizando distintos métodos de extracción (Landmarks y Plan relajado). Finalmente en la tercera parte de la tesis, comparamos el comportamiento de ambos métodos mediante la realización de un estudio detallado sohre el tiempo de generación y los predicate extraidos con el fin de analizar su efecto sohre el proceso de planificación y ejecución. Por último, ofrecemos una perspectiva sobre las posibles extensiones de nuestro trabajo en diferentes direcciones: (1) investigando formas más complejas de desplegar las abstracciones durante la búsqueda utilizando diferentes niveles de abstracciones; (2) desplegando abstraciones basadas en predicados para generar planes parciales que puedan ser utilizados con el fin de guiar el proceso de búsqueda; y (3) modificando el valor de k de forma dinámica con el fin de mejorar la calidad de los planes parciales generados por nuestra técnica.
Generar secuencias de acciones - planes - para un sistema automático, como un robot, mediante la utilización de Planificación Automática es particularmente dificil en entornos estocásticos y/ o dinámicos. Estos planes están compuestos por acciones cuya ejecución puede fallar en algunas ocasiones, evitando que se puedan ejecutar el resto de acciones que componen el plan. Además, en algunos entornos, los planes dehen ser generados rápidamente, tanto al comienzo de la ejecución, como cuando un fallo es detectado durante ésta. Estos problemas han contribuido a que aparezcan nuevos modelos de Planificación Automática (Planificación con Incertidumhre) capaces de manejar estos problemas. Estos modelos induyen cambios en la representación de la información para gestionar las dinámicas del entono (resultados de las acciones, observabilidad del entono, etc). A pesar de la ventajas iniciales de estos modelos, existen algunas importantes desventajas que producen un incremento en el coste de generación de los planes de acciones. Esto es debido a que es necesario tener una representación precisa de la dinámica del entomo y frecuentemente es extremadamente complicado obtenerla o es demasiado grande para manejarla. La solución más común para evitar estos problemas consiste en reparar o re-planificar cuando se detecta un fallo durante la ejecución debido a la falta de información. Por lo tanto, en cada proceso de planificación (re-planificación), se genera un nuevo plan de acciones induyendo los posibles cambios detectados en el entorno. El objetivo principal de esta tesis consiste en definir un nuevo enfoque de planificación-ejecución basado en abstracciones que permita reducir el coste computacional de la tarea de planificación en escenarios dinámicos y estocásticos. Estos escenarios presentan algunos desafíos que aumentan la complejidad del proceso de planificación-ejecución: (i) nueva información sobre el entono puede ser descubierta durante la ejecución de las acciones, modificando la estructura de la tarea de planificación; (ii) la ejecución de las acciones puede fallar impidiendo la ejecución del resto del plan; (iii) la ejecución de las acciones puede generar estados a partir de los cuales no hay solución ( caminos sin salida); (iv) los planes de acciones pueden necesitar ser generados rápidamente para ofrecer una interacción más realista entre el sistema de planificación automática y el entomo; y (v) este tipo i de entomos presentan problemas de escalabilidad dehido a la explosión combinatoria Por estas razones, el proceso de generar y ejecutar un plan de acciones puede ser prohibitivamente costoso en entonos del mundo real. En la primera parte de esta tesis, vamos a describir de forma detallada el método desarrollados para generar abstracciones basadas en predicados para tareas de planificación. A continuación, proponemos una forma de utilizar abstracciones basadas en predicados durante la búsqueda para generar planes parciales, considerando la información futura con diferentes niveles de detalle, mediante la eliminación de forma selectiva de predicados de la tarea de planificación. Este enfoque generará. planes parciales abstractos, donde las k-primeras acciones del plan (horizonte) podrán ser ejecutadas siempre y cuando la información sobre el entorno sea completa y no varíe, mientras que el resto del plan podría no ser necesariamente aplicable. En la segunda parte de esta tesis, nos centramos en la mejora de la técnica descrita en la primera parte mediante la implementación de diferentes técnicas para generar abstractiones basadas en predicados de forma automática utilizando distintos métodos de extracción (Landmarks y Plan relajado). Finalmente en la tercera parte de la tesis, comparamos el comportamiento de ambos métodos mediante la realización de un estudio detallado sohre el tiempo de generación y los predicate extraidos con el fin de analizar su efecto sohre el proceso de planificación y ejecución. Por último, ofrecemos una perspectiva sobre las posibles extensiones de nuestro trabajo en diferentes direcciones: (1) investigando formas más complejas de desplegar las abstracciones durante la búsqueda utilizando diferentes niveles de abstracciones; (2) desplegando abstraciones basadas en predicados para generar planes parciales que puedan ser utilizados con el fin de guiar el proceso de búsqueda; y (3) modificando el valor de k de forma dinámica con el fin de mejorar la calidad de los planes parciales generados por nuestra técnica.
Description
Mención Internacional en el título de doctor
Keywords
Automatic systems, Robotics, Stochastic scenarios, Artificial intelligence