System and method of minimum turn coverage of arbitrary non-convex regions

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.