Distance Constrained Robotic Swarm Shepherding Based on Two-Phase Ant Colony Optimisation

Abstract

This paper investigates a swarm shepherding problem which aims to herd multiple sub-swarm of robot agents (sheep) in a large-scale cluttered environment to a specific goal area using multiple distance-constrained robots (sheepdogs) located at different depots. We propose to formulate this challenging problem as a Multi-depot, Distance-constrained Close-Open Mixed Vehicle Routing Problem (MDCOMVRP). We also design a Two-phase Ant Colony Optimisation to address it by decomposing MDCOMVRP into a Multi-depot Open Vehicle Routing Problem (MOVRP) and a split problem. In the first phase, the Max-Min Ant System algorithm is employed to find open routes for all robots by transforming the MOVRP into a standard Travelling Salesman Problem using the proposed transformation method. In the second phase, a Modified Split algorithm is presented to construct a set of close or open distance-constrained routes, which are further optimised by the 2-opt local search method to generate the optimised sequence for each sheepdog robot to collect/drive sheep sub-swarms. Experiments are conducted to demonstrate that the proposed algorithm can solve MDCOMVRP successfully and assist the robots to complete the swarm shepherding mission efficiently.