Multi-agent plan diagnosis and negotiated repair

ABSTRACT

In the complex, dynamic domain of Air Traffic Control (ATC) many unexpected events can happen during the execution of a plan. Sometimes these disruptions make the plan infeasible and require a change of the original plan. Unexpected events may disrupt the execution of a plan leading to conflicts concerning the use of shared resources. By monitoring the possibly disrupted execution of a plan, air traffic controllers identify and repair conflicts before they occur, making the plan 'healthy' again. Model-based diagnosis helps to identify the causes of observed disruptions in the execution of a plan. This information enables the creation of better plan repairs. These repairs should efficient, but moreover they should be fair, i.e., one airline should not be the victim of conflicts caused by another. Due to the complexity of planning tasks, it is beneficial to provide a distributed solution such that the workload is spread instead of centralised. Moreover, since the choice between various possible solutions to a conflict in the plan execution directly influence different parties (with diverting interests), the decision about which solution to choose should not be made by a single (central) decision maker, but agreed upon by the different parties involved. The Multi-Agent Diagnosis and negotiated repair (MAD) demonstrator combines our previous research done on model-based diagnosis, planning and scheduling techniques, and methods for multi-agent negotiation to solve this problem in a distributed manner. The resulting tool is a system to support the control and adaptation of distributed plan execution in the domain of ATC.

REFERENCES

• 1: Pieter Buzing , Adriaan Ter Mors , Jeroen Valk , Cees Witteveen, Coordinating Self-interested Planning Agents, Autonomous Agents and Multi-Agent Systems, v.12 n.2, p.199-218, March 2006 [doi>10.1007/s10458-005-6104-4]
• 2: P. C. Buzing and C. Witteveen. Temporal plans and resource management. In A. Tuson, editor, Proc. of the 24th Annual Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG 2005), pages 115--124, 2005.
• 3: Femke Jonge , Nico Roos , Huib Aldewereld, Using DESs for Temporal Diagnosis of Multi-agent Plan Execution, Proceedings of the 5th German conference on Multiagent System Technologies, September 24-26, 2007, Leipzig, Germany [doi>10.1007/978-3-540-74949-3_6]
• 4: G. Jonker, H. Hesselink, J.-J. Ch. Meyer, and F. Dignum. Preventing selfish behaviour in distributed tactical airport planning. In Proc. of the 7th USA/Europe R&D Seminar on Air Traffic Management (ATM '07), 2007.
• 5: Geert Jonker , Frank Dignum , John-Jules Meyer, Achieving cooperation among selfish agents in the air traffic management domain using signed money, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329382]
• 6: N. Roos and C. Witteveen. Models and methods for plan diagnosis. Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS), to appear, 2007.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Keywords:
conflict diagnosis, multi-agents, negotiation, plan repair