C-ORCA* (Cooperative-ORCA*)

Real-Time Proactive Deadlock Avoidance for Continuous-Space Multi-Agent Navigation

C-ORCA* is a next-generation multi-agent navigation framework that transforms deadlock handling from reactive recovery to proactive prevention by integrating agents' full spatial trajectories and dependencies into a continuous-space MAPF solver, achieving significantly higher solve rates and lower flowtime overhead than current state-of-the-art methods.

Description

Background

The algorithm builds on two established techniques: a global discrete MAPF planner and local continuous-space collision avoidance.

MAPF-LNS2 is an anytime Multi-Agent Path Finding solver based on Large Neighborhood Search. It begins with an initial set of paths (computed by Prioritised Planning, PIBT, or similar algorithms) and iteratively improves the solution by destroying a subset of agents' paths and replanning them. The destroy-and-repair loop continues until a time limit is reached, progressively reducing the total path cost [1].

ORCA* (Optimal Reciprocal Collision Avoidance) is a decentralised collision avoidance algorithm for multi-agent navigation in continuous space. At each simulation step, every agent computes a set of velocity constraints — one for each nearby agent — that guarantee collision-free motion within a short time horizon. A new velocity that satisfies all constraints and is closest to a preferred velocity is then selected via linear programming. The preferred velocity is typically directed toward the agent's current target point. More details can be found on the ORCA project page [2].

ORCA* is effective in open areas but is purely reactive: it has no awareness of the global environment structure, making it prone to deadlocks in narrow corridors where agents approach from opposite directions. ORCA*-MAPF [3] addresses this by invoking a classical MAPF solver (ECBS) as a fallback when a deadlock is detected. However, the fallback only activates after a deadlock has already occurred, wasting time in stalled states, and the discrete MAPF solution must be post-processed into motions with fixed speeds and cardinal directions, undermining the benefits of continuous-space execution.

C-ORCA*: Proactive Deadlock Avoidance

C-ORCA* shifts deadlock handling from reactive recovery to proactive prevention by introducing a pre-processing stage that provides global trajectory guidance and spatial dependency information to the ORCA* execution loop. The algorithm consists of two phases:

Phase 1: Pre-Processing (LNS)

The pre-processing stage converts the continuous environment into a grid and leverages MAPF-LNS2 to compute guidance paths. Three key pieces of information are extracted:

1. Waypoint Generation — A string-pulling algorithm converts the discrete grid paths into a sequence of waypoints connected by line-of-sight segments. Each agent navigates from one waypoint to the next during execution. This preserves the global collision-free structure while allowing smooth continuous-space motion.

2. Corridor Detection — All narrow corridor structures in the map are identified via a linear scan of the grid. A cell is classified as a corridor cell if its degree (number of traversable neighbours) is at most 2. Connected corridor cells are grouped, and the two boundary cells are marked as entrances.

3. Dependency Detection — For each corridor, two groups of agents are computed based on the guidance paths: those entering from one side and those entering from the other. Two types of dependency are established:

   • Cross-corridor dependency: agents entering the same corridor from opposite ends are associated. During execution, whichever agent enters first forces the other to wait until it exits, proactively preventing head-on deadlocks.
   • Enter-corridor dependency: agents entering the same corridor from the same end are associated. The agent that arrives first is allowed to fully enter before the next one proceeds, preventing entrance congestion.

   Dependencies are built without considering the time dimension — even if two agents pass through the same corridor at very different times in the guidance path, the dependency is still recorded. The traversal order is resolved dynamically at execution time based on which agent actually arrives first.

Phase 2: Execution (ORCA*)

During execution, the algorithm follows the standard ORCA* loop with three key modifications:

• Waypoint tracking: each agent moves toward its current waypoint. When a waypoint is reached, the next one is popped from the sequence. If line-of-sight to the current waypoint is lost (due to interactions with other agents), intermediate waypoints are generated on the fly via string-pulling. If an agent has reached its goal but is blocking another agent, it is temporarily assigned a waypoint at the blocked agent's position to break the local optimum.

• Dependency-driven drifting: when an agent approaches a corridor that is occupied by agents from a dependency group, it switches to drifting mode. Instead of stopping (which would block other agents), the drifting agent adopts the velocity of its fastest neighbour, allowing agents inside the corridor to push their way out. Once all dependent agents have cleared the corridor, the drifting agent reverts to normal ORCA* mode.

• MAPF fallback (C-ORCA*-MAPF): the dependency mechanism prevents most deadlocks proactively, but residual cases may still arise under extreme congestion. C-ORCA*-MAPF inherits the ORCA*-MAPF fallback: if agents remain stalled for a threshold number of time steps, ECBS is invoked to resolve the deadlock. Empirically, C-ORCA*-MAPF invokes the fallback 3–4 orders of magnitude less frequently than ORCA*-MAPF.

Results Summary

C-ORCA* and C-ORCA*-MAPF were evaluated against ORCA* and ORCA*-MAPF on four benchmark maps (Gap, Random, Room, Warehouse) with 15–200 agents. Key findings:

• Success rate: C-ORCA*-MAPF maintains near-100% success on the Gap map across all agent counts, where ORCA* drops below 40% at 30 agents. On Random, C-ORCA*-MAPF sustains above 80% success even at 200 agents.
• Flowtime: C-ORCA*(-MAPF) consistently achieves up to 50% lower flowtime than ORCA*(-MAPF) on corridor-heavy maps.
• Runtime overhead: the dependency mechanism introduces virtually no per-step overhead compared to vanilla ORCA*.
• MAPF calls: C-ORCA*-MAPF invokes the ECBS fallback 3–4 orders of magnitude less frequently than ORCA*-MAPF.

Prerequisites

• C++17 compatible compiler
• CMake ≥ 3.10
• Boost (program_options, system)
• tinyxml2 (included in src/orca/external/tinyxml2/)

Build

mkdir build && cd build
cmake ..
make

This produces two executables: unified_mapf (single test) and unified_series (batch test).

Usage

There are two options to test the algorithm: single test on one task and series of tasks.

Single Test

./unified_mapf -x <xml_file> -k <num_agents>

Argument	Description
xml_file	XML file containing the map and agent definitions
num_agents	Number of agents to run

Example:

./unified_mapf -x ../task_examples/empty_task.xml -k 50

Summary will be displayed after execution using standard output. Full log (if logging is enabled in CMake) will be saved in the same directory as the task file, named as:

<task_filename>_<num_agents>_log.xml

Series Test

Sweep across a range of agent counts on one or more tasks:

./unified_series --min <n_min> --step <n_step> --max <n_max> --taskList <task_list>

Argument	Description
n_min	Initial number of agents
n_step	Increment between runs
n_max	Maximum number of agents
task_list	Text file listing XML task files

Example:

./unified_series --min 15 --step 5 --max 100 --taskList ../task_examples/tasks.txt

You can also run a series on a single XML file without a task list:

./unified_series --min 10 --step 10 --max 50 -x ../task_examples/empty_task.xml

Task list format: one XML path per line. Empty lines and lines starting with # are ignored.

# warehouse scenarios
warehouse_1.xml
warehouse_2.xml

If the task file contains fewer agents than the requested count, the test runs with the number of agents available in the task.

Summary will be written after execution of each task to result.csv (configurable via -o). Log files follow the same naming pattern as single test mode.

Parameters

General

Flag	Default	Description
-x, --xml	(required)	Input XML file (map + agents)
-k, --agentNum	0	Number of agents
-t, --cutoffTime	300	Total time limit (seconds)
--seed	0	Random seed
-s, --screen	1	Console verbosity (0 = silent, 3 = verbose)
--useWaypoints	true	Pass LNS waypoints to ORCA
--lnsOnly	false	Run only the LNS phase
--orcaOnly	false	Run only the ORCA phase
--waypointFile	mapf_waypoints.txt	Intermediate waypoint file path
-o, --output	—	Output file for LNS solution / CSV results
--stats	—	LNS iteration statistics file

LNS

Flag	Default	Description
--initAlgo	PP	Initial path algorithm (PP, PIBT, etc.)
--replanAlgo	PP	Replan algorithm
--neighborSize	8	Neighborhood size for destroy-repair
--maxIterations	0	Max LNS iterations (0 = unlimited)
--destoryStrategy	Adaptive	Destroy heuristic (Adaptive, RandomWalk, etc.)
--initLNS	true	Use LNS for initial solution
--initDestoryStrategy	Adaptive	Destroy heuristic for init phase
--sipp	true	Use SIPP for single-agent planning
--pibtWindow	5	PIBT window size
--winPibtSoftmode	true	PIBT soft mode

ORCA

Flag	Default	Description
--stepMax	20000	Maximum simulation steps
--stopBySpeed	true	Stop agents when speed drops to zero

Series-Only

Flag	Default	Description
--min	(required)	Minimum number of agents
--step	(required)	Agent count increment
--max	(required)	Maximum number of agents
--taskList	""	Text file listing XML task files
-o, --output	result.csv	Output CSV path

Execution Modes

The solver supports three modes controlled by --lnsOnly and --orcaOnly:

Mode	Flag	Description
Full pipeline	(default)	LNS plans paths → extracts waypoints → ORCA executes with waypoint guidance
LNS only	--lnsOnly true	Evaluate discrete path quality without continuous simulation
ORCA only	--orcaOnly true	Run ORCA with its internal planner as a baseline (no LNS waypoints)

Setting both --lnsOnly and --orcaOnly simultaneously is an error.

Output Format

Single Test (stdout)

=== Results ===
LNS: 2.145s, cost=1234
ORCA: 5.678s, rate=100.00%
  Flowtime: 890.123
  Makespan: 45.678
  Collisions: 0
  Dependency Triggers: 3
  N_ag: 50
  ECBS Count: 2
Total: 7.823s

Series Test (result.csv)

Each row represents one (task, agent count) combination:

Column	Description
num_agents	Number of agents tested
map_name	Task file name (without path or extension)
lns_success	1 if LNS found a solution, 0 otherwise
lns_runtime	LNS wall-clock time (seconds)
lns_sum_of_costs	Total path cost after LNS optimization
lns_initial_costs	Path cost before LNS improvement
lns_iterations	Number of destroy-repair iterations
lns_avg_group_size	Average neighborhood group size
corridor_identify_time	Time spent identifying corridors (seconds)
dependency_build_time	Time spent building the dependency graph (seconds)
orca_runtime	ORCA wall-clock time (seconds)
success_rate	Percentage of agents reaching their goals
flow_time	Sum of individual agent arrival times
orca_makespan	Time for the last agent to arrive
orca_collisions	Agent–agent collisions
orca_collisions_obst	Agent–obstacle collisions
orca_sum_of_costs	Total cost in continuous space
dependency_triggers	Number of dependency-based replanning events
total_runtime	End-to-end wall-clock time (seconds)
used_waypoints	1 if LNS waypoints were used, 0 otherwise
mapf_successes	Successful MAPF sub-problem solves
n_ag	Average agent count in MAPF sub-problems
init_count	Number of MAPF initializations
ecbs_count	Number of ECBS solver invocations

LNS columns are omitted when running with --orcaOnly.

Examples

Full pipeline with 100 agents and a 60-second time limit:

./unified_mapf -x ../task_examples/warehouse.xml -k 100 -t 60

Sweep 20–200 agents with custom output:

./unified_series --min 20 --step 20 --max 200 \
    --taskList ../task_examples/tasks.txt \
    -o experiment_results.csv -t 120

ORCA-only baseline:

./unified_series --min 20 --step 20 --max 200 \
    --taskList ../task_examples/tasks.txt \
    --orcaOnly true -o baseline_orca.csv

Compare with and without waypoints:

# With waypoints (default)
./unified_series --min 50 --step 50 --max 300 \
    --taskList tasks.txt -o with_waypoints.csv

# Without waypoints
./unified_series --min 50 --step 50 --max 300 \
    --taskList tasks.txt --useWaypoints false -o without_waypoints.csv

References

1. J. Li, Z. Chen, D. Harabor, P. Stuckey, and S. Koenig. MAPF-LNS2: Fast Repairing for Multi-Agent Path Finding via Large Neighborhood Search. AAAI Conference on Artificial Intelligence, 2022.
2. J. van den Berg, S. Guy, M. Lin, and D. Manocha. Reciprocal n-Body Collision Avoidance. Robotics Research, 2011. See also the ORCA project page.
3. S. Dergachev and K. Yakovlev. Distributed Multi-Agent Navigation Based on Reciprocal Collision Avoidance and Locally Confined Multi-Agent Path Finding. arXiv:2107.00246, 2021.
4. ORCA* algorithm implementation on GitHub.