Coordination of Multiple Autonomous Vehicles with Directed Communication Graphs

Abstract

A considerable amount of research has been conducted on coordination control of vehicle formations in the last few decades due to its possible applications in numerous areas, such as patrolling, search and rescue, vehicle platoons, etc. Information flow between vehicles is vital for the formation to function properly. Controllability and stability of the formation depends on the type of information flow that is employed between vehicles. This work focuses on using a type of directed communication graph, called the ring graph, for coordination control of vehicle platoons. A detailed study of literature is undertaken to clearly understand the limitations of the various types of undirected graphs in terms of stability and scalability. The use of ring graph in vehicle platoons is investigated. The problems associated with the ring graph in its basic form related to communication sensor range and the scalability of ring graph are investigated. Methods to create a ring graph topology that requires minimal communication distance over a given formation are also investigated. A survey of literature was undertaken to investigate the formulation of the Traveling Salesman Problem (TSP), constraints involved in TSP, methods to solve TSP including exact and approximate algorithms. The problem of finding a ring graph for a given vehicle formation is addressed by formulating this problem as a special case of the TSP. Properties such as stability and scalability of the formation with a controller based on the ring graph are studied. Lack of scalability of the controller that is based on the ring graph is discussed. Alternate ring graph topologies which address the practical issues such as communication range of transmitters are proposed. Simulations which show that the alternate ring graphs have similar properties as the basic ring graph are carried out. Controller based on multiple ring graphs on a vehicle platoon and its advantages over the single ring topologies are studied. An algorithm based on the branch and bound method is proposed to solve the modified TSP and to generate a ring graph for the given vehicle platoons, or two- and three-dimensional vehicle formations. An experimental platform consisting of multiple homogeneous autonomous robots is developed. A coordination controller using ring graph is implemented on the experimental platform and results for a number of platoon initial condition scenarios are presented.