Fast and Optimal Planner for the Discrete Grid-Based Coverage Path-Planning Problem


This paper introduces a new algorithm for solving the discrete grid-based coverage path-planning (CPP) problem. This problem consists in finding a path that covers a given region completely. Our algorithm is based on an iterative deepening depth-first search. We introduce two branch-and-bound improvements (Loop detection and Admissible heuristic) to this algorithm. We evaluate the performance of our planner using four types of generated grids. The obtained results show that the proposed branch-and-bound algorithm solves the problem optimally and orders of magnitude faster than traditional optimal CPP planners.

Intelligent Data Engineering and Automated Learning
Jaël Champagne Gareau
Jaël Champagne Gareau
PhD Student in Computer Science

My research interests include AI, data structures, algorithms and HPC.