[1]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]
Copy

Discrete brainstorm optimization algorithm for solving multi-target route planning problems

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 18 Number of periods: 2023 1 Page number: 96-103 Column: 学术论文—知识工程 Public date: 2023-01-05
Title:
Discrete brainstorm optimization algorithm for solving multi-target route planning problems
Author(s):
CHEN Qiang;  MA Jian;  YANG Fan
College of Information Engineering, Zhejiang University of Technology, Hangzhou 310013, China
Keywords:
mobile robot; path planning; discrete brainstorm optimization; combinatorial optimization problem; local optimum; shortest obstacle avoidance distance; fitness selection function; heuristic crossover operator
CLC:
TP399;TP18;TN911.7
DOI:
10.11992/tis.202206018
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.
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems