FOND planning via explicit search

Abstract

Fully-observable non-deterministic (FOND) planning is at the core of artificial intelli gence planning with uncertainty. It models uncertainty through actions with non-determi nistic outcomes. The goal is to find a policy that guides one to the goal regardless of the outcome of each action. There are several works in the literature that present techniques for solving FOND planning tasks. However, prior to this thesis, to our knowledge, none of the existing works presents a FOND planner that explicitly searches a space of policies to find a solution policy. In this thesis, we present a range of contributions for FOND planning: (1) an A*-based search algorithm for FOND planning, which we call A* with Non-Determinism (AND* for short) that searches a constructive space of policies; (2) heuristic functions that aggregate determinized information to evaluate how far a policy is from becoming a solution and can be used by AND∗ to find compact solutions; (3) a procedure that constructs a solution in time polynomial to its size given just the knowl edge of the set of states that should be mapped in it; and (4) a compression approach that, given a solution policy defined over complete states, produces a partial-state policy that represents it unambiguously with the fewest partial states possible. Some of these contributions can be applied for other paradigms. Besides these contributions, we also show that it is possible to accelerate the computation of state-space symmetries through the use of a group theory technique. We also study different possible concepts of equiva lences between policies in the context of AND*’s policy-space search, and also deadlock pruning and greedier approaches. The introduced techniques establish A*-based explicit policy-space search as a competitive method for addressing FOND planning tasks.

Planejamento completamente-observável não-determinístico (planejameno "FOND") está no centro da inteligência artificial com incerteza. Ele modela incerteza através de ações com resultados não-determinísticos. Existem diversos trabalhos na literatura que apresen tam técnicas para resolver tarefas de planejamento FOND. Contudo, antes dessa tese, ao que sabemos, nenhum dos trabalhos existentes apresenta um planejador FOND que explí citamente busca em um espaço de políticas para encontrar uma política solução. Nessa tese nós apresentamos uma gama de contribuições para planejamento FOND: (1) um al goritmo de busca para planejamento FOND baseado em A*, que chamamos de A* with Non-Determinism (ou AND*, abreviado), que busca em um espaço de políticas constru tivo; (2) funções heurísticas que agregram informações determinizadas para avaliar o quão longe uma política está de se tornar uma solução e que podem ser usadas pelo AND* para encontrar soluções compactas; (3) um procedimento que constrói uma solução em tempo polinomial ao seu tamanho* dado apenas o conhecimento do conjunto de estados que precisa ser mapeado nela; e (4) uma abordagem de compressão que, dada uma política solução definida através de estados completos, produz uma política de estados parciais que a representa sem ambiguidades com o menor número de estados parciais possível. Algumas dessas contribuições podem ser aplicadas a outros paradigmas. Além dessas constribuições, nós também monstramos que é possível acelerar a computação de sime trias de espaço de estados através do uso de técnicas de teoria dos grupos. Nós também estudamos diferentes possíveis conceitos de equivalências entre políticas no contexto da busca em espaço de políticas do AND, e também poda por deadlock e abordagens mais gulosas. As buscas introduzidas estabelecem busca explícita em espaço de políticas ba seada em A* como um método competitivo para tratar tarefas de planejamento FOND.