Solving the Plan Coordination Problem

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.Department of AlgorithmicsSoftware EngineeringElectrical Engineering, Mathematics and Computer Scienc