-
摘要:
为更好地解决移动机器人路径规划问题, 改进蝙蝠算法的寻优性能, 拓展其应用领域, 提出了一种具有反向学习和正切随机探索机制的蝙蝠算法. 在全局搜索阶段的位置更新中引入动态扰动系数, 提高算法全局搜索能力; 在局部搜索阶段, 融入正切随机探索机制, 增强算法局部寻优的策略性, 避免算法陷入局部极值. 同时, 加入反向学习选择策略, 进一步平衡蝙蝠种群多样性和算法局部开采能力, 提高算法的收敛精度. 然后, 把改进算法与三次样条插值方法相结合去求解机器人全局路径规划问题, 定义了基于路径结点的编码方式, 构造了绕避障碍求解最短路径的方法和适应度函数. 最后, 在简单和复杂障碍环境下分别对单机器人和多机器人系统进行了路径规划对比实验. 实验结果表明, 改进后算法无论在最优解还是平均解方面都要优于其他几种对比算法, 对于求解机器人全局路径规划问题具有较好的可行性和有效性.
Abstract:In order to better solve the problem of mobile robot path planning, improve the optimization performance of bat algorithm and expand its application field, a bat algorithm with reverse learning and tangent random exploration mechanism is proposed. The dynamic perturbation coefficient is introduced into the position update in the global search stage to improve the global search ability of the algorithm. In the local search phase, the tangent random exploration mechanism is incorporated to enhance the strategy of local optimization and avoid the algorithm falling into local extremum. At the same time, the reverse learning selection strategy is added to further balance the diversity of bat population and local mining ability of the algorithm, and improve the convergence accuracy of the algorithm. Then, the improved algorithm and cubic spline interpolation method are combined to solve the robot global path planning problem, the coding method based on path node is defined, the method and the fitness function for solving the shortest path without collision with obstacles are constructed. Finally, the path planning experiments of single robot and multi-robot system are carried out in simple and complex obstacle environment. The experimental results show that the improved algorithm is superior to other comparison algorithms in terms of the optimal solution and the average solution, which is feasible and effective for solving the robot global path planning problem.
-
图 1 简单环境下4种算法路径规划对比图
Fig. 1 Comparison of four algorithm path planning in a simple environment
图 2 简单环境下4种算法迭代曲线对比图
Fig. 2 Comparison of four algorithm iteration curves in a simple environment
图 3 复杂环境下4种算法路径规划对比图
Fig. 3 Comparison of four algorithm path planning in a complex environment
图 4 复杂环境下4种算法迭代曲线对比图
Fig. 4 Comparison of four algorithm iteration curves in a complex environment
图 11 复杂环境下UGBA算法所规划路径
Fig. 11 Planning path of UGBA algorithm in a complex environment
图 12 复杂环境下PTRBA算法所规划路径
Fig. 12 Planning path of PTRBA algorithm in a complex environment
表 1 简单环境下4种算法所求路径长度比较
Table 1 Comparison of path lengths obtained by four algorithms in a simple environment
算法 最优解 最差解 平均解 PSO 9.0853 9.8596 9.4564 BA 10.9109 13.4622 11.8820 UGBA 9.0346 11.8220 10.0908 PTRBA 8.9638 9.0151 8.9821 
下载: 导出CSV
表 2 复杂环境下4种算法所求路径长度比较
Table 2 Comparison of path length obtained by four algorithms in a complex environment
算法 最优解 最差解 平均解 PSO 9.4117 11.0475 10.1180 BA 10.5201 15.3563 12.3124 UGBA 9.4695 13.9027 11.1290 PTRBA 8.8452 9.8183 9.1892
下载: 导出CSV
表 3 简单环境下4种算法所求路径比较
Table 3 Comparison of path lengths obtained by four algorithms in a simple environment
算法 机器人1平均解 机器人2平均解 机器人3平均解 总路径最优解 总路径最差解 总路径平均解 PSO 10.1045 10.4892 11.3857 31.2132 32.6915 31.9794 BA 11.3361 12.4762 12.7646 34.6364 39.3087 36.5770 UGBA 10.9146 11.2058 11.8302 32.6335 35.1046 33.9507 PTRBA 8.9105 9.7747 10.8018 28.4527 29.8305 29.4870
下载: 导出CSV
表 4 复杂环境下4种算法所求路径比较
Table 4 Comparison of path lengths obtained by four algorithms in a complex environment
算法 机器人1平均解 机器人2平均解 机器人3平均解 总路径最优解 总路径最差解 总路径平均解 PSO 10.1527 10.7141 11.3416 30.8667 33.3565 32.2085 BA 11.6525 11.6937 13.2311 35.3250 37.7116 36.5773 UGBA 9.7856 11.8275 12.0380 32.7774 35.0416 33.6512 PTRBA 9.2125 9.6017 10.5695 29.2493 29.7060 29.3837
下载: 导出CSV
-
[1] 张立建, 胡瑞钦, 易旺民. 基于六维力传感器的工业机器人末端负载受力感知研究. 自动化学报, 2017, 43(3): 439-447 doi: 10.16383/j.aas.2017.c150753Zhang Li-Jian, Hu Rui-Qin, Yi Wang-Min. Research on force sensing for the end-load of industrial robot based on a 6-axis force/torque sensor. Acta Automatica Sinica, 2017, 43(3): 439-447 doi: 10.16383/j.aas.2017.c150753 [2] 杜义浩, 邱石, 谢平, 郭子晖, 吴晓光, 李小俚. 下肢康复机器人的自适应人机交互控制策略. 自动化学报, 2018, 44(4): 743-750 doi: 10.16383/j.aas.2017.c160128Du Yi-Hao, Qiu Shi, Xie Ping, Guo Zi-Hui, Wu Xiao-Guang, Li Xiao-Li. RAdaptive interaction control for lower limb rehabilitation robots. Acta Automatica Sinica, 2018, 44(4): 743-750 doi: 10.16383/j.aas.2017.c160128 [3] 白天翔, 王帅, 沈震, 曹东璞, 郑南宁, 王飞跃. 平行机器人与平行无人系统: 框架、结构、过程、平台及其应用. 自动化学报, 2017, 43(2): 161-175 doi: 10.16383/j.aas.2017.y000002Bai Tian-Xiang, Wang Shuai, Shen Zhen, Cao Dong-Pu, Zheng Nan-Ning, Wang Fei-Yue. Parallel robotics and parallel unmanned systems: Framework, structure, process, platform and applications. Acta Automatica Sinica, 2017, 43(2): 161-175 doi: 10.16383/j.aas.2017.y000002 [4] Toan T Q, Sorokin A A. Trang V T H. Using modification of visibility-graph in solving the problem of finding shortest path for robot. In: Proceedings of the 2017 IEEE International Siberian Conference on Control and Communications. Astana, Kazakhstan: IEEE, 2017. 1-6 [5] Conn R A, Kam M. Robot motion planning on dimensional star worlds among moving obstacles. IEEE Transactions on Robotics and Automation, 1998, 14(2): 320-325 doi: 10.1109/70.681250 [6] 徐飞. 基于改进人工势场法的机器人避障及路径规划研究. 计算机科学, 2016, 42(12): 293-296 doi: 10.11896/j.issn.1002-137X.2016.12.054Xu Fei. Research on robot obstacle avoidance and path planning based on improved artificial potential field method. Computer Science, 2016, 42(12): 293-296 doi: 10.11896/j.issn.1002-137X.2016.12.054 [7] 张继文, 刘莉, 陈恳. 面向全方位双足步行跟随的路径规划. 自动化学报, 2016, 42(2): 189-201 doi: 10.16383/j.aas.2016.c150432Zhang Ji-Wen, Liu Li, Chen Ken. Omni-directional bipedal walking path planning. Acta Automatica Sinica, 2016, 42(2): 189-201 doi: 10.16383/j.aas.2016.c150432 [8] Pfeiffer M, Schaeuble M, Nieto J, Siegwart R, Cadena C. From perception to decision: A data-driven approach to end-to-end motion planning for autonomous ground robots. In: Proceedings of the 2016 IEEE International Conference on Robotics and Automation. Stockholm, Sweden: IEEE, 2016, 485-501 [9] 张福海, 李宁, 袁儒鹏, 付宜利. 基于强化学习的机器人路径规划算法. 华中科技大学学报(自然科学版), 22018, 46(12): 65-70 https://www.cnki.com.cn/Article/CJFDTOTAL-HZLG201812012.htmZhang Fu-Hai, Li Ning, Yuan Ru-Peng, Fu Yi-Li. Robot path planning algorithm based on reinforcement learning. Journal of Huazhong University of Science and Technology (National Science Edition), 2018, 46(12): 65-70 https://www.cnki.com.cn/Article/CJFDTOTAL-HZLG201812012.htm [10] 王晓燕, 杨乐, 张宇, 孟帅. 基于改进势场蚁群算法的机器人路径规划. 控制与决策, 2018, 33(10): 1775-1781 https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201810006.htmWang Xiao-Yan, Yang Le, Zhang Yu, Meng Shuai. Robot path planning based on improved potential field ant colony algorithm. Control and Decision-Making, 2018, 33(10): 1775-1781 https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201810006.htm [11] 黄宜庆, 彭凯, 袁梦茹. 基于多策略混合人工鱼群算法的移动机器人路径规划. 信息与控制, 2017, 46(3): 283-288 https://www.cnki.com.cn/Article/CJFDTOTAL-XXYK201703005.htmHuang Yi-Qing, Peng Kai, Yuan Meng-Ru. Path planning of mobile robot based on multi-strategy hybrid artificial fish swarm algorithm. Information and Control, 2017, 46(3): 283-288 https://www.cnki.com.cn/Article/CJFDTOTAL-XXYK201703005.htm [12] Sariff N B, Buniyamin N. Comparative study of genetic algorithm and ant colony optimization algorithm performances for robot path planning in global static environments of different complexities. In: Proceedings of the 2016 IEEE International Symposium on Computational Intelligence in Robotics and Automation. Singapore, Singapore: IEEE, 2016. 132-137 [13] Lamini C, Benhlima S, Elbekri A. Genetic algorithm based approach for autonomous mobile robot path planning. Procedia Computer Science, 2018, 127(2): 180-189 https://www.sciencedirect.com/science/article/pii/S187705091830125X [14] Das P K, Behera H S, Panigrahi B K. A hybridization of an improved particle swarm optimization and gravitational search algorithm for multi-robot path planning. Swarm and Evolutionary Computation, 2016, 28(1): 14-28 http://www.sciencedirect.com/science/article/pii/S2210650215001005 [15] Das P K, Behera H S, Panigrahi B K. Intelligent-based multi-robot path planning inspired by improved classical Q-learning and improved particle swarm optimization with perturbed velocity. Engineering Science and Technology, an International Journal, 2016, 19(3): 651-669 http://www.sciencedirect.com/science/article/pii/S2215098615001548 [16] Yang X S. A new metaheuristic bat-Inspired algorithm. Computer Knowledge and Technology, 2010, 284(1): 65-74 http://www.scienceopen.com/document/vid/851e27f2-134f-4d9b-b08e-38bfb7af65ce [17] Alsariera Y A, Majid M A, Zamli K Z. Adopting the bat-inspired algorithm for interaction testing. In: Proceedings of the 8th Edition of Annual Software Testing Conference (SOFTEC Asia 2015). Kuala Lumpur, Malaysia, 2015. 1-4 [18] Kashi S, Minuchehr A, Poursalehi N, Zolfaghari A. Bat algorithm for the fuel arrangement optimization of reactor core. Annals of Nuclear Energy, 2017, 64(2): 144-151 http://www.sciencedirect.com/science/article/pii/S0306454913005148 [19] Chakri A, Khelif R, Benouaret M, Yang X S. New directional bat algorithm for continuous optimization problems. Expert Systems with Applications, 2017, 69(1): 159-175 http://www.sciencedirect.com/science/article/pii/S0957417416305905 [20] 戚远航, 蔡延光, 蔡颢, 黄何列. 带时间窗的车辆路径问题的离散蝙蝠算法. 电子学报, 2018, 46(3): 672-679 doi: 10.3969/j.issn.0372-2112.2018.03.024Qi Yuan-Hang, Cai Yan-Guang, Cai Hao, Huang He-Lie. Discrete bat algorithm for vehicle routing problem with time window. Acta Electronica Sinica, 2018, 46(3): 672-679 doi: 10.3969/j.issn.0372-2112.2018.03.024 [21] Grewal N S, Rattan M, Patterh M S. A linear antenna array failure correction using improved bat algorithm. International Journal of RF and Microwave Computer-aided Engineering, 2017, 27(7): e21119 doi: 10.1002/mmce.21119 [22] Kao C, Tang H C. Symmetry property of multiplicative congruential random number generator in chi-square test. International Journal of Computer Mathematics, 2007, 55(1-2): 113-118 doi: 10.1080/00207169508804367 [23] Tizhoosh H. Opposition-based learning: A new scheme for machine intelligence. In: Proceedings of the 2015 International Conference on Intelligent Agent, Web Technologies and Internet Commerce. Vienna, Austria: IEEE, 2005. 695- 701 [24] 李煜, 裴宇航, 刘景森. 融合均匀变异与高斯变异的蝙蝠优化算法. 控制与决策, 2017, 32(10): 1775-1781 https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201710006.htmLi Yu, Pei Yu-Hang, Liu Jing-Sen. A bat optimal algorithm combined uniform mutation with Gaussian mutation. Control and Decision Making, 2017, 32(10): 1775-1781 https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201710006.htm [25] 强宁, 高洁, 康凤举. 基于PSO和三次样条插值的多机器人全局路径规划. 系统仿真学报, 2017, 29(7): 1397-1404 https://www.cnki.com.cn/Article/CJFDTOTAL-XTFZ201707002.htmQiang Ning, Gao Jie, Kang Feng-Ju. Global path planning for multi-robot based on PSO and cubic spline interpolation. Journal of System Simulation, 2017, 29(7): 1397-1404 https://www.cnki.com.cn/Article/CJFDTOTAL-XTFZ201707002.htm [26] 叶炜垚, 王春香, 杨明. 基于虚拟障碍物的移动机器人路径规划方法. 机器人, 2011, 33(3): 273-278 https://www.cnki.com.cn/Article/CJFDTOTAL-JQRR201103005.htmYe Wei-Yao, Wang Chun-Xiang, Yang Ming. Path planning method for mobile robot based on virtual obstacle. Robot, 2011, 33(3): 273-278 https://www.cnki.com.cn/Article/CJFDTOTAL-JQRR201103005.htm -
点击查看大图
计量
- 文章访问数: 1105
- HTML全文浏览量: 321
- PDF下载量: 293
- 被引次数: 0
