Research On Planning And Adaptive Collaborating In RoboCupRescue Simulation System

Over the last few years, a multi-agent system (MAS) has been the important branch in the field of distributed artificial intelligence. The dissertation is studied based on RoboCup Rescue Simulation System, due to the limited communications and the dynamic complicated rescue environment, the weighted AND/OR tree, activity on edges-network (AOE-NET), co-evolution and ant colony algorithm are introduced. The key issues such as task planning, path searching and adaptive collaboration are investigated in a complex, dynamic and heterogeneous multi-agent system. The main research contents and contributions are listed as follows:A hierarchical architecture contains reactive layer and deliberative layer of MAS has been built. Reactive layer is based on important degree information processing algorithm to filter perception information. The system state is predicted and the world model of agent is established. The act is obtained according to the world model and the rule base, a rapid response capability is provided for agent. Task planning and adaptive collaborative is included in deliberative layer, deliberative task planning and decision-making self-adaptive ability are provided for the agent.The study of task planning in multi-agent system focuses on the task decomposition and task coordination. A weighted AND/OR tree based task decomposition method is proposed. The hierarchical relationship between complex tasks and subtasks and the AND/OR relationship among subtasks are described through introduced AND/OR tree. The execution time of subtasks is represented by the weight of AND/OR tree's leaf nodes. The aid line is added into the weighted AND/OR tree to limit the relationship constraint among the relational task nodes. The completeness and timing constraints and accessibility and granularity and flexibility of task decomposition architecture are satisfied.For heterogeneous multi-agent system, the AOE-Network and the earliest time based task coordination method is proposed due to each agent is difficult to reach agreement on the implementation of Task scheduler problem.Based on the decomposition of the complex task by a weighted AND/OR tree, the child nodes or parts which dose not have the shortest executive weight in the AND/OR tree are discarded, to reduce the execution time of the unnecessary OR-subtask(sub-subtask). The earliest occurrence time of each subtask is gained by virtue of the weighted AND/OR tree is changed into an AOE-Netwrok, the entire task be completed in the shortest time, a plan coherent coordination is achievedIn order to effectively solve the executing task conflict, the complex task delay or interruption arising from the dynamic change of the target, a dynamically re-decomposed task subcontracting method is presented, eliminating the conflict and adjusting coordination dynamically, making the entire task continue to maintain coherent planning, meeting the dynamic real-time requirements of the task planning. The proposed dynamic task planning method not only enables the task to get a specific executing time, but also makes the total task be completed in the shortest time or more task be done in a certain period of time, and meet the dynamic real-time task planning.A path search method called target attraction based ant algorithm is presented to solve the shortest path search problem of the rescue robot in the city with dynamic topology after earthquake. the target attraction function is imported, making full use of the city's topology before earthquake, calculating the attraction of the target node for the alternative nodes. The target attraction function is used as heuristic function together with pheromone intensity to guide the ant's searching and make ants chose the nodes which is closer to the target node, speeding up the convergence rates of the ant colony and enabling ants converge to the shortest path as possible as they can, avoiding converging to local optimum.Aimed at the maximization problem of the collaboration effectiveness of the cooperative heterogeneous multi-agent system in the unstructured environment and the multifarious complex task, a cooperative co-evolutionary algorithm based on evaluating sub-domain fitness is proposed. A cooperative co-evolutionary method is adopted, the general task of multi-agent system is regarded as the problem domain in the cooperative co-evolution, and the set of an agent's behavior decision-making is considered as the population in co-evolution. The agent's behavior decision-making is co-evolved cooperatively, producing adaptive collaborative behavior.To overcome the problems such as the heavy communication traffic and the difficulty of establishing the fitness function, when the cooperative co-evolutionary algorithm is used to solve the collaborative issue of the complex multi-agent system, the complex problem domain model is decomposed into some sub-domain models with small interaction and solved more easily. This algorithm completes the evolution of agents' behavior by parallel using the cooperative co-evolutionary algorithm among the sub-domain models, the dimension of fitness assessment and the communication burden are reduced. An environmental factors influence matrix is introduced to map other sub-domains'influence information to the individual fitness assessment of the population in this sub-domain while the sub-domain is executing the cooperative co-evolution, guiding the population evolving to the global optimization.The RoboCup Rescue Simulation System is a typical heterogeneous multi-agent system, which provides an advanced and interdisciplinary research platform for investigator in the fields of artificial intelligence and robotics research. The proposed algorithms of the dissertation have been applied to the robot rescue simulation team CSU_Yunlu of Central South University, which won the championship and the second place in 2006 and 2008 China Robot Contest respectively, the efficiency of the proposed algorithms are verified.