基于鸽群优化算法的实时避障算法

李霜琳; 何家皓; 敖海跃; 刘燕斌

doi:10.13700/j.bh.1001-5965.2020.0198

基于鸽群优化算法的实时避障算法

doi: 10.13700/j.bh.1001-5965.2020.0198

南京航空航天大学航天学院, 南京 210016

详细信息

作者简介:
李霜琳  女, 硕士研究生。主要研究方向: 导航制导与控制

何家皓  女, 硕士研究生。主要研究方向: 高超声速飞行控制、飞行器复杂建模与控制

敖海跃  男, 本科。主要研究方向: 导航制导与控制

刘燕斌  男, 博士, 副教授, 硕士生导师。主要研究方向: 高超声速飞行控制、飞行器复杂建模与控制

通讯作者:
刘燕斌. E-mail: liuyb@nuaa.edu.cn

中图分类号: TP242.6
计量
- 文章访问数: 1123
- HTML全文浏览量: 59
- PDF下载量: 129
- 被引次数: 0
出版历程
- 收稿日期: 2020-05-20
- 录用日期: 2020-06-18
- 网络出版日期: 2021-02-20

Real-time obstacle avoidance algorithm based on pigeon-inspired optimization

College of Astronautics, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China

More Information

Corresponding author: LIU Yanbin. E-mail: liuyb@nuaa.edu.cn

摘要

摘要:
为保证机器人能安全无碰撞地抵达目标位置，提出一种在改进版圆形扩张（CSE+）法中融合鸽群优化算法的实时避障算法。所提算法引入对障碍物密集程度的判断机制，在障碍分布密集时选择最安全的路径，在障碍物分布稀松的环境中，利用鸽群优化算法在安全范围内寻找下一目标最优位置。此外，还引入了搜索树，可实现死角的检测与避免。仿真结果显示：所提避障算法能提高路径规划的性能，在障碍物分布稀松时效果更加明显，且可实现死角检测并能通过狭长通道。
- 路径规划 /
- 局部路径规划 /
- 鸽群优化算法 /
- 改进版圆形扩张(CSE+)法 /
- 避障
Abstract:
In order to ensure that the mobile robot can reach the target position without collisions, this paper proposes a real-time obstacle avoidance algorithm that integrates the pigeon-inspired optimization into the Circle Sector Expansion plus (CSE+) method. This algorithm includes a judgment mechanism to evaluate the distribution of obstacles. When the obstacles are densely distributed, the safest path will be selected. Otherwise, the pigeon-inspired optimization will be used to find an optimal position as the next target position in the safe range. In addition, a search tree is used to detect and avoid the dead-end situation. The simulation results show that this algorithm can improve the efficiency of path planning, the effect is more obvious when the obstacles are sparsely distributed, the dead-end situation can be detected, and the robot can pass through the narrow and long corridors.
- path planning /
- local path planning /
- pigeon-inspired optimization algorithm /
- Circle Sector Expansion plus (CSE+) method /
- obstacle avoidance

HTML全文

图 1 CSE+法避障原理

Figure 1. Obstacle avoidance principle of CSE+ method

下载: 全尺寸图片幻灯片

图 2 安全范围示意

Figure 2. The graph of current safe area

下载: 全尺寸图片幻灯片

图 3 搜索树返回示意图

Figure 3. Schematic diagram of return of search tree

下载: 全尺寸图片幻灯片

图 4 基于鸽群优化算法的实时避障算法流程图

Figure 4. Flowchart of real-time obstacle avoidance algorithm based on pigeon-inspired optimization

下载: 全尺寸图片幻灯片

图 5 障碍物分布密集时路径

Figure 5. Circumatances when obstacles are densely distributed

下载: 全尺寸图片幻灯片

图 6 障碍物分布疏松时路径

Figure 6. Circumstances when obstacles are loosely distributed

下载: 全尺寸图片幻灯片

图 7 长廊检测

Figure 7. Test in corridor

下载: 全尺寸图片幻灯片

表 1 不同环境下2种算法参数对比

Table 1. Comparison of two methods' parameters in different environments

障碍物分布	算法	路径长度/m	平均转向角/(°)
密集	PIO & CSE+	117.34	40.97
密集	CSE+	125.11	52.59
疏松	PIO & CSE+	95.19	35.22
疏松	CSE+	113.50	61.76

下载: 导出CSV

参考文献(24)

[1]	VILSON G, ANGALID K.Spatial and reactive navigation for an autonomous vehicle in an unknown environment[D].Sweden: Umeå Universitet, 2011.
[2]	RÖNNBÄCK S, WESTERBERG S, PROROK K.CSE+: Path planning amid circles, 2009[C]//The 4th International Conference on Autonomous Robots and Agents.Piscataway: IEEE Press, 2009: 447-452.
[3]	王海群, 王水满, 张怡. 基于激光雷达信息的无人机避障控制研究[J]. 激光杂志, 2019, 40(12): 76-79. https://www.cnki.com.cn/Article/CJFDTOTAL-JGZZ201912017.htm WANG H Q, WANG S M, ZHANG Y. Control of UAV barrier avoidance based on lidar information[J]. Laser Journal, 2019, 40(12): 76-79(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JGZZ201912017.htm
[4]	AZIMIRAD V, SHORAKAEI H. Dual hierarchical genetic-optimal control: A new global optimal path planning method for robots[J]. Journal of Manufacturing Systems, 2014, 33(1): 139-148. doi: 10.1016/j.jmsy.2013.09.006
[5]	MAC T T, COPOT C, TRAN D T, et al. A hierarchical global path planning approach for mobile robots based on multi-objective particle swarm optimization[J]. Applied Soft Computing, 2017, 59: 68-76. doi: 10.1016/j.asoc.2017.05.012
[6]	王雷, 李明. 改进自适应遗传算法在移动机器人路径规划中的应用[J]. 南京理工大学学报(自然科学版), 2017, 41(5): 627-633. https://www.cnki.com.cn/Article/CJFDTOTAL-NJLG201705015.htm WANG L, LI M. Application of improved adaptive genetic algorithm in mobile robot path planning[J]. Journal of Nanjing University of Science and Technology(Natural Sciences), 2017, 41(5): 627-633(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-NJLG201705015.htm
[7]	魏彤, 龙琛. 基于改进遗传算法的移动机器人路径规划[J]. 北京航空航天大学学报, 2020, 46(4): 703-711. doi: 10.13700/j.bh.1001-5965.2019.0298 WEI T, LONG C. Path planning for mobile robot based on improved genetic algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(4): 703-711(in Chinese). doi: 10.13700/j.bh.1001-5965.2019.0298
[8]	王雄奇, 柯艳国, 吴贤斌, 等. 基于虚拟墙的移动机器人路径跟踪与实时避障方法[J]. 机械与电子, 2019, 37(11): 76-80. https://www.cnki.com.cn/Article/CJFDTOTAL-JXYD201911018.htm WANG X Q, KE Y G, WU X B, et al. A virtual wall-based path tracking and obstacle avoidance method for mobile robot[J]. Machinery & Electronics, 2019, 37(11): 76-80(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JXYD201911018.htm
[9]	ROSTAMI S M H, SANGAIAH A K, WANG J, et al. Obstacle avoidance of mobile robots using modified artificial potential field algorithm[J]. EURASIP Journal on Wireless Communications and Networking, 2019, 2019(1): 70. doi: 10.1186/s13638-019-1396-2
[10]	张宁, 李彩虹, 郭娜, 等. 基于CM-Q学习的自主移动机器人局部路径规划[J]. 山东理工大学学报(自然科学版), 2020, 34(4): 37-43. https://www.cnki.com.cn/Article/CJFDTOTAL-SDGC202004007.htm ZHANG N, LI C H, GUO N, et al. Local path planning of autonomous mobile robot based on CM-Q learning[J]. Journal of Shandong University of Technology (Natural Science Edition), 2020, 34(4): 37-43(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-SDGC202004007.htm
[11]	高乐, 马天录, 刘凯, 等. 改进Q-Learning算法在路径规划中的应用[J]. 吉林大学学报(信息科学版), 2018, 36(4): 439-443. https://www.cnki.com.cn/Article/CJFDTOTAL-CCYD201804013.htm GAO L, MA T L, LIU K, et al. Application of improved Q-Learning algorithm in path planning[J]. Journal of Jilin University (Information Science Edition), 2018, 36(4): 439-443(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-CCYD201804013.htm
[12]	LOW E S, ONG P, CHEAH K C. Solving the optimal path planning of a mobile robot using improved Q-learning[J]. Robotics and Autonomous Systems, 2019, 115: 143-161. doi: 10.1016/j.robot.2019.02.013
[13]	魏立新, 吴绍坤, 孙浩, 等. 基于多行为的移动机器人路径规划[J]. 控制与决策, 2019, 34(12): 2721-2726. https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201912030.htm WEI L X, WU S K, SUN H, et al. Mobile robot path planning based on multi-behaviors[J]. Control and Decision, 2019, 34(12): 2721-2726(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201912030.htm
[14]	郭娜, 李彩虹, 王迪, 等. 基于模糊控制的移动机器人局部路径规划[J]. 山东理工大学学报(自然科学版), 2020, 34(4): 24-29. https://www.cnki.com.cn/Article/CJFDTOTAL-SDGC202004005.htm GUO N, LI C H, WANG D, et al. Local path planning of mobile robot based on fuzzy control[J]. Journal of Shandong University of Technology (Natural Science Edition), 2020, 34(4): 24-29(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-SDGC202004005.htm
[15]	BORENSTEIN J, KOREN Y. The vector field histogram-fast obstacle avoidance for mobile robots[J]. IEEE Transactions on Robotics and Automation, 1991, 7(3): 278-288. doi: 10.1109/70.88137
[16]	ULRICH I, BORENSTEIN J.VFH^*: Local obstacle avoidance with look-ahead verification[C]//IEEE International Conference on Robotics and Automation.Piscataway: IEEE Press, 2000: 2505-2511.
[17]	ULRICH I, BORENSTEIN J.VFH⁺: Reliable obstacle avoidance for fast mobile robots[C]//IEEE International Conference on Robotics and Automation.Piscataway: IEEE Press, 1998: 1572-1577.
[18]	江超, 邢科新, 林叶贵, 等. 未知环境下移动机器人静态与动态实时避障方法研究[J]. 高技术通讯, 2019, 29(10): 1012-1020. https://www.cnki.com.cn/Article/CJFDTOTAL-GJSX201910010.htm JIANG C, XING K X, LIN Y G, et al. Research on static and dynamic real-time obstacle avoidance methods for mobile robots in unknown environment[J]. Chinese High Technology Letters, 2019, 29(10): 1012-1020(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-GJSX201910010.htm
[19]	张帅, 李学仁, 张鹏, 等. 基于人机合作的无人机实时航迹规划[J]. 北京航空航天大学学报, 2017, 43(4): 814-822. doi: 10.13700/j.bh.1001-5965.2016.0271 ZHANG S, LI X R, ZHANG P, et al. UAV real-time path planning based on human-machine cooperation[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 43(4): 814-822(in Chinese). doi: 10.13700/j.bh.1001-5965.2016.0271
[20]	RÖNNBÄCK S, BERGLUND T, FREDRIKSSON H, et al.Circle sector expansions for on-line exploration[C]//IEEE International Conference on Robotics and Biomimetics.Piscataway: IEEE Press, 2006: 1227-1232.
[21]	DUAN H B, QIAO P X. Pigeon-inspired optimization: A new swarm intelligence optimizer for air robot path planning[J]. International Journal of Intelligent Computing and Cybernetics, 2014, 7: 24-37. doi: 10.1108/IJICC-02-2014-0005
[22]	CHEN B, LEI H, SHEN H, et al. A hybrid quantum-based PIO algorithm for global numerical optimization[J]. Science China Information Sciences, 2019, 62(7): 33-44. doi: 10.1007/s11432-018-9546-4
[23]	胡耀龙, 冯强, 海星朔, 等. 基于自适应学习策略的改进鸽群优化算法[J]. 北京航空航天大学学报, 2020, 46(12): 2348-2356. doi: 10.13700/j.bh.1001-5965.2019.0603 HU Y L, FENG Q, HAI X S, et al. Improved pigeon-inspired optimization algorithm based on adaptive learningstrategy[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(12): 2348-2356(in Chinese). doi: 10.13700/j.bh.1001-5965.2019.0603
[24]	张亚平, 孙佩华, 李昱辉, 等. 基于改进鸽群优化算法的高超声速飞行器轨迹优化[J]. 飞行力学, 2017, 35(4): 60-64. https://www.cnki.com.cn/Article/CJFDTOTAL-FHLX201704014.htm ZHANG Y P, SUN P H, LI Y H, et al. Hypersonic vehicle trajectory optimization based on improved pigeon-inspired optimization algorithm[J]. Flight Dynamics, 2017, 35(4): 60-64(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-FHLX201704014.htm