Polynomial-time reformulations of temporally extended planning problems into classical planning problems
Loading...
Date
2016
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
La lógica lineal temporal (LTL) es un lenguaje que permite especificar objetivos y preferencias temporales. Un método general para tratar en general con propiedades LTL en planificación es por \compilación"; por ejemplo, en una fase de preprocesamiento, todas las fórmulas temporales son transformadas a fórmulas simples y no temporales que pueden evaluarse en un estado de planificación. Esto se logra primero generando un autómata finito no determinista para la fórmula, y luego agregando fluentes nuevos que son usados para capturar todas las posibles ejecuciones del autómata. Desafortunadamente, los métodos de traducción actuales son exponenciales en el peor caso sobre el tamaño de la fórmula. En esta tesis, presentamos un método polinomial para compilar objetivos temporales. Nuestro método utiliza autómatas alternantes. Dado que los autómatas alternantes son diferentes de los no deterministas, nuestra técnica de traducción no captura todas las posibles ejecuciones en un estado de planificación, y por lo tanto, es muy diferente de otros métodos. Nosotros demostramos que nuestra traducción es correcta y completa. También mostramos otras variantes de nuestro método que ayudan a mejorar el desempeño para algunos planificadores y evaluamos empíricamente mostrando que tiene ventajas y desventajas. Específicamente encontramos clases de fórmulas de las cuales nuestro método tiene mejor desempeño que el actual estado del arte.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2016