Mixed Strategy Nash Equilibrium for Crowd Navigation
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Collision AvoidanceDecision MakingGaussian ProcessesSocial NavigationSimilar Papers 제목 키워드 기반
Mixed Strategy Game Model Against Data Poisoning Attacks
In this paper we use game theory to model poisoning attack scenarios. We prove the non-existence of pure strategy Nash Equilibrium in the attacker and defender game. We then propose a mixed extension of our game model an…
Data PoisoningModel PoisoningOn the Approximate Purification of Mixed Strategies in Games with Infinite Action Sets
We consider a game in which the action set of each player is uncountable, and show that, from weak assumptions on the common prior, any mixed strategy has an approximately equivalent pure strategy. The assumption of this…
Large Language Models Playing Mixed Strategy Nash Equilibrium Games
Generative artificial intelligence (Generative AI), and in particular Large Language Models (LLMs) have gained significant popularity among researchers and industrial communities, paving the way for integrating LLMs in d…
A Real-Time Generalized Nash Equilibrium Framework for Interaction-Aware Autonomous Driving in Mixed Traffic
Safe and efficient navigation in mixed-traffic environments remains a critical challenge for Autonomous Vehicles (AVs), primarily due to the complex interdependence between the AV's decisions and the unpredictable reacti…
Autonomous VehiclesAutonomous DrivingA Characterization of Nash Equilibrium in Behavioral Strategies through Local Sequential Rationality
The concept of Nash equilibrium in behavioral strategies (NashEBS) was formulated By Nash~\cite{Nash (1951)} for an extensive-form game through global rationality of nonconvex payoff functions. Kuhn's payoff equivalence …
Form