Coverage Path-Planning

Saturday, 29 Apr 2023
An example of a 9x14 CPP grid solved by the Wavefront algorithm.
project

A problem studied in the field of AI planning is the coverage path-planning problem (CPP). This problem consists in finding a path that covers a given region entirely while respecting some constraints (e.g., avoid obstacles, use only simple movements, etc.), and minimizing the time of plan execution (or, e.g., the number of movements). This problem appears in several contexts, such as search and rescue, minesweeping, 3D reconstruction of regions flown over by a drone, submarine exploration using autonomous underwater vehicles (AUVs), floor or window cleaning, and 3D printing.

Unfortunately, no optimal CPP planner exist in literature (apart from the naïve exhaustive search solution). Furthermore, no CPP planner considers uncertainties, energetic constraints as well as dynamic environments. In this project, we developed a C++ CPP Library that supports classical algorithms (e.g., the wavefront algorithm) as well as our proposed new planning algorithms that uses heuristic search and branch-and-bound techniques.

Related Publications

Jaël Champagne Gareau, Éric Beaudry, Vladimir Makarenkov (2023). Fast and optimal branch-and-bound planner for the grid-based coverage path planning problem based on an admissible heuristic function. Frontiers in Robotics and AI.
PDF Project DOI
Jaël Champagne Gareau, Éric Beaudry, Vladimir Makarenkov (2021). Fast and Optimal Planner for the Discrete Grid-Based Coverage Path-Planning Problem. IDEAL 2021.
PDF Project Slides DOI
Deterministic Planning Heuristic Search Branch and Bound
Authors
Jaël Champagne Gareau
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).

Citation