We address the problem of finding mixed-strategy Nash equilibrium for crowd
navigation. Mixed-strategy Nash equilibrium provides a rigorous model for the
robot to anticipate uncertain yet cooperative human behavior in crowds, but the
computation cost is often too high for scalable and real-time decision-making.
Here we prove that a simple iterative Bayesian updating scheme converges to the
Nash equilibrium of a mixed-strategy social navigation game. Furthermore, we
propose a data-driven framework to construct the game by initializing agent
strategies as Gaussian processes learned from human datasets. Based on the
proposed mixed-strategy Nash equilibrium model, we develop a sampling-based
crowd navigation framework that can be integrated into existing navigation
methods and runs in real-time on a laptop CPU. We evaluate our framework in
both simulated environments and real-world human datasets in unstructured
environments. Our framework consistently outperforms both non-learning and
learning-based methods on both safety and navigation efficiency and reaches
human-level crowd navigation performance on top of a meta-planner.

用简单的迭代贝叶斯更新方案证明了混合策略纳什均衡模型收敛于混合策略社交导航游戏的纳什均衡，并提出了一个基于数据驱动的框架，该框架通过将代理策略初始化为从人类数据集中学得的高斯过程来构建游戏。基于提出的混合策略纳什均衡模型，我们开发了一个基于采样的群体导航框架，可以集成到现有的导航方法中，在笔记本电脑的 CPU 上实时运行。我们在模拟环境和非结构化环境中的真实人类数据集上评估了我们的框架，其在安全性和导航效率方面始终优于非学习和基于学习的方法，并在元规划之上达到了人类水平的群体导航性能。

人群导航的混合策略纳什均衡

Mixed-Strategy Nash Equilibrium for Crowd Navigation

We provide the first fully polynomial time approximation scheme (FPTAS) for
computing an approximate mixed-strategy Nash equilibrium in tree-structured
graphical multi-hypermatrix games (GMhGs). GMhGs are generalizations of
normal-form games, graphical games, graphical polymatrix games, and
hypergraphical games. Computing an exact mixed-strategy Nash equilibria in
graphical polymatrix games is PPAD-complete and thus generally believed to be
intractable. In contrast, to the best of our knowledge, we are the first to
establish an FPTAS for tree polymatrix games as well as tree graphical games
when the number of actions is bounded by a constant. As a corollary, we give a
quasi-polynomial time approximation scheme (quasi-PTAS) when the number of
actions is bounded by the logarithm of the number of players.

该文提供了第一个完全多项式时间的近似混合策略纳什均衡算法，用于计算树形图多超矩阵博弈中的纳什均衡，并证明当操作数量受到限制时，该算法适用于树状多项式博弈和树形图博弈，并引出了拟多项式时间的近似算法。