Recent advances in the miniaturization of computing, communication, sensing, and actuation have made it feasible to envision large numbers of autonomous vehicles—air, ground, and water—working cooperatively to accomplish an objective. However, communication bandwidth and power constraints will preclude centralized command and control.

“This paper describes a new discovery that extends previous results in information consensus to the case of directed or one-way communication, and explores the minimum requirements sufficient to reach consensus.”

This paper addresses the problem of information consensus, where a team of vehicles must agree on key pieces of information to enable them to work together in a coordinated fashion. The problem is particularly challenging because communication channels have limited range and experience fading and drop-out.

The study of information flow and interaction among multiple autonomous vehicles in a group plays an important role in understanding the coordinated movements of these vehicles. As a result, a critical problem for coordinated control is to design appropriate protocols and algorithms such that the group of vehicles can reach consensus on the shared information in the presence of limited and unreliable information exchange and dynamically changing interaction topologies.

This paper addresses the general case of dynamically changing directed interaction topologies. Since the information consensus problem is a central issue in the design of distributed coordination strategies for multiple autonomous vehicles, it has received significant attention.

This paper describes a new discovery that extends previous results in information consensus to the case of directed or one-way communication, and explores the minimum requirements sufficient to reach consensus. To make this contribution, the paper extends the famous Perron-Frobenius Theorem in matrix theory to reducible matrices.

In particular, we show that under certain assumptions information consensus can be achieved asymptotically under dynamically changing communication links if the union of the collection of directed communication links across repeatable time intervals has a directed spanning tree. The directed spanning tree requirement is a milder condition than connectedness and is therefore more suitable for practical applications. We also allow the relative weighting factors among vehicles to be time-varying, which provides additional flexibility.

Suppose that a large group of friends has a tradition of meeting for dinner at a certain location on a particular day during the year. As the date approaches, they need to communicate with each other to decide the time to meet for dinner. Suppose also, that each individual only knows the phone numbers of a small subset of the group. Since members of the group are very busy, the only mode of communication is to leave messages on voice mail. What strategy should each individual use to ensure that the entire group agrees on the time to meet for dinner? This paper essentially addresses that problem.

Agreeing on a common time is an information consensus problem. Leaving voice messages is a form of one-way communication. The fact that a conference call is not possible, and that communication only occurs between small groups of friends, one a time, implies a dynamically changing, locally connected communication network.

The essential result in this paper is that if each friend decides on a time for dinner, and then averages his or her decision with his or her friends’ decisions, and then subsequently communicate that new data the next time they communicate, then the group will come to consensus if there exists at least one individual whose information is eventually passed to all of the other individuals, either directly or indirectly—i.e., your friend knows a friend who knows a friend, etc.

Our interest in this problem was motivated by our research efforts in coordinated control of multiple unmanned air vehicles (UAVs). Air vehicles are constantly moving and consequently their ability to communicate is dynamically changing. In addition, in current military scenarios involving UAVs, large assets like the high-altitude, long-endurance Globalhawk may have two way communication capabilities, but small micro air vehicles may only have the ability to receive commands. Therefore, we were motivated to study decentralized coordination problems where the communication network was noise, time-varying, and possibly uni-directional.

The research in distributed coordination of multiple autonomous vehicles has potential technical impact in numerous civilian, homeland security, and military applications. In civilian applications, the research results can be applied to monitoring forest fires, oil fields and pipelines, and tracking wildlife. In homeland security applications, the research results can be applied in border patrol and monitoring the perimeter of nuclear power plants. In military applications, the research results can be applied in surveillance, reconnaissance, and battle damage assessment.