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

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 whic...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-06
Main Authors: Chandra, Rohan, Menon, Rahul, Sprague, Zayne, Arya Anantula, Biswas, Joydeep
Format: Article
Language:English
Subjects:
Algorithms
Collision avoidance
Collision dynamics
Flow velocity
Game theory
Games
Machine learning
Multiagent systems
Multiple robots
Navigation
Optimization
Real time
Robot dynamics
Simulation models
Trajectory optimization
Trajectory planning
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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}\).
ISSN:2331-8422