Please use this identifier to cite or link to this item:
Title: A distributed method to avoid higher-order deadlocks in multi-robot systems
Authors: Zhou, Yuan
Hu, Hesuan
Liu, Yang
Lin, Shang-Wei
Ding, Zuohua
Keywords: Engineering::Computer science and engineering
Issue Date: 2019
Source: Zhou, Y., Hu, H., Liu, Y., Lin, S. & Ding, Z. (2019). A distributed method to avoid higher-order deadlocks in multi-robot systems. Automatica, 112, 108706-.
Project: MOE2015-T2-2-049
Journal: Automatica
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.
ISSN: 0005-1098
DOI: 10.1016/j.automatica.2019.108706
Rights: © 2019 Elsevier Ltd. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Citations 20

Updated on Jul 5, 2022

Citations 20

Updated on Jul 6, 2022

Page view(s)

Updated on Aug 7, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.