This paper presents a fully decentralized approach for realtime
non-cooperative multi-robot navigation in social mini-games, such as navigating
through a narrow doorway or negotiating right of way at a corridor
intersection. Our contribution is a new realtime bi-level optimization
algorithm, in which the top-level optimization consists of computing a fair and
collision-free ordering followed by the bottom-level optimization which plans
optimal trajectories conditioned on the ordering. We show that, given such a
priority order, we can impose simple kinodynamic constraints on each robot that
are sufficient for it to plan collision-free trajectories with minimal
deviation from their preferred velocities, similar to how humans navigate in
these scenarios.
We successfully deploy the proposed algorithm in the real world using F$1/10$
robots, a Clearpath Jackal, and a Boston Dynamics Spot as well as in simulation
using the SocialGym 2.0 multi-agent social navigation simulator, in the doorway
and corridor intersection scenarios. We compare with state-of-the-art social
navigation methods using multi-agent reinforcement learning, collision
avoidance algorithms, and crowd simulation models. We show that $(i)$ classical
navigation performs $44\%$ better than the state-of-the-art learning-based
social navigation algorithms, $(ii)$ without a scheduling protocol, our
approach results in collisions in social mini-games $(iii)$ our approach yields
$2\times$ and $5\times$ fewer velocity changes than CADRL in doorways and
intersections, and finally $(iv)$ bi-level navigation in doorways at a flow
rate of $2.8 - 3.3$ (ms)$^{-1}$ is comparable to flow rate in human navigation
at a flow rate of $4$ (ms)$^{-1}$.

本文提出了一种全面去中心化的方法，用于社交小游戏中的实时非合作多机器人导航，使用新的实时双层优化算法来规划基于优先顺序的最优轨迹，并证明了该算法的有效性。

通过双层优化的去中心化非合作机器人社交导航

Decentralized Social Navigation with Non-Cooperative Robots via Bi-Level  Optimization

When robots share the same workspace with other intelligent agents (e.g.,
other robots or humans), they must be able to reason about the behaviors of
their neighboring agents while accomplishing the designated tasks. In practice,
frequently, agents do not exhibit absolutely rational behavior due to their
limited computational resources. Thus, predicting the optimal agent behaviors
is undesirable (because it demands prohibitive computational resources) and
undesirable (because the prediction may be wrong). Motivated by this
observation, we remove the assumption of perfectly rational agents and propose
incorporating the concept of bounded rationality from an information-theoretic
view into the game-theoretic framework. This allows the robots to reason other
agents' sub-optimal behaviors and act accordingly under their computational
constraints. Specifically, bounded rationality directly models the agent's
information processing ability, which is represented as the KL-divergence
between nominal and optimized stochastic policies, and the solution to the
bounded-optimal policy can be obtained by an efficient importance sampling
approach. Using both simulated and real-world experiments in multi-robot
navigation tasks, we demonstrate that the resulting framework allows the robots
to reason about different levels of rational behaviors of other agents and
compute a reasonable strategy under its computational constraint.

通过将有限理性概念与信息论观点相结合，将其融入博弈论框架中以预测自己及其它机器人或人类邻近代理的行为以及在其计算限制下采取行动，模拟与实际实验都证明这种方法可以帮助机器人推理其他代理的不同智能水平并计算出合理的策略。