Multi-objective Reward-Based Algorithms for the Complete Coverage Path Planning Problem on Arbitrary Grids

The paper introduces a new multi-objective approach for the development of algorithms that guide the motion of an autonomous vehicle in real time, with the goal to cover every accessible cell in an arbitrary rectangular grid environment. The grid contains accessible cells and obstacles and its configuration is ex ante unknown to the algorithm. The method combines multiple objectives in a novel Reward function that assigns values to the neighboring cells. By seeking the maximum positive Reward at each step, the algorithm navigates an autonomous vehicle to explore and completely cover every cell of a grid environment. The method also includes a “Checkpoint” logic that guides the backtracking in order to ensure complete coverage in every case. The algorithm includes exploitation and exploration features to operate in a learning fashion, as the vehicle gradually discovers and accounts for the disposition of obstacles and accessible areas in its vicinity. Simulation tests demonstrate that the algorithm is computationally efficient and performs effectively against different unknown environments. Also, the approach opens the way for several further extensions and improvements.