Mixed Strategy Nash Equilibrium for Crowd Navigation

📄 arXiv: 2403.01537v6 📥 PDF

作者: Max Muchen Sun, Francesca Baldini, Katie Hughes, Peter Trautman, Todd Murphey

分类: cs.RO, cs.GT, cs.LG

发布日期: 2024-03-03 (更新: 2024-11-25)

备注: Accepted to The International Journal of Robotics Research (IJRR)

💡 一句话要点

提出贝叶斯递归纳什均衡以解决人群导航问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 人群导航 博弈论 混合策略纳什均衡 贝叶斯更新 实时路径规划 机器人导航 人机协作

📋 核心要点

  1. 现有方法在拥挤环境中容易导致机器人冻结，无法有效应对动态人群。
  2. 提出的贝叶斯递归纳什均衡（BRNE）算法通过迭代更新概率分布，实现实时路径规划与行人路径预测。
  3. BRNE在模拟和真实数据集上均表现出色，超越了传统方法，达到人类水平的导航效率。

📝 摘要（中文）

在拥挤区域中，机器人应与人类协商自由空间，而非完全控制碰撞避免，这样可以避免冻结行为。本文利用博弈论为机器人提供了在路径规划中考虑人类潜在合作的框架。特别地，混合策略纳什均衡能够捕捉不确定性下的协商行为，适用于人群导航。然而，计算混合策略纳什均衡通常在实时决策中代价高昂。我们提出了一种基于概率分布的迭代贝叶斯更新方案，算法同时生成机器人的随机规划和对其他行人路径的概率预测。我们证明该算法等同于解决人群导航的混合策略博弈，并保证恢复全局纳什均衡。我们将算法命名为贝叶斯递归纳什均衡（BRNE），并开发了实时模型预测的人群导航框架。BRNE在模拟环境和真实行人数据集中的表现优于非学习和基于学习的方法，达到了人类水平的导航性能。

🔬 方法详解

问题定义：本文旨在解决机器人在拥挤环境中导航时的碰撞避免问题。现有方法往往依赖于完全控制，导致机器人在复杂人群中出现冻结行为，无法有效应对动态变化。

核心思路：论文提出的BRNE算法通过博弈论框架，利用混合策略纳什均衡来处理不确定性下的人类行为，允许机器人与行人进行协商，从而实现更自然的导航。

技术框架：BRNE算法的整体架构包括两个主要模块：一是生成机器人的随机路径规划，二是对其他行人路径的概率预测。算法通过迭代贝叶斯更新，实时调整路径规划以适应环境变化。

关键创新：BRNE的最大创新在于其专门为人群导航设计的混合策略博弈解决方案，使得算法能够在低功耗嵌入式计算机上实时运行，克服了传统方法的计算复杂性。

关键设计：算法在参数设置上进行了优化，采用了适合人群导航的损失函数和网络结构，确保了在动态环境中的高效决策和路径规划。具体的技术细节包括对行人行为的概率建模和路径预测的精确性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

BRNE算法在多个实验中表现优异，尤其是在安全性和导航效率方面，超越了传统的非学习和基于学习的方法。在真实行人数据集基准测试中，BRNE达到了人类水平的导航性能，显示出其在实际应用中的巨大潜力。

🎯 应用场景

该研究的潜在应用领域包括智能机器人、自动驾驶汽车和人机协作系统等。在这些场景中，机器人能够更自然地与人类互动，提升安全性和效率。未来，该算法有望在更复杂的动态环境中得到广泛应用，推动人机协作技术的发展。

📄 摘要（原文）

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.