【作者】 刘莹；

【导师】 谷文祥；

【作者基本信息】 东北师范大学 ， 运筹学与控制论， 2013， 博士

【摘要】 智能规划和规划识别的研究一直是人工智能的核心技术和最具挑战性的研究方向之一，其应用价值和研究前景也是有目共睹的。智能规划是关于动作的推理，该过程是通过预期动作的期望效果，选择和组织一系列动作，来尽可能好地实现预先给定的目标。在现实生活中，当我们要完成一项复杂的任务，或是执行的动作受到某些约束的时候，就需要计划动作应如何执行，这就是简单意义上的规划。智能规划是一个涵盖知识表达、人机交互、情景演算、知识推理、非单调逻辑和认知科学等多领域的交叉性学科。其相应的求解算法种类繁多，研究者们试图用多种方法对规划问题进行表示、求解，以期得到较优的规划解，并更好地在现实世界得到广泛的应用。其中之一就是在车间作业调度规划问题中的应用，即在加工资源有限的情况下，根据已知工件的加工顺序要求对整个车间的生产作出安排，使得最大完工时间最短，每台机器的等待时间最短。规划识别是根据观察到的某一智能体的琐碎的、片断的动作,推导出该智能体的一系列相关行动和最终目标。历经30多年的发展，其方法已经日趋成熟，目前，规划识别已经成为人工智能中的热门研究方向之一。本文主要针对智能规划和规划识别这两个相关的研究方向进行探讨，旨在找到解决现实问题更好的方法。本文的创新成果如下：第一，我们介绍了图规划及其扩展规划，如一致图规划、感知图规划、灵活图规划、概率图规划等，其中重点讨论了在规划图框架下的对象集合动态可变的规划问题。该方法解除了经典图规划中不能生成对象和不能消灭对象的假设，使其在实际应用中更为灵活。第二，应对规划与规划识别、对手规划的关系密不可分，它们是一个有机的整体。因此，我们对这些问题进行了细致的研究与分析。同时，还分析了对手规划与敌意规划的区别和特点，重点讨论了应对规划的求解方法及其应用，为后面的研究工作打下基础。第三，我们在前面的研究基础上，提出了对象集合动态可变的应对规划的参考模型及其算法，使其可以在动态环境下执行有效的应对规划。在对手领域中，应用HTN（分层任务网络）规划，实现快速识别并搜索到有效的应对策略进行应对。并以军事领域中的实际问题为例，用该算法对其进行详细的分析与求解。第四，我们在目标图的基础上提出了一个网络攻击识别算法，该算法可以在网络的复杂环境中识别攻击规划，并预测下一步的动作。同时，还在因果网络中加入了时序约束，更可以清晰地分析每一步动作，并可以识别无效、试探性的网络攻击。第五，我们对近年来PFSP问题的求解方法进行了详细的综述，纵观当前的求解算法，基本上都是以Makespan、Total flowtime和Tardiness为目标，我们便以这三类目标进行分类，对每个类别的求解方法进行对比、分析，总结各个算法的优点和不足，为后面的研究工作打下基础。第六，我们在微分进化算法的基础上，提出了一个有效的调度算法，即混合微分进化算法，简称为L-HDE。该算法结合了IIS局部搜索和贪婪局搜索，改进了种群的多样性，并使算法跳出了局部极小。同时，我们还与多个知名的算法进行对比。实验结果表明，L-HDE具有优越的搜索性能和鲁棒性，它可以在全局搜索和局部搜索之间实现良好地折衷，并且非常适合处理PFSP问题，是一个具有良好性能和效率的算法。综上所述，本文的研究成果具有一定的理论意义和应用价值，为推动智能规划和规划识别的研究提供了良好的方法和手段。更多还原

【Abstract】 The research on intelligent planning and plan recognition has always been thecore of artificial intelligence technology and the most challenging one of researchdirections, and the application value and research prospect are obvious to all.Intelligent planning is about action reasoning, which process is through theexpectation effect of expected action, selected and organized a series of actions, as faras possible to achieve a given goal in advance. In real word, when we want tocomplete a complicated task, or execute action with some constraints, it needs to planthe movements how to carry out，this is the simple sense of planning. Intelligentplanning covers knowledge representation, human-computer interaction, situationcalculus, knowledge reasoning, non monotonic logic and cognitive science and otherfields with its overlapping subject. There are great of corresponding algorithms. Theresearchers try to use a variety of methods for solving the planning problem, in orderto get the optimal planning solution and widely application in the real world.Intelligent planning has a strong applicability, one of which is in the workshopscheduling. In the limited resources, according to the known processing orderrequirements to make arrangement for the production, the makespan is the shortest,and every machine of waiting time shortest.Plan recognition is a process, according to the observed an agent of fragmentsactions, deduces a series of related actions and ultimate goal. After30years ofdevelopment, its approach has become increasingly mature, for now, plan recognitionhas become one of the hot researchs of artificial intelligence. This paper mainly aimsto intelligent planning and plan recognition, and discuss this two related researchdirections. The innovation achievement as follows:First, we introduced the graphplan and its expansion, such as consistentgraphplan, Sensory graphplan, flexible graphplan, probabilitc graphplan, and so on.We mainly discusse the plan with the dynamic variable object set. This methodrelaxes the hypothesis that the classic graphplan can’t generate objects and destroyobject, make its more flexible in practical application.Second, counterplanning, planning recognition, and adversial plan are closelylinked, they are an organic whole. Therefore, we research and analysis the problems detailedly, and we also analyze the difference and characteristics between adversialplanning and hostile planning. The solving method of counterplanning and itsapplication has been discussed.Third, we propose a modle and its algorithm of conterplanning with the variableobject set. It can execute the effective counterplanning in dynamic environment. Inthe adversial field, the HTN (hierarchical task network) planning is applied torecognize fastly and search the effective strategies to deal with. In order to themilitary problems as an example, we use the algorithm to analyse and solve it.Fourth, we propose a network attack recognition algorithm on the basis of goalgraph, which can recognize the attack planning in the complex network environment,and predict the actions of the next step. At the same time, we also join timingconstraints in the causal network to analysis each step action clearly, and can identifyinvalid and tentative network attacks.Fifth, we have reviewed the solving method of PFSP problem in recent years, allthe current algorithm can be divided into three types roughly, the Makespan and Totalflowtime and Tardiness as the goal. Then three types of solving methods arecompared and analysis, and the advantages and disadvantages of each algorithm aresummarized.Sixth, we propose an effective scheduling algorithm based on the differentialevolution algorithm, namely hybrid differential evolution algorithm, referred to asL-HDE. The algorithm combines the IIS local search and greed bureau search toimprove the diversity of population, and the method can jump out the local minimum.At the same time, we also compare our algrithm with a number of well-knownalgorithms. The experimental results show that L-HDE has superior performance androbustness. L-HDE can realize good compromise in the global search and local search,and is very suitable for processing PFSP problem, which has a good performance andefficiency.In conclusion, the result of this paper has certain theoretical significance andapplication value. It provides a good method and means of promoting the intelligentplanning and plan recognition.更多还原