In this paper, we focus on the classical variant consisting of a single agent in a 2D discrete grid-based environment with no specific constraints or uncertainties. Some variants even consider positional uncertainties and energetic constraints of the agent. Some variants also restrict the type of allowed movements or add different kinds of sensors to the agent (e.g., proximity sensor, GPS, gyroscopic sensor, etc.). Moreover, the coverage can be done by a single agent, or by the cooperation of multiple agents. The working environment can be either discrete (e.g., grid-based, graph-based, etc.) or continuous, 2D or 3D, known a priori (i.e., off-line algorithms), or discovered while doing the coverage (i.e., on-line algorithms). The algorithm to be used depends a lot on the variant under study. All of them rely on efficient CPP algorithms to accomplish their task ( Choset, 2001 Galceran and Carreras, 2013 Khan et al., 2017). I) search and rescue aerial drones ( Hayat et al., 2020 Ai et al., 2021 Cho et al., 2021).įigure 1 gives a visual representation of these applications. H) surveillance drones ( Ahmadzadeh et al., 2008 Modares et al., 2017 Vasquez-Gomez et al., 2018) G) agriculture and farming ( Oksanen and Visala, 2009 Jin, 2010 Santos et al., 2020) John Dhanaseely and Srinivasan, 2021) Į) disinfection of regions ( Conroy et al., 2021 Nasirian et al., 2021 Vazquez-Carmona et al., 2022) į) minesweeping ( Healey, 2001 Williams, 2010 Ðakulovic and Petrovic, 2012) This problem has many practical applications, such as:Ī) robotic vacuum-cleaning ( Viet et al., 2013 Yakoubi and Laskri, 2016 Edwards and Sörme, 2018 Liu et al., 2018) ī) underwater autonomous vehicles (AUVs) ( Zhu et al., 2019 Han et al., 2020 Yordanova and Gips, 2020) Ĭ) 3d printing using fused deposition modeling ( Lechowicz et al., 2016 Afzal et al., 2019 Gupta, 2021) ĭ) window washer robots ( Farsi et al., 1994 Dr. Another problem studied in automated planning is the complete Coverage Path-Planning (CPP) problem, where the objective is to find an optimal or quasi-optimal path that covers every area in the region (we call such a path a complete coverage path of the region). An example of a real-world application of automated planning is the problem of finding an optimal path for an electric vehicle ( Champagne Gareau et al., 2021a). The field of automated planning (sometimes called AI planning) focuses on finding a sequence of actions that allows an intelligent agent (for example, a robot) to reach a goal state (for example, a specific position in the environment) from a given initial state ( Ghallab et al., 2016). To the best of our knowledge, no general CPP-solving exact algorithms, apart from an exhaustive search planner, have been proposed in the literature. The obtained results suggest that the proposed branch-and-bound algorithm solves the problem optimally (i.e., the exact solution is found in each case) orders of magnitude faster than an exhaustive search CPP planner. All of them find their practical applications in real-world CPP problems from a variety of fields. We are first to consider these types of grids in the context of CPP. We evaluate the performance of our planner using six types of benchmark grids considered in this study: Coast-like, Random links, Random walk, Simple-shapes, Labyrinth and Wide-Labyrinth grids. Then, we introduce two branch-and-bound strategies (Loop detection and an Admissible heuristic function) to improve the results of our baseline algorithm. First, we propose a CPP-solving baseline algorithm based on the iterative deepening depth-first search (ID-DFS) approach. This problem consists in finding a path that covers a given region completely. This paper introduces an optimal algorithm for solving the discrete grid-based coverage path planning (CPP) problem. GDAC-LIA, Computer Science Department, Université du Québec à Montréal, Montréal, QC, Canada. Jaël Champagne Gareau*, Éric Beaudry and Vladimir Makarenkov
0 Comments
Leave a Reply. |