Multi-robot Path Planning with the Spatio-Temporal A* Algorithm and Its Variants

This paper presents the design of an offline collision-free path planning algorithm for multiple mobile robots travelling simultaneously on a 2D gridded map. We first solved this problem by extending the traditional A* algorithm into 3D, namely two spatial and one time dimensions. This 3D approach is proved computationally costly and this led to the development of a novel and faster Spatio-Temporal (S-T) A* algorithm. This is a modified A* algorithm, which uses discrete time stamps and a temporal occupancy table to communicate previously planned routes and potential collision among robots. We further adapted the S-T A* algorithm to allow robots to stop and wait near nodes where potential collision is detected in order to increase their probability of finding a viable path to their destination. Using a time-based objective function that requires all robots in the environment to reach their respective destination in the shortest possible time, this decoupled planning strategy was done using a fixed priority based on the slowest robot first. Another variant using an adaptive priority scheme was then introduced to improve the success rate of finding a viable path for all robots as the number of robots in the fixed-sized environment increased. We present experimental results comparing the performance of the various path planning and priority schemes.