A distributed method to avoid higher-order deadlocks in multi-robot systems. (February 2020)

• Record Type: Journal Article
• Authors: Zhou, Yuan; Hu, Hesuan; Liu, Yang; Lin, Shang-Wei; Ding, Zuohua
• Is Part Of: Automatica. Volume 112(2020)
• Publication Date: 2020-02
• Subjects: Autonomous mobile robots -- Deadlock -- Robot control -- Discrete-event systems -- Distributed control; Automatic control -- Periodicals; Automation -- Periodicals; 629.805
• DOI: 10.1016/j.automatica.2019.108706
• Languages: English
• ISSNs: 0005-1098

Abstract

Abstract: Deadlock avoidance is a crucial problem in motion control of multi-robot systems since deadlocks can crash the systems and ∕ or degrade their performance. However, deadlocks sometimes are difficult to predict in advance because of the existence of higher-order deadlocks, from which a system can lead to a deadlock inevitably. In this paper, we investigate the properties of higher-order deadlocks and propose a distributed approach to their avoidance in multi-robot systems where each robot has a predetermined and closed path to execute persistent motion. After modeling the motion of robots by labeled transition systems (LTSs), we first conclude that there exist at most the ( N − 3 ) -th order deadlocks with N robots. This means that deadlocks, if any, will occur unavoidably within N − 3 steps of corresponding transitions. A distributed algorithm is then proposed to avoid deadlocks in such systems. In the algorithm, each robot only needs to look ahead at most N − 1 states, i.e., N − 3 intermediate states and two endpoint states, to decide whether its move can cause higher-order deadlocks. To execute the algorithm, each robot needs to communicate with its neighbors. The theoretical analysis and experimental study show that the proposed algorithm is practically operative.