Decentralized Motion Coordination and Team Coherence

Motion Coordination

Approach and Motivation
Many different application areas can utilize decentralized control solutions for the traffic management of multiple vehicles. Examples include coordinated control of robots, such as UAVs, industrial automation systems, as well as collision avoidance assistance for manually controlled systems in congested regions, e.g., aircraft approaching airports, marine vessels at harbors, etc. Such problems introduce important challenges, including the need to design decentralized control laws with safety and liveness guarantees.

In relation to the above challenge, this work focuses on providing collision avoidance and completeness guarantees for multiple autonomous vehicles operating in the same obstacle-free space. The vehicles have to move from distinct, non-overlapping start configurations to their goals. These goals may be potentially overlapping but once a vehicle reaches its goal, it is no longer part of the coordination problem. For example: a scenario where multiple aircraft coordinate when flying at constant altitude. When an airplane reaches the vicinity of an airport, it initiates its landing maneuver and no longer constrains the remaining aircraft.

In this work, each vehicle uses only information from its local neighborhood. The information corresponds either to the observable position and orientation of nearby vehicles, or the communicated priority and destination of its neighbors. Modes corresponding to a hybrid automaton are employed that define the vehicle's high-level behavior, such as moving towards its goal, waiting for a neighbor to pass or avoiding another vehicle like the image above. A dynamic priority scheme is used to guarantee that at least one vehicle is always making progress towards its goal.
Two automata are working together so as to decide the best controls for the agent, so as to reach its goal safely without collisions. The first automaton is using, as input, the true direction to the goal. It computes a set of valid desired directions that the vehicle can move towards. Out of this set, the desired direction for the agent is chosen. These are used by the second hybrid automaton. The second automaton computes a valid set of achievable directions. Using the desired directions of the first automaton and the valid achievable directions, the vehicle computes the control for the agent.
An additional property of the approach is that there is communication between the agents. Every time that an agent is changing its behavior, it has to inform its neighbors with its new behavior. The behavior of an agent can be changed when either its priority changes, or the direction to its goal changes, or the mode that the agent is in changes. In order for the aircraft to have progress a Respected Area is computed for the robot. The lower priority agents has to respect and avoid his area, so as to allow the higher priority agent to have progress to its goal.
  • Extended Roundabout Policy for 60 Agents with 60 Different Targets
  • Generalized Roundabout Policy (GRP) vs Extended Roundabout Policy (ERP)
  • Landing Scenario using Extended Roundabout Policy (ERP)

Team Coherence

Approach and Motivation

Many multi-agent applications may involve a notion of spatial coherence. For instance, simulations of virtual agents often need to model a coherent group or crowd. Alternatively, robots may prefer to stay within a pre-specified communication range.

This paper proposes an extension of a decentralized, reactive collision avoidance framework, which defines obstacles in the velocity space, known as Velocity Obstacles (VOs), for coherent groups of agents. The extension, referred to in this work as a Loss of Communication Obstacle (LOCO), aims to maintain proximity among agents by imposing constraints in the velocity space and restricting the set of feasible controls.

If the introduction of LOCOs results in a problem that is too restrictive, then the proximity constraints are relaxed in order to maintain collision avoidance. If agents break their proximity constraints, a method is applied to reconnect them. The approach is fast and integrates nicely with the Velocity Obstacle framework. It yields improved coherence for groups of robots connected through an input constraint graph that are moving with constant velocity.

Simulated environments involving a single team moving among static obstacles, as well as multiple teams operating in the same environment, are considered in the experiments and evaluated for collisions, computational cost and proximity constraint maintenance. The experiments show that improved coherence is achieved while maintaining collision avoidance, at a small computational cost and path quality degradation.


Although VOs are not designed to maintain coherence of agents, it is still the most relevant method to compare against, due to both approaches being decentralized and sharing the exact same information constraints.

Related Publications


This work has been supported by NSF CNS 0932423. Any opinions and findings expressed in this paper are those of the authors and do not necessarily reflect the views of the sponsor.

People Involved