未知环境下的蚁群-聚类自适应动态路径规划
|
摘要
针对用于动态环境中的机器人路径规划的蚁群算法存在收敛速度慢,路径累计转折角大,对环境变化适应性低等问题,提出了一种未知环境下的蚁群-聚类自适应动态路径规划方法。依据聚类算法对环境复杂程度的准确判别自动改变寻优半径,达到充分利用机器人有限的计算能力,提高收敛速度的目的;通过识别对角障碍,生成虚拟障碍,确保规划的路径不穿过对角障碍;通过平滑机制对搜索的动态路径做平滑优化处理,有效降低了路径长度,减少了累计转折角。仿真结果表明,提出的算法能够根据障碍的复杂程度自动选择合适的搜索半径,完成路径的动态规划,体现出良好的环境适应能力和较好的综合路径优化性能。
When the traditional ant colony algorithm is applied to the path planning of robot in the time-varying environments, there are several problems such as slower convergence speed, lager path integral turning angle and poor self-adaptive ability. So, a self-adjustable dynamic path plan algorithm is presented based on both the ant colony and the clustering algorithm in this paper. In the new ant colony-clustering algorithm proposed here, a suitable searching radius is chosen automatically by using the clustering algorithm for different environmental complexities, which can make full use of the limited computing resources of the robot and improve the convergence speed. By identifying the diagonal obstacles with the proposed virtual obstacle generation method, virtual obstacles are used to guarantee that the problem of planning path crossing diagonal obstacles is nonexistent. The dynamic searching path is smoothed and optimized by the smoothing mechanism, which can effectively reduce the path length and the cumulative turning angle. Simulation examples are provided to show that the algorithm can find suitable searching radius according to different obstacle distributions, complete the dynamic path planning, show good environmental self-adaptability and better total path optimization performances.
When the traditional ant colony algorithm is applied to the path planning of robot in the time-varying environments, there are several problems such as slower convergence speed, lager path integral turning angle and poor self-adaptive ability. So, a self-adjustable dynamic path plan algorithm is presented based on both the ant colony and the clustering algorithm in this paper. In the new ant colony-clustering algorithm proposed here, a suitable searching radius is chosen automatically by using the clustering algorithm for different environmental complexities, which can make full use of the limited computing resources of the robot and improve the convergence speed. By identifying the diagonal obstacles with the proposed virtual obstacle generation method, virtual obstacles are used to guarantee that the problem of planning path crossing diagonal obstacles is nonexistent. The dynamic searching path is smoothed and optimized by the smoothing mechanism, which can effectively reduce the path length and the cumulative turning angle. Simulation examples are provided to show that the algorithm can find suitable searching radius according to different obstacle distributions, complete the dynamic path planning, show good environmental self-adaptability and better total path optimization performances.
引文
[1]Zeng M R,Lu X,Xiao A M.The free step length ant colony algorithm in mobile robot path planning[J].Advanced Robotics,2016,30(23):1509-1514.
[2]Zhao J P,Gao X W,Liu J G,et al.Parameters self-adaptive fuzzy ant colony optimization algorithm with searching window for path planning of mobile robot[J].Control and Decision,2011,26(7):1096-1100.
[3]Dorigo M,Maniezzo V,Colorni A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics:Part B,1996,26(1):29-41.
[4]Liu C A,Yan X H,Liu C Y,et al.Dynamic path planning for mobile robot based on improved ant colony optimization algorithm[J].Acta Electronica Sinica,2011,39(5):1220-1224.
[5]Chen G P,Yang Y B.Memory-type image retrieval method based on ant colony algorithm[J].Journal of Frontiers of Computer Science and Technology,2011,5(1):32-37.
[6]Qu H,Huang L W,Ke X.Research of improved ant colony based robot path planning under dynamic environment[J].Journal of University of Electronic Science and Technology of China,2015,44(2):260-265.
[7]Zhu Y,You X M,Liu S,et al.Research for robot path planning problem based on improved ant colony system(ACS)algorithm[J].Computer Engineering and Applications,2018,54(19):129-134.
[8]Li L N,Guo Y Q,Zhang X D,et al.Path planning algorithm for robot based on firefly algorithm combined with artificial potential field method[J].Computer Engineering and Applications,2018,54(20):104-109.
[9]Zhou M X,Cheng K,Wang Z X.Improved ant colony algorithm with planning of dynamic path[J].Computer Science,2013,40(1):314-316.
[10]Shi P,Cui Y J.Dynamic path planning for mobile robot based on genetic algorithm in unknown environment[C]//Proceedings of 2010 Chinese Control and Decision Conference,Xuzhou,May 26-28,2010.Piscataway:IEEE,2010:4325-4329.
[11]Zhao F,Yang C X,Chen F,et al.Self-adjust searching radius dynamic planning algorithm based on ant colony algorithm[J].Computer Engineering and Applications,2018,54(19):56-61.
[12]Wang H J,Xu J,Zhao H,et al.Robot path planning based on smooth ant colony algorithm[J].Journal of Yanshan University,2017,41(3):278-282.
[13]Han L,Liu G D.A local path planning method for mobile robots based on the windows[J].Computer Systems and Applications,2011,20(8):160-163.
[14]Zhang C G,Xi Y G.Robot rolling path planning based on locally detected information[J].Acta Automatica Sinica,2003,29(1):38-44.
[15]Zhu M.Data mining[M].Hefei:University of Science and Technology of China Press,2002.
[16]Zhu Q B,Zhang Y L.An ant colony algorithm based on grid method for mobile robot path planning[J].Robot,2005,27(2):132-136.
[17]Xu M L,You X M,Liu S.Self-adaptive ant colony algorithm based on statistical analysis and its application[J].Computer Application and Software,2017,34(7):204-211.
[2]赵娟平,高宪文,刘金刚,等.移动机器人路径规划的参数模糊自适应窗口蚁群优化算法[J].控制与决策, 2011, 26(7):1096-1100.
[4]柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报, 2011, 39(5):1220-1224.
[5]陈光鹏,杨育彬.利用蚁群算法的记忆式图像检索方法[J].计算机科学与探索, 2011, 5(1):32-37.
[6]屈鸿,黄利伟,柯星.动态环境下基于改进蚁群算法的机器人路径规划研究[J].电子科技大学学报, 2015, 44(2):260-265.
[7]朱艳,游晓明,刘升,等.基于改进蚁群算法的机器人路径规划问题研究[J].计算机工程与应用, 2018, 54(19):129-134.
[8]李丽娜,郭永强,张晓东,等.萤火虫算法结合人工势场法的机器人路径规划[J].计算机工程与应用, 2018, 54(20):104-109.
[9]周明秀,程科,汪正霞.动态路径规划中的改进蚁群算法[J].计算机科学, 2013, 40(1):314-316.
[11]赵峰,杨春曦,陈飞,等.自适应搜索半径蚁群动态路径规划算法[J].计算机工程与应用, 2018, 54(19):56-61.
[12]王红军,徐军,赵辉,等.基于平滑蚁群算法的机器人路径规划[J].燕山大学学报, 2017, 41(3):278-282.
[13]韩龙,刘国栋.一种基于滚动窗口的移动机器人局部路径规划方法[J].计算机系统应用, 2011, 20(8):160-163.
[14]张纯刚,席裕庚.基于局部探测信息的机器人滚动路径规划[J].自动化学报, 2003, 29(1):38-44.
[15]朱明.数据挖掘[M].合肥:中国科学技术大学出版社,2002.
[16]朱庆保,张玉兰.基于栅格法的机器人路径规划蚁群算法[J].机器人, 2005, 27(2):132-136.
[17]许明乐,游晓明,刘升.基于统计分析的自适应蚁群算法及应用[J].计算机应用与软件, 2017, 34(7):204-211.
[2]Zhao J P,Gao X W,Liu J G,et al.Parameters self-adaptive fuzzy ant colony optimization algorithm with searching window for path planning of mobile robot[J].Control and Decision,2011,26(7):1096-1100.
[3]Dorigo M,Maniezzo V,Colorni A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics:Part B,1996,26(1):29-41.
[4]Liu C A,Yan X H,Liu C Y,et al.Dynamic path planning for mobile robot based on improved ant colony optimization algorithm[J].Acta Electronica Sinica,2011,39(5):1220-1224.
[5]Chen G P,Yang Y B.Memory-type image retrieval method based on ant colony algorithm[J].Journal of Frontiers of Computer Science and Technology,2011,5(1):32-37.
[6]Qu H,Huang L W,Ke X.Research of improved ant colony based robot path planning under dynamic environment[J].Journal of University of Electronic Science and Technology of China,2015,44(2):260-265.
[7]Zhu Y,You X M,Liu S,et al.Research for robot path planning problem based on improved ant colony system(ACS)algorithm[J].Computer Engineering and Applications,2018,54(19):129-134.
[8]Li L N,Guo Y Q,Zhang X D,et al.Path planning algorithm for robot based on firefly algorithm combined with artificial potential field method[J].Computer Engineering and Applications,2018,54(20):104-109.
[9]Zhou M X,Cheng K,Wang Z X.Improved ant colony algorithm with planning of dynamic path[J].Computer Science,2013,40(1):314-316.
[10]Shi P,Cui Y J.Dynamic path planning for mobile robot based on genetic algorithm in unknown environment[C]//Proceedings of 2010 Chinese Control and Decision Conference,Xuzhou,May 26-28,2010.Piscataway:IEEE,2010:4325-4329.
[11]Zhao F,Yang C X,Chen F,et al.Self-adjust searching radius dynamic planning algorithm based on ant colony algorithm[J].Computer Engineering and Applications,2018,54(19):56-61.
[12]Wang H J,Xu J,Zhao H,et al.Robot path planning based on smooth ant colony algorithm[J].Journal of Yanshan University,2017,41(3):278-282.
[13]Han L,Liu G D.A local path planning method for mobile robots based on the windows[J].Computer Systems and Applications,2011,20(8):160-163.
[14]Zhang C G,Xi Y G.Robot rolling path planning based on locally detected information[J].Acta Automatica Sinica,2003,29(1):38-44.
[15]Zhu M.Data mining[M].Hefei:University of Science and Technology of China Press,2002.
[16]Zhu Q B,Zhang Y L.An ant colony algorithm based on grid method for mobile robot path planning[J].Robot,2005,27(2):132-136.
[17]Xu M L,You X M,Liu S.Self-adaptive ant colony algorithm based on statistical analysis and its application[J].Computer Application and Software,2017,34(7):204-211.
[2]赵娟平,高宪文,刘金刚,等.移动机器人路径规划的参数模糊自适应窗口蚁群优化算法[J].控制与决策, 2011, 26(7):1096-1100.
[4]柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报, 2011, 39(5):1220-1224.
[5]陈光鹏,杨育彬.利用蚁群算法的记忆式图像检索方法[J].计算机科学与探索, 2011, 5(1):32-37.
[6]屈鸿,黄利伟,柯星.动态环境下基于改进蚁群算法的机器人路径规划研究[J].电子科技大学学报, 2015, 44(2):260-265.
[7]朱艳,游晓明,刘升,等.基于改进蚁群算法的机器人路径规划问题研究[J].计算机工程与应用, 2018, 54(19):129-134.
[8]李丽娜,郭永强,张晓东,等.萤火虫算法结合人工势场法的机器人路径规划[J].计算机工程与应用, 2018, 54(20):104-109.
[9]周明秀,程科,汪正霞.动态路径规划中的改进蚁群算法[J].计算机科学, 2013, 40(1):314-316.
[11]赵峰,杨春曦,陈飞,等.自适应搜索半径蚁群动态路径规划算法[J].计算机工程与应用, 2018, 54(19):56-61.
[12]王红军,徐军,赵辉,等.基于平滑蚁群算法的机器人路径规划[J].燕山大学学报, 2017, 41(3):278-282.
[13]韩龙,刘国栋.一种基于滚动窗口的移动机器人局部路径规划方法[J].计算机系统应用, 2011, 20(8):160-163.
[14]张纯刚,席裕庚.基于局部探测信息的机器人滚动路径规划[J].自动化学报, 2003, 29(1):38-44.
[15]朱明.数据挖掘[M].合肥:中国科学技术大学出版社,2002.
[16]朱庆保,张玉兰.基于栅格法的机器人路径规划蚁群算法[J].机器人, 2005, 27(2):132-136.
[17]许明乐,游晓明,刘升.基于统计分析的自适应蚁群算法及应用[J].计算机应用与软件, 2017, 34(7):204-211.