Belief tracking for multi-agent planning

Abstract

Classical planning is the problem of finding a sequence of actions that achieve a desired goal from an initial state, assuming deterministic actions. Dynamic epistemic logic (DEL) on the other hand, provides formal frameworks that allow the modeling of complex beliefs in multi-agent settings and define how those beliefs change due to physical and communication actions. In this dissertation we focus on bridging the gap between the expressivity of DEL and the computational approaches used in classical planning. First, we present formulations that capture a fragment of the expressivity of DEL and can model nested knowledge in two different multi-agent settings. Second, we tackle the computational problem of finding plans by providing translations to classical planning that allow the use of classical planners and heuristic search. We empirically evaluate our approaches and discuss their formal properties.

La Planificació Clàssica és un problema que busca una seqüèencia d’accions per arribar a una meta o objectiu des d’un estat inicial, assumint que les accions són deterministes. Per una altra banda, la Lògica Epistèmica Dinàmica (LED), proporciona una eina de treball formal que permet el modelatge de creences complexes en un entorn de múltiples agents, i defineix com aquestes creences varien aplicant accions físiques i de comunicació. En aquesta disertació ens centrem en connectar l’expressivitat de LED amb els diferents enfocaments que s’utilitzen a planificació clàssica. Primer presentem les formulacions que capturen un fragment de l’expressivitat de LED i que pot modelar coneixement anidat en dos configuracions diferents amb múltiples agents. Després abordem el problema computacional de trobar plans, tot proporcionant traduccions de planificació clàssica que permeten utilitzar planificadors clàssics amb búsquedes heurístiques. Finalment, evaluem de forma empírica els nostres enfocaments i parlem sobre les seves propietats formals.