• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

A full coverage path planning algorithm
based on backtracking method
 

LI Kai,CHEN Yongfu,JIN Zhiyong,LIU Tian,WANG Zhenting,ZHENG Jiongzhi
 
  

  1. (School of Mechanical Science and Engineering,
    Huazhong University of Science and Technology,Wuhan 430074,China)
  • Received:2018-09-07 Revised:2018-11-30 Online:2019-07-25 Published:2019-07-25

Abstract:

With the rapid development of sweeping robots, as the core technology, full coverage path planning technology has become increasingly important. Many algorithms have been proposed so far, such as the artificial potential field method, template method and unit decomposition method, however, they have problems such as low coverage, high repetition rate and low operating efficiency. In order to solve the problems existing in the proposed algorithms, we propose a full coverage path planning algorithm based on backtracking method. The algorithm firstly uses the westmove first algorithm to achieve local area coverage. Then, in order to solve the problem that the missing area is not covered in the process of local area coverage, we establish a perfect backtracking mechanism. And the improved A* algorithm is used to plan a smooth unobstructed path from dead points to backtracking points. Simulation results show that compared with the BA* algorithm, the proposed algorithm has higher operating efficiency and lower overlap rate.
 

Key words: full coverage path planning, West-Move First local area coverage algorithm, backtracking mechanism, improved A* algorithm