Hamiltonian coordination primitives for decentralized multiagent navigation. (September 2021)

• Record Type: Journal Article
• Authors: Mavrogiannis, Christoforos; Knepper, Ross A.
• Other Names: Morales Marco guest-editor.; Tapia Lydia guest-editor.; Sánchez-Ante Gildardo guest-editor.; Hutchinson Seth guest-editor.
• Is Part Of: International journal of robotics research. Volume 40:Number 10/11(2021)
• Page Start: 1234
• Page End: 1254
• Publication Date: 2021-09
• Subjects: Robot navigation -- multi-robot systems -- motion planning -- trajectory optimization -- topological methods; Robots -- Periodicals; Robots, Industrial -- Periodicals; 629.89205
• DOI: 10.1177/02783649211037731
• Languages: English
• ISSNs: 0278-3649

Abstract

We focus on decentralized navigation among multiple non-communicating agents in continuous domains without explicit traffic rules, such as sidewalks, hallways, or squares. Following collision-free motion in such domains requires effective mechanisms of multiagent behavior prediction. Although this prediction problem can be shown to be NP-hard, humans are often capable of solving it efficiently by leveraging sophisticated mechanisms of implicit coordination. Inspired by the human paradigm, we propose a novel topological formalism that explicitly models multiagent coordination. Our formalism features both geometric and algebraic descriptions enabling the use of standard gradient-based optimization techniques for trajectory generation but also symbolic inference over coordination strategies. In this article, we contribute (a) HCP (Hamiltonian Coordination Primitives), a novel multiagent trajectory-generation pipeline that accommodates spatiotemporal constraints formulated as symbolic topological specifications corresponding to a desired coordination strategy; (b) HCPnav, an online planning framework for decentralized collision avoidance that generates motion by following multiagent trajectory primitives corresponding to high-likelihood, low-cost coordination strategies. Through a series of challenging trajectory-generation experiments, we show that HCP outperforms a trajectory-optimization baseline in generating trajectories of desired topological specifications in terms of success rate and computational efficiency. Finally, through a variety of navigation experiments, we illustrate the efficacy of HCPnav in handling challenging multiagent navigation scenarios under homogeneous or heterogeneous agents across a series of environments of different geometry.