| Citation: | ZHAO M，LU H，WANG S Q，et al. A multimodal multi-objective path planning algorithm based on multi-swarm cooperative learning[J]. Journal of Beijing University of Aeronautics and Astronautics，2023，49（3）：606-616 （in Chinese） doi: 10.13700/j.bh.1001-5965.2021.0274
|
An algorithm based on multi-swarm cooperative learning was proposed to plan multiple optimal paths to meet multiple objectives, which can improve the robustness and practicability of the planned paths. The concept of the particle swarm optimization algorithm served as the algorithm's guidance. First, to address the issue that a single population is easy to trap in local optimum in the multi-dimensional target space, a strategy of sub-swarm division was proposed. The population was divided into many sub-swarms according to the number of objectives, balancing the searching ability of the algorithm in each dimension of the target space. Second, key path points were extracted according to the in-degree and out-degree of the path points in the map. In the coding process, real coding was used to initialize the population. The dimension of the path code was equal to the number of key path points, reducing the size of the solution space. In the decoding process, the decoding experience of the elite solutions guided the fast search for feasible solutions. This method can transfer the decoding experience efficiently and reduce the uncertainty of decoding, which improved the optimization ability of the algorithm. Finally, the search results of all sub-swarms were sorted by the non-dominated sorting method to obtain the paths satisfying the planning objectives. The path planning algorithm based on the multi-swarm cooperative learning outperforms the standard particle swarm optimization algorithm in terms of search and optimization ability and is capable of solving the multimodal multi-objective path planning problem.
| [1] |
DEB K. Multi-objective genetic algorithms: Problem difficulties and construction of test problems[J]. Evolutionary Computation, 1999, 7(3): 205-230. doi: 10.1162/evco.1999.7.3.205
|
| [2] |
FENG G, KORKMAZ T. Finding multi-constrained multiple shortest paths[J]. IEEE Transactions on Computers, 2015, 64(9): 2559-2572. doi: 10.1109/TC.2014.2366762
|
| [3] |
王树西, 李安渝. Dijkstra算法中的多邻接点与多条最短路径问题[J]. 计算机科学, 2014, 41(6): 217-224. doi: 10.11896/j.issn.1002-137X.2014.06.043
WANG S X, LI A Y. Multi-adjacent-vertexes and multi-shortest-paths problem of Dijkstra algorithm[J]. Computer Science, 2014, 41(6): 217-224(in Chinese). doi: 10.11896/j.issn.1002-137X.2014.06.043
|
| [4] |
HAYAT S, YANMAZ E, BROWN T X, et al. Multi-objective UAV path planning for search and rescue[C]//IEEE International Conference on Robotics and Automation. Piscataway: IEEE Press, 2017, 5569-5574.
|
| [5] |
马小铭, 靳伍银. 基于改进蚁群算法的多目标路径规划研究[J]. 计算技术与自动化, 2020, 39(4): 100-105. doi: 10.16339/j.cnki.jsjsyzdh.202004018
MA X M, JIN W Y. Multi-objective path planning based on improved and colony algorithm[J]. Computing Technology and Automation, 2020, 39(4): 100-105(in Chinese). doi: 10.16339/j.cnki.jsjsyzdh.202004018
|
| [6] |
DENG Y T, RONG D C, SHANGGUAN W, et al. Multi-objective path optimization method in terminal building based on improved genetic algorithm[C]//Chinese Automation Congress. 2020, 3181-3186.
|
| [7] |
NAZARAHARI M, KHANMIRZA E, DOOSTIE S. Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm[J]. Expert Systems with Applications, 2018, 115: 106-120.
|
| [8] |
LI Z J, LIU Y, YANG Z. An effective kernel search and dynamic programming hybrid heuristic for a multimodal transportation planning problem with order consolidation[J]. Transportation Research Part E:Logistics and Transportation Review, 2021, 152: 102408. doi: 10.1016/j.tre.2021.102408
|
| [9] |
WANG Z Z, ZHANG M H, CHU R J, et al. Modeling and planning multimodal transport paths for risk and energy efficiency using AND/OR graphs and discrete ant colony optimization[J]. IEEE Access, 2020, 8: 132642-132654.
|
| [10] |
张启钱, 许卫卫, 张洪海, 等. 复杂低空物流无人机路径规划[J]. 北京亚洲成人在线一二三四五六区学报, 2020, 46(7): 1275-1286. doi: 10.13700/j.bh.1001-5965.2019.0455
ZHANG Q Q, XU W W, ZHANG H H, et al. Plan planning for logistics UAV in complex low-altitude airspace[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(7): 1275-1286(in Chinese). doi: 10.13700/j.bh.1001-5965.2019.0455
|
| [11] |
MIAO C, GHEN G, YAN C, et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J]. Computers & Industrial Engineering, 2021, 156: 107230.
|
| [12] |
ZHOU X, WANG X, GU X. Welding robot path planning problem based on discrete MOEA/D with hybrid environment selection[J]. Neural Computing and Applications, 2021, 4: 12881-12903.
|
| [13] |
肖博. 基于多目标优化的震后应急物流路径规划研究[D]. 西安: 长安大学, 2019: 10-14.
XIAO B. Study on post-earthquake emergency logistics path planning based on multi-objective optimization[D]. Xi’an: Chang’an University, 2019: 10-14(in Chinese).
|
| [14] |
CHOU Y T, HSIA S Y, LAN C H. A hybrid approach on multi-objective route planning and assignment optimization for urban lorry transportation[C]//International Conference on Applied System Innovation. Piscataway: IEEE Press, 2017: 1006-1009.
|
| [15] |
蒋强, 易春林, 张伟, 等. 基于蚁群算法的移动机器人多目标路径规划[J]. 计算机仿真, 2021, 38(2): 318-325. doi: 10.3969/j.issn.1006-9348.2021.02.068
JIANG Q, YI C L, ZHANG W, et al. The multi-objective path planning for mobile robot based on ant colony algorithm[J]. Computer Simulation, 2021, 38(2): 318-325(in Chinese). doi: 10.3969/j.issn.1006-9348.2021.02.068
|
| [16] |
王晨宇. 基于智能优化算法的多目标路径规划方法研究[D]. 桂林: 桂林电子科技大学, 2020: 18-27.
WANG C Y. Research on multi-objective path planning method based on intelligent optimization algorithm[D]. Guilin: Guilin University of Electronic Technology, 2020: 18-27(in Chinese).
|
| [17] |
熊昕霞, 何利力. 基于混合粒子群算法的移动机器人路径规划[J]. 计算机系统应用, 2021, 30(4): 153-159. doi: 10.15888/j.cnki.csa.007865
XIONG X X, HE L L. Path planning for mobile robot based on improved particle swarm optimization algorithm[J]. Computer Systems & Applications, 2021, 30(4): 153-159(in Chinese). doi: 10.15888/j.cnki.csa.007865
|
| [18] |
GUL F, RAHIMAN W, ALHADY S S N, et al. Meta-heuristic approach for solving multi-objective path planning for autonomous guided robot using PSO-GWO optimization algorithm with evolutionary programming[J]. Journal of Ambient Intelligence and Humanized Computing, 2021, 12: 7873-7890. doi: 10.1007/s12652-020-02514-w
|
| [19] |
HIDALGO-PANIAGUA A, VEGA-RODRÍGUEZ M A, FERRUZ J, et al. Solving the multi-objective path planning problem in mobile robotics with a firefly-based approach[J]. Soft Computing, 2017, 21(4): 1-16.
|
| [20] |
段益琴. 基于多目标优化的多机器人路径规划研究[D]. 重庆: 重庆邮电大学, 2020: 23-34.
DUAN Y Q. Research on multi-robot path planning based on multi-objective optimization[D]. Chongqing: Chongqing University of Posts and Telecommunications, 2020: 23-34(in Chinese).
|
| [21] |
樊娇, 雷涛, 董南江, 等. 基于改进NSGA-Ⅱ算法的多目标无人机路径规划[J]. 火力与指挥控制, 2022, 47(2): 43-48. doi: 10.3969/j.issn.1002-0640.2022.02.008
FAN J, LEI T, DONG N J, et al. Multi-objective UAV path planning based on an improved NSGA-Ⅱ[J]. Fire Control & Command Control, 2022, 47(2): 43-48(in Chinese). doi: 10.3969/j.issn.1002-0640.2022.02.008
|
| [22] |
DHIKARI D, KIM E, REZA H. A fuzzy adaptive differential evolution for multi-objective 3D UAV path optimization[C]//IEEE Congress on Evolutionary Computation. Piscataway: IEEE Press, 2017: 2258-2265.
|
| [23] |
SHI Y, EBERHART R. A modified particle swarm optimizer[C]//IEEE World Congress on Computational Intelligence. Piscataway: IEEE Press, 1998: 69-73.
|
| [24] |
EBERHART R, KENNEDY J. A new optimizer using particle swarm theory[C]//Proceedings of the Sixth International Symposium on Micro Machine and Human Science. Piscataway: IEEE Press, 1995: 39-43.
|
| [25] |
LIANG J, YUE C, LI G, et al. Problem definitions and evaluation criteria for the CEC 2021 on multimodal multiobjective path planning optimization[EB/OL]. (2020-12)[2021-05-24].
|
Figures(15) / Tables(6)
Copyright © Journal of Beijing University of Aeronautics and Astronautics
Address: Editorial Department of Journal of Beijing University of Aeronautics and Astronautics, 37 Xueyuan Road, Haidian District, Beijing Post Code: 100191 Email: jbuaa@cqjj8.com
Supported by:
Beijing Renhe Information Technology Co., Ltd.
DownLoad:
