Search this site
Embedded Files
Bayesian Recursive Nash Equilibrium

Mixed Strategy Nash Equilibrium for Crowd Navigation

Max M. Sun, Francesca Baldini, Katie Hughes, Peter Trautman, and Todd Murphey

Department of Mechanical Engineering, Northwestern University

Honda Research Institute (USA)

Update: We recently completed a five-month field deployment of the algorithm on an untethered robot relying only on onboard computation and perception in Santa Cruz, CA. This was part of a large-scale field study of robot crowd navigation in the wild, in collaboration with Honda Research Institute and UC Santa Cruz. The results are currently under review, so stay tuned for more information!

(Courtesy: Kevin Weatherwax)

Publications

[IJRR] paper: Mixed Strategy Nash Equilibrium for Crowd Navigation (GitHub)

[RSS] Move Beyond Trajectories: Distribution Space Coupling for Crowd Navigation (GitHub)

[ICRA] Inverse Mixed Strategy Games with Generative Trajectory Models (GitHub)

GitHub:  Tutorials + Full ROS Implementation + Simulated Benchmark

https://github.com/MurpheyLab/brne

Abstract

Robots navigating in crowded areas should negotiate free space with humans rather than fully controlling collision avoidance, as this can lead to freezing behavior. Game theory provides a framework for the robot to reason about potential cooperation from humans for collision avoidance during path planning. In particular, the mixed strategy Nash equilibrium captures the negotiation behavior under uncertainty, making it well suited for crowd navigation. However, computing the mixed strategy Nash equilibrium is often prohibitively expensive for real-time decision-making. In this paper, we propose an iterative Bayesian update scheme over probability distributions of trajectories. The algorithm simultaneously generates a stochastic plan for the robot and probabilistic predictions of other pedestrians’ paths. We prove that the proposed algorithm is equivalent to solving a mixed strategy game for crowd navigation, and the algorithm guarantees the recovery of the global Nash equilibrium of the game. We name our algorithm Bayesian Recursive Nash Equilibrium (BRNE) and develop a real-time model prediction crowd navigation framework. Since BRNE is not solving a general-purpose mixed strategy Nash equilibrium but a tailored formula specifically for crowd navigation, it can compute the solution in real-time on a low-power embedded computer. We evaluate BRNE in both simulated environments and real-world pedestrian datasets. BRNE consistently outperforms non-learning and learning-based methods regarding safety and navigation efficiency. It also reaches human-level crowd navigation performance in the pedestrian dataset benchmark. Lastly, we demonstrate the practicality of our algorithm with real humans on an untethered quadruped robot with fully onboard perception and computation.

Video: Hardware demonstrations with 10 pedestrians

Video: Hardware demonstrations with 4 pedestrians

Video: Demonstration of the evolution of mixed strategies during 

the proposed iterative Bayesian update scheme.

Video: Example trials from the multi-agent navigation experiment

Video: Example trials from the simulated crowd navigation experiment

Video: Example trials from the human dataset benchmark

Google Sites
Report abuse
Page details
Page updated
Google Sites
Report abuse