Fair Path Generation for Multiple Agents Using Ant Colony Optimization in Consecutive Pattern Formations

Abstract

This study proposes a method to automatically generate paths for multiple autonomous agents to collectively form a sequence of consecutive patterns. Several studies have considered minimizing the total travel distances of all agents for formation transitions in applications with multiple self-driving robots, such as unmanned aerial vehicle shows by drones or group actions in which self-propelled robots synchronously move together, consecutively transforming the patterns without collisions. However, few studies consider fairness in travel distance between agents, which can lead to battery exhaustion for certain agents and thereafter reduced operating time. Furthermore, because these group actions are usually performed with a large number of agents, they can have only small batteries to reduce cost and weight, but their performance time depends on the battery duration. The proposed method, which is based on ant colony optimization (ACO), considers the fairness in distances traveled by agents as well as the less total traveling distances, and can achieve long transitions in both three- and two-dimensional spaces. Our experiments demonstrate that the proposed method based on ACO allows agents to execute more formation patterns without collisions than the conventional method, which is also based on ACO.