Complete Coverage Path Planning of Mobile Robot Based on Dynamic Programming Algorithm

Abstract

A complete coverage path planning algorithm, which combines local space coverage with global planning, is proposed. At first, environmental model of mobile robot in a space with obstacles is built by Boustrophedon unit decomposition method, and mobile robot realizes coverage in a reciprocating way in local space. Secondly, it takes local space dividing, sub-space connecting sequence and sub-space walking route into account, then a completely connected distance matrix that represents the connecting relationship of the coverage space are defined. Thirdly, dynamic programming algorithm is used to optimize this matrix and a shortest global coverage sequence is acquired. Simulation example proves the effectiveness of the proposed algorithm.