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.
Type
Publication
Intelligent Data Engineering and Automated Learning
Authors
Postdoctoral Researcher in Computer Science
I am currently a postdoctoral researcher in computer science at Université
TÉLUQ, where my research focuses on speeding up the conversion of integer and
floating-point numbers into decimal strings. During my doctoral studies, I
designed algorithms and data structures that leverage modern computer
architectures to solve large instances of Markov decision processes (MDPs). In
my master’s research, I developed routing algorithms for electric vehicles
aimed at determining the optimal path between two points while minimizing
travel time (including driving, charging, and expected waiting time at
charging stations).
Authors
Authors