Route design in sheepdog system–traveling salesman problem formulation and evolutionary computation solution–

In this study, we consider the guidance control problem of the sheepdog system, which involves the guidance of a flock using the characteristics of the sheepdog and sheep. Sheepdog systems require strategies to guide sheep agents to a goal area using small numbers of sheepdog agents, and various methods have been proposed. Previous studies have proposed a guidance control law to reliably guide sheep herds; however, the movement distance required by the sheepdog for guidance has not been considered. Therefore, in this study, we propose a novel guidance algorithm in which a supposedly efficient route for guiding a flock of sheep is designed via the traveling salesman problem and evolutionary computation. Numerical simulations were performed to confirm whether sheep flocks could be guided and controlled using the obtained guidance routes. We revealed that the proposed method reduces both the guidance failure rate and the guidance distance.