A Decentralized Approach to Space DeconflictionPaul Scerri, Sean Owens, Bin Yu, and Katia SycaraSchool of Computer ScienceCarnegie Mellon UniversityPittsburgh, PA 15213, USA{pscerri, owens, byu, katia}@cs.cmu.eduAbstract—This paper presents a decentralized approach topath planning for large numbers of autonomous vehicles insparse environments. Unlike existing approaches, which areeither computationally expensive or communication intensive, thepresented approach allows large numbers of vehicles to planindependently with low communication overhead. The key to thealgorithm is to observe that, in sparse environments, collisionsare exceptional and that most of the time vehicles will simply nothit each other. Hence, it is reasonable to allow vehicles to planindependently and then resolve the small number of conflicts.We operationalize this by having each vehicle send their plannedpaths to a small number of their team mates via tokens.Eachteam member is required to check for conflicting paths that theyhave been informed about via a token and inform those involvedwhen any conflict is detected. Both analytic and empirical resultsshow that the approach has very high probability of detectingall potential collisions for large numbers of vehicles in both 2Dand 3D environments.I. INTRODUCTIONIn emerging applications, large numbers of cooperative au-tonomous vehicles, such as autonomous ground vehicles [1] orunmanned aerial vehicles (UAVs) [2], will be required to sharethe same physical space. Of particular interest are domainswhere many sensor assets are simultaneously working in ashared environment. A critical challenge in such applicationsis to plan paths that ensure collisions do not occur as vehiclesmove around. While there are many applications with differentspecific requirements, this paper focuses on ones where thereare up to 100s of vehicles performing time-critical missions,e.g., disaster response [3], [4] and battlefield operations [5],[6], in a relatively sparse 2D or 3D environment. Noticethat fast moving vehicles typically do not have sensors onboard to detect collisions sufficiently far in advance to safelyavoid the collision. This is particularly the case for small andmedium sized UAVs which have no ability to detect othersimilarly sized UAVs. Without such sensors, the vehicles mustproactively cooperate to avoid collisions.Recently, a number of researchers have looked at real-timecooperative path planning for multiple fast-moving vehiclessuch as UAVs, but typically in a centralized and computation-ally expensive manner [5], [7], [8], [9], [10]. Most previouswork casts the problem as a centralized optimization problemand many solve it using linear programming techniques. Anotable exception is [7], however, that approach does notconsider the communication overhead of the broadcast forsharing the path information among vehicles and is impracticalfor large teams. Hence, despite much research into path plan-ning, there are not readily available solutions for environmentswhere many vehicles must share an environment.The main reason why most previous approaches are ineffi-cient is they attempt to ensure that the planner has completeknowledge prior to planning, so that it will never plan a paththat will conflict with another vehicle. However, in sparseenvironments, we observe that collisions between vehicles willbe the exception rather than the rule. That is, even if vehiclesmoved without consideration of one another, extended periodsmight pass without a collision occurring. Thus, we hypothesizethat it will be more efficient to plan paths independently, thenresolve conflicts, rather than to gather information about allvehicle paths before planning. Such an approach can allowdistributed planning but still ensure collision free paths withlow communication overhead.Motivated by recent work on token passing algorithms [11],[12], we have developed a token-based approach to detectingpath conflicts in a distributed manner. Specifically, when avehicle plans a path, it creates a token encapsulating its pathand sends it to one of its team mates. That team mate checksthe path to determine whether it conflicts with any other pathsthat it knows about and, if not, passes the token to anotherteam mate. This process continues until either a conflict isfound or the token has been passed to a fixed, small numberof team mates. If a conflict is found, the vehicles with theconflicting paths are notified and generate new, non-conflictingpaths. Vehicles plan slightly in advance of when their plans areneeded, to allow time for conflicts to be detected and resolved.In this paper we present an efficient conflict free pathplanning algorithm for large numbers of autonomous vehi-cles with various kinematic constraints in both 2D and 3Denvironments. Additionally, we provide a quantitative studyof token movements for collision detection applying randomwalk theory to the communication graphs. We demonstratethat, for a given team, a lower bound on the number ofagent a token must visit can be determined, so that tokenscontaining conflicting paths will meet at some vehicle withvery high probability. We validate the proposed algorithm withtwo different path planners and both 2D and 3D simulation en-vironments containing both stationary and dynamic obstacles.Both analytic and empirical results show that our approachhas very high probability of detecting all potential collisionsfor large numbers of vehicles.II. PROBLEMIn the following, we formally describe the cooperative pathplanning problem. Vehicles V = {v1,...,vn} are able tomove around some 2D or 3D environment. The communi-cation network connecting the team is a connected undirectedgraph G =(V,E),whereE is the set of links between vehi-cles.1For vi,vj∈ V , vi,vj ∈E denotes that vehicles viandvjare neighbors and are able to exchange tokens directly. Theenvironment contains stationary obstacles, O = {o1,...,on}.A predicate intersects(x, y, z ,oi) →{true, false} is trueif and only if the stationary obstacle oidoes not allow thevehicle to be at location x, y, z .We define L(vi,tk)=(x, y, z ,tk) as the location of thevehicle viat time tk. The path planning algorithm must finda continuous path, Γ(vi)=L(vi,t0), L(vi,t1),...L(vi,tg) satisfying kinematic constraints on the vehicle and ending atthe vehicle’s destination. L(vi,t0)=siis the start locationof the vehicle and L(vi,tg)=giis the goal location of thevehicle. Paths must not intersect with