Virtual Spring-Based
3D Multi-Agent
Group Coordination
Roozbeh Daneshvar and Liwen Shih
School of Science and Computer Engineering
University of Houston Clear Lake, Houston, TX
roozbeh@[Link], shih@[Link]
As future personal vehicles start enjoying the ability to fly, tackling safe trans-
portation coordination can be a tremendous task, far beyond the current chal-
lenge on radar screen monitoring of the already saturated air traffic control.
Our focus is on the distributed safe-distance coordination among a group of au-
tonomous flying vehicle agents, where each follows its own current straight-line
direction in a 3D space with variable speeds. A virtual spring-based model is
proposed for the group coordination. Within a specified neighborhood radius,
each vehicle forms a virtual connection with each neighbor vehicle by a vir-
tual spring. As the vehicle changes its position, speed and altitude, the total
resultant forces on each virtual spring try to maintain zero by moving to the me-
chanical equilibrium point. The agents then add the simple total virtual spring
constraints to their movements to determine their next positions individually.
Together, the multi-agent vehicles reach a group behavior, where each of them
keeps a minimal safe-distance with others. A new safe behavior thus arises in
the group level. With the proposed virtual spring coordination model, the vehi-
cles need no direct communication with each other, require only minimum local
processing resources, and the control is completely distributed. New behaviors
can now be formulated and studied based on the proposed model, e.g., how a
fast driving vehicle can find its way though the crowd by avoiding the other
vehicles effortlessly1 .
1 Introduction
Multi agent systems offer many potential advantages with respect to single-agent
systems such as speedup in task execution, robustness with respect to failure of
one or more agents, and scalability [17]. The role of larger multi-agent sys-
tems has become more significant in recent years, due to lower cost for simpler
agents and increased potential group capabilities in robustness and flexibility.
These newly evolved, highly complex large-scaled multi-agent systems demand
improved interaction study and innovated group coordination approaches. De-
spite these initial efforts, further investigations are desperately needed in this
new group emergence paradigm. In the following, we will first review the current
progress in multi-agent coordination field, and then propose a Virtual-Spring
based group coordination to cope with the increased complexity, as the problem
scaled to many more agents in 3D.
1.1 Flying Vehicles
A multi-agent System for formation flying missions is proposed in [19] and for
collaborative sensing, multiple Unmanned Aerial Vehicles (UAVs) are considered
in [18].Methods for optimizing the task allocation problem for a fleet of UAVs
with tightly coupled tasks and rigid relative timing constraints are described
in [2]. Minimization of the mission completion time for the fleet is the overall
objective in this work that uses timing constraints and loitering. The problem
of decentralized task assignment for a fleet of cooperative UAVs is considered
in [1] which extends the analysis of the algorithm of previous work to consider
the performance with different communication network topologies. In [9], [7]
and [10] cooperative UAV routing with limited sensor range is considered (the
problem for one UAV is investigated in [8]).
1.2 Spatial Multi Agent Systems and their Coordination
Multi agent coordination techniques are used in various tasks like Air Traffic
Management [16] while there are several decentralized algorithms like [13] for
aircraft-like vehicles. Air Traffic Management of the future allows for the possi-
bility of free flight, in which aircrafts choose their own optimal routes, altitudes,
and velocities. The safe resolution of trajectory conflicts between aircraft is nec-
essary to the success of such a distributed control system [21]. In [14] it is tried
to capture the idea that the less coordination a multi-robot system requires, the
better it should scale to large numbers of robots. In [6] the real-time multi-agent
coordination and control requirements of automobile and submarine systems are
discussed. The use of hybrid systems techniques for analyzing and synthesizing
1 Any kind of military uses from the content and approaches of this article is against the
intent of the authors.
the control architectures have been under investigation. Also in [12] a method
for cooperative control in a distributed autonomous robotic system is proposed.
A reactive navigation strategy is used for controllers of robots by combining
repulsion from obstacles with attraction to a goal. A class of dynamic vehicle
routing problems (in which a number of mobile agents in the plane must visit
target points generated over time by a stochastic process) are considered in [4].
The aim has been to minimize the expected time between the appearance of a
target point and the time it is visited by one of the agents by making minimal or
no assumptions on communications between agents. It is shown that inter-agent
communication does not improve the efficiency of such systems, but merely af-
fects the rate of convergence to the steady state. In [17] a policy for steering
multiple vehicles between assigned independent start and goal configurations is
proposed which ensures collision avoidance. The decentralized policy rests on
the assumption that agents are all cooperating by implementing the same traffic
rules (each agent decides its own motion by applying those rules only on locally
available information). In [5], formations of robots are considered. In this work
a motion plan for the overall formation is used to control a single leader and the
followers use local control laws.
A simulation environment for massive systems is proposed in [3] which is
capable of coping with 3D environments. In [15] an approach to qualitative
spatial orientation reasoning in 3-dimensional spatial environment is proposed.
The problem of positioning a group of autonomous but coordinating mobile
robots into a specified spatial configuration is considered in [11]. In this work
there is no central controller or inter-agent communication. The robots move
into position without collision or unnecessary delay. A hierarchical controller
with three levels (Execution, Coordination and Organization) has been adopted
in their approach.
2 Spatial Coordination using Spring Forces
A virtual street is built for flying vehicles as shown in Fig.1. This environment
is made with NetLogo program [22]. In this program a setup code specifies the
initial positions and orientations. The group of agents moves in a 3D space and
the behavior of each agent for every time step is defined by a piece of code.
One of the approaches is to use virtual springs for coordination of agents.
This idea has been used for coordination of soccer simulation footballers in [20]
in which each of the players was constrained with a group of springs with other
teammates. As a result, the team demonstrated group behaviors that met the
desired criteria.
An agent is constrained by a group of springs that specify the later position of
the agent in the space (This applies similarly to both 2D and 3D environments).
The length, stiffness and the total number of the springs can vary from agent to
agent depending on the environments, systems, and designers. Under a group
of forces, an agent moves until the total resultant forces (vectors) becomes zero
on the agent. When the spring forces are applied to an agent, the total applied
Figure 1: The virtual street with some flying vehicles in the two sides (left) and
spatial coordination of vehicles (right)
force is calculated with Eq.1.
n
X ∆Li × Ki × (Xi − XA )
Fx =
i=1
Di
n
X ∆Li × Ki × (Yi − YA )
Fy =
i=1
Di
n
X ∆Li × Ki × (Zi − ZA )
Fz = (1)
i=1
Di
in which XA , YA and ZA specify present position of agent, n is the number of
factors the agent has spring connections with (for this case it is equal to the
number of neighbors), Li is the length of the spring with ith factor, Ki is the
constant of that spring, Di is the distance to the ith factor and (Xi , Yi ) specify
the position of the ith point.
Hence the agent moves towards the direction of the applied force to get closer
to the mechanical equilibrium point. This changes the position of the agent and
is able to play a role in the coordination of the group (the agent has only observed
the positions of the neighbors). The proposed spring-based model is dimension
scalable, where no extra effort is needed for agents to make movement decisions
extending from 2D to 3 D space (see Fig.1).
Agents with different velocities show different behaviors for finding their
paths (according to their relative velocity to other members of the group). As
an example, Fig.2 illustrates how the fastest agent overtakes the other slow
agents and how the inter-agent distances change in time. It shows that how the
agent driving faster than others, overtakes the other slower agents and how the
distances change during time.
3 Benefits of Spring-Based Group Coordination
Compared with the current, generally pre-fixed and centrally controlled multi-
agents group coordination, the benefits of the proposed spring-based method are
detailed as follows:
• Swift Mutual Collision Avoidance Sometimes the path for an agent
with a velocity higher than the others is blocked by front agents (as in
Fig.3). In this case if the agents use spring forces, they not only maneuver
their paths to squeeze through the crowd, they are also able to affect other
agents without communicating with them directly. When the agent with
higher velocity gets too close to other neighbors, they change to yield their
positions respectively (to move to the new mechanical equilibrium point)
and hence new space for the agent is made so that it can overtake.
• Simple New Agents Inclusion to the Group When new vehicles want
to join the group of agents, by the spring method they can enter the group
just by setting new positions in the space (probably in the group) as their
set points. If their positions were fixed in the group, a new vehicle should
have waited for an available empty space to join the 3D street.
• Easy 3D Maneuver When a vehicle wants to move horizontally or ver-
tically (X or Z directions, if considering the direction of street as Y) it
only needs to move to that direction slowly while obeying the same coor-
dination process. This forces other neighbors to leave more room for the
vehicle to change its position. A sample is shown in Fig.2 in which the
agent is moving to the right constantly and for some periods it has to find
its path (for demonstration purposes, the agent is moved to the left most
position when it reaches the right most limit).
4 Conclusion
In this article, we investigated a Virtual-Spring based group coordination model
in 3D environments. The main aspect considered in this model was to demon-
strate how collision-avoidance group level behaviors emerge from the interactions
of agents with their individual safe-distance minded behaviors.
Bibliography
[1] Alighanbari, Mehdi, and Jonathan P. How, “Robust decentralized task
assignment for cooperative uavs”, AIAA Guidance, Navigation and Control
Conference, (2006).
Figure 2: Distances of two normal agents from the agent which has the most velocity
in the group (top), Distances of two normal agents from the agent which has the most
velocity in the group (middle) and the X value for an agent which drives to the right
at each step beside doing coordination (bottom)
Figure 3: The agent with white color is behind the other three agents who have
blocked the way
[2] Alighanbari, Mehdi, Yoshiaki Kuwata, and Jonathan P. How, “Coordi-
nation and control of multiple uavs with timing constraints and loitering”,
IEEE American Control Conference, (June 2003).
[3] Aoyagi, Masaru, and Akira Namatame, “Massive multi-agent simula-
tion in 3d”, Soft Computing as Transdisciplinary Science and Technology,
Springer (2005), 260–272.
[4] Arsie, A., and E. Frazzoli, “Efficient routing of multiple vehicles with no
communications”, International Journal of Robust and Nonlinear Control
(2006), To appear.
[5] Desai, J. P., J. Ostrowski, and V. Kumar, “Controlling formations of
multiple mobile robots”, Proceedings of the IEEE International Conference
on Robotics and Automation (Leuven, Belgium, ), (May 1998), 2864–2869.
[6] Deshpande, A., and J. de Sousa, “Real-time multi-agent coordination
using diadem 5 : Applications to automobile and submarine control” (1997).
[7] Enright, J.J., E. Frazzoli, K. Savla, and F. Bullo, “On multiple
UAV routing with stochastic targets: Performance bounds and algorithms”,
Proc. of the AIAA Conf. on Guidance, Navigation, and Control (San Fran-
cisco, CA, ), (August 2005).
[8] Enright, J. J., and E. Frazzoli, “UAV routing in a stochastic, time-
varying environment”, Proc. of the IFAC World Congress (Prague, Czech
Republic, ), (July 2005).
[9] Enright, John J., and E. Frazzoli, “Cooperative uav routing with lim-
ited sensor range”, AIAA Conf. on Guidance, Navigation, and Control
(Keystone, CO, ), (August 2006), Paper AIAA-2006-6208.
[10] Frazzoli, E., “Maneuver-based motion planning and coordination for mul-
tiple UAVs”, Proc. of the AIAA/IEEE Digital Avionics Systems Conference
(Irvine, CA, ), (2002).
[11] Gold, Timothy B., James K. Archibald, and Richard L. Frost, “A util-
ity approach to multi-agent coordination”, IEEE International Conference
on Robotics and Automation (San Francisco, CA, ), (April 2000).
[12] Hang, Seong-Woo, Shang-Woon Shin, and Doo-Sung Ahn, “Formation
control based on artificial intelligence for multi-agent coordination”, Pro-
ceedings of the IEEE ISIE 2001 (Pusan, Korea, ), (2001).
[13] Inalhan, Gokhan, Dusan Stipanovic, and Claire J. Tomlin, “Decen-
tralized optimization, with application to multiple aircraft coordination”,
41st IEEE Conference on Decision and Control (Las Vegas, NV, ), IEEE,
(December 2002).
[14] Klavins, Eric, “Communication complexity of multi-robot systems”, Al-
gorithmic Foundations of Robotics V, (J.-D. Boissonnat, J. Burdick,
K. Goldberg, and S. Hutchinson eds.) vol. 7 of Springer Tracts in
Advanced Robotics. Springer (2003), pp. 275–292.
[15] Liu, Jianhui, “Qualitative orientation reasoning in spatial multi-agent en-
vironment.”, IAT, (2005), 266–272.
[16] Nguyen-Duc, Minh, Jean-Pierre Briot, and Alexis Drogoul, “An
application of multi-agent coordination techniques in air traffic manage-
ment”, Proceedings of the IEEE/WIC International Conference on Intelli-
gent Agent Technology (IAT03), (2003).
[17] Pallottino, L., V.G. Scordio, E. Frazzoli, and A. Bicchi, “Decen-
tralized cooperative policy for conflict resolution in multi-vehicle systems”,
IEEE Trans. on Robotics (2007), To appear.
[18] Parunak, H. Van Dyke, Sven A. Brueckner, and James J. Odell,
“Swarming coordination of multiple uavs for collaborative sensing”, Sec-
ond 2ND AIAA Unmanned Unlimited Systems Technologies and Operations
Aerospace Land and Sea Conference and Workshop and Exhibit (San Diego,
CA, ), (September 2003).
[19] Sanda Mandutianu, Fred Hadaegh, and Paul Elliot, “Multi-agent sys-
tem for formation flying missions”.
[20] Sharbafi, Maziar, Roozbeh Daneshvar, and Caro Lucas, “New implicit
approach in coordination between soccer simulation footballers”, Fifth Con-
ference on Computer Science and Information Technologies (CSIT 2005)
(Yerevan, Armenia, ), (September 2005).
[21] Tomlin, Claire J., George J. Pappas, and Shankar Sastry, “Conflict res-
olution for air traffic management: A study in multi-agent hybrid systems”,
IEEE Transactions on Automatic Control 43, 4 (April 1998).
[22] Wilensky, Uri, “NetLogo: Center for connected learning and computer-
based modeling, Northwestern University. Evanston, IL” (1999).