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

Abstract

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.

Publication
Intelligent Data Engineering and Automated Learning – IDEAL 2021
Jaël Champagne Gareau
Jaël Champagne Gareau
PhD Student of Computer Science

My research interests include AI (both planning and machine learning) and theoretical computer science.