Improving Task-based Plan Coordination

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.