基于PSO和三次样条插值的多机器人全局路径规划

doi:10.16182/j.issn1004731x.joss.201707002

系统仿真学报 ›› 2017, Vol. 29 ›› Issue (7): 1397-1404.doi: 10.16182/j.issn1004731x.joss.201707002

基于PSO和三次样条插值的多机器人全局路径规划

强宁¹, 高洁¹, 康凤举²

1. 陕西师范大学物理学与信息技术学院,西安 710119;
2. 西北工业大学航海学院,西安 710072

收稿日期:2016-07-09 发布日期:2020-06-01
通讯作者: 高洁(1982-),女,陕西西安,博士,研究方向为噪声控制技术。
作者简介:强宁(1981-),男,陕西西安,博士,研究方向为进化计算。
基金资助:
国家自然科学基金(11404205),中央高校基本科研业务费专项资金(GK201703015)

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

Qiang Ning¹, Gao Jie¹, Kang Fengju²

1. School of Physics and Information Technology, Shaanxi Normal University, Xi'an 710119, China;
2. School of Marine Science and Technology, Northwestern Polytechnical University, Xi'an 710072, China

Received:2016-07-09 Published:2020-06-01

摘要/Abstract

摘要： 在自由空间下粒子群算法(Particle Swarm Optimization,PSO)求解机器人路径规划问题时,存在易早熟、编码维度高和路径不平滑等问题,为此提出了一种基于PSO和三次样条插值的路径规划方法。所设计的粒子编码为环境中若干个路径节点的坐标,路径节点的个数决定了样条曲线的个数同时也决定了路径转向的次数。通过3次样条函数对路径的起点、路径节点和终点进行插值,从而得到一条由插值点构成的路径。仿真结果表明,相比传统方法所提出的算法能快速找到平滑的最优路径,并且能为多个机器人规划出最优的无碰路径。

关键词: 粒子群算法, 三次样条, 多机器人, 路径规划

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

中图分类号:

TP391.9

强宁, 高洁, 康凤举. 基于PSO和三次样条插值的多机器人全局路径规划[J]. 系统仿真学报, 2017, 29(7): 1397-1404.

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.

参考文献

[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.)

基于PSO和三次样条插值的多机器人全局路径规划

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

PDF (PC)

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	陆淼嘉, 黄承媛, 滕靖. 基于多智能体的网购生鲜无人车配送调度仿真[J]. 系统仿真学报, 2022, 34(6): 1185-1195.
[2]	张森, 张孟炎, 邵敬平, 普杰信. 基于随机策略搜索的多机三维路径规划方法[J]. 系统仿真学报, 2022, 34(6): 1286-1295.
[3]	蒙盾, 胡卓, 张华军. 基于改进A^*算法的多层邮轮疏散系统仿真[J]. 系统仿真学报, 2022, 34(6): 1375-1382.
[4]	梁江涛, 王慧琴. 基于改进蚁群算法的建筑火灾疏散路径规划研究[J]. 系统仿真学报, 2022, 34(5): 1044-1053.
[5]	邓向阳, 张立民, 方伟, 汤淼. 基于双向汇聚引导蚁群算法的机器人路径规划[J]. 系统仿真学报, 2022, 34(5): 1101-1108.
[6]	马立新, 程颍. 计及可中断负荷的园区综合能源系统优化调度[J]. 系统仿真学报, 2022, 34(4): 817-825.
[7]	张凯庆, 嵇启春. 速度时变的多中心半开放式车辆路径问题研究[J]. 系统仿真学报, 2022, 34(4): 836-846.
[8]	陈魁, 毕利, 王文雅. 柔性作业车间AGV与机器双资源集成调度研究[J]. 系统仿真学报, 2022, 34(3): 461-469.
[9]	李兆强, 张时雨. 基于快速RRT算法的三维路径规划算法研究[J]. 系统仿真学报, 2022, 34(3): 503-511.
[10]	孙晓安, 栾小丽, 刘飞. 基于智能优化灰色模型的电子固废预测[J]. 系统仿真学报, 2022, 34(3): 536-542.
[11]	王启明, 宗高强, 胥津铭. 多段式自动泊车最优路径规划与仿真分析[J]. 系统仿真学报, 2022, 34(2): 385-395.
[12]	王语童, 马世伟, 杨元睿, 陈超宇. 多机器人组合最大覆盖面积寻优及预测方法[J]. 系统仿真学报, 2022, 34(1): 86-92.
[13]	陈志梅, 李敏, 邵雪卷, 赵志诚. 基于改进RRT算法的桥式起重机避障路径规划[J]. 系统仿真学报, 2021, 33(8): 1832-1838.
[14]	魏腾飞, 潘庭龙. 基于改进PSO优化LSTM网络的短期电力负荷预测[J]. 系统仿真学报, 2021, 33(8): 1866-1874.
[15]	牛侃, 李冰, 付强. 基于混沌扰动机制粒子群算法的战场频率分配方法[J]. 系统仿真学报, 2021, 33(8): 1905-1913.