LF-ACO: an effective formation path planning for multi-mobile robot

Liwei Yang; Lixia Fu; Ping Li; Jianlin Mao; Ning Guo; Linghao Du; Liwei Yang; Lixia Fu; Ping Li; Jianlin Mao; Ning Guo; Linghao Du

doi:10.3934/mbe.2022012

Mathematical Biosciences and Engineering

2022, Volume 19, Issue 1: 225-252. doi: 10.3934/mbe.2022012

Previous Article Next Article

Research article Special Issues

LF-ACO: an effective formation path planning for multi-mobile robot

School of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650093, China

Academic Editor: Yang Kuang

Received: 26 August 2021 Accepted: 21 October 2021 Published: 09 November 2021

Multi-robot path planning is a hot problem in the field of robotics. Compared with single-robot path planning, complex problems such as obstacle avoidance and mutual collaboration need to be considered. This paper proposes an efficient leader follower-ant colony optimization (LF-ACO) to solve the collaborative path planning problem. Firstly, a new Multi-factor heuristic functor is proposed, the distance factor heuristic function and the smoothing factor heuristic function. This improves the convergence speed of the algorithm and enhances the smoothness of the initial path. The leader-follower structure is reconstructed for the position constraint problem of multi-robots in a grid environment. Then, the pheromone of the leader ant and the follower ants are used in the pheromone update rule of the ACO to improve the search quality of the formation path. To improve the global search capability, a max-min ant strategy is used. Finally, the path is optimized by the turning point optimization algorithm and dynamic cut-point method to improve path quality further. The simulation and experimental results based on MATLAB and ROS show that the proposed method can successfully solve the path planning and formation problem.
- multi-robot,
- leader follower-ant colony algorithm (LF-ACO),
- formation path planning,
- dynamic tangent point method
Citation: Liwei Yang, Lixia Fu, Ping Li, Jianlin Mao, Ning Guo, Linghao Du. LF-ACO: an effective formation path planning for multi-mobile robot[J]. Mathematical Biosciences and Engineering, 2022, 19(1): 225-252. doi: 10.3934/mbe.2022012

Related Papers:

Abstract

Multi-robot path planning is a hot problem in the field of robotics. Compared with single-robot path planning, complex problems such as obstacle avoidance and mutual collaboration need to be considered. This paper proposes an efficient leader follower-ant colony optimization (LF-ACO) to solve the collaborative path planning problem. Firstly, a new Multi-factor heuristic functor is proposed, the distance factor heuristic function and the smoothing factor heuristic function. This improves the convergence speed of the algorithm and enhances the smoothness of the initial path. The leader-follower structure is reconstructed for the position constraint problem of multi-robots in a grid environment. Then, the pheromone of the leader ant and the follower ants are used in the pheromone update rule of the ACO to improve the search quality of the formation path. To improve the global search capability, a max-min ant strategy is used. Finally, the path is optimized by the turning point optimization algorithm and dynamic cut-point method to improve path quality further. The simulation and experimental results based on MATLAB and ROS show that the proposed method can successfully solve the path planning and formation problem.

References

[1]	S. K. Tse, Y. B. Wong, J. Tang, P. Duan, S. W. W. Leung, L. Shi, Relative state formation-based warehouse multi-robot collaborative parcel moving, in 2021 4th IEEE International Conference on Industrial Cyber-Physical Systems (ICPS), IEEE, (2020), 375-380. doi: 10.1109/ICPS49255.2021.9468127.
[2]	J. P. Queralta, J. Taipalmaa, B. C. Pullinen, V. K. Sarker, T. N. Gia, H. Tenhunen, et al., Collaborative multi-robot search and rescue: planning, coordination, perception, and active vision, IEEE Access, 8 (2020), 191617-191643. doi: 10.1109/ACCESS.2020.3030190. doi: 10.1109/ACCESS.2020.3030190
[3]	Z. Li, Y. Yuan, F. Ke, W. He, C. Y. Su, Robust vision-based tube model predictive control of multiple mobile robots for leader-follower formation, IEEE Trans. Ind. Electro., 67 (2019), 3096-3106. doi: 10.1109/TIE.2019.2913813. doi: 10.1109/TIE.2019.2913813
[4]	C. Y. Kim, D. Song, Y. Xu, J. Yi, X. Wu, Cooperative search of multiple unknown transient radio sources using multiple paired mobile robots, IEEE Trans. Rob., 30 (2014), 1161-1173. doi: 10.1109/TRO.2014.2333097. doi: 10.1109/TRO.2014.2333097
[5]	L. Z. Du, S. Ke, Z. Wang, J. Tao, L. Yu, H. Li, Research on multi-load AGV path planning of weaving workshop based on time priority, Math. Biosci. Eng, 16 (2019), 2277-2292. doi: 10.3934/mbe.2019113. doi: 10.3934/mbe.2019113
[6]	J. Han, Y. Chen, Multiple UAV formations for cooperative source seeking and contour mapping of a radiative signal field, J. Intell. Rob. Syst., 74 (2014), 323-332. doi: 10.1007/s10846-013-9897-4. doi: 10.1007/s10846-013-9897-4
[7]	X. Zhang, J. Wang, Y. Fang, J. Yuan, Multilevel humanlike motion planning for mobile robots in complex indoor environments, IEEE Trans. Autom. Sci. Eng., 16 (2018), 1244-1258. doi: 10.1109/TASE.2018.2880245. doi: 10.1109/TASE.2018.2880245
[8]	B. Patle, A. Pandey, D. Parhi, A. Jagadeesh, A review: on path planning strategies for navigation of mobile robot, Def. Technol., 15 (2019), 582-606. doi: 10.1016/j.dt.2019.04.011. doi: 10.1016/j.dt.2019.04.011
[9]	X. Wang, X. Li, Z. Zheng, Survey of developments on multi-agent formation control related problems, Control Decis. (Chin.), 28 (2013), 1601-1613. doi: 10.13195/j.kzyjc.2013.11.026. doi: 10.13195/j.kzyjc.2013.11.026
[10]	Y. Gu, B. Seanor, G. Campa, M. R. Napolitano, L. Rowe, S. Gururajan, et al., Design and flight testing evaluation of formation control laws, IEEE Trans. Control Syst. Technol., 14 (2016), 1105-1112. doi: 10.1109/TCST.2006.880203. doi: 10.1109/TCST.2006.880203
[11]	Y. He, M. Wu, S. Liu, An optimisation-based distributed cooperative control for multi-robot manipulation with obstacle avoidance, IFAC Pap. Online, 53 (2020), 9859-9864. doi: 10.1016/j.ifacol.2020.12.2691. doi: 10.1016/j.ifacol.2020.12.2691
[12]	G. Liu, C. Shu, Z. Liang, B. Peng, L. Cheng, A modified sparrow search algorithm with application in 3d route planning for UAV, Sensors, 21 (2021), 1224. doi: 10.3390/s21041224. doi: 10.3390/s21041224
[13]	A. Chhillar, A. Choudhary, Mobile Robot Path Planning Based Upon Updated Whale Optimization Algorithm, in 2020 10th International Conference on Cloud Computing, Data Science & Engineering (Confluence), IEEE, (2020), 684-691. doi: 110.1109/Confluence47617.2020.9058323.
[14]	M. Dorigo, V. Maniezzo, A. Colorni, Ant system: optimization by a colony of cooperating agents, IEEE Trans. Cybern., 26 (1996), 29-41. doi: 10.1109/3477.484436. doi: 10.1109/3477.484436
[15]	Q. Luo, H. Wang, Y. Zheng, J. He, Research on path planning of mobile robot based on improved ant colony algorithm, Neural Comput. Appl., 32 (2020), 1555-1566. doi: 10.1007/s00521-019-04172-2. doi: 10.1007/s00521-019-04172-2
[16]	J. Liu, J. Yang, H. Liu, X. Tian, M. Gao, An improved ant colony algorithm for robot path planning, Soft Comput., 21 (2017), 5829-5839. doi: 10.1007/s00500-016-2161-7. doi: 10.1007/s00500-016-2161-7
[17]	X. You, S. Liu, C. Zhang, An improved ant colony system algorithm for robot path planning and performance analysis, Int. J. Rob. Autom., 33 (2018), 527-533. doi: 10.2316/Journal.206.2018.5.206-0071. doi: 10.2316/Journal.206.2018.5.206-0071
[18]	X. Dai, S. Long, Z. Zhang, D. Gong, Mobile robot path planning based on ant colony algorithm with A* heuristic method, Front. Neurorobotics, 13 (2019), 15. doi: 10.3389/fnbot.2019.00015. doi: 10.3389/fnbot.2019.00015
[19]	Z. Jiao, K. Ma, Y. Rong, P. Wang, H. Zhang, S. Wang, A path planning method using adaptive polymorphic ant colony algorithm for smart wheelchairs, J. Comput. Sci., 25 (2018), 50-57. doi: 10.1016/j.jocs.2018.02.004. doi: 10.1016/j.jocs.2018.02.004
[20]	K. Akka, F. Khaber, Mobile robot path planning using an improved ant colony optimization, Int. J. Adv. Rob. Syst., 15 (2018). doi: 10.1177/1729881418774673. doi: 10.1177/1729881418774673
[21]	J. Xin, M. Chuang, S. Frederik, P. Jinzhu, L. Yanhong, R. R. Negenborn, A time-space network model for collision-free routing of planar motions in a multirobot station, IEEE Trans. Ind. Inf., 16 (2020), 6413-6422. doi: 10.1109/TⅡ.2020.2968099. doi: 10.1109/TⅡ.2020.2968099
[22]	P. K. Das, S. B. Himansu, K. P. Bijaya, A hybridization of an improved particle swarm optimization and gravitational search algorithm for multi-robot path planning, Swarm Evol. Comput., 28 (2016), 14-28. doi: 10.1016/j.swevo.2015.10.011. doi: 10.1016/j.swevo.2015.10.011
[23]	P. K. Das, K. J. Prabir, Multi-robot path planning using improved particle swarm optimization algorithm through novel evolutionary operators, Appl. Soft Comput., 92 (2020), 106312. doi: 10.1016/j.asoc.2020.106312. doi: 10.1016/j.asoc.2020.106312
[24]	M. Nazarahari, E. Khanmirza, S. Doostie, Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm, Expert Syst. Appl., 115 (2018), 106-120. doi: 10.1016/j.eswa.2018.08.008. doi: 10.1016/j.eswa.2018.08.008
[25]	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. doi: 10.1142/S0217984920501377. doi: 10.1142/S0217984920501377
[26]	Y. Zheng, X. Li, D. Duan, A path planning method to maintain the team formation of Agent, Comput. Technol. Dev. (Chin.), 19 (2009), 159-162. doi: 10.3969/j.issn.1673-629X.2009.07.046. doi: 10.3969/j.issn.1673-629X.2009.07.046
[27]	T. Jiang, Z. Zhang, Z. Cheng, J. Li, J. Lu, Improved robot formation method with genetic algorithm and pilot-following method, Comput. Eng. Appl. (Chin.), 56 (2020), 240-245. doi: 10.3778/j.issn.1002-8331.1906-0376. doi: 10.3778/j.issn.1002-8331.1906-0376
[28]	Y. Dong, C. Fu, E. Kayacan, RRT-based 3D path planning for formation landing of quadrotor UAVs, in 2016 14th International Conference on Control, Automation, Robotics and Vision (ICARCV), IEEE, (2016), 1-6. doi: 10.1109/ICARCV.2016.7838567.
[29]	S. Liu, D. Sun, C. Zhu, A dynamic priority based path planning for cooperation of multiple mobile robots in formation forming, Rob. Comput. Integr. Manuf., 30 (2014), 589-596. doi: 10.1016/j.rcim.2014.04.002. doi: 10.1016/j.rcim.2014.04.002
[30]	D. Sun, C. Wang, W. Shang, G. Feng, A synchronization approach to multiple mobile robots in switching between formations, IEEE Trans. Rob., 25 (2009), 1074-1086. doi: 10.1109/TRO.2009.2027384. doi: 10.1109/TRO.2009.2027384
[31]	L. Wang, Z. Sui, Z. PU, Z. Liu, J. Yi, An improved RRT algorithm for multi-robot formation path planning, Acta Electonica Sin. (Chin.), 48 (2020), 2138. doi: 10.3969/j.issn.0372-2112.2020.11.007. doi: 10.3969/j.issn.0372-2112.2020.11.007
[32]	H. Wang, C. Hao, P. Zhang, M. Zhang, P. Yin, Y. Zhang, Path planning of mobile robots based on A* algorithm and artificial potential field algorithm, China Mech. Eng. (Chin.), 30 (2019), 2489. doi: 10.3969/j.issn.1004-132X.2019.20.012. doi: 10.3969/j.issn.1004-132X.2019.20.012
[33]	W. Zhang, Y. Ma, H. D. Zhao, L. Zhang, Y. Li, X. D. Li, Obstacle avoidance path planning of intelligent mobile based on improved fireworks-ant colony hybrid algorithm, Control Decis., 34 (2019), 335-343. doi: 10.13195/j.kzyjc.2017.0870. doi: 10.13195/j.kzyjc.2017.0870
[34]	H. Yang, J. Qi, Y. Miao, H. Sun, J. Li, A new robot navigation algorithm based on a double-layer ant algorithm and trajectory optimization, IEEE Trans. Ind. Electron., 66 (2018), 8557-8566. doi: 10.1109/TIE.2018.2886798. doi: 10.1109/TIE.2018.2886798
[35]	H. Zhang, L. He, L. Yuan, T. Ran, Path planning for mobile robots based on improved two-layer ant colony algorithm, Control Decis. Making (Chin.), (2021), 1-10. doi: 10.13195/j.kzyjc.2020.0610. doi: 10.13195/j.kzyjc.2020.0610

Reader Comments

Your name:*

Email:*
© 2022 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)