The earliest CDP planner was Corkhill's [16] distributed version of Sacerdoti's [60] hierarchical planner Noah. This planner used critics which were invoked at each level of abstraction, to incrementally check for coordination of the developing plan. Later, the Partial Global Planning (PGP) [19] system was developed for a distributed vehicle monitoring application. This system could decompose tasks, and then hold negotiation dialogues to identify conflicts and opportunities for coordination by each agent passing their localised view of the global plan.
CDP differs from the planning approach that will be developed in this thesis. It is more useful when plans can be pursued for the most part independently with only a few coordination points. Furthermore CDP does not have anything to say about the efficiency of coordination dialogues, since it is assumed that communication is relatively inexpensive. Nor can CDP be easily adapted to account for communication cost. This is because the planning approach taken in CDP emphasises the exchange of proposed plans rather than exchange of the beliefs that are used to form those plans. The plan space grows exponentially with the number of beliefs about the domain state and the plan rules, and so the number of plan proposals that must be exchanged is exponential as well. Conversely, exchange of beliefs and is more more efficient from the perspective of communication costs. In addition, the probabilistic approach to planning that will be taken here allows an agent to prune the space of multi-agent plans of the unlikely alternatives, so that the likelihood that a subplan is easy to coordinate is increased. Conversely, CDP makes no distinction among the plans that the other agent would chose to put forward. DSIPE [77] is one exception. It deals with the information overload problem by filtering out the constraints that are unlikely to be relevant to another planner.