PIPO: Policy Optimization with Permutation-Invariant Constraint for Distributed Multi-Robot Navigation

For large-scale multi-agent systems (MAS), ensuring the safety and effectiveness of navigation in complicated scenarios is a challenging task. With the agent scale increasing, most existing centralized methods lose their magic for the lack of scalability, and the popular decentralized approaches are hampered by high latency and computing requirements. In this research, we offer PIPO, a novel policy optimization algorithm for decentralized MAS navigation with permutation-invariant constraints. To conduct navigation and avoid un-necessary exploration in the early episodes, we first defined a guide-policy. Then, we introduce the permutation invariant property in decentralized multi-agent systems and leverage the graph convolution network to produce the same output under shuffled observations. Our approach can be easily scaled to an arbitrary number of agents and used in large-scale systems for its decentralized training and execution. We also provide extensive experiments to demonstrate that our PIPO significantly outperforms the baselines of multi-agent reinforcement learning algorithms and other leading methods in variant scenarios.

I. Introduction

Multi-agent navigation is a promising issue and has wide real-world applications such as cargo transportation, traffic scheduling and autonomous driving [1]. However, safe navigation from the initial location to the destination is always challenging due to the high density of agents, partial observation, high-dimensional state space, nonlinear dynamics, etc. Moreover, in a multi-agent system (MAS), we take the overall system efficiency and security as the main criterion rather than only considering the single-agent tasks. In other words, for each individual, a reasonable policy is required in some cases to make altruistic behavior in the shared environment to maximize total returns, rather than just greedily obtaining private rewards.