不确定环境下基于改进萤火虫算法的地面自主车辆全局路径规划方法

doi:10.3969/j.iss.0372-2012-2014.03.031

电子学报 ›› 2014, Vol. 42 ›› Issue (3): 616-624.DOI: 10.3969/j.iss.0372-2012-2014.03.031

• 科研通信 • 上一篇

不确定环境下基于改进萤火虫算法的地面自主车辆全局路径规划方法

杜鹏桢, 唐振民, 陆建峰, 孙研

南京理工大学计算机科学与工程学院, 江苏南京 210094

收稿日期:2013-08-14 修回日期:2013-10-15 出版日期:2014-03-25
- 作者简介:
- 杜鹏桢 男，1982年11月出生.2005年本科毕业于南京理工大学电子工程与光电技术学院，现为南京理工大学计算机科学与工程学院硕博连读生，从事机器人及智能计算相关研究.E-mail：h.k@foxmail.com
- 基金资助:
- 国家自然科学基金 (No.91220301，No.61371040）; 高等学校学科创新引智计划资助课题 (No.B13022）

Global Path Planning for ALVBased on Improved Glowworm Swarm Optimization Under Uncertain Environment

DU Peng-zhen, TANG Zhen-min, LU Jian-feng, SUN Yan

College of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing, Jiangsu 210094, China

Received:2013-08-14 Revised:2013-10-15 Online:2014-03-25 Published:2014-03-25
- Supported by:
- National Natural Science Foundation of China (No.91220301, No.61371040); Supported by Overseas Expertise Introduction Project for Discipline Innovation (“111Project”) (No.B13022)

摘要/Abstract

摘要： 针对地面自主车辆的特点，提出了一种基于改进萤火虫算法（Glowworm Swarm Optimization，GSO）的路径规划方法.首先利用GSO覆盖多个局部最优解的能力，一次生成多条规划路径；然后提出两种路径切换算法，分别用于调优和脱困.在通过路径交叉点时，调优切换算法对交叉路径进行重新评估并切换到较优路径，最终达到实际行驶路径的最优化.在遇到环境发生改变时，脱困切换算法通过启发式搜索快速切换到适当路径，重用了原搜索结果，避免了二次规划.通过大量的仿真实验及实际试用，证明了所提方法的可行性和有效性.

关键词: 路径规划, 地面自主车辆, 人工萤火虫算法, 二次规划, 路径切换

Abstract: According to the characteristics of autonomous land vehicle,a global path planning method based on improved glowworm swarm optimization(GSO)is proposed.Firstly,more than one path is generated with GSO which covers multiple local optima.Then two path switching algorithms are proposed,of which one aims at optimization and the other aims at rescue.When the cross point is passed through,the optimization switching algorithm revaluates the paths,switches to the optimum path,and ultimately attains optimal actual travel route.When the environment changes,the rescue switching algorithm switches to the appropriate path by heuristic search,which reuses the original search results,avoiding the secondary planning.Many simulation experiments and actual trial show that the proposed method is feasible and effective.

Key words: path planning, autonomous land vehicle(ALV), glowworm swarm optimization(GSO), secondary planning, path switching

中图分类号:

TP242

杜鹏桢, 唐振民, 陆建峰, 等. 不确定环境下基于改进萤火虫算法的地面自主车辆全局路径规划方法[J]. 电子学报, 2014, 42(3): 616-624.

DU Peng-zhen, TANG Zhen-min, LU Jian-feng, et al. Global Path Planning for ALVBased on Improved Glowworm Swarm Optimization Under Uncertain Environment[J]. Acta Electronica Sinica, 2014, 42(3): 616-624.

参考文献

[1] Ge S S, Cui Y J.Dynamic motion planning for mobile robots using potential field method[J].Autonomous Robots, 2002, 13(2):207-222.
[2] Csiszar A, Drust M, Dietz T, et al.Dynamic andInteractive Path Planning and Collision Avoidance for an Industrial Robot Using Artificial Potential Field Based Method[M].Berlin:Springer, 2012.413-421.
[3] Jaradat M A K, Garibeh M H, Feilat E A.Autonomous mobile robot dynamic motion planning using hybrid fuzzy potential field[J].Soft Computing, 2012, 16(1):153-164.
[4] Pan C Z, Lai X Z, Yang S X, et al.An efficient neural network approach to tracking control of an autonomous surface vehicle with unknown dynamics[J].Expert Systems with Applications, 2013, 40(5):1629-1635.
[5] Masoud A A.Managing the dynamics of a harmonic potential field-guided robot in a cluttered environment[J].IEEE Transactions on Industrial Electronics, 2009, 56(2):488-496.
[6] Pal A, Tiwari R, Shukla A.Modified A*Algorithm for Mobile Robot Path Planning[M].Berlin:Springer, 2012.183-193.
[7] Stentz A.Optimal and efficient path planning for partially-known environments[A].Proceedings of the 1994 International Conference on Robotics and Automation[C].San Diego, USA:IEEE Computer Society, 1994.3310-3317.
[8] Ferguson D, Stentz A.The delayed D* algorithm for efficient path replanning[A].Proceedings of the 2005 IEEE International Conference on Robotics and Automation, ICRA 2005[C].Barcelona, Spain:IEEE Press, 2005.2045-2050.
[9] Devaurs D, Siméon T, Cortés Mastral J.Parallelizing RRT on large-scale distributed-memory architectures[J].IEEE Transactions on Robotics and Automation, 2013, 29(2):571-579.
[10] 宋金泽, 戴斌, 单恩忠, 等.一种改进的RRT路径规划算法[J].电子学报, 2010, 38(2A):225-228. SONG Jin-ze, DAI Bin, SHAN En-zhong et al.An improved RRT path planning algorithm[J].Acta Electronica Sinica, 2010, 38(2A):225-228.(in Chinese)
[11] Lee J, Kang B Y, Kim D W.Fast genetic algorithm for robot path planning[J].Electronics Letters, 2013, 49(23):1449-1451.
[12] 李志海, 付宜利.基于遗传算法的仿生双足爬壁机器人越障运动规划[J].机器人, 2012, 34(6):751-757. LI Zhihai, FU Yi-li.Motion planning of a bio-inspired biped wall climbing robot stepping over obstacles based on genetic algorithm[J].ROBOT, 2012, 34(6):751-757.(in Chinese)
[13] Chen X, Kong Y, Fang X, et al.A fast two-stage ACO algorithm for robotic path planning[J].Neural Computing and Applications, 2013, 22(2):313-319.
[14] Zhao J, Fu X.Improvedant colony optimization algorithm and its application on path planning of mobile robot[J].Journal of Computers, 2012, 7(8):2055-2062.
[15] 陈雄, 赵一路, 韩建达.一种改进的机器人路径规划的蚁群算法[J].控制理论与应用, 2010, 27(6):821-825. Chen Xiong, Zhao Yi-lu, Han Jian-da.An improved ant colony optimization algorithm for robotic path planning[J].Control Theory & Applications, 2010, 27(6):821-825.(in Chinese)
[16] 柳长安, 鄢小虎, 刘春阳, 等.基于改进蚁群算法的移动机器人动态路径规划方法[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 Electronica Sinica, 2011, 39(5):1220-1224.(in Chinese)
[17] 徐晓晴, 朱庆保.动态环境下基于多人工鱼群算法和避碰规则库的机器人路径规划[J].电子学报, 2012, 40(8):1694-1700. XUXiao-qing, ZHU Qing-bao.Multi-artificial fish-swarm algorithm and a rule library based dynamic collision avoidance algorithm for robot path planning in a dynamic environment[J].Acta Electronica Sinica, 2012, 40(8):1694-1700.(in Chinese)
[18] Krishnanand K N, Ghose D.Glowworm swarm optimization for simultaneous capture of multiple local optima ofmultimodal functions[J].Swarm Intelligence, 2009, 3(2):87-124.
[19] Wu B, Qian C, Ni W, et al.The improvement of glowworm swarm optimization for continuous optimization problems[J].Expert Systems with Applications, 2012, 39(7):6335-6342.
[20] Krishnanand K, Ghose D.Aglowworm swarm optimization based multi-robot system for signal source localization[J].Design and Control of Intelligent Robotic Systems, 2009:49-68.
[21] Krishnanand K N, Ghose D.Theoretical foundations for rendezvous of glowworm-inspired agent swarms at multiple locations[J].Robotics and Autonomous Systems, 2008, 56(7):549-569.
[22] 周永权, 黄正新, 刘洪霞.求解TSP问题的离散型萤火虫群优化算法[J].电子学报, 2012, 40(6):1164-1170. Zhou Y Q, Huang Z X, Liu H X.Discreteglowworm swarm optimization algorithm for TSP problem[J].Acta Electronica Sinica, 2012, 40(6):1164-1170.(in Chinese)
[23] Hart P E, Nilsson N J, Raphael B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2):100-107.

不确定环境下基于改进萤火虫算法的地面自主车辆全局路径规划方法

Global Path Planning for ALVBased on Improved Glowworm Swarm Optimization Under Uncertain Environment

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	宣志玮, 毛剑琳, 张凯翔. CBS框架下面向复杂地图的低拓展度A*算法[J]. 电子学报, 2022, 50(8): 1943-1950.
[2]	段世红, 何昊, 徐诚, 殷楠, 王然. 未知环境下基于深度序列蒙特卡罗树搜索的信源导航方法[J]. 电子学报, 2022, 50(7): 1744-1752.
[3]	蒋林, 方东君, 周和文, 黄惠保. 基于射线模型的改进全局路径规划算法[J]. 电子学报, 2022, 50(3): 548-556.
[4]	马慧, 汤庸, 何怀文. 主存高效的公交网络路径规划索引[J]. 电子学报, 2021, 49(11): 2273-2278.
[5]	王乐乐, 眭泽智, 蒲志强, 刘振, 易建强. 一种改进RRT的多机器人编队路径规划算法[J]. 电子学报, 2020, 48(11): 2138-2145.
[6]	王秋萍, 王彦军, 戴芳. 多策略集成的樽海鞘群算法的机器人路径规划[J]. 电子学报, 2020, 48(11): 2101-2113.
[7]	杨亮, 付根平, 陈勇. 考虑关节角加速度约束的仿人机器人偏摆力矩控制方法[J]. 电子学报, 2019, 47(2): 475-482.
[8]	许凯波, 鲁海燕, 黄洋, 胡士娟. 基于双层蚁群算法和动态环境的机器人路径规划方法[J]. 电子学报, 2019, 47(10): 2166-2176.
[9]	彭亚丽, 刘侍刚, 孙增国, 洪灵, 曹菡. 迭代二次规划遮挡点恢复[J]. 电子学报, 2018, 46(11): 2733-2737.
[10]	李宝磊, 吕丹桔, 张钦虎, 施心陵, 陈建华, 张榆锋. 基于多元优化算法的路径规划[J]. 电子学报, 2016, 44(9): 2242-2247.
[11]	徐晓晴, 朱庆保. 动态环境下基于多人工鱼群算法和避碰规则库的机器人路径规划[J]. 电子学报, 2012, 40(8): 1694-1700.
[12]	欧庆于, 张焕国, 吴晓平, 李凤华, 罗芳. 基于亚稳态的QDI逻辑随机路径切换方法研究[J]. 电子学报, 2012, 40(10): 1996-2001.
[13]	柳长安;鄢小虎;刘春阳;吴华. 基于改进蚁群算法的移动机器人动态路径规划方法[J]. 电子学报, 2011, 39(5): 1220-1224.
[14]	陈卫东;朱奇光. 基于模糊算法的移动机器人路径规划[J]. 电子学报, 2011, 39(4): 971-974.
[15]	李珺;潘启树;周浦城;洪炳镕. 未知环境下多机器人协作追捕算法[J]. 电子学报, 2011, 39(3): 567-574.