  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 Bayes' Rule 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.
