Decentralised Multi-Agent Crowd Navigation Using Braid-Inspired Topological Planning
W. van Mildert (TU Delft - Mechanical Engineering)
B. De Schutter – Mentor (TU Delft - Mechanical Engineering)
G. Battocletti – Mentor (TU Delft - Mechanical Engineering)
L. Ferranti – Graduation committee member (TU Delft - Mechanical Engineering)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
This thesis studies decentralised multi-robot navigation through dense pedestrian crowds. In such environments, robots must do more than avoid immediate collisions: they must make consistent qualitative decisions about how to pass pedestrians and how to yield or proceed in close robot-robot encounters. These decisions are difficult to represent in a purely reactive controller, yet enumerating all possible interaction patterns is too expensive for online planning in dense scenes.
The proposed method addresses this problem with a three-layer topology-inspired planner. First, deterministic pedestrian predictions are converted into a space-time density field, and a time-expanded A* search computes a coarse route that biases each robot away from high-density regions. Second, a local interaction layer selects the nearby agent-pedestrian and agent-agent events that matter for the current replanning window and searches the resulting sequence space with a bounded best-first procedure. Third, the selected sequence is converted into signed winding-number targets and realised by a short-horizon velocity-sampling controller. The method is decentralised: each robot runs the same planner locally, while the same execution-level safety layer is applied to all
methods in the comparison.
The planner is evaluated in simulation against ORCA, the Social Force model, Dynamic Channel, Socially Competent Navigation, and a decentralised model predictive control (MPC) baseline across several crowd densities and motion patterns. In the random-crowd comparison, the proposed method obtains the lowest collision rate at the highest tested density and reaches goals with competitive time to goal, while requiring substantially less computation time than the MPC baseline. The results indicate that separating route-level guidance, qualitative interaction search, and continuous realisation can make dense crowd navigation safer than purely reactive planning and cheaper than full optimisation-based control. The remaining limitations are the deterministic pedestrian predictions, simplified holonomic-disc dynamics, and hand-designed search and scoring rules, which motivate future work on uncertainty, richer robot dynamics, and more principled topological search.