考虑方案质量的HTN应急任务规划方法

发布时间：2017-12-27 13:14

本文关键词：考虑方案质量的HTN应急任务规划方法　出处：《华中科技大学》2016年博士论文　论文类型：学位论文

【摘要】：近年来,突发事件频繁发生,而且新的突发事件也不断出现。这不仅给相关地区的经济和社会造成严重的冲击,也给应急管理部门科学有效地应对突发事件带来巨大的挑战。应急行动方案制定是突发事件应急响应决策的关键阶段,需要在突发事件发生后,快速有效地制定出应急行动方案,并且开展应急处置工作。传统的数学建模方法难以适应复杂的应急响应决策问题,而层次任务网络(HTN,Hierarchy Task Network)规划作为人工智能自动规划的一种,能够充分使用领域知识对动作进行推理,从而快速生成应急行动方案,已经在实际应急行动方案制定中获得成功的应用。然而,目前的HTN规划只关注于如何快速生成可行方案,没有考虑如何生成高质量的方案。在很多情况下,应急行动方案的质量直接影响到应急响应决策的效果,低质量的应急行动方案不仅难以完成当前的应急任务,也可能给其它应急任务的执行带来麻烦。为了科学有效地进行应急响应决策,亟需研究如何生成高质量的应急行动方案。本文就应急行动方案制定中需要考虑方案质量的几种实际情况,以HTN规划为研究对象,针对应急行动方案制定问题中的时态偏好、时间柔性和方案的多目标优化等方面来设计相应的HTN应急任务规划方法,探讨如何生成高质量的应急行动方案。主要的创新性研究成果如下:(1)为了获得满足应急决策者时态偏好的应急行动方案,提出了一个时态HTN应急任务规划方法,TPHTN。TPHTN将简单时态网络(STN)扩展为带偏好的简单时态网络(STNP)使其能够表示应急行动方案制定问题的时态约束以及时态偏好信息。同时,TPHTN扩展了HTN的领域知识用以表达规划领域中的时态偏好信息。在TPHTN的规划过程中,设计了α-,β-和γ-3种水平一致性来评估STNP的质量,并以此设计启发式搜索规则来选择合适的规划方向。当规划过程结束时,TPHTN能够生成满足决策者时态偏好的应急行动方案。(2)为了生成高质量的应急行动方案应对方案执行过程中遇到的时态异常,提出了一种考虑时间柔性HTN应急任务规划方法,FHTN-CON。FHTN-CON分为应急行动方案生成和应急行动方案执行两个部分:应急行动方案生成部分使用STN来表示规划问题中的时态约束信息,并使用了一种基于STN的启发式搜索,最终生成一个高质量的带时间柔性的应急行动方案;在应急行动方案执行部分,FHTN-CON监控方案的执行过程,当方案的执行发生时态异常时,检测未执行的方案是否可行,当且仅当这个方案是不可行的,才进行重规划。FHTN-CON可以有效地减少应急行动方案执行中因时态异常而导致的重规划。(3)为了对应急行动方案进行多目标优化,提出了一种多目标HTN应急任务规划方法,PSA。首先,PSA对传统的HTN操作符进行扩展,使其能够表达操作符的多个性能特征;其次,PSA使用基于偏好关系的方法对应急行动方案进行多目标评价;再次,PSA将启发式搜索和Anytime搜索结合在一起,通过引导HTN规划方向和对HTN搜索空间进行削减等策略,使PSA能够不断生成高质量的应急行动方案。(4)提出了一种基于支配关系的多目标HTN应急任务规划方法,DSA。针对无法提供目标间偏好信息的情况,DSA使用支配关系对应急行动方案进行多目标评价。其次,DSA的规划算法结合了启发式搜索和Anytime搜索:启发式搜索对规划中的方法和操作符进行基于支配关系的排序;Anytime搜索则对规划空间进行基于支配关系的削减,在提高规划方法搜索效率的同时保证了后生成的方案不被先生成的方案所支配。最终,DSA能够生成一个非支配方案集合,供决策者从中选择合适的应急行动方案。
[Abstract]:In recent years, sudden events have occurred frequently, and new emergencies are also appearing. This not only causes serious impact on the economy and society of the related areas, but also brings great challenges to emergency management departments to deal with emergencies scientifically and effectively. The formulation of emergency action plan is the key stage of emergency response decision-making. It is necessary to establish emergency response plan quickly and effectively and carry out emergency disposal after emergency. The traditional methods of mathematical modeling is difficult to adapt to the emergency response to a complex problem, and hierarchical task network (HTN Hierarchy, Task Network) a plan as artificial intelligence automatic planning, to make use of domain knowledge in reasoning about action, so as to quickly generate the emergency action plan, has been applied in actual emergency action plan successfully the. However, the current HTN program focuses only on how to generate feasible solutions quickly, without considering how to generate high quality solutions. In many cases, the quality of emergency action plan directly affects the effect of emergency response decision. Low quality emergency action plan is not only difficult to complete the current emergency task, but also may bring trouble to other emergency tasks. In order to make the emergency response decision scientifically and effectively, it is urgent to study how to generate high quality emergency action plan. The emergency action plan needs to consider the actual situation in several schemes of quality, with HTN planning as the research object, aiming at multi-objective optimization problems and other aspects of the development of temporal preferences, time flexibility and scheme of emergency action plan to design the HTN emergency task planning corresponding planning method, to explore the emergency action plan how to generate high quality. The main innovative research results are as follows: (1) in order to get an emergency action plan satisfying the temporal preference of emergency decision makers, a temporal HTN emergency mission planning method, TPHTN is proposed. TPHTN extends the simple temporal network (STN) to a simple temporal network with preferences (STNP), enabling it to express emergency action plans, temporal constraints and temporal preference information. At the same time, TPHTN extends the domain knowledge of HTN to express the temporal preference information in the planning field. In the planning process of TPHTN, we designed alpha, beta and gamma -3 level consistency to evaluate the quality of STNP, and designed heuristic search rules to select the appropriate planning direction. At the end of the planning process, TPHTN can generate an emergency action plan that satisfies the decision maker's temporal preference. (2) in order to generate high-quality emergency response plan to deal with temporal anomalies encountered in the implementation of the plan, a time dependent flexible HTN emergency mission planning method, FHTN-CON, is proposed. FHTN-CON divided into emergency action plan and emergency action plan for two parts: emergency action plan generation part of the use of STN to programming problem in the temporal information, and use a STN based heuristic search, with a time of high quality flexible emergency action plan generated in the emergency action plan implementation; part of the implementation process of FHTN-CON monitoring program, when the program execution occurs when the temporal anomaly detection, the non implementation scheme is feasible, if and only if this solution is not feasible, only re planning. FHTN-CON can effectively reduce the replanning caused by temporal anomalies in the execution of emergency action plans. (3) in order to optimize the emergency action plan, a multi-objective HTN emergency task planning method, PSA, is proposed. First of all, the traditional PSA HTN operator was extended to multiple performance characteristics can express operator; secondly, using PSA method based on the preference relation and emergency action plan for multi target evaluation; thirdly, PSA heuristic search and Anytime search together, cut strategy by guiding the direction and planning of HTN the HTN search space, which allows the PSA to continue to generate high quality emergency action plan. (4) a multi-objective HTN emergency task planning method based on domination relation, DSA, is proposed. In view of the inability to provide preference information between targets, DSA uses a dominating relationship to Multiobjective evaluation of emergency action plans. Secondly, planning algorithm DSA combines heuristic search and Anytime search, heuristic search methods and operators in planning of dominance based sorting; Anytime search for planning space is cut based on dominance relation, at the same time improve the efficiency of search planning method to ensure the program is not generated after the program by Mr. control. In the end, DSA can generate a set of non dominated schemes for decision makers to choose the appropriate emergency action plan from it.
【学位授予单位】：华中科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP18

【相似文献】