Journal of Frontiers of Computer Science and Technology ›› 2020, Vol. 14 ›› Issue (12): 1995-2003.DOI: 10.3778/j.issn.1673-9418.2003059

Previous Articles     Next Articles

Research on Development and Application of AI Planning Decomposition

LI Li, WANG Dayong   

  1. College of Innovation and Entrepreneurship, Liaoning University, Shenyang 110036, China
  • Online:2020-12-01 Published:2020-12-11

智能规划分解的发展与应用研究

李丽王大勇   

  1. 辽宁大学 创新创业学院,沈阳 110036

Abstract:

AI (artificial intelligence) planning is an important branch of artificial intelligence. Planning decomposition is an important topic of intelligent planning research, which plays a key role in improving planning speed and reducing the scale of planning expansion. The decomposition algorithm in intelligent planning is studied extensively and deeply, and the development history is introduced comprehensively. This paper expounds and analyzes the general forms of planning decomposition, and classifies the planning decomposition from various situations, in which key methods and popular applications of planning decomposition are mainly introduced. The main contents and advantages of the decomposition method are introduced from the aspects of traditional methods, abstraction levels, constraint satisfaction problems, sub-objective ordering, etc. Application areas include improvements in planning algorithms, multi-agent systems, software test-case generation, large Markov decision processes, etc. This paper summarizes the problems and deficiencies of the existing planning decomposition, and analyzes the future direction.

Key words: artificial intelligence (AI), planning decomposition, AI planning, complex planning problem, planner

摘要:

智能规划是人工智能的一个重要分支。规划分解是智能规划研究的一个不可或缺的组成部分,为提升规划速度,缩小规划扩张规模起到了关键的作用。对智能规划中分解算法进行了广泛而深入的研究,较为全面地介绍了规划分解的发展历程。阐述和分析了规划分解问题的一般形式,并以多种角度对规划分解进行了分类,着重介绍了规划分解的一些关键技术和热门应用。从传统方法、抽象层次、约束可满足、子目标排序等方面分别介绍了所采用分解方法的主要内容和优势。应用领域包括规划算法的改进、多智能体系统、软件测试用例生成、大型马尔可夫决策过程的求解等。对现有规划分解存在的问题和不足进行了归纳总结,并分析了未来的发展方向。

关键词: 人工智能(AI), 规划分解, 智能规划, 复杂规划问题, 规划器