Coordination in Multi-Agent Planning with an Application in Logistics
Jeroen Valk (Delft University of Technology, The Netherlands), Mathijs de Weerdt (Delft University of Technology, The Netherlands) and Cees Witteveen (Delft University of Technology, The Netherlands)
Copyright: © 2005
Multi-agent planning comprises planning in an environment with multiple autonomous actors. Techniques for multi-agent planning differ from conventional planning in that planning activities are distributed and the planning autonomy of the agents must be respected. We focus on approaches to coordinate the multi-agent planning process. While usually coordination is intertwined with the planning process, we distinguish a number of separate phases in the planning process to get a clear view on the different role(s) of coordination. In particular, we discuss the pre-planning coordination phase and post-planning coordination phase. In the pre-planning part, we view coordination as the process of managing (sub) task dependencies and we discuss a method that ensures complete planning autonomy by introducing additional (intra-agent) dependencies. In the post-planning part, we will show how agents can improve their plans through the exchange of resources. We present a plan merging algorithm that uses these resources to reduce the costs of independently developed plans. This (any-time) algorithm runs in polynomial time.