Coordinated dynamic mission planning scheme for intelligent multi-agent systems

Abstract

Mission planning was thoroughly studied in the areas of multiple intelligent agent systems, such as multiple unmanned air vehicles, and multiple processor systems. However, it still faces challenges due to the system complexity, the execution order constraints, and the dynamic environment uncertainty. To address it, a coordinated dynamic mission planning scheme is proposed utilizing the method of the weighted AND/OR tree and the AOE-Network. In the scheme, the mission is decomposed into a time-constraint weighted AND/OR tree, which is converted into an AOE-Network for mission planning. Then, a dynamic planning algorithm is designed which uses task subcontracting and dynamic re-decomposition to coordinate conflicts. The scheme can reduce the task complexity and its execution time by implementing real-time dynamic re-planning. The simulation proves the effectiveness of this approach.

Keywords

weighted AND/OR tree / multiple intelligent agent / coordinated dynamic mission planning / AOE-Network

References

[1] GyorfiJ. S., WuC.-haur.. A minimum-jerk speed-planning algorithm for coordinated planning and control of automated assembly manufacturing [J]. IEEE Transactions on Automation Science and Engineering, 2006, 3(4): 454-462

[2] WuF., ZilbersteinS., ChenX.-ping.. Online planning for multi-agent systems with bounded communication [J]. Artificial Intelligence, 2011, 175(2): 487-511

[3] KitanoH., TadokorS., NodaI., MatsubaraH., TakahashiT., ShinjouA., ShimadaS.. Robocup-rescue: Search and rescue for large scale disasters as a domain for multi-agent research [C]. IEEE SMC Conference Proceedings on Systems, Man, and Cybernetics, 1999Tokyo, JapanIEEE Press739-743

[4] VannoyJ., JingXiao.. Real-time adaptive motion planning (RAMP) of mobile manipulators in dynamic environments with unforeseen changes [J]. IEEE Transactions on Robotics, 2008, 24(5): 1199-1212

[5] GuanS.-g., BaoC.-y., NeoTsengee.. Reduced pattern training based on task decomposition using pattern distributor neural networks [J]. IEEE Transactions on Neural Networks, 2007, 18(6): 1738-1749

[6] VakiliS., FakhraieS. M., MohammadiS.. Evolvable multi-processor: A novel MPSoC architecture with evolvable task decomposition and scheduling [J]. Computers and Digital Techniques, IET, 2010, 4(2): 143-156

[7] LiK.-qin.. Performance analysis of power-aware task scheduling algorithms on multiprocessor computers with dynamic voltage and speed [J]. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(11): 1484-1497

[8] BeaumontP., Chaib-DraaB.. Multiagent coordination techniques for complex environments: The case of a fleet of combat ships [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2007, 37(3): 373-385

[9] HiraiH., MiyazakiF.. Dynamic coordination between robots: Self-organized timing selection in a juggling-like ball-passing task [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2006, 36(4): 738-754

[10] KumarV., KanalL. N.. Parallel branch-and-bound formulations for AND/OR tree search [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1984, 6(6): 768-778

[11] SiddiquiM. K., O’BrienW. J.. A formal mapping-based approach for distributed schedule coordination on projects [J]. Advanced Engineering Informatics, 2009, 23(1): 104-115

[12] GuerrieroF., TalaricoL.. A solution approach to find the critical path in a time-constrained activity network [J]. Computers and Operations Research, 2010, 37(9): 1557-1569

[13] XuX.-l., WangR.-chuan.. A dynamic mobile multi-agent-based collaboration model of peer-to-peer computing [J]. Computer Science, 2008, 31(7): 1262-1267

[14] LuoJ.-w., ShiZ.-z., WangM.-g., LinFen.. A multi-agent cooperation model based on dynamic description logic [J]. Journal of Computer Research and Development, 2006, 43(8): 1317-1322

[15] LiS., DickR. P., JhaN. K.. DESP: A distributed economics-based subcontracting protocol for computation distribution in power-aware mobile ad hoc networks [J]. IEEE Transactions on Mobile Computing, 2004, 3(1): 33-45

[16] LIU Chun-hsien, LI Chia-feng, LAI Kuan-chou, WU Chao-chin. A dynamic critical path duplication task scheduling algorithm for distributed heterogeneous computing systems [C]// Proceedings of the 12th International Conference on Parallel and Distributed Systems. Washington D C, USA, 2006: 265–274.

[17] TAKPE T, SUTER F. Critical path and area based scheduling of parallel task graphs on heterogeneous platforms [C]// Proceedings of the 12th International Conference on Parallel and Distributed Systems. Minnesota, USA, 2006: 3–10.

[18] DongM.-kai.Research on dynamic description logic for intelligent agent [D], 2003ChengduChinese Academy of Sciences

[19] MortonI., KamienL.. Subcontracting, coordination, flexibility, and production smoothing in aggregate planning [J]. Management Science, 1990, 36(11): 1352-1363

[20] CHEN Fan, WANG Meng-jun. Research on subcontracting boundary of engineering project [C]// Proceedings of the 4th International Conference on Wireless Communications, Networking and Mobile Computing. Dalian, China, 2008: 1–4.

[21] ASHAR P, DEVADAS S, NEWTON A R. A unified approach to the decomposition and re-decomposition of sequential machines [C]// Proceedings of the 27th ACM/IEEE on Design Automation Conference. Orlando, Florida, USA, 1990: 601–606.

[22] UNRUH A, HARJADI H, BAILEY J, RAMAMOHANARAO K. Semantic-compensation-based recovery in multi-agent systems [C]// IEEE 2nd Symposium on Multi-Agent Security and Survivability. Philadelphia, PA, USA, 2005: 85–94.

[23] TAKANO F, MAEKAWA Y, KASAHARA H. Multiple-paths search with concurrent thread scheduling for fast AND/OR tree search [C]// International Conference on Complex, Intelligent and Software Intensive Systems. Dalian, China, 2009: 51–58.