基于栅格地图的移动机器人完全遍历算法——矩形分解法

COMPLETE COVERAGE OF KNOWN SPACE——RECTANGULAR DECOMPOSITION

提出移动机器人的一种新的完全遍历算法:矩形分解算法。首先通过机器人环境学习建立栅格地图,对环境中的障碍物实行矩形化建模。而后应用矩形化模型中的关键点将环境分解成为矩形块,最后在这个分块环境的拓扑图中寻找到一条Hamilton路径,机器人沿此路径即可实现对环境的完全遍历。为处理复杂的局部情况,又提出基于模板的局部环境处理算法。矩形算法的优点在于机器人可以实现完全自主的复杂环境遍历,并且可以处理未知障碍,从而使算法适合于任意非结构化的工作环境。

A new cellular decomposition approach, rectangular decomposition, is proposed for the purpose of complete coverage path planning. Firstly, the known grid map is used to build each obstacle into a rectangular model. Secondly, the critical points of each model are used to decompose the environment into rectangular cells. Each cell can be represented as a node in a graph, and then a Hamilton path is found in this graph. Because the environment is very complicated and sometimes there are some unexpected obstacles in the environment, sensors are needed and a local template algorithm is designed. The novelty of the proposed algorithm is that Hamilton path can be found in the topology of the environment and reduce the redundancy produced by the robot when it moves from one cell to the next. A simulation based on a grid map validates this algorithm.