Abstract:Cleaning robots has become an important one among the family as service robots; full coverage path planning is one of the important technologies. This paper presents a new path planning algorithm, which uses a grid model for modeling for the indoor environment, and generates an undirected complete graph G. It uses depth-first search and breadth-first search combined in figure G, while applying topological sorting constantly updated graph G to generate the full coverage of the shortest path planning. Finally, it uses the spanning tree to prove the effectiveness and feasibility of this algorithm.