基于回溯法的全覆盖路径规划算法

计算机工程与科学

基于回溯法的全覆盖路径规划算法

李楷，陈永府,金志勇，刘田，王振庭，郑迥之

（华中科技大学机械科学与工程学院,湖北武汉 430074）

收稿日期:2018-09-07 修回日期:2018-11-30 出版日期:2019-07-25 发布日期:2019-07-25

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

（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

摘要：

随着扫地机器人的快速发展，作为其核心技术的全覆盖路径规划技术也变得日益重要。目前已经提出的许多算法，如人工势场法、模板法、单元分解法等，都存在一些问题，如覆盖率低、重复率高、运行效率低等等。针对目前已有算法存在的问题，提出了一种基于回溯法的全覆盖路径规划算法。首先利用WestMove First算法实现局部区域覆盖，然后为了解决扫地机器人局部区域覆盖过程中存在遗漏区域未覆盖的问题，建立了完善的回溯机制，并采用改进的A*算法规划出一条从死点到回溯点的光滑无障碍路径。通过与BA*算法进行仿真对比分析，表明了该算法具有更高的运行效率和更低的重叠率。

关键词: 全覆盖路径规划, West-Move First局部区域覆盖算法, 回溯机制, 改进A*算法

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

李楷，陈永府,金志勇，刘田，王振庭，郑迥之. 基于回溯法的全覆盖路径规划算法[J]. 计算机工程与科学.

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

A full coverage path planning algorithm

based on backtracking method

[J]. Computer Engineering & Science.