Improving task-based plan coordination

Chetan Yadati, Cees Witteveen, Yingqian Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


A multi-agent planning problem consists of a set of activities that need to be planned by several autonomous agents. Here, plan coordination methods play an important role, since independently generated plans by different agents can easily lead to an infeasible joint plan. We study a coordination-by-design approach which allows each agent to make its own plan completely independently of the others, while still guaranteeing the feasibility of the joint plan. The essence of this coordination approach is to determine a minimum number of additional constraints (a minimum coordination set) such that autonomously developed plans satisfying these constraints are always mergeable into an overall feasible plan. It has been shown that such coordination problems are very hard to solve. Therefore, approximation algorithms have been developed to compute a sufficient, but not necessarily minimum coordination set.

In this paper, we concentrate on a special class of multi-agent planning problems. These problems arise in several practical applications such as supply chain management and hospital patient treatment. The plan coordination instances in these applications turn out to have a special structure. Using so-called agent dependency graphs, we show that for this special class of problems a better approximation algorithm to compute a sufficient coordination set can be obtained.
Original languageEnglish
Title of host publicationCollaborative Agents - Research and Development
Subtitle of host publicationInternational Workshops, CARE@AI09 2009 / CARE@IAT10 2010, Melbourne Australia, December 1, 2009 and Toronto Canada, August 31, 2010, Revised Selected Papers
Place of PublicationBerlin
ISBN (Electronic)978-3-642-22427-0
ISBN (Print)978-3-642-22426-3
Publication statusPublished - 2011

Publication series



Dive into the research topics of 'Improving task-based plan coordination'. Together they form a unique fingerprint.

Cite this