Dead ends in FOND planning : from theory to practical contributions

Abstract

We study Fully-Observable Non-Deterministic (FOND) planning, which models uncertainty through actions with non-deterministic effects. In FOND planning, the objective is to find a policy that, when followed, ensures we will eventually reach a goal state from the initial state, regardless of the outcome of the applied actions. We theoretically study the structure of FOND planning tasks, identifying all the features that can make a task challenging. In this study, we show that the dead-end states of a FOND planning task can be separated into two categories: deterministic and fully non-deterministic. Considering the determinization of the FOND planning task, where all actions are separated into their non-deterministic effects, thus becoming deterministic actions, there is a function that perfectly identifies all states that cannot reach a goal state. Deterministic dead-end states can be identified using this perfect function, while fully non-deterministic cannot. The fact that fully non-deterministic dead-end states cannot be identified by reducing the problem to classical planning makes them particularly noteworthy. More importantly, we conclude this theoretical study by showing that if a FOND planning task is not prohibitively large, then the only way it can be hard is by having fully non-deterministic dead-end states. Finally, we use these new insights to propose a set of new FOND planning domains that are more challenging for the existing state-of-the-art FOND solvers than the domains of the traditional FOND benchmark. Through empirical experiments, we infer that the performance of existing FOND solvers would be substantially improved if they had full knowledge of the fully non-deterministic dead-end states of a FOND planning task.

Neste trabalho, estudamos o planejamento FOND (Fully-Observable Non-Deterministic), o qual modela incerteza através de ações com efeitos não-determinísticos. No planejamento FOND, o objetivo é encontrar uma política, que quando seguida, assegure que eventualmente alcançaremos um estado objetivo a partir do estado inicial, independentemente do resultado das ações aplicadas. Estudamos teoricamente a estrutura das tarefas de planejamento FOND, identificando todos os aspectos que podem tornar uma tarefa desafiadora. Neste estudo, mostramos que os estados sem-saída de uma tarefa FOND podem ser separados em duas categorias: estados sem-saída determinísticos e estados sem-saída totalmente não-determinísticos. Considerando a “determinização” da tarefa de planejamento FOND, onde todas as ações são divididas em seus efeitos não-determinísticos, tornando-se ações determinísticas, temos uma função que identifica perfeitamente todos os estados que não podem alcançar um estado objetivo. Estados sem-saída determinísticos podem ser identificados usando essa função perfeita, enquanto estados sem-saída totalmente não-determinísticos não podem. Isso torna os estados sem-saída totalmente nãodeterminísticos particularmente interessantes. Mais importante, concluímos este estudo teórico mostrando que, se uma tarefa FOND não for proibitivamente grande, então a única maneira dela ser difícil é contendo estados sem-saída totalmente não-determinísticos. Finalmente, utilizamos esses novo conhecimento para propor um conjunto de novos domí- nios de planejamento FOND que são mais desafiadores para os planejadores FOND existentes do que os domínios do benchmark FOND tradicional. Através de experimentos empíricos, inferimos que o desempenho dos planejadores FOND existentes seria substancialmente melhorado se eles tivessem pleno conhecimento dos estados sem-saída totalmente não-determinísticos de uma tarefa FOND.