Esta dissertação tem como objetivo estudar a combinação de duas técnicas de planejamento em inteligência artificial: planejamento hierárquico e planejamento sob incerteza Knightiana. Cada uma delas possui vantagens distintas, mas que podem ser combinadas, permitindo um ganho de eficiência para o planejamento sob incerteza e maior robustez a planos gerados por planejadores hierárquicos. Primeiramente, estudamos um meio de efetuar uma transformação, de modo sistemático, que permite habilitar algoritmos de planejamento determinístico com busca progressiva no espaço de estados a tratar problemas com ações não-determinísticas, sem considerar a distribuição de probabilidades de efeitos das ações (incerteza Knightiana). Em seguida, esta transformação é aplicada a um algoritmo de planejamento hierárquico que efetua decomposição a partir das tarefas sem predecessoras, de modo progressivo. O planejador obtido é competitivo com planejadores que representam o estado-da-arte em planejamento sob incerteza, devido à informação adicional que pode ser fornecida ao planejador, na forma de métodos de decomposição de tarefas. / This dissertation\'s objective is to study the combination of two artificial intelligence planning techniques, namely: hierarchical planning and planning under Knightian uncertainty. Each one of these has distinct advantages, but they can be combined, allowing the planning under uncertainty a performance gain and giving the hierarchical planning the ability to produce more robust plans. First, we study a way of performing a transformation, in a sistematic way, that enables forward-chaining deterministic planning algorithms to deal with non-deterministic actions, that doesn\'t take into account the probability distribution of actions\' effects (Knightian uncertainty). Afterwards, this transformation is applied to a hierarchical planning algorithm that progressively performs decomposition starting from tasks without predecessors. The obtained planner is competitive with state-of-the-art non-deterministic planners, thanks to the additional information that can be given to the planner, in the form of task decomposition methods.
Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-06082008-171546 |
Date | 05 May 2008 |
Creators | Ricardo Guimaraes Herrmann |
Contributors | Leliane Nunes de Barros, Fabio Gagliardi Cozman, Marcelo Finger |
Publisher | Universidade de São Paulo, Ciência da Computação, USP, BR |
Source Sets | IBICT Brazilian ETDs |
Language | Portuguese |
Detected Language | Portuguese |
Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0094 seconds