Belief tracking for multi-agent planning

Author

Kominis, Filippos

Director

Geffner, Héctor

Date of defense

2017-12-01

Pages

152 p.



Department/Institute

Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions

Doctorate programs

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; Lògica epistèmica dinàmica; Planificació clàssica; Aproximacions de compilació; Representació del coneixement

Subjects

62 - Engineering. Technology in general

Documents

tfk.pdf

967.2Kb

 

Rights

L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/

This item appears in the following Collection(s)