Translation-Based Approaches to Automated Planning with Incomplete Information and Sensing

TitleTranslation-Based Approaches to Automated Planning with Incomplete Information and Sensing
Publication TypeThesis
Year of Publication2011
AuthorsAlbore, A
Secondary AuthorsGeffner, H
UniversityUniversitat Pompeu Fabra
Thesis Typephd
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 modeled 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.

URLhttp://www.tdx.cat/handle/10803/78939