INCREMENTAL COORDINATION FOR TIME-BOUNDED AGENTS
Abdel‐Illah Mouaddib · International Journal of Artificial Intelligence Tools · 2004
We address in this paper a problem of autonomous agents performing in a common environment where each agent has a goal to achieve before a given deadline. Each agent must determine a local plan and then react properly to the local plans of other agents before a given deadline. The solution presented consists in using progressive planning that adapts the detail of local plans according to local deadlines, and progressive negotiation that organizes conflicts between local plans into categories and solves them progressively from a mandatory category to an optional one. This structuration of conflicts in categories contributes in solving first, the most important conflicts in order to guarantee, when it is possible, the coordination of the mandatory part of the plan before the deadline. Our negotiation model is based on the modified PGP (Partial Global Planning) approach, named Partial Global Progressive Planning (PGPP), which is an incremental strategy to insert partial local plans progressively one by one. This strategy consists in discarding optional partial local plans of an agent when a deadline is exceeded or global consistency is violated. We show that this approach reduces the costs of detecting and solving conflicts. This approach can be seen as a step towards the application of contract-net type systems to real-world problems.