Decentralized Multi-robot Path Planning using Graph Neural Networks

Communication plays a key role for fruitful decentralized multi-robot path planning. However, it is quite difficult to discern which insight is necessary to perform the assignment, when and how it should be exchanged among robots. To avoid these problems and go beyond the ad hoc design of heuristics, we introduce an integrated model that generates coherent, inter-communication and decision-making for robots operating in a confined working environment. The architecture of our work includes a convolutional neural network (CNN) to achieve sufficient patterns from nearby sensing and a graph neural network (GNN) to share these characteristics within robots. This trained network mimics an expert algorithm and can be employed online in decentralized planning where we have only local interaction and observations. In the simulation-based evaluation, we steer group of robots to their goals in 2D complex work environments. We compute the success probability and total cost along each of planned strategies. The performance of our algorithm is nearly the same as our expert algorithm, which proves the potency of the advocated technique. Specifically, we demonstrate that our model allows for testing on new cases (large environments, a larger number of robots).

I. Introduction

Mobility and collaboration in multiple robot systems require basic algorithms for near-optimal and collision-free motion planning. This scenario is known as the Multi-Agent Path Finding (MAPF) or Multi-Robot Path Planning (MRPP), and the goal is to find paths that will lead the robots from start positions to desired goals without colliding with each other. Existing strategies can be broken down into coupled or decoupled, based on the nature of the state space that is explored. Although these techniques couple the sub-problems and are able to provide an optimal and complete solution, they contain centralized components, and their efficiency reduces as the amount of autonomous bodies grows [1] [2]. In contrast, decoupled methods, individually compute tracks for every robot, and re-schedule only in the situation of interferences [3] [4] [5]. This can greatly lessen the computational load of planning issue, though typically yields imprudent and partial solutions. The balance between optimality, completeness, and the computational complexity of discovering a resolution, though it is a challenging research direction [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19]. This work deals with multiple robot path planning in cases where the robots have limited visibility and communication capability, and no absolute frame of reference for navigation. This is a natural extension to consider especially when one is thinking of physical robots which have inherent limitations in terms of their communication and perception interfaces [17].