进化行为树方法研究综述

doi:10.16182/j.issn1004731x.joss.21-FZ0753

摘要/Abstract

摘要： 进化行为树方法是一种利用进化算法自主生成和优化行为树模型的智能体行为建模方法。从介绍行为树、进化算法相关背景知识入手,阐述了基于遗传编程、语法演化、混合算法三类进化行为树算法以及相应改进算法,分析比较不同算法的优劣;梳理总结了进化行为树方法在作战仿真、游戏人工智能、机器人等领域的具体应用;从搜索能力、泛化能力、行为树优化、多智能体应用方面提出并探讨了未来的发展趋势。

关键词: 进化行为树, 行为树, 遗传编程, 语法演化, 混合算法

Abstract: Evolutionary behavior tree method is an agent behavior modeling method which uses evolutionary algorithm to generate and optimize behavior tree model. Based on the background knowledge of behavior tree and evolutionary algorithm, three kinds of evolutionary behavior tree algorithms based on genetic programming, grammar evolution and hybrid algorithm as well as corresponding improved algorithms are described, and the advantages and disadvantages of different algorithms are analyzed and compared. The specific applications of evolutionary behavior tree in combat simulation, game artificial intelligence, robotics and other fields are summarized. The future development trends of evolutionary behavior tree are proposed and discussed from the perspectives of search ability, generalization ability, behavior tree optimization and multi-agent application.

Key words: evolutionary behavior tree, behavior tree, genetic programming, grammar evolution, hybrid algorithm

中图分类号:

TP391.9

杨杰, 张琪, 曾俊杰, 尹全军. 进化行为树方法研究综述[J]. 系统仿真学报, 2021, 33(10): 2315-2322.

Yang Jie, Zhang Qi, Zeng Junjie, Yin Quanjun. Survey of Evolutionary Behavior Tree Algorithm[J]. Journal of System Simulation, 2021, 33(10): 2315-2322.

参考文献

[1] Iovino M, Scukins E, Styrud J, et al.A Survey of Behavior Trees in Robotics and AI[J]. arXiv preprint arXiv:2005.05842, 2020.
[2] Sekhavat Y A.Behavior Trees for Computer Games[J]. International Journal on Artificial Intelligence Tools (S0218-2130), 2017, 26(2): 1730001.
[3] Zhu X.Behavior Tree Design of Intelligent Behavior of Non-player Character (NPC) based on Unity3d[J]. Journal of Intelligent & Fuzzy Systems (S1064-1246), 2019, 37(5): 6071-6079.
[4] 陈妙云, 王雷, 丁治强. 基于DP-SAMQ行为树的智能体决策模型研究[J]. 计算机仿真, 2021, 38(2): 301-307.
Chen Miaoyun, Wang Lei, Ding Zhiqiang.Research on Agent Decision Model based on DP_SAMQ Behavior Tree[J].Computer Simulation, 2021, 38(2): 301-307.
[5] Palma R, Sánchez-Ruiz A A, Gómez-Martín M A, et al. Combining Expert Knowledge and Learning from Demonstration in real-time Strategy Games[C]// International Conference on Case-Based Reasoning. Berlin, Heidelberg: Springer, 2011: 181-195.
[6] Sagredo-Olivenza I, Gómez-Martín P P, Gómez-Martín M A, et al. Trained Behavior Trees: Programming by Demonstration to Support AI Game Designers[J]. IEEE Transactions on Games (S2475-1502), 2017, 11(1): 5-14.
[7] Buche C, Even C, Soler J.Orion: A Generic Model and Tool for Data Mining[M]. Transactions on Computational Science XXXVI. Berlin, Heidelberg: Springer, 2020: 1-25.
[8] French K, Wu S, Pan T, et al.Learning Behavior Trees from Demonstration[C]// 2019 International Conference on Robotics and Automation (ICRA). Montreal, Canada: IEEE, 2019: 7791-7797.
[9] Colledanchise M, Ögren P.Behavior Trees in Robotics and AI: An introduction[M]. Los Angeles: CRC Press, 2018.
[10] Yu X, Gen M.Introduction to Evolutionary Algorithms[M]. London: Springer Science & Business Media, 2010.
[11] Banzhaf W, Nordin P, Keller R E, et al.Genetic Programming: an Introduction[M]. San Francisco: Morgan Kaufmann Publishers, 1998.
[12] O’Neill M, Ryan C. Grammatical Evolution[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 2001, 5(4): 349-358.
[13] Tsao Y C, Hung C H, Vu T L. Hybrid Heuristics for Marker Planning in the Apparel Industry[EJ/OL]. Arabian Journal for Science and Engineering (S2193-567X), 2021, https://schlr.cnki.net/zn/Detail/ index/SSJDLAST/SSJD7C082C0F01D88E9AAA202FC339D52729.
[14] Wang S T, Li M H, Lien C C.Analysis of the Optimal Application of Blockchain-Based Smart Lockers in the Logistics Industry Based on FFD-SAGA and Grey Decision-Making[J]. Symmetry (S2073-8994), 2021, 13(2): 329.
[15] Jakus D, Čađenović R, Vasilj J, et al.Optimal Reconfiguration of Distribution Networks using Hybrid Heuristic-Genetic Algorithm[J]. Energies (S1996-1073), 2020, 13(7): 1544.
[16] Shang L, Shang Y, Hu L, et al.Performance of Genetic Algorithms with Different Selection Operators for Solving Short-term Optimized Reservoir Scheduling Problem[J]. Soft Computing (S1432-7643), 2020, 24(9): 6771-6785.
[17] 易欣, 郭武士, 赵丽. 利用自适应选择算子结合遗传算法的机器人路径规划方法[J]. 计算机应用研究, 2020, 37(6): 1745-1749.
Yi Xin, Guo Wushi, Zhao Li.Robot Path Planning Method based on Adaptive Selection Operator and Genetic Algorithm[J]. Computer Application Research, 2020, 37(6): 1745-1749.
[18] Estgren M, Jansson E S V. Behaviour Tree Evolution by Genetic Programming[R]. Technical report, Linköping University, 2017.
[19] Paduraru C, Paduraru M.Automatic Difficulty Management and Testing in Games using a Framework based on Behavior Trees and Genetic Algorithms[C]// 2019 24th International Conference on Engineering of Complex Computer Systems (ICECCS). Guangzhou, China: IEEE, 2019: 170-179.
[20] Oakes B.Practical and Theoretical Issues of Evolving Behaviour Trees for a Turn-based Game[D]. McGill, Canada: McGill University, 2013.
[21] Hoff J W, Christensen H J.Evolving Behaviour Trees:-Automatic Generation of AI Opponents for Real-Time Strategy Games[D]. Trondheim, Norway: NTNU, 2016.
[22] Hogg E, Hauert S, Harvey D, et al.Evolving Behaviour Trees for Supervisory Control of Robot Swarms[J]. Artificial Life and Robotics (S1433-5298), 2020, 25(4): 569-577.
[23] Jones S, Studley M, Hauert S, et al.Evolving Behaviour Trees for Swarm Robotics[M]. Distributed Autonomous Robotic Systems. Cham: Springer, 2018: 487-501.
[24] Scheper K Y W, Tijmons S, de Visser C C, et al. Behavior Trees for Evolutionary Robotics[J]. Artificial Life (S1064-5462), 2016, 22(1): 23-48.
[25] Masek M, Lam C P, Kelly L, et al.A Genetic Programming Framework for Novel Behaviour Discovery in Air Combat Scenarios[C]// Data and Decision Sciences in Action 2: ASOR/DORS Conference 2018. Germany: Springer, 2021: 263-277.
[26] Lim C U, Baumgarten R, Colton S.Evolving Behaviour Trees for the Commercial Game DEFCON[C]// European Conference on the Applications of Evolutionary Computation. Berlin, Heidelberg: Springer, 2010: 100-110.
[27] McClarron P, Ollington R, Lewis I. Effect of constraints on evolving behavior trees for game AI[C]//International Conference on Computer Games, Multimedia & Allied Technology (CGAT). Proceedings. Global Science and Technology Forum, 2016: 1-6.
[28] Zhang Q, Xu K, Jiao P, et al.Behavior Modeling for Autonomous Agents Based on Modified Evolving Behavior Trees[C]// 2018 IEEE 7th Data Driven Control and Learning Systems Conference (DDCLS). USA: IEEE, 2018: 1140-1145.
[29] Zhang Q, Yao J, Yin Q, et al.Learning Behavior Trees for Autonomous Agents with Hybrid Constraints Evolution[J]. Applied Sciences (S2076-3417), 2018, 8(7): 1077.
[30] Iovino M, Styrud J, Falco P, et al.Learning Behavior Trees with Genetic Programming in Unpredictable Environments[J]. arXiv preprint arXiv: 2011.03252, 2020.
[31] de Freitas J M, de Souza F R, Bernardino H S. Evolving Controllers for Mario AI Using Grammar-based Genetic Programming[C]// 2018 IEEE Congress on Evolutionary Computation (CEC). USA: IEEE, 2018: 1-8.
[32] Yao J, Huang Q, Wang W.Adaptive Human Behavior Modeling for Air Combat Simulation[C]// 2015 IEEE/ACM 19th International Symposium on Distributed Simulation and Real Time Applications (DS-RT). USA: IEEE, 2015: 100-103.
[33] Yao J, Wang W, Li Z, et al.Tactics Exploration Framework based on Genetic Programming[J]. International Journal of Computational Intelligence Systems (S1875-6891), 2017, 10(1): 804-814.
[34] Hallawa A, Schug S, Iacca G, et al.Evolving Instinctive Behaviour in Resource-Constrained Autonomous Agents Using Grammatical Evolution[C]// International Conference on the Applications of Evolutionary Computation (Part of EvoStar). Cham: Springer, 2020: 369-383.
[35] Perez D, Nicolau M, O’Neill M, et al. Evolving Behaviour Trees for the Mario AI Competition using Grammatical Evolution[C]// European Conference on the Applications of Evolutionary Computation. Berlin, Heidelberg: Springer, 2011: 123-132.
[36] Nicolau M, Perez-Liebana D, O’Neill M, et al. Evolutionary Behavior Tree Approaches for Navigating Platform Games[J]. IEEE Transactions on Computational Intelligence and AI in Games (S1943-068X), 2016, 9(3): 227-238.
[37] 姚剑. 面向装备效能仿真的战术探索方法研究[D]. 长沙: 国防科技大学, 2017.
Yao Jian.Research on Tactics Exploration Method for Equipment Effectiveness Simulation[D]. Changsha: National University of Defense Technology, 2017
[38] Neupane A.Emergence of Collective Behaviors in Hub-Based Colonies Using Grammatical Evolution and Behavior Trees[D]. Provo: Brigham Young University, 2019.
[39] Neupane A, Goodrich M.Learning Swarm Behaviors using Grammatical Evolution and Behavior Trees[C]// Twenty-Eighth International Joint Conference on Artificial Intelligence IJCAI-19. Macao, China: IJCAI, 2019: 513-520.
[40] Colledanchise M, Parasuraman R, Ögren P.Learning of Behavior Trees for Autonomous Agents[J]. IEEE Transactions on Games (S2475-1502), 2018, 11(2): 183-189.
[41] Styrud J, Iovino M, Norrlöf M, et al.Combining Planning and Learning of Behavior Trees for Robotic Assembly[J]. arXiv preprint arXiv:2103.09036, 2021.
[42] Gaudl S E. A Genetic Programming Framework for 2D Platform AI[J]. arXiv preprint arXiv:1803.01648, 2018.
[43] Berthling-Hansen G, Morch E, Løvlid R A, et al.Automating Behaviour Tree Generation for Simulating Troop Movements (Poster)[C]// 2018 IEEE Conference on Cognitive and Computational Aspects of Situation Management (CogSIMA). USA: IEEE, 2018: 147-153.
[44] 杨贵军, 孟杰, 王双喜. 基于赤池信息准则的分类回归决策树剪枝算法[J]. 计算机应用, 2014(增2): 147-150.
Yang Guijun, Meng Jie, Wang Shuangxi.Pruning Algorithm of Classificaiton and Regression Decision Tree based on Akaike Information Criteria[J]. Computer Application, 2014(S2): 147-150.