C-ABT: A continuous control layer for inter-agent collision avoidance based on asynchronous backtracking

Abstract

When using multiple robotic agents for waypoint-based exploration or coverage tasks, collision avoidance between agents is an important issue. With a centralized planner, this issue arises only at one central instance. However, when using asynchronous and/or decentralized algorithms, decentralized methods for collision avoidance need to be used. We propose a novel approach based on the asynchronous backtracking (ABT) algorithm which provides decentralized constraint satisfaction called continuous ABT(C-ABT). C-ABT is a continuous extension to ABT intended as a collision avoidance layer for existing multi-agent waypoint navigation. It extends ABT in the sense that participating agents know when they found a valid solution. In this case, agents can safely move to their selected waypoints. While ABT only finds one static solution, C-ABT is suited for continuously provided new waypoints for all agents. By using the concept of local neighborhoods, C-ABT is also scalable to swarms of arbitrary size.