Hierarchical task network based emergency resource coordinated planning approach
ZHOU Chao1,2, WANG Hong-wei1,2, QI Chao1,2
1. Institute of Systems Engineering, Huazhong University of Science and Technology, Wuhan 430074, China; 2. Key Laboratory of Image Processing and Intelligent Control of Education Ministry, Huazhong University of Science and Technology, Wuhan 430074, China
Abstract:The departments involved in emergency decision-making are required to perform coordinated planning for a global action plan. The coordination of using emergency resource is a key issue of coordinated planning for an valid emergency response plan. In order to handle the real-time generated emergency resource conflict along with the distributed planning process, an hierarchical task network (HTN) planning process based multi-agent distributed coordinated planning method is designed. The method embeds the coordination process into hierarchical task network (HTN) planning process with the consideration that the action plan generation process should also be coordinated. This method can reduce the generation of useless plan and improve the efficiency of cooperation. Additionally, the coordination mechanism dealing with the reusable resources is developed, and a variety of priority rules are used to resolve resource using conflicts. Next, based on these designs, an hierarchical task network (HTN) based coordinated planning algorithm is proposed and implemented. Finally, an experimental study was presented to demonstrate the application of emergency resource coordinated planning and the validity and the efficiency of the method.
[1] 钟永光, 毛中根, 翁文国, 等. 非常规突发事件应急管理研究进展[J]. 系统工程理论与实践, 2012, 32(5): 911-918. Zhong Yongguang, Mao Zhonggen, Weng Wenguo, et al. Progress of "study on unconventional emergencies management"[J]. Systems Engineering - Theory & Practice, 2012, 32(5): 911-918. [2] Salmon P, Stanton N, Jenkins D, et al. Coordination during multi-agency emergency response: Issues and solutions[J]. Disaster Prevention and Management, 2011, 20(2): 140-158. [3] Tang P, Wang Z, Qi C, et al. Anytime heuristic search in temporal HTN planning for developing incident action plans[J]. AI Communications, 2012, 25(4): 321-342. [4] Malone T W, Crowston K. The interdisciplinary study of coordination[J]. ACM Computing Surveys (CSUR), 1994, 26(1): 87-119. [5] Decker K S. Environment centered analysis and design of coordination mechanisms[D]. University of Massachusetts, 1995. [6] Decker K S. TAEMS: A framework for environment centered analysis and design of coordination mechanisms[J]. Foundations of Distributed Artificial Intelligence, 1996: 429-448. [7] Durfee E H, Lesser V R. Partial global planning: A coordination framework for distributed hypothesis formation[J]. IEEE Transactions on Systems, Man and Cybernetics, 1991, 21(5): 1167-1183. [8] Lesser V R, Decker K S, Carver N, et al. Evolution of the GPGP domain independent coordination framework[R]. University of Massachusetts Computer Science Technical Report 1998-05, 1998. [9] Lesser V R. Reflections on the nature of multi-agent coordination and its implications for an agent architecture[J]. Autonomous Agents and Multi-agent Systems, 1998, 1(1): 89-111. [10] Wagner T, Lesser V. Toward generalized organizationally contexted agent control[R]. AAAI Technical Report WS-99-14, 1999. [11] Lesser V R, Decker K S, Wagner T, et al. Evolution of the GPGP/TEAMs domain-independent coordination framework[J]. Autonomous Agents and Multi-Agent Systems, 2004, 9(1): 87-143. [12] Wagner T, Phelps J, Guralnik V, et al. COORDINATORS: Coordination managers for first responders[C]// Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems, NY, USA, IEEE Computer Society, 2004, 3: 1140-1147. [13] Musliner D J, Durfee E H, Wu J, et al. Coordinated plan management using multiagent MDPs[R]. Technical Report SS-06-04, AAAI Spring Symposium: Distributed Plan and Schedule Management, 2006: 73-80. [14] Chen W. Designing an extended set of coordination mechanisms for multi-agent systems[D]. University of Delaware, 2005. [15] Erol K, Hendler J, Nau D. Complexity results for hierarchical task network planning[J]. Annals of Mathematics and Artificial Intelligence, 1996, 18(1): 69-93. [16] Dix J, Muñoz-Avila H, Nau D S, et al. IMPACTing SHOP: Putting an AI planner into a multi-agent environment[J]. Annals of Mathematics and Artificial Intelligence, 2003, 37(4): 381-407. [17] Kabanza F, Lu S, Goodwin S. Distributed hierarchical task planning on a network of clusters[C]// Proceedings of International Conference on Parallel and Distributed Computing and Systems, Calgary, Canada, ACTA Press, 2004: 439-444. [18] Hayashi H, TokuraS, Ozaki F. Towards real-world HTN planning agents[J]. Knowledge Processing and Decision Making in Agent-based Systems, 2009, 170: 13-41. [19] Decker K S, Li J. Coordinating mutually exclusive resources using GPGP[J]. Autonomous Agents and Multi-Agent Systems, 2000, 3(2): 1. [20] Nau D, Tsz-Chiu A, Iighami O, et al. SHOP2: An HTN planning system[J]. Journal of Artificial Intelligence Research, 2003, 20: 379-404.