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 — bundled as a git submodule in external/tinyxml2/

Build

tinyxml2 is a git submodule, so fetch it before configuring (or clone the repo with git clone --recursive <url>):

git submodule update --init --recursive

mkdir build && cd build
cmake ..
make

This produces a single executable, corca, which solves one instance per invocation. Agent-count / map / variant sweeps are driven by the Python experiment runner under exp/ — one process per (map, scen, agent-count, variant) run.

Usage

corca solves one instance per invocation. It takes the instance geometry on the command line (a MovingAI .map + .scen), every hyper-parameter from a YAML --config file, and the algorithm --variant:

./corca --map <map> --scen <scen> --config <config.yml> --variant <name> -k <num_agents>

Argument	Required	Description
--map	✓	MovingAI .map (occupancy grid; ./G free, everything else blocked)
--scen	✓	MovingAI .scen (start/goal pairs; the first -k are used)
--config	✓	YAML file with every hyper-parameter — see Configuration and config/default.yml
--variant	✓	Algorithm variant: orca | orca-mapf | corca | corca-mapf | lns-only
-k, --agentNum	✓	Number of agents (capped at the scen's count)
-o, --output		Experiment result CSV (one row)
--debugLog		Per-step plain-text trace of the ORCA execution — see Debug logging
-s, --screen		Console verbosity (0 = silent, 3 = verbose)

Example (C-ORCA*-MAPF, 50 agents):

./corca --map ../dataset/room-32-32-4/room-32-32-4.map \
        --scen ../dataset/room-32-32-4/room-32-32-4-even-1.scen \
        --config ../config/default.yml --variant corca-mapf -k 50 -o out.csv

Run controls (random seed, time limit, step cap) and every agent / simulation / LNS / corridor parameter live in the --config file — only the agent count -k varies per run on the command line. The summary is printed to stdout and, with -o, written as a one-row CSV (see Output Format).

Running experiments (sweeps)

Multi-instance sweeps (the paper's agent-count curves over the benchmark maps) are owned by the Python runner in exp/, not the binary. It fans one corca process out per (map × scen × agent-count × variant), collects the per-run CSV rows, and renders success-rate / flowtime / ECBS-call figures.

cd exp
python3 runAll.py --procs 8            # full sweep: generate -> run -> merge -> plot
python3 runAll.py --limit 8 --procs 4  # quick smoke test (first 8 commands)

The sweep axes (maps, scen instances, agent counts, the four variants) are configured in exp/config.py, which also points at the shared --config YAML (CONFIG); the solver hyper-parameters — including seed and time limit — live in that YAML (config/default.yml). Everything a run produces lands under exp/<date>/ (results/ per-run CSVs, the merged <date>.csv, and figures/). Set the DISCORD_WEBHOOK environment variable to also post progress + figures to Discord (unset = no notifications). See exp/ for details.

Configuration

Every hyper-parameter lives in the --config YAML file (required). Start from config/default.yml — it documents every key with its default. The format is a small YAML subset: key: value scalars, # comments, and section headers that are purely cosmetic (keys share one flat namespace, so each key must be unique). Missing keys keep their built-in defaults.

Section	Keys (default)
run	seed (0), time_limit (300 s, LNS + ORCA), step_max (20000), stop_by_speed (true)
agent	radius (0.3), max_speed (1.0), sight_radius (10), time_boundary (5.4), time_boundary_obst (10), reps (0.1), agents_max_num (10)
sim	cell_size (1.0), timestep (0.25), delta (0.1, goal-reached distance)
mapf	trigger (speed-buffer), mapf_num (3) — the ECBS/PnR fallback trigger
lns	init_algo (PP), replan_algo (PP), destroy_strategy (Adaptive), init_destroy_strategy (Adaptive), neighbor_size (8), max_iterations (0), pibt_window (5), init_lns (true), sipp (true), pibt_soft (true)
corridor	waypoint_reach_tol (0.3), in_corridor_tol (0.8), goal_in_corridor_tol (0.5), gate_match_eps (0.1), priority_threshold (0.001)

The algorithm variant is not in the config — it is --variant on the command line, so one config sweeps all four methods. -k (agent count) is also a CLI flag. A few non-hyper-parameter flags stay on the CLI too: --waypointFile (intermediate file path), --stats (LNS iteration trace), -s/--screen (verbosity).

Debug logging

--debugLog <file> writes a plain-text trace of the ORCA execution, one block per simulation time step. Each block lists, for every agent:

• position, preferred velocity (pv, before ORCA's collision-avoidance projection) and actual velocity (v, applied this step, with its speed s);
• the current target (tgt) it steers to and, under corridor guidance, its SADG waypoint (wp);
• its state — ORCA (regular reactive navigation), DRIFT (waiting at a corridor mouth under the C-ORCA* gate), MAPF (executing an ECBS/PnR sub-plan), or YIELD (yielding to another agent);
• when drifting, which corridor it is queued behind and which agent it is waiting for (waitFor); when yielding, yieldTo.

./corca --map ../dataset/room-32-32-4/room-32-32-4.map \
        --scen ../dataset/room-32-32-4/room-32-32-4-even-1.scen \
        --config ../config/default.yml --variant corca-mapf -k 50 --debugLog run.log

Render the trace as a portable, interactive HTML viewer with example/viz_debug.py:

python3 example/viz_debug.py --log run.log --map ../dataset/room-32-32-4/room-32-32-4.map

Sample lines:

# step 812  t=203.0000
id=36 pos=(30.36,32.11) v=(0.62,0.12)|s=0.63 pv=(0.00,0.00)|s=0.00 tgt=(30.20,32.08) state=DRIFT wp=(32.50,31.50) corridor=4 waitFor=9
id=41 pos=(22.47,19.41) v=(0.00,0.00)|s=0.00 pv=(0.00,0.00)|s=0.00 tgt=(22.50,19.50) state=MAPF wp=(22.50,15.50)

Note: the trace is verbose — one line per agent per step, and the ORCA phase runs up to step_max steps — so a full run can produce hundreds of MB. For interactive debugging keep -k and step_max small.

Reproducing the Paper Variants

The paper evaluates four methods that differ along two independent axes. A single binary + config runs any of them; the axis combination is selected by --variant:

• C- layer — the proactive corridor guidance (LNS waypoints + corridor dependencies).
• -MAPF layer — the reactive ECBS deadlock fallback.

Variant	Corridor guidance (C-)	ECBS fallback (-MAPF)	--variant
ORCA*	✗	✗	orca
ORCA*-MAPF	✗	✓	orca-mapf
C-ORCA*	✓	✗	corca
C-ORCA*-MAPF	✓	✓	corca-mapf

(lns-only is a fifth variant that runs just the LNS pre-processing, for evaluating discrete path quality.) To confirm the fallback is truly disabled, check that the ecbs_count column is 0 for the orca and corca runs.

Example runs (single instance)

One .map/.scen instance with 50 agents — same config, one command per variant:

MAP=../dataset/room-32-32-4/room-32-32-4.map
SCEN=../dataset/room-32-32-4/room-32-32-4-even-1.scen
CFG=../config/default.yml

./corca --map $MAP --scen $SCEN --config $CFG --variant orca       -k 50 -o orca.csv        # ORCA*
./corca --map $MAP --scen $SCEN --config $CFG --variant orca-mapf  -k 50 -o orca_mapf.csv   # ORCA*-MAPF
./corca --map $MAP --scen $SCEN --config $CFG --variant corca      -k 50 -o corca.csv       # C-ORCA*
./corca --map $MAP --scen $SCEN --config $CFG --variant corca-mapf -k 50 -o corca_mapf.csv  # C-ORCA*-MAPF

Example runs (agent-count sweep)

Sweeps over agent counts, maps, and instances are driven by the experiment runner, which fans the four variants out automatically. The variant list is in exp/config.py (VARIANTS), the shared config in CONFIG, and the agent-count axis in AGENT_NUMS.

cd exp
python3 runAll.py --procs 8

See Running experiments (sweeps).

Output Format

Console (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

CSV (-o <file>)

Each corca run writes a header plus one data row for its single (map, scen, agent-count, variant) instance. The experiment runner (exp/merge.py) stitches these per-run rows into one table for plotting. Columns:

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 for the orca / orca-mapf variants (no LNS phase).

Examples

Full pipeline (C-ORCA*-MAPF) with 50 agents, writing a one-row CSV:

./corca --map ../dataset/room-32-32-4/room-32-32-4.map \
        --scen ../dataset/room-32-32-4/room-32-32-4-even-1.scen \
        --config ../config/default.yml --variant corca-mapf -k 50 -o result.csv

ORCA-only baseline (no corridor guidance, no ECBS fallback):

./corca --map ../dataset/room-32-32-4/room-32-32-4.map \
        --scen ../dataset/room-32-32-4/room-32-32-4-even-1.scen \
        --config ../config/default.yml --variant orca -k 50 -o baseline_orca.csv

For agent-count sweeps across the benchmark maps, use the experiment runner rather than looping the binary by hand — it fans out all four variants over the configured agent counts and instances and produces the comparison figures:

cd exp
python3 runAll.py --procs 8

See Running experiments (sweeps).

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.