Solving the Plan Coordination Problem

Solving the Plan Coordination Problem

Scharpff, J.C.D.

Klos, T.B. (mentor)

Electrical Engineering, Mathematics and Computer Science

Software Engineering

Department of Algorithmics

2010-08-30

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.

multi-agent planning
coordination mechanisms
implicit coordination

http://resolver.tudelft.nl/uuid:81749be6-b1b2-40fe-ad13-02be9b9fbd01

Student theses

master thesis

(c) 2010 Scharpff, J.C.D.