Real time replanning based on A* for collision avoidance in multi-robot systems

Abstract

This paper deals with collision avoidance for multiple robots and methods to allow robots to replan their routes in real time, taking into account a dynamic environment. A number of collision types are defined for multiple robots and, in particular, between pairs of robots that need to be handled by any real-time collision avoidance system. A novel extension to the standard A* algorithm is presented (Super A*) that solves these collision types by using dynamic real time monitoring and iterative move-evaluate-move cycles. The proposed extension to A* is capable of avoiding not just other moving robots but also static obstacles. Also, the proposed extension allows robots to replan their routes as optimally as possible. Simulations of the algorithm are conducted in different state-space configurations. The algorithm is tested on two minibots in real world, small-scale environments containing obstacles. The results show that the collision avoidance and replanning approach is effective and useful for managing possible collisions between robots working independently in a shared physical environment and needing to traverse the environment to undertake and complete their tasks.