Solving the Plan Coordination Problem

Master thesis (2010)

Authors

Contributors

T.B. Klos (mentor)
Programme
Department of Algorithmics (EEMCS) (TU Delft)
Copyright: © 2010 Scharpff, J.C.D.
More Info
expand_more

Published Date

30-08-2010

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Programme

Department of Algorithmics

Abstract

In this thesis we focus on implicit coordination for multi-agent planning problems. In such problems, agents are not able or willing to cooperate with each other and hence we need to perform pre-planning coordination in order to ensure that merging all their plans always results in a feasible joint plan. More specifically, we are interested in finding a minimal cardinality set of constraints such that when add this set to the multi-agent planning problem, no infeasible joint plan can be constructed, whatever local plan each agent develops. Finding such a minimal cardinality set is known as the PLAN COORDINATION PROBLEM (PC) which has been proven to be ?p2 -complete [44]. Previous work has focussed on approximation and special cases for PC, however some scenarios require or allow for exact solutions. Also, smaller instances might be solvable in reasonable time. This thesis discusses several exact solving methods and combines them into one exact algorithm that is able to solve instances with task sizes up to 50 planarcs within the hour.