Fast and Optimal Planner for the Discrete Grid-Based Coverage Path-Planning Problem
jeudi, 25 nov. 2021·
,,
Jaël Champagne Gareau
Éric Beaudry
Vladimir Makarenkov
Résumé
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
Auteurs
Chercheur postdoctoral en informatique
Je suis actuellement chercheur postdoctoral en informatique à l’Université
TÉLUQ, où mes travaux portent sur l’accélération de la conversion de nombres
entiers et flottants en chaînes de caractères décimales. Au cours de mon
doctorat, j’ai conçu des algorithmes et des structures de données exploitant
l’architecture moderne des ordinateurs afin de résoudre de grandes instances
de processus décisionnels de Markov (MDP). Durant ma maîtrise, j’ai développé
des algorithmes de planification d’itinéraires pour véhicules électriques,
visant à déterminer le chemin optimal entre deux points tout en minimisant
le temps total du trajet (déplacement, recharge et attente aux bornes).
Auteurs
Auteurs