Modified continuous Ant Colony Optimisation for multiple Unmanned Ground Vehicle path planning

• Published in: Expert systems with applications 2022-06, Vol.196, p.116605, Article 116605
• Main Authors: Liu, Jing, Anavatti, Sreenatha, Garratt, Matthew, Abbass, Hussein A.
• Format: Article
• Language: English
• Subjects: ACO; Algorithms; Ant Colony Optimisation; Ant colony optimization; Collision avoidance; Coordination; multi-UGV; Multiagent systems; Path planning; Planning; Repair; Strategy; Unmanned Ground Vehicles; Waypoints
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2022.116605

Path planning for multiple Unmanned Ground Vehicles (UGVs) is a critical problem for UGV autonomy and is increasingly attracting attention due to its wide applications. This paper presents a continuous ant colony-based multi-UGV path planner, which consists of UGV path planning and multi-UGV coordination. A continuous Ant Colony Optimisation with a Probability-based random-walk strategy and an Adaptive waypoints-repair method (ACOPAR) is proposed to optimise the path for each UGV. Collision avoidance among the UGVs for the multi-agent coordination problem is then resolved via a velocity shifting optimisation algorithm. In ACOPAR, exploration and exploitation are balanced using a probability-based random-walk strategy switching between a Brownian and a Cauchy motion to modify the construction process of new solutions. An adaptive waypoints-repair strategy and a re-initialisation strategy are designed to improve the algorithm’s performance in finding feasible paths. A test suite of multi-UGV path planning with 12 cases is proposed to evaluate the search capability and scalability of the proposed ACOPAR compared to other algorithms. Experimental results validate the superiority of ACOPAR, especially when solving complex, high-dimensional problems. •A new ACOPARis designed for optimising the path for each UGV.•A new random-walk strategy switching between Brownian and Cauchy motion is designed.•Adaptive waypoints-repair-strategy to improve search accuracy and scalability.•Multi-agent coordination is designed to avoid the collision among UGVs.•Experiments validate the superiority of ACOPAR, especially on complex problems.