Research on Development and Application of AI Planning Decomposition

doi:10.3778/j.issn.1673-9418.2003059

Abstract

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）, 规划分解, 智能规划, 复杂规划问题, 规划器

LI Li, WANG Dayong. Research on Development and Application of AI Planning Decomposition[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(12): 1995-2003.

李丽，王大勇. 智能规划分解的发展与应用研究[J]. 计算机科学与探索, 2020, 14(12): 1995-2003.

References

[1] Corkhill D D. Hierarchical planning in a distributed environ-ment[C]//Proceedings of the 6th International Joint Conference on Artificial Intelligence, Tokyo, Aug 20-24, 1979. New York: ACM, 1979: 168-175.
[2] Korf R E. Planning as search: a quantitative approach[J]. Arti-ficial Intelligence, 1987, 33(1): 65-88.
[3] Sebastia L, Onaindia E, Marzal E. Decomposition of planning problems[J]. AI Communications, 2006, 19(1): 49-81.
[4] Bibaï J, Savéant P, Schoenauer M, et al. An evolutionary meta-heuristic based on state decomposition for domain-independent satisficing planning[C]//Proceedings of the 20th International Conference on Automated Planning and Scheduling, Toronto, May 12-16, 2010. Menlo Park: AAAI, 2010: 18-25.
[5] Hu G, Miller T, Lipovetzky N. What you get is what you see: decomposing epistemic planning using functional STRIPS[J].?arXiv:1903.11777, 2019.
[6] Fox M, Long D. Hybrid STAN: identifying and managing com-binatorial optimisation sub-problems in planning[C]//Proceed-ings of the 17th International Joint Conference on Artificial Intelligence, Seattle, Aug 4-10, 2001. San Mateo: Morgan Kau-fmann, 2001: 445-450.
[7] Srivastava B. RealPlan: decoupling causal and resource reason-ing in planning[C]//Proceedings of the 17th National Con-ference on Artificial Intelligence & 12th Conference on Innovative Applications of Artificial Intelligence, Austin, Jul 30-Aug 3, 2000. Menlo Park: AAAI, 2000: 812-818.
[8] Chen Y X, Hsu C W, Wah B W. SGPlan: subgoal partition-ing and resolution in planning[C]//Proceedings of the 4th International Planning Competition: International Conference on Automated Planning and Scheduling, Whistler, Jun 3-7, 2004. Menlo Park: AAAI, 2004: 30-32.
[9] Iwen M, Mali A D. Automatic problem decomposition for distributed planning[C]//Proceedings of the 2002 International Conference on Artificial Intelligence, Las Vegas, Jun 24-27, 2002: 411-417.
[10] Yang Q. Intelligent planning: a decomposition and abstraction based approach[M]. Berlin, Heidelberg: Springer, 1997.
[11] Xie G, Pegn J, Zhang X, et al. A dynamic task planning based on task subcontracting and dynamic re-decomposition[C]//Proceedings of the 29th Chinese Control Conference,Beijing, Jul 29-31, 2010. Piscataway: IEEE, 2010: 29-31.
[12] Sacerdoti E D. Planning in a hierarchy of abstraction spaces[J]. Artificial Intelligence, 1974, 5(2): 115-135.
[13] Knoblock C A. Generating abstraction hierarchies: an auto-mated approach to reducing search in planning[M]. Hingham: Kluwer Academic Publishers, 1993.
[14] Bacchus F, Yang Q. Downward refinement and the efficiency of hierarchical problem solving[M]. New York: Elsevier Science Inc., 1994.
[15] Hoffmann J, Porteous J, Sebastia L. Ordered landmarks in planning[J]. Journal of Artificial Intelligence Research, 2004, 22(1): 215-278.
[16] Refanidis I, Vlahavas I. The GRT planning system: back-ward heuristic construction in forward state-space planning[J]. Journal of Artificial Intelligence Research, 2001, 15(1): 115-161.
[17] Li L, Shen X H, Wei Y, et al. Improved AI planner and the application on GUI test case generation of military software[J]. Journal of PLA University of Science and Technology(Natural Science Edition), 2010, 11(3): 267-273.李丽, 沈湘衡, 魏颖, 等. 一种改进的规划器算法在军用软件GUI测试用例自动生成中的应用[J]. 解放军理工大学学报(自然科学版), 2010, 11(3): 267-273.
[18] Barry J L, Kaelbling L P, Lozano-Pérez P. DetH*: approxi-mate hierarchical solution of large Markov decision pro-cesses[C]//Proceedings of the 22nd International Joint Con-ference on Artificial Intelligence, Barcelona, Jul 16-22, 2011. Menlo Park: AAAI, 2011: 1928-1935.
[19] Bai A J, Wu F, Chen X P. Online planning for large MDPs with MAXQ decomposition[C]//Proceedings of the 11th Inter-national Conference on Autonomous Agents and Multiagent Systems, Valencia, Jun 4-8, 2012. New York: ACM, 2012: 1215-1216.
[20] Siddiqui F H, Haslum P. Plan quality optimisation via block decomposition[C]//Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, Aug 3-9, 2013. Menlo Park: AAAI, 2013: 2387-2393.
[21] Gopalan N, des Jardins M, Littman M L, et al. Planning with abstract Markov decision processes[C]//Proceedings of the 27th International Conference on Automated Planning and Scheduling, Pittsburgh, Jun 18-23, 2017. Menlo Park:AAAI, 2017: 480-488.
[22] Schillinger P, Bürger M, Dimarogonas D V. Decomposition of finite LTL specifications for efficient multi-agent planning[C]//Proceedings of the 13th International Symposium on Distributed Autonomous Robotic Systems, London, Nov 7-9, 2016. Berlin, Heidelberg: Springer, 2018: 253-267.
[23] Milani A, Niyogi R, Biondi G. Neural network based app-roach for learning planning action models[C]//LNCS 11624: Proceedings of the 19th International Conference on Com-putational Science and Its Applications, Saint Petersburg, Jul 1-4, 2019. Berlin, Heidelberg: Springer, 2019: 526-537.
[24] Lai Z F, Jiang Y F. Learning action model in AI planning based on genetic algorithm[J]. Chinese Journal of Computers, 2007, 30(6): 945-953.赖志锋, 姜云飞. 智能规划中基于遗传算法的动作模型学习[J]. 计算机学报, 2007, 30(6): 945-953.
[25] Leonetti M, Iocchi L, Stone P. A synthesis of automated plann-ing and reinforcement learning for efficient, robust decision[J]. Artificial Intelligence, 2016, 241: 103-130.
[26] Zheng X H, Sun X Q, Lv J X, et al. Action recognition based on deep learning and artificial intelligence planning[J]. Acta Electronica Sinica, 2019, 47(8): 1661-1668.郑兴华, 孙喜庆, 吕嘉欣, 等. 基于深度学习和智能规划的行为识别[J]. 电子学报, 2019, 47(8): 1661-1668.
[27] Lv S, Liu L, Shi L, et al. Artificial intelligence planning methods based on automated reasoning techniques[J]. Journal of Software, 2009, 20(5): 1226-1240.吕帅, 刘磊, 石莲, 等. 基于自动推理技术的智能规划方法[J]. 软件学报, 2009, 20(5): 1226-1240.