Multi-Robots Global Path Planning Based on PSO Algorithm and Cubic Spline

doi:10.16182/j.issn1004731x.joss.201707002

Abstract

Abstract: There are shortcomings such as premature convergence, high encoding dimension and unsmooth path for particle swarm optimization (PSO) algorithm to solve the robot path planning problem under free space. The particle coding is coordinates of several path nodes in the environment. The number of spline curves and the maximum turnings of path were determined by the number of path nodes. The cubic spline function was used to interpolate on the path of the starting point, path nodes and target point, thus a full path which was formed by connecting all interpolation points was obtained. Simulation results show that compared with the traditional methods, the proposed algorithm can quickly find the optimal path, and can plan the optimal collision free path for multi-robots.

Key words: particle swarm optimization algorithm, cubic spline, multi-robots, path planning

CLC Number:

TP391.9

Qiang Ning, Gao Jie, Kang Fengju. Multi-Robots Global Path Planning Based on PSO Algorithm and Cubic Spline[J]. Journal of System Simulation, 2017, 29(7): 1397-1404.

References

[1] 朱大奇, 颜明重. 移动机器人路径规划技术综述[J]. 控制与决策, 2010, 25(7): 961-967.
(Zhu Da-qi, Yan Ming-zhong.Survey on technology of mobile robot path planning[J]. Control and Decision, 2010, 25(7): 961-967.)
[2] 姚远, 周兴社, 张凯龙, 等. 基于稀疏A*搜索和改进人工势场的无人机动态航迹规划[J]. 控制理论与应用, 2010, 27(7): 953-959.
(Yao Yuan, Zhou Xing-she, Zhang Kai-long, et al.Dynamic trajectory planning for unmanned aerial vehicle based on sparse A* search and improved artificial potential field[J]. Control Theory & Applications, 2010, 27(7): 953-959.)
[3] 王芳, 万磊, 徐玉如, 等. 基于改进人工势场的水下机器人路径规划[J]. 华中科技大学学报(自然科学版), 2011, 39(增2): 184-187.
(Wang Fang, Wan Lei, Xu Yu-ru, et al.Path Planning Base on Improved Artificial Potential Flied for Autonomous Underwater Vehicle[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2011, 39(S2): 184-187.)
[4] Takahashi O, Schilling R J.Motion planning in a plane using generalized Voronoi diagrams[J]. IEEE Trans on Robotics and Automation (S1042-296X), 1989, 5(2): 143-150.
[5] Avneesh S, Erik A, Sean C, et al.Real-time path planning in dynamic virtual environment using multiagent navigation graphs[J]. IEEE Trans on Visualization and Computer Graphics (S1077-2626), 2008, 14(3): 526-538.
[6] Shi C, Wang Y, Yang J.A local obstacle avoidance method for mobile robots in partially known environment[J]. Robotics and Autonomous Systems (S0921-8890), 2010, 58(5): 425-434.
[7] 王雪松, 高阳, 程玉虎, 等. 知识引导遗传算法实现机器人路径规划[J]. 控制与决策, 2009, 24(7): 1043-1049.
(Wang Xue-song, Gao Yang, Cheng Yu-hu, et al.Knowledge-guided genetic algorithm for path planning of robot[J]. Control and Decision, 2009, 24(7): 1043-1049.)
[8] 柳长安, 鄢小虎, 刘春阳, 等. 基于改进蚁群算法的移动机器人动态路径规划方法[J]. 电子学报, 2011, 39(5): 1220-1224.
(Liu Chang-an, Yan Xiao-hu, Liu Chun-yang, et al.Dynamic Path Planning for Mobile Robot Based on Improved Ant Colony Optimization Algorithm[J]. Acta Electronic Sinica, 2011, 39(5): 1220-1224.)
[9] P K Das, H S Behera, B K Panigrahi.Intelligent-based Multi-robot Path Planning Inspired by Improved Classical Q-learning and Improved Particle Swarm Optimization with Perturbed Velocity[J]. Engineering Science and Technology (S2215-0986), 2016, 19(1): 651-669.
[10] Rami Al-Jarrah, Aamir Shahzad, Hubert Roth.Path Planning and Motion Coordination for Multi-Robots System Using Probabilistic Neuro-Fuzzy[J]. IFAC- Papers on Line (S2405-8963), 2015, 48(10): 46-51.
[11] 张亚鸣, 雷小宇, 杨胜跃, 等. 多机器人路径规划研究方法[J]. 计算机应用研究, 2008, 25(9): 2566-2569.
(Zhang Ya-ming, Lei Xiao-yu, Yang Sheng-yue, et al.Path Planning Research for Multi-Robot[J]. Application Research of Computers, 2008, 25(9): 2566-2569.)
[12] 李擎, 徐银梅, 张德政, 等. 基于粒子群算法的移动机器人全局路径规划策略[J]. 北京科技大学学报, 2010, 32(3): 397-402.
(Li Qing, Xu Yin-mei, Zhang De-zheng, et al.Global Path Planning Method for Mobile Robots based on Particle Swarm Optimization Algorithm[J]. Journal of University of Science and Technology Beijing, 2010, 32(3): 397-402.)
[13] 马千知, 雷秀娟. 改进粒子群算法在机器人路径规划中的应用[J]. 计算机工程与应用, 2011, 47(25): 241-244.
(Ma Qian-zhi, Lei Xiu-juan.Application of improved particle swarm optimization algorithm in robotic path planning[J]. Computer Engineering and Applications, 2011, 47(25): 241-244.)
[14] Saska M, Macas M, Preucil L, et al.Robot path planning using particle swarm optimization of Ferguson splines[C]// Proceedings of Emerging Technologies and Factory Automation, Prague, Czech Republic, 2006: 833-839.
[15] 吴宪祥, 郭宝龙, 王娟. 基于粒子群三次样条优化的移动机器人路径规划算法[J]. 机器人, 2009, 31(6): 556-560.
(Wu Xian-xiang, Guo Bao-long, Wang Juan.Mobile Robot Path Planning Algorithm Based on Particle Swarm Optimization of Cubic Splines[J]. Robot, 2009, 31(6): 556-560.)