[1]陈强,马健,杨蘩.求解多目标点路径规划问题的离散头脑风暴算法[J].智能系统学报,2023,18(1):96-103.[doi:10.11992/tis.202206018]
CHEN Qiang,MA Jian,YANG Fan.Discrete brainstorm optimization algorithm for solving multi-target route planning problems[J].CAAI Transactions on Intelligent Systems,2023,18(1):96-103.[doi:10.11992/tis.202206018]
点击复制
CHEN Qiang,MA Jian,YANG Fan.Discrete brainstorm optimization algorithm for solving multi-target route planning problems[J].CAAI Transactions on Intelligent Systems,2023,18(1):96-103.[doi:10.11992/tis.202206018]
求解多目标点路径规划问题的离散头脑风暴算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
18
期数:
2023年第1期
页码:
96-103
栏目:
学术论文—知识工程
出版日期:
2023-01-05
- Title:
- Discrete brainstorm optimization algorithm for solving multi-target route planning problems
- Keywords:
- mobile robot; path planning; discrete brainstorm optimization; combinatorial optimization problem; local optimum; shortest obstacle avoidance distance; fitness selection function; heuristic crossover operator
- 分类号:
- TP399;TP18;TN911.7
- 摘要:
- 为保证移动机器人以最短路径遍历多目标点，该文提出一种基于离散头脑风暴的多目标点路径规划算法。首先，考虑障碍物对路径规划的影响，将目标点间的最短避障距离作为评判依据，提高规划路径合理性。其次，针对传统离散头脑风暴算法在解决组合类优化问题时提前陷入局部最优的问题，提出一种启发式自适应路径优化策略，通过设计与迭代次数相关的适应度选择函数以及改进启发式交叉算子，增加路径多样性和提高算法收敛速度。基于栅格法建立地图模型，在不同环境地图中选取多个目标进行对比仿真，验证所提算法的有效性以及对不同环境的适应性。
- Abstract:
- In this paper, a multi-target point path planning algorithm is proposed based on discrete brainstorm optimization (DBSO) to guarantee that a mobile robot can traverse multiple target points with the shortest path. First, considering the influence of obstacles on path planning, the shortest obstacle avoidance distance between target points is used as the judgment basis to improve rationality of the planned path. Secondly, the traditional discrete brainstorming algorithm will fall into local optimum in advance when solving combinatorial optimization problems. Therefore, a heuristic adaptive path optimization strategy is proposed. It increases path diversity and improves convergence speed of the algorithm by designing a fitness selection function related to the number of iterations and improving the heuristic crossover operator. A map model is established based on the grid method, and multiple targets are selected in different environmental maps for comparison and simulation to verify effectiveness of the proposed algorithm and its adaptability to different environments.
- 参考文献/References:
-
[1] LIN Wei, DELGADO-FRIAS J G, GAUSE D C, et al. Hybrid Newton-raphson genetic algorithm for the traveling salesman problem[J]. Cybernetics and systems, 1995, 26(4): 387–412.
[2] XIANG Xiaoshu, TIAN Ye, ZHANG Xingyi, et al. A pairwise proximity learning-based ant colony algorithm for dynamic vehicle routing problems[J]. IEEE transactions on intelligent transportation systems, 2022, 23(6): 5275–5286.
[3] XUE Yang, SUN Jianqiao. Solving the path planning problem in mobile robotics with the multi-objective evolutionary algorithm[J]. Applied sciences, 2018, 8(9): 1425.
[4] PARADISO R, ROBERTI R, LAGANá D, et al. An exact solution framework for multitrip vehicle-routing problems with time windows[J]. Operations research, 2020, 68(1): 180–198.
[5] CHEN Zhihuan, WU Huaiyu, CHEN Yang, et al. Patrol robot path planning in nuclear power plant using an interval multi-objective particle swarm optimization algorithm[J]. Applied soft computing, 2022, 116: 108192.
[6] 刘长石, 申立智, 盛虎宜, 等. 考虑交通拥堵规避的低碳时变车辆路径问题研究[J]. 控制与决策, 2020, 35(10): 2486–2496
LIU Changshi, SHEN Lizhi, SHENG Huyi, et al. Research on low-carbon time-dependent vehicle routing problem with traffic congestion avoidance approaches[J]. Control and decision, 2020, 35(10): 2486–2496
[7] 赵畅, 刘允刚, 陈琳, 等. 面向元启发式算法的多无人机路径规划现状与展望[J]. 控制与决策, 2022, 37(5): 1102–1115
ZHAO Chang, LIU Yungang, CHEN Lin, et al. Research and development trend of multi-UAV path planning based on metaheuristic algorithm[J]. Control and decision, 2022, 37(5): 1102–1115
[8] 胡立坤, 王帅军, 吕智林, 等. 移动机器人多目标搜寻的D*–蚁群融合算法[J]. 小型微型计算机系统, 2020, 41(3): 471–476
HU Likun, WANG Shuaijun, LYU Zhilin, et al. Multi-objective search based on d*-ant colony fusion algorithm[J]. Journal of Chinese computer systems, 2020, 41(3): 471–476
[9] 蒲兴成, 李俊杰, 吴慧超, 等. 基于改进粒子群算法的移动机器人多目标点路径规划[J]. 智能系统学报, 2017, 12(3): 301–309
PU Xingcheng, LI Junjie, WU Huichao, et al. Mobile robot multi-goal path planning using improved particle swarm optimization[J]. CAAI transactions on intelligent systems, 2017, 12(3): 301–309
[10] SHI Yuhui. Brain Storm Optimization Algorithm[C]//International Conference in Swarm Intelligence. Berlin: Springer, 2011: 303?309.
[11] 戚远航, 黄子峻, 曾楚祥, 等. 头脑风暴优化算法求解带转角能耗多无人机路径规划问题[J]. 计算机应用研究, 2022, 39(1): 177–182
QI Yuanhang, HUANG Zijun, ZENG Chuxiang, et al. Brain storm optimization algorithm for multi-UAV path planning with angular energy consumption[J]. Application research of computers, 2022, 39(1): 177–182
[12] 朱代先, 王明博, 刘树林, 等. 基于头脑风暴算法的FastSLAM2.0算法[J]. 计算机应用研究, 2021, 38(12): 3629–3633
ZHU Daixian, WANG Mingbo, LIU Shulin, et al. FastSLAM 2.0 algorithm based on brain storm optimization[J]. Application research of computers, 2021, 38(12): 3629–3633
[13] YANG Jian, ZHAO Donghui, XIANG Xinhao, et al. Robotic brain storm optimization: a multi-target collaborative searching paradigm for swarm robotics[M]//Lecture Notes in Computer Science. Cham: Springer International Publishing, 2021: 155?167.
[14] 狄卫民, 杜慧莉, 张鹏阁. 考虑动态拥堵的多车型绿色车辆路径问题优化[J]. 计算机工程与设计, 2021, 42(9): 2614–2620
DI Weimin, DU Huili, ZHANG Pengge. Optimization of multi-vehicle green vehicle routing problem considering dynamic congestion[J]. Computer engineering and design, 2021, 42(9): 2614–2620
[15] 刘伯运, 赵帅, 赵强强, 等. 水面垃圾清理机器人[J]. 兵工自动化, 2022, 41(2): 92–96
LIU Boyun, ZHAO Shuai, ZHAO Qiangqiang, et al. Water surface garbage cleaning robot[J]. Ordnance industry automation, 2022, 41(2): 92–96
[16] 周立辉, 张永生, 孙勇, 等. 智能变电站巡检机器人研制及应用[J]. 电力系统自动化, 2011, 35(19): 85–88,96
ZHOU Lihui, ZHANG Yongsheng, SUN Yong, et al. Development and application of equipment inspection robot for smart substations[J]. Automation of electric power systems, 2011, 35(19): 85–88,96
[17] CHENG Shi, SHI Yuhui, QIN Quande, et al. Maintaining population diversity in brain storm optimization algorithm[C]//2014 IEEE Congress on Evolutionary Computation. Beijing: IEEE, 2014: 3230-3237.
[18] 杨玉婷, 史玉回, 夏顺仁. 基于讨论机制的头脑风暴优化算法[J]. 浙江大学学报(工学版), 2013, 47(10): 1705–1711,1746
YANG Yuting, SHI Yuhui, XIA Shunren. Discussion mechanism based brain storm optimization algorithm[J]. Journal of Zhejiang university (engineering science edition), 2013, 47(10): 1705–1711,1746
[19] NAZARAHARI M. Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm[J]. Expert systems with applications, 2019, 115: 106–120.
[20] 吴晓涛, 孙增圻. 用遗传算法进行路径规划[J]. 清华大学学报(自然科学版), 1995, 35(5): 14–19
WU Xiaotao, SUN Zengqi. Using genetic algorithm for path planning[J]. Journal of Tsinghua University (science and technology edition), 1995, 35(5): 14–19
[21] CHICCO G. Overview and performance assessment of the clustering methods for electrical load pattern grouping[J]. Energy, 2012, 42(1): 68–80.
[22] PONNAMBALAM S G, JAGANNATHAN H, KATARIA M, et al. A TSP-GA multi-objective algorithm for flow-shop scheduling[J]. The international journal of advanced manufacturing technology, 2004, 23(11): 909–915.
[23] DEEP K. A new crossover operator for real coded genetic algorithms[J]. Applied mathematics and computation, 2007, 188(1): 895–911.
[24] DUCHO? F, BABINEC A, KAJAN M, et al. Path planning with modified a star algorithm for a mobile robot[J]. Procedia engineering, 2014, 96: 59–69.
[25] 刘晓莹, 蔡自兴, 余伶俐, 等. 一种正交混沌蚁群算法在群机器人任务规划中的应用研究[J]. 小型微型计算机系统, 2010, 31(1): 164–168
LIU Xiaoying, CAI Zixing, YU Lingli, et al. An orthogonal-cluster chaos ant colony algorithm based on swarm-robots system mission planning application research[J]. Journal of Chinese computer systems, 2010, 31(1): 164–168
[26] WU Changyou, FU Xisong. An agglomerative greedy brain storm optimization algorithm for solving the TSP[J]. IEEE access, 2016, 8: 201606–201621.
- 相似文献/References:
-
[1]蔡自兴,王 勇,王 璐.基于角点聚类的移动机器人自然路标检测与识别[J].智能系统学报,2006,1(1):52.
CAI Zi-xing,WANG Yong,WANG Lu.Corner clustering based detection and recognition of natural landmark for mobile robot[J].CAAI Transactions on Intelligent Systems,2006,1():52.
[2]杨甜甜,刘志远,陈 虹,等.移动机器人编队控制的现状与问题[J].智能系统学报,2007,2(4):21.
YANG Tian-tian,LIU Zhi-yuan,CHEN Hong,et al.Formation control of mobile robots: state and open prob lems[J].CAAI Transactions on Intelligent Systems,2007,2():21.
[3]黄彦文,曹其新.RoboCup比赛环境下足球机器人路径规划研究[J].智能系统学报,2007,2(4):52.
HUANG Yan-wen,CAO Qin-xin.Path planning for robot soccer in the RoboCup environment[J].CAAI Transactions on Intelligent Systems,2007,2():52.
[4]李润伟,蔡自兴,童宇,等.基于ATM的提高狭窄环境探测精度的改进方法[J].智能系统学报,2008,3(4):283.
LI Run-wei,CAI Zi-xing,TONG Yu.Improving the accuracy of exploring the narrow environment by using ATM[J].CAAI Transactions on Intelligent Systems,2008,3():283.
[5]霍成立,谢 凡,秦世引.面向室内移动机器人的无迹滤波实时导航方法[J].智能系统学报,2009,4(4):295.
HUO Cheng-li,XIE Fan,QIN Shi-yin.A case study in realtime UKFbased navigation for indoor autonomous travel of mobile robots[J].CAAI Transactions on Intelligent Systems,2009,4():295.
[6]秦世引,高书征.面向救援任务的地面移动机器人路径规划[J].智能系统学报,2009,4(5):414.[doi:10.3969/j.issn.1673-4785.2009.05.005]
QIN Shi-yin,GAO Shu-zhen.Path planning for mobile rescue robots in disaster areas with complex environments[J].CAAI Transactions on Intelligent Systems,2009,4():414.[doi:10.3969/j.issn.1673-4785.2009.05.005]
[7]曹卫华,吴净斌,吴 敏,等.无路标环境下遥操作机器人SLAM系统[J].智能系统学报,2010,5(3):240.
CAO Wei-hua,WU Jing-bin,WU Min,et al.A system for telerobotics in environments without landmarks[J].CAAI Transactions on Intelligent Systems,2010,5():240.
[8]薛英花,田国会,吴 皓,等.智能空间中的服务机器人路径规划[J].智能系统学报,2010,5(3):260.
XUE Ying-hua,TIAN Guo-hui,WU Hao,et al.Path planning for service robots in an intelligent space[J].CAAI Transactions on Intelligent Systems,2010,5():260.
[9]黄晓丹,王粉花,王志良.情感决策的智能家居虚拟人路径规划[J].智能系统学报,2010,5(4):292.
HUANG Xiao-dan,WANG Fen-hua,WANG Zhi-liang.Using affective decisionmaking for the path planning of virtual humans in a smart home[J].CAAI Transactions on Intelligent Systems,2010,5():292.
[10]海 丹,李 勇,张 辉,等.无线传感器网络环境下基于粒子滤波的移动机器人SLAM算法[J].智能系统学报,2010,5(5):425.[doi:10.3969/j.issn.1673-4785.2010.05.008]
HAI Dan,LI Yong,ZHANG Hui,et al.Simultaneous localization and mapping of a mobile robot in wireless sensor networks based on particle filtering[J].CAAI Transactions on Intelligent Systems,2010,5():425.[doi:10.3969/j.issn.1673-4785.2010.05.008]
[11]沈博闻,于宁波,刘景泰.仓储物流机器人集群的智能调度和路径规划[J].智能系统学报,2014,9(6):659.[doi:10.3969/j.issn.1673-4785.201312048]
SHEN Bowen,YU Ningbo,LIU Jingtai.Intelligent scheduling and path planning of warehouse mobile robots[J].CAAI Transactions on Intelligent Systems,2014,9():659.[doi:10.3969/j.issn.1673-4785.201312048]
[12]莫宏伟,马靖雯.一种生物地理学移动机器人路径规划算法[J].智能系统学报,2015,10(5):705.[doi:10.11992/tis.201407003]
MO Hongwei,MA Jingwen.A biogeography-based mobile robot path planning algorithm[J].CAAI Transactions on Intelligent Systems,2015,10():705.[doi:10.11992/tis.201407003]
[13]李元,王石荣,于宁波.基于RGB-D信息的移动机器人SLAM和路径规划方法研究与实现[J].智能系统学报,2018,13(3):445.[doi:10.11992/tis.201702005]
LI Yuan,WANG Shirong,YU Ningbo.RGB-D-based SLAM and path planning for mobile robots[J].CAAI Transactions on Intelligent Systems,2018,13():445.[doi:10.11992/tis.201702005]
[14]徐玉琼,娄柯,李志锟.基于变步长蚁群算法的移动机器人路径规划[J].智能系统学报,2021,16(2):330.[doi:10.11992/tis.202004011]
XU Yuqiong,LOU Ke,LI Zhikun.Mobile robot path planning based on variable-step ant colony algorithm[J].CAAI Transactions on Intelligent Systems,2021,16():330.[doi:10.11992/tis.202004011]
[15]蒲兴成,宋欣琳.分组教学蚁群算法改进及其在机器人路径规划中应用[J].智能系统学报,2022,17(4):764.[doi:10.11992/tis.202108020]
PU Xingcheng,SONG Xinlin.Improvement of ant colony algorithm in group teaching and its application in robot path planning[J].CAAI Transactions on Intelligent Systems,2022,17():764.[doi:10.11992/tis.202108020]
备注/Memo
收稿日期:2022-06-11。
基金项目:国家自然科学基金项目(61973274);浙江省自然科学基金重点项目(LZ22F030007).
作者简介:陈强,副教授,博士生导师,主要研究方向为伺服系统智能控制、移动机器人调度与控制。获授权发明专利60余项,发表学术论文100余篇,出版英文专著1部;马健,硕士研究生,主要研究方向为机器人多目标路径规划;杨蘩,硕士研究生,主要研究方向为移动机器人调度与多目标路径规划
通讯作者:陈强.E-mail:sdnjchq@zjut.edu.cn
更新日期/Last Update:
1900-01-01