Translation-based approaches to automated planning with incomplete information and sensing

Abstract

Artificial Intelligence Planning is about acting in order to achieve a desired goal. Under incomplete information, the task of finding the actions needed to achieve the goal can be modelled as a search problem in the belief space. This task is costly, as belief space is exponential in the number of states, which is exponential in the number of variables. Good belief representations and heuristics are thus critical for scaling up in this setting.

The translation-based approach to automated planning with incomplete information deals with both issues by casting the problem of search in belief space to a search problem in state space, where each node of the search space represents a belief state. We develop plan synthesis tools that use translated versions of planning problems under uncertainty, with partial or null sensing available. We show formally under which conditions the introduced translations are polynomial, and capture all and only the plans of the original problems. We study empirically the value of these translations.

La Planificación es la disciplina de Inteligencia Artificial que estudia los procesos de razonamiento necesarios para conseguir las acciones que logren un objetivo dado.

En presencia de información incompleta, el problema de planificación puede ser modelado como una búsqueda en el espacio de estados de creencia, cada uno de ellos representando un conjunto de estados posibles. Este problema es costoso ya que el numero de estados de creencia puede ser exponencial en el número de estados, lo cual es exponencial en el número de variables del problema. El uso de buenas representaciónes de los estados y de heurísticas informadas resultan cruciales para escalar en este espacio de búsqueda.

En esta tesis se presentan traducciones para planificación con información incompleta, que transforman el problema de búsqueda en el espacio de estados de creencia, en búsqueda en espacio de estados, donde cada nodo representa un estado de creencia. Hemos desarrollado herramientas para la generación de planes para el problema traducido, ya sea con percepción parcial o nula. A su vez, demostramos formalmente bajo qué circunstancias las traducciones son polinómicas, completas y correctas. La evaluación empírica remarca el valor de dichas traducciones