基于区域优化分割的机器人全覆盖路径规划

Optimized Region Decomposition Based Complete Coverage Path Planning for Mobile Robot

在移动机器人全覆盖路径规划问题中,将区域分割、子区域内部行走方式、子区域衔接顺序三个子问题的优化置于整个含障区域覆盖任务总体优化的目标下考虑,探讨着眼于实用的用时最少且路程最短的子区域内部行走方式、区域分割方法和子区域间衔接顺序。确定子区域应为凸多边形;证明从路程最短和时间最少两方面讲,向内螺旋方式都是完成子区域内行走的最优行走方式;提出兼顾子区域内部行走方式和子区域衔接顺序的分割含障区域的优化方法;建立分割后整个区域的连通图模型并运用Hopfield神经网络算法求得优化的子区域间衔接顺序。

For mobile robot＇s the task of coveting whole region with obstacles,this paper takes all three sub-problems such as region decomposition,walking path in free sub-region and linking sequence of sub-regions into account altogether under the optimization of coveting task,and submits the practical and optimal walking path in sub-region, approach to region decomposition and method to obtain the linking order of sub-regions.This paper concludes the shape of sub-region should be convex polygon,points out and proves the inward spiral path is the best in free sub-region, submits a general optimization based method to decompose the whole region with obstacles,submits and applies the Hopfield Artificial Neural Network Algorithm to solve the linking order of sub-regions.