Sage Journals: Discover world-class research

Abstract

Obstacle avoidance is a critical issue in autonomous agent spatial navigation, moreover in the case of team coordinated navigation with moving obstacles. Algorithms for obstacle avoidance by unconstrained teams of agents, i.e. agents that have no relative position restrictions, such as the Reciprocal Velocity Obstacle (RVO), and the Hybrid Reciprocal Velocity Obstacle (HRVO) have been proposed in the literature. However, in some tasks the agents must comply with relative spatial restrictions, i.e. agents must maintain specific distances between them within some tolerance thresholds. These tasks include robotic team coordination, human-robot collaboration and autonomous vehicle platooning. This paper presents a novel Extended Hybrid Reciprocal Velocity Obstacle (EHRVO) algorithm for multi-agent collision avoidance that incorporates linked agent constraints. The proposed approach introduces proximity constraints between paired agents while adapting the collision avoidance geometry to maintain these relationships. This research work extends the HRVO framework to create a hierarchical set of constraints that prioritize maintenance of spatial consistent agent pairs or triads while ensuring collision-free trajectories. Prior to actual physical implementation, the EHRVO navigation algorithm is validated through exhaustive simulations involving multiple paired agents and triads navigating in cluttered spaces with many moving obstacles, namely the agents in the other teams. Results demonstrate that this novel approach successfully maintains the spatial relative positions of linked group agents while avoiding collisions with other agents, showing significant improvements over traditional RVO and HRVO algorithms in scenarios requiring coordinated movement.

Keywords

Multi-agent obstacle avoidance robotics constraints RVO

1. Introduction

The issue of collision avoidance in the navigation of multi-agent systems has been a central concern since the early works on this area, because it has been recognized that solving it is critical for both safety and system preservation.^1,2 As robotics applications expand into diverse civilian domains, the newly created multiagent systems must navigate in an increasingly coordinated manner in dynamic environments while maintaining reliability and safety. This challenge is further compounded in scenarios where communication infrastructure is inconsistent, disrupted, or potentially compromised, requiring robust solutions that can operate under uncertainty.³

The growing deployment of autonomous systems in real-world applications has highlighted the need for more sophisticated collision avoidance strategies that can handle complex interactions between agents. Traditional approaches have considered each agent as an independent entity, but many practical applications require agents to maintain specific relationships or formations while avoiding collisions.^4,5 This creates an additional layer of complexity in the collision avoidance problem that has not been addressed in the existing literature^6–8 Recent advances in continual learning have demonstrated the effectiveness of ensemble-based approaches for handling complex multi-agent scenarios, where selectively trained experts can adapt to different task conditions while maintaining system stability,⁹ suggesting potential applications to dynamic multi-agent navigation challenges.

Collision avoidance strategies typically fall into one of two categories: cooperative and non-cooperative approaches.^10,11 While both categories assume some prior knowledge of object geometry, they differ in their communication requirements. Cooperative strategies rely on the explicit communication of agent intentions, enabling coordinated movements but requiring reliable communication infrastructure. In contrast, non-cooperative approaches operate with limited knowledge, relying only on locally sensed kinematic data. This latter scenario reduces to a localized Sense, Detect, and Avoid (SDA) problem,^12,13 which is particularly relevant in uncharted or communication-constrained environments.

The SDA problem has been tackled following various approaches. Probabilistic modelling techniques¹⁴ account for uncertainties in sensor measurements and motion predictions. Trajectory optimization approaches^12,15–17 seek to find optimal paths while satisfying multiple constraints. Potential field methods^18,19 create virtual force fields around obstacles, as shown in Figure 1. Geometry-based techniques^20,21 construct explicit collision avoidance regions. Among these, the Velocity Obstacle (VO) approach that introduces the concept of Collision Cones (CC)²² has gained significant traction in the multi-agent community. Its popularity stems from two key factors: first, the intuitive geometric construction of collision constraints, and, second, the ability to determine the velocity vectors that avoid the collision efficiently requiring minimal obstacle information.²³ This approach has been proven particularly effective in real-time applications where computational efficiency is crucial.²⁴

Figure 1.

Schematic drawing of obstacle avoidance approach with potential field.

The most relevant variants of the VO algorithm are the following ones. Reciprocal Velocity Obstacles (RVO)^10,23,25,26 reduces oscillatory paths by considering the reactive nature of agents, leading to smoother trajectories. Acceleration Velocity Obstacles (AVO)²⁷ extends the VO algorithm to handle varying accelerations, making the approach more suitable for dynamic environments. Optimal Reciprocal Collision Avoidance (ORCA)^28,29 uses half-planes as linear constraints to guarantee smooth trajectories while maintaining computational efficiency. Kinematic Velocity Obstacles (KVO)³⁰ incorporates additional kinematic constraints, making the approach more realistic for physical systems. Nonlinear motion handling³¹ uses nonlinear descriptions of agent and obstacle motion for increased accuracy. Hybrid-Reciprocal Velocity Obstacles (HRVO)^20,32 aims to eliminate directional ambiguity and the “reciprocal dance” phenomenon, improving the stability of avoidance manoeuvres.

The work reported in this paper extends the HRVO approach by considering collision avoidance for paired or linked multi-agent systems, as can be seen in Figure 2, introducing a novel inner-group spatial constraint previously disregarded in the literature. This constraint requires certain agents to maintain a fixed spatial distance to their partners while avoiding collisions with other agents (belonging either to the same or to an external group) and obstacles, creating a hierarchical set of constraints that must be satisfied simultaneously. This innovation enables more complex and realistic simulations of interdependent multi-agent systems^3,33 and we call it Extended HRVO (EHRVO).

Figure 2.

Two paired agents (above) and a single agent (below). Agents are represented as quadrotors.

Which applications do require these new constraints for modelling the actual operation of the multi-agent system? We can mention a few: teams of unmanned autonomous vehicles (UAV) performing formation-based search and rescue operations require maintaining specific geometric relationships for effective area coverage; human-robot collaborative tasks in manufacturing or healthcare settings demand continuous coordination between paired agents; crowd simulations involving social clusters such as family groups must represent realistic group behaviours while avoiding collisions; swarm robotics applications requiring sub-group cohesion can achieve more complex collective behaviours; finally, autonomous vehicle platoons need to maintain safe distances between consecutive vehicles while avoiding collisions with other traffic and coordinated material handling systems often involve multiple robots working in pairs to transport large objects.³⁴

Summarizing, the main contribution of this paper is an extension of the RVO algorithm to incorporate paired agent constraints, introducing a new dimension to multi-agent collision avoidance. We provide the formal description of the model, which is computationally light, allowing for onboard implementation in small capacity drones. The algorithm is safe and general, because it is founded on sound general principles. Prior to physical implementation, we provide exhaustive simulation results that confirm the theoretical expectations. In order to facilitate reproducibility, the code and the computational experiments are published in an open access repository.

The rest of this paper is organized as follows: Section 2 reviews related work in multi-agent path planning and constrained navigation. Section 3 details the methodology, including the proposed Extended HRVO algorithm for paired agents and the setup for the simulation experiments. Section 4 presents the experiments designed to test the proposed EHRVO algoithm. Section 5 provides the results of the experiments. Section 6 discusses the results, demonstrating the effectiveness of this new approach in various scenarios. Finally, Section 8 provides the conclusions of the paper and suggests directions for future work.

2. State of the art

The field of multi-agent navigation algorithms with endowed collision avoidance has evolved significantly since the introduction of Velocity Obstacles (VO) by Fiorini and Shiller.^22,35 While various approaches effectively handle independent agents, the challenge of maintaining specific spatial relationships between agents while avoiding collisions remains an active area of research with several unresolved problems.^6,7,36 We call “paired agents” to to groups of agents that, for some reason, are required to maintain a spatial relation, i.e. a fixed distance, within some tolerance.

Recent developments in multi-agent system navigation requiring strict formation control or including physically linked agents highlight the difficulty of achieving both collision avoidance and formation maintenance.³⁷ Alonso-Mora et al.²⁵ addressed the challenge of coordinated object transport using multiple robots, demonstrating that maintaining rigid formations while avoiding obstacles requires sophisticated optimization techniques. Their work revealed fundamental limitations in traditional RVO approaches when agents must maintain strict spatial relationships.

The emerging field of applications requiring tight coordination between multiple robots has brought to light new challenges.³⁸ Formation flight and swarm behavior present particularly challenging scenarios.³⁹ Zhou et al.⁴⁰ explored formation control strategies for multi-UAV systems, identifying significant challenges in maintaining stable formations while ensuring collision-free trajectories. Their work demonstrates that existing velocity-based approaches often struggle to handle both objectives simultaneously. This challenge is further emphasized by Luis and Schoellig,⁴¹ who found that traditional collision avoidance methods become significantly more complex when incorporating strict formation requirements.

The integration of swarm behavior with collision avoidance has been extensively studied by Zhu et al.,⁴² who identified significant challenges in maintaining sub-group cohesion while ensuring collision-free trajectories. Building on this, Lu et al.⁴³ proposed a hybrid approach combining formation control with collision avoidance, though their results indicate continuing challenges in scenarios with dense obstacle fields.

Kang et al.⁴⁴ investigated formation-preservation methods for multi-robot systems, revealing that existing approaches often fail to maintain critical formation requirements while navigating through complex environments. Their work highlights the need for more sophisticated algorithms that can handle both local collision avoidance and global formation objectives.

In the context of human-robot interaction, maintaining specific spatial relationships while avoiding collisions becomes even more critical. Mavrogiannis et al.⁴⁵ studied the challenges of social navigation with paired robots, demonstrating that current RVO-based approaches struggle to incorporate social norms and proximity requirements simultaneously.

Van Den Berg et al.²⁷ established foundational work for handling the navigation of multiple agents with their reciprocal n-body collision avoidance approach, but their method does not explicitly address the requirement to maintenain specific inter-agent spatial relationships. A recent work by Huang et al.⁷ attempted to extend this framework to handle formation constraints, though their results indicate continuing challenges in achieving computational efficiency.

The computational complexity involved in handling multiple types of constraints simultaneously remains a significant challenge. Alonso-Mora et al.²⁵ highlighted this issue, particularly when adding proximity requirements to collision avoidance constraints. A more recent work by Yang et al.⁴⁶ proposed optimization-based solutions, though scalability remains a concern for large groups of paired agents.

In order to deal with cooperative load transport, researchers have been investigating the challenges of maintaining object-carrying formations while avoiding obstacles.^47,48 Their work revealed fundamental limitations in current approaches when dealing with dynamically linked agents, particularly in scenarios requiring precise position coordination between paired agents.

Recent advances in distributed control systems, as surveyed by Fan et al.,⁴⁹ suggest promising directions for addressing these challenges. However, their analysis also highlights the continuing difficulty of balancing formation maintenance with collision avoidance guarantees, particularly in real-time applications.¹⁹

The emergence of learning-based approaches, as demonstrated by Yun et al.,⁵⁰ offers new possibilities for handling linked agent constraints. However, their results also indicate that maintaining strict formation requirements while ensuring collision-free trajectories remains a significant challenge, even with modern machine learning techniques.

These studies collectively demonstrate that while significant progress has been made in multi-agent collision avoidance, the specific challenge of maintaining agent relationships while ensuring collision-free trajectories remains largely unsolved.^51,52

In summary, the limitations of current approaches become particularly evident in the following settings:

Dynamic formation maintenance while avoiding moving obstacles.

Guaranteed minimum and maximum distances between paired agents.

Real-time computation of feasible trajectories for multiple paired agents.

Robust handling of sensor uncertainty while maintaining formation constraints.

Scalable solutions for large numbers of paired agents.

This gap in current capabilities, combined with the growing demand for sophisticated multi-agent coordination in various applications, underscores the need for developing new approaches that can effectively handle linked multi-agent systems while maintaining the computational efficiency and collision avoidance guarantees that made VO-based methods popular.

3. System modeling

The proposed linked multi-agent system (EHRVO) extends the traditional VO, RVO, and HRVO frameworks incorporating proximity constraints between designated agent pairs while avoiding collisions with other agents and obstacles. Consider a system of $n$ agents moving in a two-dimensional Cartesian workspace, where certain agents are paired and must maintain specific spatial relationships.

3.1. VO, RVO, and HRVO definitions

Velocity Obstacle (VO) is a geometric approach to collision avoidance that analyzes potential collision regions based on the observed velocity vectors of moving obstacles. In other words, each agent constructs its velocity obstacle space by estimating the velocities of nearby obstacles within its detection range.

The VO algorithm comprises two fundamental components:

The determination of velocity obstacle region boundaries for each detected obstacle.

The selection of appropriate agent velocity vector avpiding the estimated obstacle velocity regions.

The velocity obstacle region represents the set of all velocity vectors that would result in a collision if maintained by the obstacle while the agent travels along its current trajectory. To generate avoidance maneuvers, the VO navigation algorithm selects velocity vectors that lie outside these computed obstacle regions. The velocity obstacle region is constructed by translating the collision cone centered in the agent by the obstacle’s velocity vector $v_{B}$ , as can be seen in Figure 3a), where the new collision cone is denoted by $V O_{A B}$ .

Figure 3.

Collision cones of (a) VO, (b) RVO, and (c) HRVO collision avoidance algorithms.

Several enhanced variants of the VO method have been developed to address specific limitations. A notable challenge in multi-agent navigation algorithms, including the original VO, is the occurrence of oscillatory behaviors. The Reciprocal Velocity Obstacle (RVO) method was introduced to resolve this issue, ensuring safe and oscillation-free motion trajectories for each agent. RVO has proven particularly effective in navigation through densely populated environments containing both static and dynamic obstacles. The key innovation in RVO lies in its consideration of the agent’s velocity vector ( $v_{A}$ ), achieved by translating the velocity obstacle by $\frac{1}{2}$ ( $v_{A} + v_{B}$ ). This algorithm is illustrated Figure 3b), where the new collision cone is denoted by $R V O_{A B}$ .

The Hybrid Reciprocal Velocity Obstacle (HRVO) represents a further advancement, incorporating additional parameters such as:

Environmental obstacles

Uncertainty in radius, position, and velocity measurements

Robot dynamics and kinematics

HRVO combines aspects of both VO and RVO, with its behavior dependent on the robot’s velocity ( $v_{A}$ ) relative to the centerline of the RVO region. When $v_{A}$ lies to the right of this centerline, the RVO region extends to the VO region on the left side, and vice versa. This approach is illustrated in Figure 3c) , where the new collision cone is denoted by $H R V O_{A B}$ . This hybrid approach has demonstrated superior performance in achieving collision-free and oscillation-free navigation for multiple agents compared to its predecessors.

All variants in the VO family–VO, RVO, and HRVO–require the specification of some input parameters including agent shape, position, and velocity information to function effectively. This comprehensive approach enables robust collision avoidance in dynamic environments while maintaining smooth trajectories.

3.2. Extended HRVO for paired agents (EHRVO)

This section describes the proposed extension of HRVO in order to handle linked agents, namely EHRVO. Consider a system of $n$ agents where some agents are paired. If the number of paired agents is greater than two, the spatial restrictions can always be written in terms of couples of agents, so in the following we deal with couples of agents. Each agent’s state is described by its position vector ${\vec{p}}_{i}$ and velocity vector ${\vec{v}}_{i}$ , where its position evolves according to the following equation:

\begin{aligned} \vec{p_{i}} (k + 1) = \vec{p_{i}} (k) + \vec{v_{i}} (k) \cdot Δ t . \end{aligned}

(1)

Paired agents

(i, j) \in P

are modelled by introducing a proximity constraint, so that the modified collision avoidance radius

r_{c}^{p a i r}

for paired agents is:

\begin{aligned} r_{c}^{p a i r} = 2 r_{c}, \end{aligned}

(2)

where

r_{c}

is the standard collision radius. This constraint creates a tight coupling between paired agents while maintaining safety distances with other agents, as illustrated in Figure 4.

Figure 4.

Modified and standard collision avoidance radius.

The EHRVO algorithm, which is described formally in Algorithm 1 , is constructed as follows: First, the actual distance between paired agents $i$ and $j$ is calculated:

\begin{aligned} d i s t_{B A} = ‖ {\vec{p}}_{j} - {\vec{p}}_{i} ‖ \end{aligned}

(3)

To ensure safety, this distance must be at least $r_{c}^{p a i r}$ units:

\begin{aligned} d i s t_{B A} = max (‖ {\vec{p}}_{j} - {\vec{p}}_{i} ‖, r_{c}^{p a i r}) \end{aligned}

(4)

Next, the angle used to construct the collision cone is calculated. This angle depends on the safety radius and the distance between agents:

\begin{aligned} θ_{B A o r t} = \arcsin (\frac{r_{c}^{p a i r}}{d i s t_{B A}}) \end{aligned}

(5)

For paired agents, preferred velocities are modified to help them to maintain their proximity. The modified velocity is:

\begin{aligned} {\vec{v}}_{R V O}^{p a i r} = \frac{{\vec{v}}_{i} + {\vec{v}}_{j}}{2} + α ({\vec{p}}_{j} - {\vec{p}}_{i}) \end{aligned}

(6)

where

α

is a coupling factor that helps maintain the desired proximity between paired agents. In Equation 6:

term $\frac{{\vec{v}}_{i} + {\vec{v}}_{j}}{2}$ is the average velocity of both agents

term $α ({\vec{p}}_{j} - {\vec{p}}_{i})$ is a component that pulls paired agents together ( $α$ is a small positive number)

Finally, the best velocity

{\vec{v}}_{i}^{*}

is selected for each agent such that:

It does not exceed maximum speed ( $v_{m a x}$ ),

It avoids collisions with all other agents, and

It maintains the required proximity with its paired partner.

Mathematically, it is formulated as:

\begin{aligned} {\vec{v}}_{i}^{*} = \underset{\vec{v} \notin H R V O}{argmin} | \vec{v} - {\vec{v}}_{i}^{p r e f} | \end{aligned}

(7)

This equation is the core of the agent velocity selection strategy in the EHRVO algorithm. For each agent

i

, the algorithm seeks to find an optimal velocity

{\vec{v}}_{i}^{*}

that best satisfies both collision avoidance and goal-directed movement given by

{\vec{v}}^{p r e f}

. The optimal velocity is selected among all possible velocities that lie outside the HRVO velocity obstacle regions (hence that are collision-free) minimizing the difference from the preferred velocity

{\vec{v}}_{i}^{p r e f}

, which is the velocity vector that would drive the agent directly toward its goal. This minimization ensures that while EHRVO algorithm guarantees collision avoidance, it also maintains progress toward the goal by selecting velocities that deviate as little as possible from the ideal path.

The searched velocity vectors in Equation 7 are subject to:

\begin{aligned} \begin{aligned} ‖ \vec{v} ‖ & \leq v_{max} \\ \vec{v} & \notin ⋃_{j \neq i} {HRVO}_{i j} \end{aligned} \end{aligned}

(8)

\begin{aligned} ‖ {\vec{p}}_{i} - {\vec{p}}_{j} ‖ \leq d_{max} \forall (i, j) \in P \end{aligned}

(9)

These constraints ensure that: (1) the selected velocity vector does not exceed the agent’s maximum speed capability, (2) the velocity vector remains outside all HRVO regions created by other agents, avoiding the risk of collisions, and (3) paired agents maintain their required proximity relationships. Here, $d_{m a x}$ represents the maximum allowed separation between paired agents, and $P$ denotes the set of all agent pairs that must maintain proximity constraints.

The EHRVO maintains the advantages of the HRVO while ensuring paired agents stay within prescribed distances of each other. The modified radius and velocity apex calculations create a natural hierarchy of avoidance behaviors, prioritizing pair maintenance while ensuring collision avoidance with other agents.

All the code used in this article is available on an online repository (https://github.com/Julestevez/Extended-HRVO-for-linked-agents).

4. Computational experiments

EHRVO algorithm is implemented using Python for ease installation on board. Prior to physical experiments, we evaluate its effectiveness in three different experiments involving multiple pairs of agents and static obstacles. All the code used in this article is available on an online repository (https://github.com/Julestevez/Extended-HRVO-for-linked-agents).

The settings of the simulation environment for the the three computational experiments are as follows:

Experiment 1

The workspace dimensions are 9 m $\times$ 6 m, where there are 16 agents, arranged in 8 pairs. Each agent is represented as a circular robot with radius of 0.2 m, whose maximum velocity is 1.0 m/s.

The agents were initially positioned in two opposite groups:

Group 1: 8 agents at $y = 0$ m with x-coordinates regularly spaced at 0.5 m intervals.

Group 2: 8 agents at $y = 5$ m with x-coordinates matching those of Group 1.

The couples of paired agents were defined between adjacent agents within each group, creating a total of 8 linked pairs. This setup has been the base for three different experiments:

Experiment 1A Each pair was required to maintain proximity while navigating to their respective goals. Each agent have a specific color and have to reach the goal star with the same color. At the beginning of the experiment, the agents are located in the opposite position of their goal color star. The localization of the goals in this scenario is represented in Figure 5.

Figure 5.

Setting of the goals for Experiment 1.

Experiment 1B In the same starting conditions and scenario of Experiment 1A, this experiment tests the performance of the EHRVO algorithm against other collision avoidance algorithms defined in the literature: Distributed Formation Control with Collision Avoidance (DFCA)¹ and Artificial Potential Field with Dynamic Window Approach (APF-DWA).⁵³ The code of these competing algorithms can be found in our online repository referred in the endnotes.

Experiment 1C In the same starting conditions and scenario of Experiment 1A, we include heterogeneous pairs of agents with some dynamic properties. In this test, we implement following changes to the simulation:

Add mass property to each robot (ranging from 0.5 kg to 5.0 kg)

Implement inertia-based velocity dynamics where heavier robots respond slower to velocity changes

Create mass-weighted RVO cones where lighter robots take more responsibility for collision avoidance

Define 4 distinct robot types with different maximum acceleration and max speed: –

Heavy Cargo: Large, slow, high inertia (5 kg, 0.6 m/s max)

–

Medium Drone: Balanced properties (2.5 kg, 1.0 m/s max)

–

Light Scout: Fast and responsive (1 kg, 1.5 m/s max)

–

Agile Racer: Very fast, minimal inertia (0.5 kg, 2.0 m/s max)

Experiment 1B and Experiment 1C are run in the same scenario as Experiment 1A because the absence of obstacles for the robots helps to appreciate clearly the effects of other reciprocal avoidance algorithms and dynamic properties on the behavior of agents.

Experiment 2

Same initial conditions as in Experiment 1, but in this case, some static circular obstacles were included in the middle of the workspace (radius: 0.125 m). The setting of the goals and static obstacles for this experiment can be seen in Figure 6.

Figure 6.

Setting of the goals and obstacles for Experiment 2.

Experiment 3

The dimensions of the workspace are 10 m $\times$ 6 mm, and there are two circular static obstacles at coordinates $[4.0, 2.5]$ m and $[6.0, 2.5]$ m. The radius of each obstacle is 0.3 m.

This case contemplates 6 agents organized in 2 triads. The robot radius is 0.2 m, and the maximum velocity is 1.0 m/s. The initial positions are the following:

Triad 1: Three agents at $x = 1.0$ m $y = [0.0, 0.5, 1.0]$ m

Triad 2: Three agents at $x = 9.0$ m $y = [4.0, 4.5, 5.0]$ m.

Again, each agent must reach the goal star with its same color. The settings of the goals and obstacles for the Experiments 3 are shown in Figure 7.

Figure 7.

Setting of the goals and obstacles for Experiment 3.

In the three experiments, the time step is 0.01 s, but the visualization frequency is 0.1 s. Coupling factor in the three experiments is $α = 2.0$ and the safety radius of each agent is 1.5 times its radius.

5. Computational experiments results

In the three experiments, paired agents successfully maintained their relative positions while navigating. In Experiment 1A and 2, the average separation of paired agents remained below 1.5 times the robot radius throughout the simulation, while in Experiment 3 this threshold increased to 1.7 times the robot radius. We found that the formation stability improved compared to standard RVO implementations. For a better follow up of the simulation evolution, full duration videos of the simulations can be viewed online (Online videos for Experiment 1A-B-C: https://youtu.be/BjU0nHoTaOc Experiment 2: https://youtu.be/YM9kyUM2tiM Experiment 3 https://youtu.be/PonRB4nM-rI). In these three experiments, no collisions were recorded between any agent during the full simulation duration. Moreover, in the three scenarios agents performed smooth trajectory adjustments when avoiding obstacles, i.e. agent velocities showed smooth acceleration and deceleration profiles.

All agents reached their goals within $7.5$ s in the case of Experiment 1A and 2, and within $12.5$ s in the case of Experiment 3. Figures 8, 9 and 10 show the video frames of the simulation and the position of every agents each $1.5$ s.

Figure 8.

Results of Experiment 1.

Figure 9.

Results of Experiment 2.

Figure 10.

Results of Experiment 3.

The result of Experiment 1B, comparing the three collision avoidance algorithms shows that the EHRVO proposal performs better than the other two algorithms in terms of smoothness and performance of the task. Finally, in Experiment 1C, where we test heterogeneous agents considering their dynamic properties, we can appreciate the fine performance of all different mass agents and their different maximum speeds. Despite their different dynamic parameters, all pairs of agents are able to avoid colliding with the pair of agents that come opposite them, and they reach their final goal smoothly after compensating for inertia.

6. Discussion of the computational results

The computational experimental results demonstrate that the EHRVO algorithm successfully addresses several key challenges identified in the literature while providing effective solutions for coordinated navigation of paired and triad-based formations. Through three distinct experiments, the introduction of a coupling factor $α = 2.0$ proved to create an effective balance between formation maintenance and collision avoidance capabilities, addressing the fundamental limitation related to the difficulty of maintaining stable formations while ensuring collision-free trajectories.

Experiment 1A, involving eight pairs of agents navigating without stationary obstacles, directly addresses the challenge of maintaining rigid formations. Unlike other approaches, which required sophisticated optimization techniques, this method achieves formation maintenance through a simple modification of the collision radius calculation. This simpler approach not only is computationally efficient but also demonstrates stable formations and smooth transitions, suggesting that sophisticated and costly optimization procedures may not be necessary for effective formation control.

Moreover, in this first experiment we also compare in Experiment 1B the performance of our EHRVO proposal with other collision avoidance algorithms: DFCA and APF-DWA, and our systems proved to be faster and more precise than the other relevant algorithms of the literature.

Next, in Experiment 1C we implement a heterogeneous multi-agent system consisting of agents with different circle radius, max acceleration / speed, and mass and added inertia effects. This test validated our model for different dynamic properties, and showed that our EHRVO proposal also works for this more realistic experiment conditions.

Experiment 2, which introduced static obstacles, tackles the limitation highlighted by Luis and Schoellig⁴¹ concerning the integration of strict formation requirements with collision avoidance. The computational experiment results show that paired agents can effectively navigate around obstacles while maintaining their spatial relationships, overcoming the traditional trade-off between formation integrity and obstacle avoidance. This success challenges the assumption made by Huang et al.⁵⁴ that maintaining formation constraints necessarily increases computational complexity significantly.

Experiment 3, featuring two triads navigating around larger obstacles, addresses the scalability concerns raised by Yang et al.⁴⁶ The computational results demonstrate that the same fundamental principles can be extended from pairs to triads without requiring additional computational frameworks. This scalability directly counters the limitations noted in current approaches that struggle with larger formations or more complex group structures.

The coupling factor of $2.0$ proved to be a crucial parameter across all experiments, addressing the challenge identified by Kang et al.⁴⁴ regarding the balance between formation preservation and navigation flexibility. The proposed approach resolves the formation-maintenance issues highlighted by Luis et al.⁴¹ without requiring their proposed hybrid approach, demonstrating that a single, unified algorithm can effectively handle both formation control and collision avoidance.

Furthermore, the proposed algorithm overcomes several key limitations identified in the state of the art:

Regarding dynamic formation maintenance while avoiding moving obstacles, it demonstrates natural deformation and reformation behaviors without requiring explicit replanning, addressing concerns raised by Fan et al.⁴⁹

On the challenge of guaranteed minimum and maximum distances between paired agents, the coupling factor provides a simple but effective mechanism for maintaining formation constraints, solving a key issue identified in recent surveys.

For real-time computation concerns, the presented method maintains the computational efficiency of basic RVO while adding formation capabilities, addressing the scalability limitations noted by Mavrogiannis et al.⁴⁵

In terms of robust handling of sensor uncertainty, the modified collision radii provide natural buffer zones that help to manage positional uncertainties, addressing a key concern in practical implementations.

7. Limitations and future works for Real-World Applicability

While the presented EHRVO algorithm shows promising results in simulation, several important considerations must be addressed when evaluating its closeness to real-world applications and practical deployment scenarios.

In real-world environments, sensors introduce errors in position and velocity estimation that can significantly affect multi-agent coordination. Although the EHRVO algorithm has some inherent robustness against sensor uncertainty, the paper does not elaborate in depth on how the proposed method would handle perception uncertainties, which are critical in scenarios with multiple agents and moving obstacles. Factors such as GPS drift, sensor noise, communication delays, and partial observability could lead to incorrect estimates of agent positions and velocities, potentially causing formation instability or collision avoidance failures.

Although the paper demonstrates that the algorithm works effectively for pairs and triads of agents, it remains unclear how it would perform with significantly larger numbers of agents. It is straightforward that any system with more than three agents can be decomposed into pairs and triads of agents, however the increasing number of constraints and calculations might affect computational efficiency in more complex scenarios involving dozens or hundreds of agents. Real-world applications such as large-scale swarm robotics or traffic management systems would require extensive testing to validate the algorithm’s performance under high-density conditions where the computational burden could become prohibitive for real-time operation.

To make the results truly representative of real-world performance, future simulations should incorporate more realistic modeling of physical constraints and uncertainties. This includes factors such as wheel slippage for ground robots, wind disturbances for aerial vehicles, sensor noise and measurement delays, communication packet loss, actuator dynamics and saturation limits, and environmental uncertainties. The inclusion of these realistic factors would provide a more accurate assessment of the algorithm’s practical viability and help identify potential failure modes that could occur in deployment.

These limitations suggest that while the EHRVO algorithm represents a significant theoretical advancement, substantial additional work is needed to bridge the gap between simulation results and real-world deployment. Future research should focus on incorporating these realistic constraints and uncertainties into both the algorithm design and validation process to ensure robust performance in practical applications.

However, the proposed algorithm also shows areas for potential improvement. While the fixed coupling factor performed well in presented test scenarios, dynamic environments or heterogeneous agent groups might benefit from adaptive coupling factors, a possibility not explored in the literature. Additionally, while EHRVO handles both pairs and triads effectively, the computational overhead increases with formation complexity, suggesting that optimization might be necessary for scaling to larger groups or more complex formations.

The computational experiment results also challenge the assertion by Zhu et al.⁴² that sub-group cohesion necessarily complicates collision-free trajectory generation. Instead, they demonstrate that with appropriate modifications to the basic RVO algorithm, group cohesion can emerge naturally from local interaction rules. This finding aligns with more recent work suggesting that simple, local rules can produce complex group behaviors, but the proposed EHRVO algorithm achieves this result without the need for the learning-based approaches suggested by Yu et al.⁵⁰

8. Conclusion

This paper has presented EHRVO as a novel extension to the well known RVO algorithm for multi-agent navigation that enables effective navigation of both paired and triad-based formations in environments with static and dynamic obstacles, the dynamic ones being the other agents in the environment. The described approach demonstrates that relatively simple modifications to the basic RVO algorithm, primarily through the introduction of a coupling factor and modified collision radii, can produce sophisticated group behaviors while maintaining the fundamental benefits of velocity obstacle methods.

The key innovation of this algorithm lies in the seamless integration of formation control with collision avoidance, achieved without the need for explicit formation constraints or complex optimization procedures. Through three distinct experiments, the presented EHRVO algorithm shows that it successfully handles both paired and triad formations, maintains collision-free trajectories and adapts to environmental constraints.

Results validate the effectiveness of the coupling factor $α = 2.0$ in creating a natural balance between formation integrity and navigational flexibility. This balance allows formations to maintain their structure while adapting to environmental constraints, a capability that has proven challenging for previous approaches. The successful navigation of different formation types through various scenarios suggests that EHRVO captures fundamental aspects of group movement that could be valuable for numerous applications.

Looking forward, several promising directions for future research emerge from this work. We are currently working on the implementation of the algorithm in physical robots in order to achieve a real life validation of the algorithm. The investigation of dynamic coupling factors could lead to more adaptive formation control, potentially improving performance in diverse environments. The extension of the EHRVO approach to larger groups and more complex formation structures could expand its applicability to broader classes of multi-agent systems. Additionally, the incorporation of learning-based methods for parameter optimization could help to tailor the approach to specific application requirements. The success of these experiments reported in this paper suggests that further exploration of the relationship between local interaction rules and global formation behavior could yield additional insights for the design of efficient and robust multi-agent systems.

Footnotes

Funding

The work in this paper has been partially supported by the MICIN project PID2020-116346GBI00, research funds from the Basque Government with codes IT1689-22, and K2025/00045. Authors have also received support by Fundacion Vitoria-Gasteiz Araba Mobility Lab.

Declaration of conflicting interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

ORCID iDs

Julian Estevez

Jose Manuel Lopez-Guede

Daniel Caballero-Martin

Manuel Graña

References

Alonso-Mora

Naegeli

Siegwart

, et al. Collision avoidance for aerial vehicles in multi-agent scenarios. Auton Robots 2015; 39: 101–121.

Xie

Zhang

Zhu

, et al. Congestion-aware multi-agent trajectory prediction for collision avoidance. In: 2021 IEEE international conference on robotics and automation (ICRA), pp. 13693–13700. IEEE, 2021.

Grosset

Ndao

Fougères

A-J

, et al. A cooperative approach to avoiding obstacles and collisions between autonomous industrial vehicles in a simulation platform. Integr Comput Aided Eng 2023; 30: 19–40.

Cheng

PDC

Indri

Possieri

, et al. Path planning in formation and collision avoidance for multi-agent systems. Nonlinear Anal: Hybrid Syst 2023; 47: 101293.

Simoes

Lau

Reis

. Exploring communication protocols and centralized critics in multi-agent deep learning. Integr Comput Aided Eng 2020; 27: 333–351.

Butler

Leung

Paré

. Collaborative safe formation control for coupled multi-agent systems. In: 2024 European control conference (ECC), pp.3410–3415. IEEE, 2024.

Huang

Meng

Dimarogonas

. Prescribed performance formation control for second-order multi-agent systems with connectivity and collision constraints. Automatica 2024; 160: 111412.

Soto

Adeli

. Multi-agent replicator controller for sustainable vibration control of smart structures. J Vibroeng 2017; 19: 4300–4322.

Rypeść

Cygert

Khan

, et al. Divide and not forget: Ensemble of selectively trained experts in continual learning. In: International conference on learning representations (ICLR), pp.1–18, 2024.

10.

Estevez

Nuñez

Lopez-Guede

, et al. A low-cost vision system for online reciprocal collision avoidance with UAVs. Aerosp Sci Technol 2024; 150: 109190.

11.

Macias-Garcia

Galeana-Perez

Medrano-Hermosillo

, et al. Multi-stage deep learning perception system for mobile robots. Integr Comput Aided Eng 2021; 28: 191–205.

12.

Douthwaite

De Freitas

Mihaylova

. An interval approach to multiple unmanned aerial vehicle collision avoidance. In: 2017 Sensor data fusion: Trends, solutions, applications (SDF), pp.1–8. IEEE, 2017.

13.

Zhahir

Razali

Mohd Ajir

. Current development of UAV sense and avoid system. In: IOP conference series: Materials science and engineering, volume 152, pp.012035. IOP Publishing, 2016.

14.

Ramasamy

Sabatini

. A unified approach to cooperative and non-cooperative sense-and-avoid. In: 2015 International conference on unmanned aircraft systems (ICUAS), pp.765–773. IEEE, 2015.

15.

Chen

Jilkov

Rong Li

. On threshold optimization for aircraft conflict detection. In: 2015 18th International conference on information fusion (Fusion), pp.1198–1204. IEEE, 2015.

16.

Marin

Radtke

Innis

, et al. Using a genetic algorithm to develop rules to guide unmanned aerial vehicles. In: IEEE SMC’99 Conference Proceedings. 1999 IEEE international conference on systems, Man, and Cybernetics (Cat. No. 99CH37028), volume 1, pp.1055–1060. IEEE, 1999.

17.

Richards

How

. Aircraft trajectory planning with collision avoidance using mixed integer linear programming. In: Proceedings of the 2002 American control conference (IEEE Cat. No. CH37301), volume 3, pp.1936–1941. IEEE, 2002.

18.

Aljassani

AMH

Ghani

Al-Hajjar

AMH

. Enhanced multi-agent systems formation and obstacle avoidance (emafoa) control algorithm. Results Eng 2023; 18: 101151.

19.

Estevez

Caballero-Martin

Lopez-Guede

, et al. A decentralized collision avoidance algorithm for individual and collaborative UAVs. In: International work-conference on the interplay between natural and artificial computation, pp.13–22. Springer, 2024.

20.

Snape

Van Den Berg

Guy

, et al. The hybrid reciprocal velocity obstacle. IEEE Trans Robot 2011; 27: 696–706.

21.

Wilkie

Van Den Berg

Manocha

. Generalized velocity obstacles. In: 2009 IEEE/RSJ international conference on intelligent robots and systems, pp.5573–5578. IEEE, 2009.

22.

Fiorini

Shiller

. Motion planning in dynamic environments using velocity obstacles. Int J Rob Res 1998; 17: 760–772.

23.

Guzzi

Giusti

Gambardella

, et al. Local reactive robot navigation: A comparison between reciprocal velocity obstacle variants and human-like behavior. In: 2013 IEEE/RSJ international conference on intelligent robots and systems, pp.2622–2629. IEEE, 2013.

24.

Tayal

Singh

Keshavan

, et al. Control barrier functions in dynamic UAVs for kinematic obstacle avoidance: A collision cone approach. In: 2024 American control conference (ACC), pp.3722–3727. IEEE, 2024.

25.

Alonso-Mora

Baker

Rus

. Multi-robot formation control and object transport in dynamic environments via constrained optimization. Int J Rob Res 2017; 36: 1000–1021.

26.

van den Berg

Lin

Manocha

. Reciprocal velocity obstacles for real-time multi-agent navigation. In: 2008 IEEE international conference on robotics and automation, pages 1928–1935, 2008.

27.

Van Den Berg

Snape

Guy

, et al. Reciprocal collision avoidance with acceleration-velocity obstacles. In: 2011 IEEE international conference on robotics and automation, pages 3475–3482. IEEE, 2011.

28.

Kim

J-H

. Study on optimal velocity selection using velocity obstacle (OVVO) in dynamic and crowded environment. Auton Robots 2016; 40: 1459–1470.

29.

Levy

Keitel

Engel

, et al. The extended velocity obstacle and applying orca in the real world. In: 2015 IEEE international conference on robotics and automation (ICRA), pages 16–22, 2015.

30.

Wilkerson

Bobinchak

Culp

, et al. Two-dimensional distributed velocity collision avoidance. Naval Air Warfare Center Weapons Division, Tech Rep 2014.

31.

Lindqvist

Sopasakis

Nikolakopoulos

. A scalable distributed collision avoidance scheme for multi-agent UAV systems. In: 2021 IEEE/RSJ international conference on intelligent robots and systems (IROS), pp.9212–9218. IEEE, 2021.

32.

Snape

Van Den Berg

Guy

, et al. Independent navigation of multiple mobile robots with hybrid reciprocal velocity obstacles. In: 2009 IEEE/RSJ international conference on intelligent robots and systems, pp.5917–5922. IEEE, 2009.

33.

Grosset

Fougères

A-J

Djoko-Kouam

, et al. Multi-agent simulation of autonomous industrial vehicle fleets: Towards dynamic task allocation in V2X cooperation mode. Integr Comput Aided Eng 2024; 31: 249–266.

34.

Estevez

Graña

Lopez-Guede

. Online fuzzy modulated adaptive PD control for cooperative aerial transportation of deformable linear objects. Integr Comput Aided Eng 2017; 24: 41–55.

35.

Caballero-Martin

Lopez-Guede

Estevez

, et al. Artificial intelligence applied to drone control: A state of the art. Drones 2024; 8: 296.

36.

Fasano

Carrio

, et al. A comprehensive survey on non-cooperative collision avoidance for micro aerial vehicles: Sensing and obstacle detection. J Field Robot 2023; 40: 1697–1720.

37.

Romero

Meden

Bellas

, et al. Using perceptual classes to dream policies in open-ended learning robotics. Integr Comput Aided Eng 2023; 30: 205–222.

38.

Estevez

Garate

Lopez-Guede

, et al. Review of aerial transportation of suspended-cable payloads with quadrotors. Drones 2024; 8: 35.

39.

Guo

Zavlanos

. Multirobot data gathering under buffer constraints and intermittent communication. IEEE Trans Robot 2018; 34: 1082–1097.

40.

Zhou

Wang

Bandyopadhyay

, et al. Fast, on-line collision avoidance for dynamic vehicles using buffered voronoi cells. IEEE Robot Autom Lett 2017; 2: 1047–1054.

41.

Luis

Schoellig

. Trajectory generation for multiagent point-to-point transitions via distributed model predictive control. IEEE Robot Autom Lett 2019; 4: 375–382.

42.

Zhu

Xie

Han

, et al. A survey on recent progress in control of swarm systems. Sci China Inform Sci 2017; 60: 1–24.

43.

Dong

, et al. Time-varying group formation-tracking control for general linear multi-agent systems with switching topologies and unknown input. Int J Robust Nonlin Control 2022; 32: 1925–1940.

44.

Kang

Wang

Yang

, et al. Leader-following formation control and collision avoidance of second-order multi-agent systems with time delay. IEEE Access 2020; 8: 142571.

45.

Mavrogiannis

Blukis

Knepper

. Socially competent navigation planning by deep learning of multi-agent path topologies. In: 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), pp.6817–6824. IEEE, 2017.

46.

Yang

Bai

, et al. Neural-network-based formation control with collision, obstacle avoidance and connectivity maintenance for a class of second-order nonlinear multi-agent systems. Neurocomputing 2021; 439: 243–255.

47.

Blais

M-A

Akhloufi

. Reinforcement learning for swarm robotics: An overview of applications, algorithms and simulators. Cogn Robot 2023; 3: 226–256.

48.

Lin

J-L

Hwang

K-S

Wang

Y-L

. A simple scheme for formation control based on weighted behavior learning. IEEE Trans Neural Netw Learn Syst 2013; 25: 1033–1044.

49.

Fan

Long

Liu

, et al. Distributed multi-robot collision avoidance via deep reinforcement learning for navigation in complex scenarios. Int J Rob Res 2020; 39: 856–892.

50.

Shi

Lim

C-C

, et al. Formation control for multi-robot systems with collision avoidance. Int J Control 2019; 92: 2223–2234.

51.

Butt

Nasir

Rashid

RBA

. A review of perception sensors, techniques, and hardware architectures for autonomous low-altitude UAVs in non-cooperative local obstacle avoidance. Rob Auton Syst 2024; 173: 104629.

52.

Wakabayashi

Suzuki

. Dynamic obstacle avoidance for multi-rotor UAV using chance-constraints based on obstacle velocity. Rob Auton Syst 2023; 160: 104320.

53.

Sun

Tang

Lao

. Collision avoidance for cooperative UAVs with optimized artificial potential field algorithm. IEEE Access 2017; 5: 18382–18390.

54.

Huang

Teo

RSH

Tan

. Collision avoidance of multi unmanned aerial vehicles: A review. Annu Rev Control 2019; 48: 147–164.

Enhanced dynamic obstacle avoidance for linked multi-agent systems by an extended hybrid reciprocal velocity obstacle model

Abstract

Keywords

1. Introduction

3. System modeling

3.1. VO, RVO, and HRVO definitions

7. Limitations and future works for Real-World Applicability

8. Conclusion

Footnotes

Funding

Declaration of conflicting interests

ORCID iDs

References