To address the problem of planning complete coverage paths for cleaning robots that have the greatest coverage rates and the lowest recover rates, we propose a back propagation (BP) neural network algorithm for local path planning based on plowing global path planning. We also propose an improved BP neural network algorithm based on the deepfirst coverage algorithm for the issue of cleaning dead areas. Simulation results show that the proposed algorithm can plan complete paths for the robots.