Vehicle formations using directed information flow graphs

In this paper, we investigate vehicle formations using a ring graph. A ring graph is a directed graph with a unique path for communication between any two vehicles in the formation. In vehicle platoons, a ring type directed information flow graph is formed when each vehicle receives information from its predecessor and the first vehicle receives information from the last vehicle, thus forming a communication ring in its basic form. In such basic form of the ring information structure, the communication distance between the first and the last vehicle increases with platoon size, which creates implementation issues. To overcome this limitation, alternative ring graphs which keep the ring structure but allow for smaller communication distances between vehicles are studied in this paper. If one were to employ a communication protocol such as the token ring protocol, the delay in updating information and communication arise from the need for the token to travel across the information flow graph. For a given formation and a constraint on the maximum allowable communication distance between any two vehicles, an algorithm to create an alternative ring graph can be obtained by formulating this problem as an instance of the traveling salesman problem (TSP); this follows because of the similarity between a ring graph and a Hamiltonian cycle. In addition to vehicle platoons, this algorithm can also be used for two- and three-dimensional formations. An experimental setup consisting of four differential drive mobile robots is used to conduct formation experiments with the basic and alternative ring graphs; a sample of these results will be shown and discussed. We also discuss scalability issues related to ring graphs and conclude with a summary of this work.