A Combinatorial Approach for Developing Ring Communication Graphs for Vehicle Formations

Abstract

In this paper, we study vehicle formations employing ring-structured communication strategies and propose a combinatorial approach for developing ring graphs for vehicle formations. In vehicle platoons, a ring graph is formed when each vehicle receives information from its predecessor, and the lead vehicle receives information from the last vehicle, thus forming a ring in its basic form. In such basic form, the communication distance between the first and the last vehicle increases with the platoon size, which creates implementation issues due to sensing range limitations. If one were to employ a communication protocol such as the token ring protocol, the delay in updating information and communication arises from the need for the token to travel across the entire graph. To overcome this limitation, alternative ring graphs which are formed by smaller communication distances between vehicles are proposed in this paper. For a given formation and a constraint on the maximum communication distance between any two vehicles, an algorithm to generate a ring graph is obtained by formulating the problem as an instance of the traveling salesman problem (TSP). In contrast to the vehicle platoons, generation of a ring communication graph is not straightforward for two- and three-dimensional formations; the TSP formulation allows this for both two- and three-dimensional formations with specific constraints. In addition, with ring communication structure, it is possible to devise simple ways to reconfigure the graph when vehicles are added/removed to/from the formation, which is discussed in the paper. Further, the experimental results using mobile robots for platooning and two-dimensional formations using ring graphs are shown and discussed.