System and method of minimum turn coverage of arbitrary non-convex regions
A system and method of minimum turn coverage of arbitrary non-convex regions. Coverage planning is the task of generating a path that ensures the tool carried by the robot covers all regions of interest. The number of turns in the path can affect the time to cover the region and the quality of coverage (tools like cameras and cleaning attachments commonly have poor performance around turns). In recent turn-minimizing coverage methods, the region is partitioned to be covered by the least number of rectangles of width equal to the tool's width. The partitioning problem is typically solved using heuristics that have no optimality guarantees. A linear programming (LP) approach is disclosed to generate an axis-parallel coverage plan that minimizes the number of turns taken by the robot. The LP method solves this problem optimally in polynomial time. Coverage plans are generated for real regions using the LP method.
1 . A computer-implemented method for generating a turn-minimizing coverage path for a semi-autonomous cleaning apparatus operating in an environment with obstacles, the method comprising the steps of:
providing a processor on the semi-autonomous cleaning apparatus, the processor configured for:
receiving map data representing a non-convex environment including inaccessible regions;
generating a grid-based approximation of the environment with cells sized to match a footprint of a cleaning tool mounted on the device;
formulating a mixed-integer linear programming (MILP) problem that assigns orientations to each cell to form maximally mergeable, axis-aligned ranks, wherein each rank corresponds to a straight-line cleaning path;
solving the MILP problem to determine an optimal minimal set of axis-aligned ranks covering all accessible grid cells;
constructing a coverage plan by connecting the ranks using a generalized traveling salesman problem (GTSP) solver that accounts for the robot's dynamic constraints and obstacle avoidance by using real-time sensor input from the semi-autonomous cleaning apparatus;
applying an axis-parallel constraint, resulting in “stair-case” paths to cover narrow areas with non-axis-parallel or curved boundaries;
transmitting the constructed coverage plan to the semi-autonomous cleaning device; and
executing the constructed coverage path plan on the semi-autonomous cleaning apparatus.
2 . The method of claim 1 wherein the semi-autonomous cleaning apparatus is a cleaning robot.
3 . The method of claim 1 wherein the regions further comprises an arbitrary non-convex region.
4 . The method of claim 1 further comprising the step of updating a program for a path of travel by the semi-autonomous cleaning apparatus based on the computed results.
5 . The method of claim 4 further comprising the step of executing the coverage path plan on the semi-autonomous cleaning apparatus.
6 . The method of claim 1 wherein the step of partitioning the region of the coverage path further comprises partitioning the environment into thin axis-parallel ranks using a linear program approach.
7 . The method of claim 1 further comprising using the Optimal Axis-Parallel Rank Partitioning (OARP) method for rank partitioning.
8 . The method of claim 1 wherein the method further comprises a single grid overlay to generate a linear programming problem instance to solve.
9 . The method of claim 1 wherein the coverage path planning for the semi-autonomous cleaning apparatus is configured for indoor and outdoor environments.
10 . The method of claim 1 the coverage path is selected from a list consisting of the Boustrophedon Cell Decomposition (BCD) method, turning-minimizing multi-robot coverage method, the Boustrophedon Cellular Decomposition method, minimizing turns in single and multi-robot coverage path planning method.
11 . The method of claim 1 wherein the formulation of the mixed integer linear programming (MILP) further comprises:
min
∑
i
=
0
n
y
k
i
+
∑
j
=
0
n
y
v
i
,
s
.
t
.
A
H
x
h
-
y
h
≤
0
A
V
x
v
-
y
v
≤
0
x
h
+
x
v
=
1
x
h
,
x
v
∈
{
0
,
1
}
y
h
,
y
v
≥
0.
12 . The method of claim 7 , wherein the OARP approach incorporates robot kinematic constraints, including maximum turning radius and minimum acceleration profile.
13 . The method of claim 1 , further comprising post-processing the computed path using a local planner that adapts to real-time sensor input from the semi-autonomous cleaning apparatus.
14 . The method of claim 1 , wherein the MILP is solvable in polynomial time.