Conflict-free and energy-efficient path planning for multi-robots based on priority free ant colony optimization

Ping Li; Liwei Yang; Ping Li; Liwei Yang

doi:10.3934/mbe.2023165

Mathematical Biosciences and Engineering

2023, Volume 20, Issue 2: 3528-3565. doi: 10.3934/mbe.2023165

Previous Article Next Article

Theory article Special Issues

Conflict-free and energy-efficient path planning for multi-robots based on priority free ant colony optimization

Ping Li ^1,2,
Liwei Yang ^{1,2
,
,}

1.
Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650093, China
2.
Faculty of Information Engineering, Xinjiang Institute of Technology, Akesu 843100, China

Academic Editor: Wenqiang Zhang

Received: 19 October 2022 Revised: 14 November 2022 Accepted: 21 November 2022 Published: 06 December 2022

With the background of limited energy storage of robots and considering the high coupling problem of multi-agent path finding (MAPF), we propose a priority-free ant colony optimization (PFACO) to plan conflict-free and energy-efficient paths, reducing multi-robots motion cost in the rough ground environment. First, a dual-resolution grid map considering obstacles and ground friction factors is designed to model the unstructured rough terrain. Second, an energy-constrained ant colony optimization (ECACO) is proposed to achieve energy-optimal path planning for a single robot, in which we improve the heuristic function based on the combined effects of path length, path smoothness, ground friction coefficient and energy consumption, and consider multiple energy consumption metrics during robot motion to improved pheromone update strategy. Finally, considering multiple collision conflict cases among multiple robots, we incorporate a prioritized conflict-free strategy (PCS) and a route conflict-free strategy (RCS) based on ECACO to achieve MAPF with low-energy and conflict-free in a rough environment. Simulation and experimental results show that ECACO can achieve better energy saving for single robot motion under all three common neighborhood search strategies. PFACO achieves both the conflict-free path and energy-saving planning for robots in complex scenarios, and the study has some reference value for solving practical problems.
- multi-agent path finding,
- ant colony optimization,
- conflict-free,
- energy-efficient,
- unstructured rough terrain
Citation: Ping Li, Liwei Yang. Conflict-free and energy-efficient path planning for multi-robots based on priority free ant colony optimization[J]. Mathematical Biosciences and Engineering, 2023, 20(2): 3528-3565. doi: 10.3934/mbe.2023165

Related Papers:

Abstract

With the background of limited energy storage of robots and considering the high coupling problem of multi-agent path finding (MAPF), we propose a priority-free ant colony optimization (PFACO) to plan conflict-free and energy-efficient paths, reducing multi-robots motion cost in the rough ground environment. First, a dual-resolution grid map considering obstacles and ground friction factors is designed to model the unstructured rough terrain. Second, an energy-constrained ant colony optimization (ECACO) is proposed to achieve energy-optimal path planning for a single robot, in which we improve the heuristic function based on the combined effects of path length, path smoothness, ground friction coefficient and energy consumption, and consider multiple energy consumption metrics during robot motion to improved pheromone update strategy. Finally, considering multiple collision conflict cases among multiple robots, we incorporate a prioritized conflict-free strategy (PCS) and a route conflict-free strategy (RCS) based on ECACO to achieve MAPF with low-energy and conflict-free in a rough environment. Simulation and experimental results show that ECACO can achieve better energy saving for single robot motion under all three common neighborhood search strategies. PFACO achieves both the conflict-free path and energy-saving planning for robots in complex scenarios, and the study has some reference value for solving practical problems.

References

[1]	B. Ai, J. C. Jiang, Yu. S, S. S. Yu, Y. C. Jiang, Multi-agent path finding with heterogeneous edges and round trips, Knowl.-Based Syst., 234 (2021), 107554. https://doi.org/10.1016/j.knosys.2021.107554 doi: 10.1016/j.knosys.2021.107554
[2]	E. T. S. Alotaibi, A. Hisham, Multi-robot path-planning problem for a heavy traffic control application: a survey, Int. J. Adv. Comput. Sci. Appl., 7 (2016), 179–188. https://doi.org/10.14569/IJACSA.2016.070623 doi: 10.14569/IJACSA.2016.070623
[3]	G. Sharon, R. Stern, M. Goldenberg, A. Felner, The increasing cost tree search for optimal multi-agent path finding, Artif. Intell., 195 (2013), 470–495. https://doi.org/10.1016/j.artint.2012.11.006 doi: 10.1016/j.artint.2012.11.006
[4]	J. J. Yu, S. M. LaValle, Optimal multirobot path planning on graphs: complete algorithms and effective heuristics, IEEE Trans. Rob., 32 (2016), 1163–1177. https://doi.org/10.1109/TRO.2016.2593448 doi: 10.1109/TRO.2016.2593448
[5]	L. Tian, Z. Zhang, C. Zheng, Y. Tian, Y. Zhao, Z. Wang, et al., An improved rapidly‐exploring random trees algorithm combining parent point priority determination strategy and real‐time optimization strategy for path planning, Sensors, 21 (2021). https://doi.org/10.3390/s21206907 doi: 10.3390/s21206907
[6]	F. Lu, C. Han, G. X. Wu, M. R. Lu, J. K. Yang, B. R. Miao, et al., Dynamic adaptive security path planning based on A^* algorithm, in Journal of Physics: Conference Series, 2234 (2022), 012002. https://doi.org/10.1088/1742-6596/2234/1/012002
[7]	M. B. Du, J. J. Chen, P. Zhao, H. W. Liang, Y. Xin, T. Mei, An improved RRT-based motion planner for autonomous vehicle in cluttered environments, in 2014 IEEE International Conference on Robotics and Automation (ICRA), (2014), 4674–4679. https://doi.org/10.1109/ICRA.2014.6907542
[8]	W. Xu, Y. Yang, L. Yu, L. Zhu, A global path planning algorithm based on improved RRT, Control Decis., 37 (2022), 829–838. https://doi.org/10.13195/j.kzyjc.2020.1354 doi: 10.13195/j.kzyjc.2020.1354
[9]	X. G. Ruan, J. Zhou, J. J. Zhang, X. Q. Zhu, Robot goal guide RRT path planning based on sub-target search, Control Decis., 35 (2020), 2543–2548. https://doi.org/10.13195/j.kzyjc.2019.0043 doi: 10.13195/j.kzyjc.2019.0043
[10]	W. M. Zhang, S. X. Fu, Mobile robot path planning based on improved RRT* algorithm, J. Huazhong Univ. Sci. Technol. (Nat. Sci. Ed.), 49 (2021), 31–36. https://doi.org/10.13245/j.hust.210101 doi: 10.13245/j.hust.210101
[11]	X. Y. Zhong, J. Tian, H. S. Hu, X. F. Peng, Hybrid path planning based on safe a* algorithm and adaptive window approach for mobile robot in large-scale dynamic environment, J. Intell. Rob. Syst., 99 (2020), 65–77. https://doi.org/10.1007/s10846-019-01112-z doi: 10.1007/s10846-019-01112-z
[12]	X. Xu, X. Yu, Y. Zhao, C. Liu, X. Wu, Global path planning of mobile robot based on improved genetic algorithm, Comput. Integr. Manuf. Syst., 28 (2022), 1659–1672. https://doi.org/10.13196/j.cims.2022.06.006 doi: 10.13196/j.cims.2022.06.006
[13]	Z. Zhang, R. He, K. Yang, A bioinspired path planning approach for mobile robots based on improved sparrow search algorithm, Adv. Manuf., 1 (2022), 114–130. https://doi.org/10.1007/s40436-021-00366-x doi: 10.1007/s40436-021-00366-x
[14]	L. W. Yang, L. X. Fu, P. Li, J. L. Mao, N. Guo, An effective dynamic path planning approach for mobile robots based on ant colony fusion dynamic windows, Machines, 10 (2022), 2075–1702. https://doi.org/10.3390/machines10010050 doi: 10.3390/machines10010050
[15]	K. Xu, H. Lu, Y. Huang, S. Hu, Robot path planning based on double-layer ant colony optimization algorithm and dynamic environment, Acta Electron. Sin. (Chin.), 47 (2019), 2166–2176. https://doi.org/10.3969/j.issn.0372-2112.2019.10.019 doi: 10.3969/j.issn.0372-2112.2019.10.019
[16]	H. D. Li, T, Zhao, S. Y. Dian, Forward search optimization and subgoal-based hybrid path planning to shorten and smooth global path for mobile robots, Knowl.-Based Syst., 258 (2022), 110034. https://doi.org/10.1016/j.knosys.2022.110034 doi: 10.1016/j.knosys.2022.110034
[17]	D. Ratner, M. Warmuth, Finding a shortest solution for the N×N extension of the 15-puzzle is intractable, AAAI, (1986), 168–172.
[18]	S. W. Lin, A. Liu, J. G. Wang, X. Y. Kong, A review of path-planning approaches for multiple mobile robots. Machines, 10 (2022), 773. https://doi.org/10.3390/machines10090773 doi: 10.3390/machines10090773
[19]	L. P. Cheng, C. X. Liu, B. Yan, Improved hierarchical A-star algorithm for optimal parking path planning of the largeparking lot, in 2014 IEEE International Conference on Information and Automation(ICIA), (2014), 695–698. https://doi.org/10.1109/ICInfA.2014.6932742
[20]	Z. Q. Ren, S. Rathinam, H. Choset, Ms: A new exact algorithm for multi-agent simultaneous multi-goalsequencing and path finding, in 2021 IEEE International Conference on Robotics and Automation (ICRA)*, (2021), 11560–11565. https://doi.org/10.1109/ICRA48506.2021.9561779
[21]	L. C. Wen, Y. Liu, H. L. Li, CL-MAPF: Multi-Agent PathFinding for Car-Like robots with kinematic andspatiotemporal constraints, Rob. Auton. Syst., 150 (2020), 103997. https://doi.org/10.1016/j.robot.2021.103997 doi: 10.1016/j.robot.2021.103997
[22]	J. B. Xin, L. Q. Wei, D. S. Wang, H. Xuan, Receding horizon path planning of automated guided vehicles using a time-space network model, Optim. Control. Appl. Methods, 41 (2020), 1889–1903. https://doi.org/10.1002/oca.2654 doi: 10.1002/oca.2654
[23]	K. Murakami, Time-space network model and MILP formulation of the conflict-free routing problem of a capacitated AGV system, Comput. Ind. Eng., 141 (2020). https://doi.org/10.1016/j.cie.2020.106270 doi: 10.1016/j.cie.2020.106270
[24]	M. Cap, P. Novak, A. Kleiner, M. Selecky, Prioritized planning algorithms for trajectory coordination of multiple mobile robots, IEEE Trans. Autom. Sci. Eng., 12 (2015), 835–849. https://doi.org/10.1109/TASE.2015.2445780 doi: 10.1109/TASE.2015.2445780
[25]	N. Greshler, O. Gordon, O. Salzman, N. Shimkin, Cooperative multi-agent path finding: beyond path planning and collision avoidance, in 2021 International Symposium on Multi-Robot and Multi-Agent Systems (MRS), (2021), 20–28. https://doi.org/10.1109/MRS50823.2021.9620590
[26]	H. I. Wang, Y. F. Li, W. J. Jiang, P. F. Wang, Q. X. Cao, Combined priority and path planning through a double-layer structure for multiple robots, in 2020 5th International Conference on Advanced Robotics and Mechatronics (ICARM), 2020. https://doi.org/10.1109/ICARM49381.2020.9195297
[27]	H. D. Li, T. Zhao, S. Y. Dian, Prioritized planning algorithm for multi-robot collision avoidance based on artificial untraversable vertex, Appl. Intell., 52 (2022), 429–451. https://doi.org/10.1007/s10489-021-02397-0 doi: 10.1007/s10489-021-02397-0
[28]	W. Y. Wu, S. Bhattacharya, A. Prorok, Multi-robot path deconfliction through prioritization by path prospects, in 2020 IEEE International Conference on Robotics and Automation (ICRA), 2020. https://doi.org/10.1109/ICRA40945.2020.9196813
[29]	R. K. Dewangan, A. Shukla, W. W. Godfrey, A solution for priority-based multi-robot path planning problem with obstacles using ant lion optimization, Mod. Phys. Lett. B, 34 (2020), 2050137. https://doi.org/10.1142/S0217984920501377 doi: 10.1142/S0217984920501377
[30]	H. J. Zhang, Y. D. Zhang, T. T. Yang, A survey of energy-efficient motion planning for wheeled mobile robots, Ind. Rob., 47 (2020), 607–621. https://doi.org/10.1108/IR-03-2020-0063 doi: 10.1108/IR-03-2020-0063
[31]	S. Liu, D. Sun, Optimal motion planning of a mobile robot with minimum energy consumption, in 2011 IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM), (2011), 43–48. https://doi.org/10.1109/AIM.2011.6027010
[32]	H. Zhang, Z. Su, D. E. Hernandez, B. Su, Energy optimal path planning for mobile robots based on improved AD* algorithm, Trans. Chin. Soc. Agric. Mach., 49 (2018), 19–26. https://doi.org/10.6041/j.issn.1000-1298.2018.09.002 doi: 10.6041/j.issn.1000-1298.2018.09.002
[33]	Y. Mei, Y. H. Lu, Y. C. Hu, C. S. G. Lee, Energy-efficient motion planning for mobile robots, in IEEE International Conference on Robotics and Automation, 5 (2004), 4344–4349. https://doi.org/10.1109/ROBOT.2004.1302401
[34]	V. Singh, R. K. Barai, P. Mandal, Real-time heuristic search based minimum energy path planning of wheeled mobile robot, in Proceedings of the 2015 Conference on Advances in Robotics, 2015. https://doi.org/10.1145/2783449.2783489
[35]	I. Noreen, A. Khan, Z. Habib, Optimal path planning using RRT* based approaches: a survey and future directions, Int. J. Adv. Comput. Sci. Appl., 7 (2016), 97–107. https://doi.org/ 10.14569/IJACSA.2016.071114 doi: 10.14569/IJACSA.2016.071114
[36]	C. W. Miao, G. Z. Chen, C. L. Yan, Y. Y. Wu, Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm, Comput. Ind. Eng., 156 (2021). https://doi.org/10.1016/j.cie.2021.107230 doi: 10.1016/j.cie.2021.107230
[37]	G. H. Yi, Z. I. Feng, T. C. Mei, P. S. Li, W. Jin, S. Y. Chen, Multi-AGVs path planning based on improved ant colony algorithm, J. Supercomput., 75 (2019), 5898–5913. https://doi.org/10.1007/s11227-019-02884-9 doi: 10.1007/s11227-019-02884-9
[38]	C. Ntakolia, D. Lyridis, A comparative study on ant colony optimization algorithm approaches for solving multi-objective path planning problems in case of unmanned surface vehicles, Ocean Eng., 255 (2022), 111418. https://doi.org/10.1016/j.oceaneng.2022.111418 doi: 10.1016/j.oceaneng.2022.111418
[39]	J. Faiz, F. Parvin, Trends and technical advancements on high-efficiency electric motors: a review, Effic. Complex Syst., 2022, 81–95. https://doi.org/10.1007/978-3-030-69288-9_5 doi: 10.1007/978-3-030-69288-9_5
[40]	S. B. Santra, A. Chatterjee, D. Chatterjee, S. Padmanaban, K. Bhattacharya, High efficiency operation of brushless dc motor drive using optimized harmonic minimization based switching technique, IEEE Trans. Ind. Appl., 58 (2022), 2122–2133. https://doi.org/10.1109/TIA.2022.3146212 doi: 10.1109/TIA.2022.3146212
[41]	G. J. Liu, P. Liu, W. I. Mu, S. J. Wang, A path optimization algorithm for AUV using an improved ant colony algorithm with optimal energy consumption, J. Xian Jiaotong Univ., 50 (2016), 93–98. https://doi.org/10.7652/xjtuxb201610014 doi: 10.7652/xjtuxb201610014
[42]	Q. Luo, H. B. Wang, Y. Zheng, J. C. He, Research on path planning of mobile robot based on improved ant colony algorithm, Neural Comput. Appl., 32 (2020), 1555–1566. https://doi.org/10.1007/s00521-019-04172-2 doi: 10.1007/s00521-019-04172-2
[43]	J. Liu, L. P. He, Y. Y. Wang, H. F. Liang, Generalized path planning method for mobile medical robots integrating energy efficiency with safety factors, Comput. Integr. Manuf. Syst., (2021), 1–15. https://doi.org/10.1109/PHM-Shanghai49105.2020.9280948 doi: 10.1109/PHM-Shanghai49105.2020.9280948
[44]	S. Liu, D. Sun, Minimizing energy consumption of wheeled mobile robots via optimal motionplanning, IEEE/ASME Trans. Mechatron., 19 (2014), 401–411. https://doi.org/10.1109/TMECH.2013.2241777 doi: 10.1109/TMECH.2013.2241777
[45]	Y. J. Wang, C. D. Chen, C. K. Sung, System design of a weighted-pendulum-type electromagnetic generator for harvesting energy from a rotating wheel, IEEE/ASME Trans. Mechatron., 18 (2012), 754–763. https://doi.org/10.1109/TMECH.2012.2183640 doi: 10.1109/TMECH.2012.2183640
[46]	Y. Mei, Y. Lu, Deployment of mobile robots with energy and timing constraints, IEEE Trans. Rob., 22 (2006), 507–522. https://doi.org/10.1109/TRO.2006.875494 doi: 10.1109/TRO.2006.875494
[47]	M. Erdmann, T. Lozano-Perez, On multiple moving objects, Algorithmica, 2 (1987), 477–521. https://doi.org/10.1109/ROBOT.1986.1087401 doi: 10.1007/BF01840371
[48]	J. P. V. D. Berg, M. H. Overmars, Prioritized motion planning for multiple robots, in 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, (2005), 430–435. https://doi.org/10.1109/IROS.2005.1545306
[49]	K. X. Zhang, J. L. Mao, Z. W. Xuan, F. H. Xiang, L. X. Fu, Hierarchical scheduling based multi-agent path finding for pass Terrain, Comput. Integr. Manuf. Syst. (Chin.), (2022), 1–16.
[50]	L. W. Yang, L. X. Fu, N. Guo, Z. Yang, H.Q. Guo, Path planning with multi-factor improved ant colony algorithm, Comput. Integr. Manuf. Syst. (Chin.), (2021), 1–18.
[51]	G. Wagner, H. Choset, Subdimensional expansion for multirobot path planning, Artif. Intell., 219 (2015), 1–24. https://doi.org/10.1016/j.artint.2014.11.001 doi: 10.1016/j.artint.2014.11.001
[52]	Y. C. Sun, X. I. Zhao, Y. Z. Yu, Research on a random route-planning method based on the fusion of the A* algorithm and dynamic window method, Electronics, 11 (2022), 2683. https://doi.org/10.3390/electronics11172683 doi: 10.3390/electronics11172683

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)