基于栅格的移动机器人区域分解遍历算法

Cellular decomposition algorithm of coverage path planning based on the grid map for the mobile robot

针对不同类型障碍物提出基于栅格的区域分解方法使移动机器人实现全覆盖遍历.算法包含区域分解、子区域连接和子区域内遍历三部分.区域分解是按照凹型障碍物边缘和工作环境边界将栅格区域分解成若干个子区域.区域内遍历按照障碍物不同类型,对存在凸型障碍物的区域采用内螺旋方法,对于凹型障碍物区域采用梳状遍历方法.子区域之间通过两点法求最短路径,然后按照逆时针方向形成遍历连通图.通过MATLAB对算法进行仿真,结果验证了该算法的可行性和有效性.

According to the different types of obstacles,this paper presents a cellular decomposition algorithm of the coverage path planning based on the grid map for the mobile robot.The algorithm consists of three parts,including the cellular decomposition,the sub-regions connections and the coverage of the sub-regions inside.The cellular decomposition is to divide the feasible regions of the grid map into several sub-regions according to the boundaries of the concave obstacles and workplace.According to the different types of obstacles in the sub-regions,an internal spiral method is adopted for the area with convex obstacles and a back-and-forth method is adopted for the area with concave obstacles.Two-points method is used to find the shortest path between the adjacent sub-regions.Then a complete connected graph is formed according to the counter clockwise direction.The feasibility and effectiveness of the algorithm are verified by the simulation of MATLAB.