Frank Imeson
Frank Imeson has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Baris Fidan
Department of Mechanical and Mechatronics Engineering, University of Waterloo, Waterloo, ON, Canada
2 shared publications - Megnath Ramesh2 shared publications
- Stephen L. Smith
Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON, Canada
2 shared publications
Latest Publications
- Open Access
Approximate Environment Decompositions for Robot Coverage Planning using Submodular Set Cover
In this paper, we investigate the problem of decomposing 2D environments for robot coverage planning. Coverage path planning (CPP) involves computing a cost-minimizing path for a robot equipped with a coverage or sensing tool so that the tool visits all points in the environment. CPP is an NP-Hard problem, so existing approaches simplify the problem by decomposing the environment into the minimum number of sectors. Sectors are sub-regions of the environment that can each be covered using a lawnmower path (i.e., along parallel straight-line paths) oriented at an angle. However, traditional methods either limit the coverage orientations to be axis-parallel (horizontal/vertical) or provide no guarantees on the number of sectors in the decomposition. We introduce an approach to decompose the environment into possibly overlapping rectangular sectors. We provide an approximation guarantee on the number of sectors computed using our approach for a given environment. We do this by leveraging the submodular property of the sector coverage function, which enables us to formulate the decomposition problem as a submodular set cover (SSC) problem with well-known approximation guarantees for the greedy algorithm. Our approach improves upon existing coverage planning methods, as demonstrated through an evaluation using maps of complex real-world environments.
Open AccessApproximate Environment Decompositions for Robot Coverage Planning using Submodular Set Cover
In this paper, we investigate the problem of decomposing 2D environments for robot coverage planning. Coverage path planning (CPP) involves computing a cost-minimizing path for a robot equipped with a coverage or sensing tool so that the tool visits all points in the environment. CPP is an NP-Hard problem, so existing approaches simplify the problem by decomposing the environment into the minimum number of sectors. Sectors are sub-regions of the environment that can each be covered using a lawnmower path (i.e., along parallel straight-line paths) oriented at an angle. However, traditional methods either limit the coverage orientations to be axis-parallel (horizontal/vertical) or provide no guarantees on the number of sectors in the decomposition. We introduce an approach to decompose the environment into possibly overlapping rectangular sectors. We provide an approximation guarantee on the number of sectors computed using our approach for a given environment. We do this by leveraging the submodular property of the sector coverage function, which enables us to formulate the decomposition problem as a submodular set cover (SSC) problem with well-known approximation guarantees for the greedy algorithm. Our approach improves upon existing coverage planning methods, as demonstrated through an evaluation using maps of complex real-world environments.
- Open Access
Optimal Partitioning of Non-Convex Environments for Minimum Turn Coverage Planning
In this paper, we tackle the problem of planning an optimal coverage path for a robot operating indoors. Many existing approaches attempt to discourage turns in the path by covering the environment along the least number of coverage lines, i.e., straight-line paths. This is because turning not only slows down the robot but also negatively affects the quality of coverage, e.g., tools like cameras and cleaning attachments commonly have poor performance around turns. The problem of minimizing coverage lines however is typically solved using heuristics that do not guarantee optimality. In this work, we propose a turn-minimizing coverage planning method that computes the optimal number of axis-parallel (horizontal/vertical) coverage lines for the environment in polynomial time. We do this by formulating a linear program (LP) that optimally partitions the environment into axis-parallel ranks (non-intersecting rectangles of width equal to the tool width). We then generate coverage paths for a set of real-world indoor environments and compare the results with state-of-the-art coverage approaches.
Open AccessOptimal Partitioning of Non-Convex Environments for Minimum Turn Coverage Planning
In this paper, we tackle the problem of planning an optimal coverage path for a robot operating indoors. Many existing approaches attempt to discourage turns in the path by covering the environment along the least number of coverage lines, i.e., straight-line paths. This is because turning not only slows down the robot but also negatively affects the quality of coverage, e.g., tools like cameras and cleaning attachments commonly have poor performance around turns. The problem of minimizing coverage lines however is typically solved using heuristics that do not guarantee optimality. In this work, we propose a turn-minimizing coverage planning method that computes the optimal number of axis-parallel (horizontal/vertical) coverage lines for the environment in polynomial time. We do this by formulating a linear program (LP) that optimally partitions the environment into axis-parallel ranks (non-intersecting rectangles of width equal to the tool width). We then generate coverage paths for a set of real-world indoor environments and compare the results with state-of-the-art coverage approaches.