Action Selection Methods for Multi-Agent Navigation in Crowded Environments

Julio GodoyIJCAI 2016

Introduction

In multi-agent systems, such as warehouse robotics or autonomous traffic management, agents must navigate toward goals while maintaining safety. The current industry-standard framework, Optimal Reciprocal Collision Avoidance (ORCA), provides local optimality but often fails in high-density scenarios. In crowded environments, purely selfish local avoidance leads to "freezing" or gridlock. This paper proposes three decentralized methods—PHOP, ALAN, and C-Nav—that leverage online action selection and implicit coordination to achieve global efficiency without a central controller.

Proposed Navigation Methods

To move beyond simple collision avoidance, the authors introduce three distinct approaches:

  1. Progressive Hindsight Optimization (PHOP): This planning-based method allows agents to simulate multiple action sequences over a specific time horizon. By evaluating these plans in "hindsight," agents can identify and avoid regions likely to become congested, making more informed immediate moves.
  2. Adaptive Learning for Agent Navigation (ALAN): Treating navigation as a non-stationary multi-armed bandit problem, ALAN uses a mix of exploitation and biased exploration. This learning-based framework allows agents to adapt to the changing behaviors of their neighbors using game-theoretic principles.
  3. Coordinated Navigation (C-Nav): Designed specifically for high-density crowds, C-Nav enables agents to predict the likely trajectories of neighbors. Agents then select velocities that optimize the group's overall flow. This implicit coordination scales effectively to hundreds of agents as it requires no explicit communication.

Experimental Evaluation

The proposed methods were tested across three simulated environments designed to provoke specific navigation challenges: Circle (bottlenecking), Bidirectional (corridor flow), and Crowd (general high-density movement).

Evaluation environments and interaction overhead results comparing ORCA, ALAN, and C-Nav.

Key Results and Insights

The primary metric for evaluation is Interaction Overhead, which quantifies the time agents spend navigating around others compared to their ideal travel time in an empty space.

Quantitative Performance

As shown in the experimental results, C-Nav consistently achieves the lowest interaction overhead across all scenarios. ALAN also demonstrates a significant improvement over the standard ORCA framework in the Circle and Bidirectional environments, validating the utility of online learning in dynamic navigation tasks.

Qualitative Coordination and Congestion Resolution

A critical insight of this work is the distinction between local and global efficiency. While ORCA prevents collisions, it often results in deadlocks in narrow passages because agents do not account for the space needed by others.

Comparison of agent flow in a bidirectional corridor: (a) shows congestion/deadlock, while (b) demonstrates smooth coordination.

As illustrated in the bidirectional corridor test, C-Nav agents successfully resolve potential deadlocks that freeze ORCA-based systems. By predicting neighbor motion and choosing velocities that benefit the group flow, agents achieve fluid movement through implicit coordination.

Conclusion and Future Work

The research demonstrates that moving beyond local collision avoidance to implicit coordination significantly reduces congestion in multi-agent systems. While the current models assume homogeneous agents, future work will address heterogeneous environments where agents must infer the strategies of others—including humans—to maintain safety and efficiency.

Summary updated

BibTeX
@inproceedings{godoy2016action,
  author = {Julio Godoy},
  title = {{Action Selection Methods for Multi-Agent Navigation in Crowded Environments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure