4.6 Article

Deadlock avoidance based on connectivity detection and dynamic backtracking for path planning

Journal

SOFT COMPUTING
Volume 27, Issue 8, Pages 4931-4942

Publisher

SPRINGER
DOI: 10.1007/s00500-022-07557-z

Keywords

Path planning; Deadlock prediction; Dynamic backtracking; Ant colony algorithm

Ask authors/readers for more resources

The main purpose of this paper is to solve the deadlock problem encountered by the algorithm in robot path planning. Two strategies are proposed to help the algorithm solve the common deadlock problem, including a deadlock prediction strategy based on connectivity detection and a dynamic backtracking strategy. The paper demonstrates the effectiveness of these strategies through a case study using the ant colony algorithm, showing significant improvement in the optimization rate of the optimal path and number of iterations.
The main purpose of this paper is to solve the deadlock problem encountered by the algorithm in robot path planning, so as to improve the efficiency of the algorithm. Therefore, two strategies are proposed in this paper to help the algorithm solve the common deadlock problem. First, a deadlock prediction strategy based on connectivity detection is proposed to preprocess the map. The deadlock region is filled by the image processing method. Second, a dynamic backtracking strategy is proposed to help the algorithm exit quickly in the deadlock region to complete the task. With these two strategies, even if the deadlock region is large, the algorithm can get the result quickly. This paper takes the ant colony algorithm as an example to demonstrate the deadlock strategy. By comparing with other algorithms, it can be found that the optimization rate of the proposed strategy is up to 5.96% and 88.5% for the optimal path and the number of iterations, respectively.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.6
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available