Web3D山地场景中多智能体mACO路径规划算法

系统仿真学报 ›› 2016, Vol. 28 ›› Issue (10): 2312-2320.

Web3D山地场景中多智能体mACO路径规划算法

闫丰亭, 贾金原

同济大学,上海 201804

收稿日期:2016-05-31 修回日期:2016-07-14 出版日期:2016-10-08 发布日期:2020-08-13
作者简介:闫丰亭(1980-),男,山东,博士生,研究方向为虚拟现实与机器学习;贾金原(1963-),男,内蒙古,博士,教授,研究方向为分布式虚拟现实、Web3D、游戏引擎。
基金资助:
国家自然科学基金(61272270)

Multi-agent Path Planning mACO Algorithm in Web3D Mountain Scene

Yan Fengting, Jia Jinyuan

Tongji University, Shanghai 201804, China

Received:2016-05-31 Revised:2016-07-14 Online:2016-10-08 Published:2020-08-13

摘要/Abstract

摘要： 山地场景数据量大,路径规划算法复杂,难以在网页上精确显示,通常采用的基于等高线的势能路径规划,往往得不到最优路径,且容易被隔断在悬崖下面。为解决以上问题,提出并实现了Web3D上的mACO (mountain ACO)路径规划算法,并在Web3D上实现了基于平面网格的pgACO (planar grid ACO)路径规划算法,以及一个Web3D上的A*路径规划算法。再以典型战斗场景为案例,针对mACO算法、pgACO算法以及A*算法,就实现效果、效率、网页刷新率(FPS)做了对比实验,结果显示,三种算法均可达到实时性,但mACO算法规划的路径更加精确。最后根据规划出来的最优路径,采用leader-follower思想,在Web3D上实现了实时高效的多智能体路径规划方案。

关键词: Web3D山地场景, mACO算法, 平面网格pgACO算法, A*算法, 多智能体路径规划

Abstract: There is amount of data in a mountain scene, and the path planning algorithm in it is very complex, so it is not impossible to be shown detailed in Web. Usually the common potential path planning using contours can not find an optimal path because the path is easily cut under the cliff. To solve the above problems, a mACO (mountain ACO) path planning algorithm was addressed for the Web3D application, a planar grid ACO path planning algorithm and a A* path planning were completed in Web3D environment. Then a typical battle scene case was used for the three kinds of algorithms to be compared in effectiveness, efficiency, and FPS. The result can be seen that all the three kinds of algorithms are real-time, but the mACO algorithm is more accurate than the others. Based on the optimal path and using leader-follower idea, a real-time effective multi-agent path planning is implemented.

Key words: Web3D mountain scene, mACO (mountain ACO) algorithm, planar grid ACO algorithm, A* algorithm, multi-agent path planning

中图分类号:

TP391

闫丰亭, 贾金原. Web3D山地场景中多智能体mACO路径规划算法[J]. 系统仿真学报, 2016, 28(10): 2312-2320.

Yan Fengting, Jia Jinyuan. Multi-agent Path Planning mACO Algorithm in Web3D Mountain Scene[J]. Journal of System Simulation, 2016, 28(10): 2312-2320.

参考文献 16

[1]	Deepika P Vinchurkar, Alpa Reshamwala.Robot Path Planning Using An Ant Colony Optimization Approach: A Survey[J]. International Journal of Advanced Research in Artificial Intelligence (S2165-4069), 2013, 2(3): 65-71.
[2]	Colonia Dorigo M, Maniezzo V. Distributed Optimization by Ant Colonies [EB/OL]. (2010-09-14) [2016-09-12]. 2010-09. ftp://iridia.ulb.ac.be/pub/mdorigo/conference/IC.0ECAL92.pdf.
[3]	Anna Gorbeno, Vladimir Popov.Multi-agent Path Planning[J]. Applied Mathematical Sciences,(S1312-885X), 2012, 6(135): 6733-6737.
[4]	Dorigo M, Maniezzo V, Coloni A. The Ant System: Optimization by a Colony of Cooperating Agents [EB/OL]. (2012-09-20) [2016-09-12]. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=484436.
[5]	Taher Niknam, Babak Amiri.An Efficient Hybrid Approach Based on PSO.ACO and K-means for Cluster Analysis[J]. J. ASC.(S1568-4946), 2010, 10(1): 183-197.
[6]	Crina Groan, Ajith Abraham, Monica Chis.Swarm Intelligence in Data Mining[J]. Studies in Computational Intellgence (SCI)(S1860-949X), 2009, 40(1): 1-20.
[7]	Zhang Weiguo, Lu Tianyu. The Research of Genetic Ant Colony Algorithm and Its Application [C]// The Second SREE Conference on Engineering Modelling and Simulation (CEMS2012), Hong Kong, China. Procedia Engineering, doi:10.1016/j.proeng.2012.04.210 ,Volume 37, 101-106
[8]	Yoshiaki Kuwata, Jonathan P.How. Cooperative Distributed Robust Trajector Optimization Using Receding Horizon MILP[J]. IEEE Transactions on Control Systems Technology.(S1063-6536), 2011, 19(2): 423-431.
[9]	Dorigo M, Gmbardella L M.Ant colony system: A cooperation learning approach to the travelling salesman problem[J]. IEEE Translation on Environment Computation (S1089-778X), 1997, 1(1): 53-66.
[10]	Jiang Hui-Yan, Zong Mao, Liu Xiang-Ying.Research of software prediction model based on ACO-SVM[J]. China Journal of Computers.(S0254-4164), 2013, 34(6): 1148-1154.
[11]	Jose Bento, Nate Derbinky, Charles Math, et al.Proximal Operators for Multi-Agent Path Planning[J]. The Advancement of Artificial Intelligence.(S0738-4602), 2015, (7): 35-47.
[12]	Christopher Wilt, Adi Botea.Spatially Distributed Multiagent Path Planning[C]// Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheulng. Association for the Advancement of Artificial Intelligence, 2014: 332-340.
[13]	Ko-Hsin Cindy Wang, Ad Botea. MAAP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees[J]. Journal of Artificial Intelligence Research.(S0004-3702), 2014, 42(1): 55-90.
[14]	Istvan Nagy.From Exploring to Optimal Path Planning: Considering Error of Navigation in Multi-Agent Mobile Robot Domain[J]. Acta Poytchnica Hungrica (S1785-8860), 2014, 11(6): 39-55.
[15]	Meng Guo, Jana Tumova, Dimos V.Dimarogonas. Cooperative Decentralized Multi-agent Control under Local LTL Tasks and Connectivity Constraints[J]. (S0191-2216), 2015, 27: 33-45.
[16]	Ali Noormohammadi Asi, Mohammad Bagher Mehal, Atena Sajedin.Control of leader-follower formation and path planning of mobile robots using Asexual Reproduction Optmization (ARO)[J]. Applied Soft Computing Archive (S1568-4946), 2014, 14(4): 563-576.