With The Right Tree And The Aoe-network Multi-agent-based Dynamic Mission Planning

Task planning in multi-agent system is one of the hotspots in recent years. RoboCupRescue simulation system is a typical heterogeneous multi-agent system, for quick and efficient rescue task plan and to minimize disaster losses and improve the efficiency of rescue tasks in a complex and dynamic scenarios, an effective dynamic task planning method which mainly includes hierarchical task decomposition, consistent planning coordination, dynamic adjustment and conflict eliminating coordination which are interrelated and closely integrated process is presented by introducing weighted AND/OR tree and AOE-Network in this dissertation.For the complexity of the tasks and timing constraints, a task decomposition hierarchy planning using weighted AND/OR tree with timing constraints is presented. The weighted AND/OR tree describes the hierarchical relationship between complex tasks and subtasks and the AND/OR features of tasks; The leaf nodes of AND/OR tree are appended weights to represent the execution time of corresponding subtasks; aid line is added into the tree to restrict the time constraint among the relational task nodes, arriving a task decomposition structure model with timing constraints and for hierarchical task planning.With regards to the difficult for each agent to reach consistency in executing sub-task plan after task decomposition, a task coordination approach that the weighted AND/OR tree is converted to AOE-Network is proposed. Firstly, on the basis of decomposing the complex task by a weighted AND/OR tree with timing constraints, pruning the weighted AND/OR tree based on execution weights of node to discard partly or-subtask for reduction of the execution of unnecessary or-subtask; Then the weighted AND/OR tree with timing constraints is changed into an AOE-Network to get the each subtask's earliest occurrence time on which calculating the start time and end time of sub-tasks, making the entire task be completed in the shortest time, achieving the consistent planning coordination.Considering the problems for the delay or interruption of tasks caused by conflicts when agents carrying out them and dynamic changes under the process of consistent planning coordination, a dynamic task planning based on task subcontracting and dynamic re-decomposition is presented. When an agent's sub-task generates an interrupt, it is subcontracted to other agent or broken down into several simple sub-tasks, forming a new weighted AND/OR tree and meeting the enforceability of tasks; By converting the new weighted AND/OR tree into AOE-Network to continuously maintain consistent planning coordination of total task and meet the dynamic real-time requirements in task planning, and reach conflict elimination coordination and dynamic adjustment coordination.A dynamic task planning simulation system is developed to demonstrate the availability and effectiveness of dynamic planning method and it has been applied to the robot rescue simulation team CSU_Yunlu of Central South University, which won the second place in 2009 China Robot Contest, this also confirmed that the above method is effective.