Belief tracking for multi-agent planning

Kominis, Filippos

Belief tracking for multi-agent planning

Document Type

Doctoral thesis
Published Version

Author

Kominis, Filippos

Director

Geffner, Héctor

Publication Date

2017-12-01

Pages

152 p.

License

Citation

Kominis, F. Belief tracking for multi-agent planning. Universitat Pompeu Fabra; 2017. handle: http://hdl.handle.net/10803/457705

This citation was generated automatically.

Doctoral program

Programa de doctorat en Tecnologies de la Informació i les Comunicacions

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.

Keywords

Multi-agent planning, Epistemic planning, Dynamic epistemic logic, Classical planning, Compilation approaches, Knowledge representation, Planificació multiagent, Planificació epistèmica, Lògica epistèmica dinàmica, Planificació clàssica, Aproximacions de compilació, Representació del coneixement