Universitat Pompeu Fabra
Geffner, Héctor
2012-02-22
B. 12626-2012
174 p.
Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions
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
Artificial Intelligence; Automated Planning; Conformant Planning; Contingent Planning; Heuristic search; Belief state representation; Inteligencia Artificial; Planificación Automatica; Planificación Conformante; Planificación Contingente; Búsqueda Heuristica; Representación de estados de creencia
62 - Engineering
ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.
