Distributed Adaptive Multi-robot Navigation in Crowded and Maze-like Environments

Groups of ground robots deployed in pedestrian crowds and maze-like environments face similar challenges: no global map, unreliable long-range communication, single-file passages, and strict safety margins. This thesis develops and validates distributed navigation algorithms that enable them to move safely and efficiently in both settings using only onboard sensing and peer-to-peer messages. For crowded environments, I studied groups of simulated robots encountering different types of crowds where the people either remained passive, moved towards the robots, or crossed their path at right angles. Three behavioral strategies were tested: one involving independent movement, one involving cooperative movement, and an adaptive one combining the other two. Simulations with up to 200 robots showed that the cooperative strategy caused fewer disturbances and was more effective in dense crowds; the independent strategy was superior when there were only a few people and when people were moving at right angles to the robots. The proposed adaptive strategy switches between cooperative and independent behaviors, combining the strengths of both strategies in all the scenarios considered. For maze-like environments, I designed a distributed maze traversal strategy: one robot leads using a single agent maze solver, while others follow their neighbors. When the solver suggests a move towards another agent, the move is discarded, and instead, the lead role gets transferred to this agent. A formal analysis shows that every robot reaches the exit whenever a single-agent solver could. Simulations with up to 300 robots and several single-agent solvers show our approach finishes sooner than a naïve strategy, beats a global-communication baseline in terms of mission time, and, as I formally prove, is asymptotically equivalent to an oracle planner. Mixed reality experiments were performed to validate the proposed algorithms using up to 20 Pi-puck robots. This work enables multi-robot navigation in complex real-world environments in the future.