【作者】 徐丽；

【导师】 谷文祥；

【作者基本信息】 东北师范大学 ， 计算机软件与理论， 2006， 硕士

【摘要】 智能规划是当前人工智能领域中极为活跃的一个研究热点,它已广泛应用于自主机器人、航空航天、自然语言理解、知识推理、人机交互、数据挖掘等许多高技术领域。虽然它的一些理论问题与应用问题是世界上公认的难题,但多年来国内外许多优秀学者一直致力于这一方向的研究,特别是美国卡耐基梅隆大学的A.L.Blum教授和M.L.Furst教授利用规划图分析提出的图规划方法,第一次采用图的方式来解决规划问题,在智能规划领域中取得了革命性进展。近年来,智能规划的研究更是发展飞速,除了继续研究如何提高规划效率之外,学者们还对如何扩展规划算法处理问题的范围,如何提高规划的质量进行了大量研究。图规划算法可以成功的解决经典STRIPS域中的问题,但此算法对获得现实世界问题的细节是不充分的,导致某些有解的问题求不到解,或者导致生成某些质量较低的解,而一般来讲现实中的规划问题都是非常复杂的,如果不对它们进行处理,大部分很难完全解决;另外由于规划问题是多种多样的,对所有的规划问题以统一的方式进行处理也是不现实的,因此应该针对不同的规划问题提出与其相适应的具有其特殊性的规划算法,具体问题具体分析。本文针对规划领域中比较复杂的一类问题——灵活规划问题展开研究,对以下内容进行了创新性研究:本文系统地回顾了智能规划的研究历史,深入地介绍了在图规划框架下智能规划的研究工作,同时,全面地展示了智能规划技术的研究现状及未来的发展方向。提出了一种从目标集扩张灵活规划图的新算法。该算法与现有算法不同,采用逆向扩张、正向搜索的方法,完善了逆向互斥推理的策略,避免了逆向传播满意度的复杂过程。这种算法考虑用户的偏好,力求提高规划解的综合质量,处理的问题也从理想向现实迈进了一步,因此在解决实际问题中,具有其独特的优势。作者基于以目标为导向的灵活规划算法开发了GDFGP(Goal-Directed FlexibleGraphplan)规划系统,并在营救灵活规划域上验证了算法的有效性。由于智能规划技术本身的独立性,开展对智能规划算法的研究,对于竞赛机器人、游戏角色设计、智能用户接口的设计、自然语言理解以及多Agent系统等许多领域的研究也有广泛的应用前景。更多还原

【Abstract】 Nowadays, intelligent planning is a very hot branch in AI because of its wideapplication in high-technology fields such as autonomous robots, spacecraft, naturallanguage understanding, knowledge inference, human-machine interaction, data mining etc.Some problems in theory and in practice are international puzzles, but a lot of famousscholars home and abroad still devote themselves to the research. Specially, professorA.L.Blum and professor M.L.Furst provided the Graphplan algorithm, which causedrevolutionary progress in the intelligent planning.Recently, intelligent planning develops rapidly. Besides research on improvement ofefficiency further, a lot of work has been done to extend the range of problems handled byplanning algorithms and to improve the quality of plans. The Graphplan planner hasenjoyed considerable success as a planning algorithm for STRIPS domains planningproblems. However, it is argued that this framework is too rigid to capture the full subtletyof many real problems, which leads to no solution found or low-quality solution. In general,the real-world planning problems are complex. If not preprocessed, most are hard to settle.In addition, because of the variety of the planning problems, it is unrealistic to handle all ofthem in a uniform way. Hence, specialized planning algorithms are tailored to differentplanning problems.This paper makes research on a kind of complex planning problems—— flexibleplanning problems. The following original researches are carried out:The paper systematically reviews the history of intelligent planning, thoroughly statesresearch in the Graphplan framework, objectively shows the current state and suggestsareas for future research.The paper applies a novel intelligent planning algorithm. In contrast to the existingmethods, the algorithm expands the flexible planning graph backwards from the goal setand searches a valid plan forwards, perfects the approach of backward flexible mutexinference, and avoids a complicated process of satisfaction degree propagation. Themethod takes into account user’s requirement and taste, strives to improve comprehensivequality of a plan, makes the solution plan more suitable for the needs, and handles theplanning problems much closer to the real world. Therefore, the method has its advantageover previous ones in application.Based on the algorithm, GDFGP(Goal-Directed Flexible Graphplan) planning systemhas been developed. And its availability has been validated by a set of problems from theRescue domain.Because of the dependency of intelligent planning, our research has wide applicationoutlook on robotology, intelligent user interface design, natural language understanding,multi-agent systems etc.更多还原