Conflict-Aware ACO with ORCA-Inspired Local Avoidance for Multi-Robot Navigation

Ⅰ. Introduction

With the rapid advancement of automation and intelligent logistics, multi-robot systems have been extensively deployed in applications such as warehouse automation, service robotics, and autonomous transportation. In these scenarios, multiple robots often share constrained environments, including narrow corridors, intersections, and merging paths. While individual path planning algorithms can generate efficient routes for single robots, the interaction among multiple robots introduces significant challenges, such as collisions, congestion, and deadlocks. Therefore, designing a path planning strategy that ensures both safety and efficiency in multi-robot systems has become an important research problem [1].

Existing rule-based priority methods are simple but fail to perform effectively in complex environments. Conflict-Based Search (CBS) can provide optimal solutions but suffers from high computational complexity in large-scale scenarios [2]. Reactive approaches such as ORCA-inspired local collision avoidance enable fast local collision avoidance but lack global coordination [3]-[5]. Extensions of reciprocal collision avoidance have also been developed for non-holonomic robots, variable-responsibility settings, and hybrid collision-avoidance and route-planning problems [6]-[8]. Reinforcement learning-based methods offer adaptability but often require extensive training and exhibit limited stability [9].

Ant Colony Optimization (ACO), a swarm intelligence-based metaheuristic, has shown strong performance in solving combinatorial optimization problems due to its distributed decision-making mechanism and pheromone-based indirect communication. These characteristics make ACO particularly suitable for multi-robot systems, where decentralized coordination is desirable. However, standard ACO does not explicitly consider collision avoidance in multi-agent environments, as it primarily focuses on optimizing individual path quality rather than joint execution feasibility [10]-[12].

To address these limitations, this paper proposes a hybrid global–local path planning framework that integrates conflict-aware ACO with ORCA-inspired local collision avoidance. In the proposed method, ACO is employed as a global planner to generate efficient paths with conflict-aware pheromone updates, while ORCA-inspired local avoidance is used as a local reactive controller to ensure real-time collision avoidance during execution.

By combining global conflict-aware planning with local avoidance and corridor coordination, the proposed framework is designed to improve conflict handling in constrained multi-robot environments.

The main contributions of this paper are summarized as follows:

• 1. A hybrid global–local path planning framework that integrates Ant Colony Optimization (ACO) with ORCA-inspired local collision avoidance for multi-robot systems.
• 2. A conflict-aware ACO strategy incorporating spatio-temporal node and edge conflict penalties.
• 3. A coordination mechanism supporting two-robot navigation in constrained environments.
• 4. CoppeliaSim-based implementation validation and MATLAB-based quantitative comparison in representative two-robot scenarios.

Ⅱ. Problem Formulation

In this study, the multi-robot path planning problem is formulated as a graph-based optimization problem in a shared environment. The environment is represented as a graph G=(V,E), where V denotes the set of nodes (positions in the environment), and E represents the set of edges connecting nodes [13]. Each edge is associated with a travel cost reflecting distance or traversal time. A set of robots R={r1,r2,...rn} operate in the environment. Each robot is assigned a start node and a goal node, and must find a path from its start to its destination. A path is defined as a sequence of nodes over discrete time steps [14][15].

In multi-robot settings, conflicts may occur when multiple robots attempt to occupy the same resource simultaneously. In this work, two types of conflicts are considered:

• 1. Node conflict, where two robots occupy the same node at the same time step.
• 2. Edge conflict, where two robots traverse the same edge in opposite directions at the same time.

The objective of the problem is to find a set of collision-free paths for all robots while minimizing the overall cost. This can be formulated as:

where cost(P_k) represents the travel cost of robot k. N_node(P) and N_edge(P) represent the numbers of node and edge conflicts, respectively. The weights ω_n and ω_e are used for the two conflict types, and λ controls the overall conflict penalty.

Specifically, the optimization aims to reduce collision occurrences and deadlocks while maintaining reasonable path length and travel time, thereby balancing safety and efficiency in shared environments.

Ⅲ. Proposed Method

3.2 Conflict-aware path evaluation

To reduce path conflicts in global planning, the path of Robot A is first generated and used as a spatio-temporal reference when planning the path of Robot B. In the current two-robot implementation, the planning order is fixed. The planning order does not depend on the initial positions of the robots. However, different initial positions may affect the generated paths. Changing the planning order may affect the generated paths. For each movement, node and edge conflicts are evaluated at the corresponding discrete time steps. The conflict cost is defined as:

$\[ C_{ij}={\omega }_n{C}_{node}+{\omega }_e{C}_{edge} \]$

(3)

where C_node=1 when two robots occupy the same node at the same time, and C_edge=1 when two robots traverse the same edge in opposite directions during the same time step.

The transition score used in the implemented ACO planner is modified as:

$\[ S_{ij}={\tau }_{ij}^{\alpha }{\eta }_{ij}^{\beta }\text{exp}\left(-\lambda C_{ij}\right) \]$

(4)

Therefore, candidate movements associated with higher conflict costs receive lower selection scores during path construction.

Table 1.

Main parameters of the conflict-aware ACO planner

The number of ACO iterations was fixed at 12 in the reported experiments. The effect of increasing the iteration count was not separately evaluated.

Ⅳ. Experimental Setup

CoppeliaSim was used for implementation validation and qualitative visualization of the two-robot navigation process. The simulated environment included narrow corridors, intersections, and obstacles, allowing corridor access, local avoidance, and waypoint following to be observed directly. The CoppeliaSim demonstrations were not used to generate the quantitative comparison reported in Tables 3 and 4.

Quantitative experiments were conducted in MATLAB using three representative two-robot scenarios: a head-on encounter in a narrow corridor, simultaneous entry into an intersection, and an alternative-route scenario. Four methods—Standard ACO, Local Avoidance Only, Standard ACO + Local Avoidance + Corridor Coordination, and the Proposed Method—were each evaluated over 30 independent runs per scenario. Success rate, collision events, deadlock events, completion time, and path length were recorded. Average completion time and path length were calculated only for successful runs.

The methods with local avoidance use the same local avoidance function and parameters. Standard ACO + Local + Corridor and the Proposed Method also use the same corridor coordination mechanism when it is enabled. In the Alternative Route scenario, a central obstacle allows robots to take either an upper or a lower route. Corridor coordination is disabled in this scenario.

Ⅴ. Results and Analysis

The proposed method was evaluated using collision count, deadlock count, travel time, path length, and success rate, which reflect both safety and efficiency in multi-robot navigation. For comparison, four methods were considered: Standard ACO, Local Avoidance Only, Standard ACO + Local Avoidance + Corridor Coordination, and the Proposed Method. The comparison focused on their ability to handle conflicts in constrained two-robot environments.

Fig. 1 illustrates a representative CoppeliaSim conflict scenario used for qualitative validation. In Fig. 1(a), two robots approach a constrained region and may encounter a conflict. In Fig. 1(b), the local avoidance and corridor coordination mechanisms modify robot motion to reduce the immediate conflict.

Fig. 1.

Robot navigation and conflict resolution in CoppeliaSim.

Table 2 summarizes the main controller parameters used in the CoppeliaSim experiments. The maximum linear and angular velocities were set to 0.38 m/s and 2.2 rad/s, respectively. The waypoint reaching threshold was 0.38 m. The robot safety distance and obstacle safety distance were set to 0.90 m and 0.12 m, respectively. The corridor detection radius was 1.25 m, the buffer offset distance was 0.60 m, and the local avoidance gain was 0.20 m/s. These parameters remained fixed during the CoppeliaSim experiment

Table 2.

Main parameters used in the CoppeliaSim simulation

Tables 3 and 4 present the scenario-wise quantitative comparison of the four navigation methods. In the Narrow Corridor scenario, the Proposed Method achieved an 80.0% success rate, while Standard ACO + Local Avoidance + Corridor Coordination achieved 83.33%. Their collision and deadlock counts were also similar, indicating that corridor coordination was the dominant factor in this scenario.

Table 3.

Comparison of success rates and conflict events (30 runs per method).

Table 4.

Scenario-wise comparison of completion time and path length

Although the success rate in the “narrow corridor” was only 13.33% and 0% at “intersections,” these results indicate that global path planning alone cannot handle obstacle avoidance for robots in narrow passages, as completion time and path length are calculated only for successful runs. Therefore, the standard ACO achieved only four successful trials in the “narrow corridor” environment. Its shorter completion time does not necessarily indicate superior overall performance. The proposed framework improves conflict resolution capabilities by combining global planning, local avoidance, and corridor coordination.

In the Intersection scenario, both the Proposed Method and Standard ACO + Local Avoidance + Corridor Coordination achieved a 100% success rate with no collision or deadlock events, indicating that the coordination mechanism was sufficient to resolve the tested intersection conflicts.

In the Alternative Route scenario, the Proposed Method achieved an 83.33% success rate, compared with 46.67% for Standard ACO, Local Avoidance Only, and Standard ACO + Local Avoidance + Corridor Coordination. The Proposed Method also reduced collision and deadlock events from 16 to 5, demonstrating the additional contribution of Conflict-Aware ACO when alternative global routes were available.

In the “Alternative Route” scenario, the corridor coordination function is disabled. Therefore, “Local Avoidance Only” and “Standard ACO + Local + Corridor” use the same control settings and produce exactly the same results. The standard ACO also achieved 14 successful runs, although the completion times and path lengths of some failed runs differed. Since the averages are calculated based solely on successful runs, the averages for these three methods are exactly the same.

Although the Proposed Method improved conflict-handling performance, it did not consistently reduce completion time or path length. In the Narrow Corridor scenario, the additional waiting and coordination increased completion time and path length, indicating a trade-off between safety and efficiency.

Ⅵ. Discussion

The experimental results show that the contribution of each component depends on the navigation scenario. In the Narrow Corridor scenario, Standard ACO + Local Avoidance + Corridor Coordination achieved an 83.33% success rate, which was comparable to the 80.0% achieved by the Proposed Method. In the Intersection scenario, both methods achieved a 100% success rate with no collision or deadlock events. These results indicate that corridor coordination is the dominant factor in structurally constrained passages. In contrast, in the Alternative Route scenario, the Proposed Method increased the success rate from 46.67% to 83.33% and reduced collision and deadlock events from 16 to 5, showing that Conflict-Aware ACO provides an additional benefit when alternative global routes are available. However, the Proposed Method did not consistently reduce completion time or path length. In the Narrow Corridor scenario, the additional waiting and coordination increased both completion time and path length, indicating a trade-off between safety and efficiency. The current experiments were limited to two robots and three simulation scenarios. Future work will include larger-scale multi-robot experiments and validation using real robots.

Ⅶ. Conclusion

This paper presented a hybrid multi-robot navigation framework combining Conflict-Aware ACO, ORCA-inspired local avoidance, and corridor coordination. The Proposed Method achieved success rates of 80.0%, 100%, and 83.33% in the Narrow Corridor, Intersection, and Alternative Route scenarios, respectively. The additional control experiment showed that corridor coordination was the dominant factor in the Narrow Corridor and Intersection scenarios, whereas Conflict-Aware ACO provided a clear additional benefit in the Alternative Route scenario. Although the proposed framework improved conflict-handling performance, additional coordination increased completion time and path length in narrow corridors, indicating a safety–efficiency trade-off. Future work will extend the proposed framework to scenarios involving three or more robots. To prevent deadlocks caused by fixed priority assignments, priority will be adjusted based on waiting times and the operational status of channels. Next, deadlock and recovery mechanisms should be considered, including temporary waiting, buffer backtracking, and other path re-planning issues. Through further experiments, the framework’s scalability and robustness for multi-robot systems in more complex environments will be evaluated.

Acknowledgments

This work was supported by the Korea government (MSIT) through the COMPA under Grant RS-2025-02315174-2027, and by MOTIE, Korea, through the Technology Innovation Program under Grant RS-2024-00433599.

References

• L. E. Parker, "Current State of the Art in Distributed Autonomous Mobile Robotics", Distributed Autonomous Robotic Systems 4, Springer, pp. 3-12, Oct. 2000. [https://doi.org/10.1007/978-4-431-67919-6_1]
• G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, "Conflict-based search for optimal multi-agent path finding", Artificial Intelligence, Vol. 219, pp. 40-66, Feb. 2015. [https://doi.org/10.1016/j.artint.2014.11.006]
• J. van den Berg, S. J. Guy, M. Lin, and D. Manocha, "Reciprocal n-body collision avoidance", Robotics Research: The 14th International Symposium ISRR, Springer Tracts in Advanced Robotics, Vol. 70, pp. 3-19, May 2011. [https://doi.org/10.1007/978-3-642-19457-3_1]
• J. Alonso-Mora, A. Breitenmoser, P. Beardsley, and R. Siegwart, "Reciprocal collision avoidance for multiple car-like robots", Proc. IEEE International Conference on Robotics and Automation (ICRA), Saint Paul, MN, USA, pp. 360-366, May 2012. [https://doi.org/10.1109/ICRA.2012.6225166]
• J. van den Berg, M. Lin, and D. Manocha, "Reciprocal velocity obstacles for real-time multi-agent navigation", Proc. IEEE International Conference on Robotics and Automation (ICRA), Pasadena, CA, USA, pp. 1928-1935, May 2008. [https://doi.org/10.1109/ROBOT.2008.4543489]
• J. Alonso-Mora, A. Breitenmoser, M. Rufli, P. Beardsley, and R. Siegwart, "Optimal reciprocal collision avoidance for multiple non-holonomic robots", Distributed Autonomous Robotic Systems: The 10th International Symposium, Springer Tracts in Advanced Robotics, Vol. 83, pp. 203-216, Sep. 2012. [https://doi.org/10.1007/978-3-642-32723-0_15]
• K. Guo, D. Wang, T. Fan, and J. Pan, "VR-ORCA: Variable Responsibility Optimal Reciprocal Collision Avoidance", IEEE Robotics and Automation Letters, Vol. 6, No. 3, pp. 4520-4527, Jul. 2021. [https://doi.org/10.1109/LRA.2021.3067851]
• T. Chauvin, D. Gianazza, and N. Durand, "ORCA-A*: A Hybrid Reciprocal Collision Avoidance and Route Planning Algorithm for UAS in Dense Urban Areas", Proc. SESAR Innovation Days, Rome, Italy, pp. 2024-059, Nov. 2024. https://www.sesarju.eu/sites/default/files/documents/sid/2024/papers/SIDs_2024_paper_059%20final.pdf, .
• S. J. Guy, J. Chhugani, C. Kim, N. Satish, M. C. Lin, D. Manocha, and P. Dubey, "ClearPath: Highly Parallel Collision Avoidance for Multi-Agent Simulation", Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, New Orleans, Louisiana, USA, pp. 177-187, Aug. 2009. [https://doi.org/10.1145/1599470.1599494]
• M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: Optimization by a colony of cooperating agents", IEEE Transactions on Systems, Man, and Cybernetics, Part B, Vol. 26, No. 1, pp. 29-41, Feb. 1996. [https://doi.org/10.1109/3477.484436]
• M. Dorigo and L. M. Gambardella, "Ant colony system: A cooperative learning approach to the traveling salesman problem", IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53-66, Apr. 1997. [https://doi.org/10.1109/4235.585892]
• M. Dorigo, M. Birattari, and T. Stützle, "Ant colony optimization", IEEE Computational Intelligence Magazine, Vol. 1, No. 4, pp. 28-39, Nov. 2006. [https://doi.org/10.1109/MCI.2006.329691]
• S. M. LaValle, "Planning Algorithms", Cambridge University Press, May 2006. [https://doi.org/10.1017/CBO9780511546877]
• R. Stern, N. R. Sturtevant, A. Felner, S. Koenig, H. Ma, T. T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, R. Barták, and E. Boyarski, "Multi-agent pathfinding: Definitions, variants, and benchmarks", Proceedings of the International Symposium on Combinatorial Search, Napa, California, USA, Vol. 10, No. 1, pp. 151-158, Jul. 2019. [https://doi.org/10.1609/socs.v10i1.18510]
• R. Stern, "Multi-Agent Path Finding - An Overview", Artificial Intelligence: 5th RAAI Summer School, Dolgoprudny, Russia, Vol. 11866, pp. 96-115, Jul. 2019. [https://doi.org/10.1007/978-3-030-33274-7_6]