Symmetry-Breaking in Multi-Agent Navigation: Winding Number-Aware MPC with a Learned Topological Strategy

Abstract

In decentralized multi-agent navigation, agents that independently compute their controls without communicating goals or intentions can fall into symmetry-induced deadlocks because each agent must decide how to pass others. We study this problem under the assumption that each agent has access to the current observable states of other agents, including their positions, velocities, and radii, while their goals, intentions, and future trajectories remain unobserved. To address this problem, we propose WNumMPC, a hierarchical navigation method that quantifies cooperative symmetry-breaking strategies via a topological invariant, the winding number, and learns such strategies through reinforcement learning. The learning-based Planner outputs continuous-valued signed target winding numbers and dynamic importance weights to prioritize critical interactions in dense crossings. Then, the model-based Controller generates collision-free and efficient motions based on the strategy and weights provided by the Planner. Simulation and real-world robot experiments indicate that WNumMPC effectively avoids deadlocks and collisions and achieves better performance than the baselines, particularly in dense and symmetry-prone scenarios. These experiments also suggest that explicitly leveraging winding numbers yields robust sim-to-real transfer with minimal performance degradation. The code for the experiments is available at https://github.com/omron-sinicx/WNumMPC.