System and method of replanning for coverage of environments with unknown obstacles

Abstract

A system and method to replan coverage paths for a robot operating in an environment with initially unknown static obstacles. Existing coverage approaches reduce coverage time by covering along the minimum number of coverage lines (straight-line paths). However, recomputing such paths online can be computationally expensive resulting in robot stoppages that increase coverage time. An alternative is greedy detour replanning, i.e., replanning with minimum deviation from the initial path, which is efficient to compute but may result in unnecessary detours. In this work, an anytime coverage replanning approach named OARP-Replan is proposed that performs near-optimal replans to an interrupted coverage path within a given time budget. This is accomplished by solving linear relaxations of mixed-integer linear programs (MILPs) to identify sections of the interrupted path that can be optimally replanned within the time budget.

What is claimed: 
     
         1 . A system for coverage re-planning of an environment with unknown obstacles for a semi-autonomous cleaning apparatus comprising:
 a processor;   one or more LIDAR sensor or cameras configured for obstacle detection;   one or more motors or actuators configured for movement of the cleaning apparatus;   cleaning apparatus navigation software modules, further comprising:
 a coverage planner module; 
 a local planner module; 
 a local controller module; and 
 a coverage replanner module; 
   wherein the navigation software modules are configured to receive a cleaning plan and compute a executable coverage paths;   wherein the navigation software modules are configured to provide feedback to create coverage paths and replanned coverage paths.   
     
     
         2 . The system of  claim 1  wherein the coverage planner module is configured to convert cleaning path plant to sectors or straight-line paths, avoid known obstacles and uses connection planner to connect sectors and compute a coverage path. 
     
     
         3 . The system of  claim 1  wherein the local planner module splits the coverage path to executable path for the local controller and makes small changes to the path to go around detected obstacles. 
     
     
         4 . The system of  claim 1  wherein if larger changes to path are required a request is sent to conduct a coverage replan. 
     
     
         5 . The system of  claim 1  wherein the local controller module is configured to move the apparatus to cover the environment along the executable paths and if new obstacles are detected, ask the local replanner for a new path. 
     
     
         6 . The system of  claim 1  wherein the local controller module is further configured to provide feedback of the executable path progress and completion and report whether the robot is stuck. 
     
     
         7 . The system of  claim 1  wherein the coverage replanner module is configured to receive information about new obstacles from the local planner and the time to reach the obstacles and optimally replans the remainder of the coverage path given the available time. 
     
     
         8 . The system of  claim 1  wherein the coverage replanner module further provides feedback to the local planner by providing info on coverage plan progress, new obstacles and time along current path to reach new obstacles. 
     
     
         9 . The system of  claim 1  wherein the LIDAR sensor and cameras are provided to input data to the local planner module. 
     
     
         10 . The system of  claim 1  wherein the local controller module executes the executable paths by moving the apparatus by actuating motors and actuators. 
     
     
         11 . The system of  claim 1  wherein an OARP-Replan coverage replanning method is used to perform replanning by solving linear relaxations of mixed-integer linear programs (MILPs) to identify sections of the interrupted path that can be optimally replanned within the time budget. 
     
     
         12 . The system of  claim 1  wherein the coverage replanner module utilizes the time spent driving to conduct near-optimal replans on the provided coverage paths. 
     
     
         13 . The system of  claim 1  wherein an Optimal Axis-Parallel Rank Partitioning (OARP) approach is used to plan coverage paths is used whereby the OARP approach minimizes the number of turns. 
     
     
         14 . A computer-implemented method for a semi-autonomous cleaning apparatus comprising a processor, hardware and navigation software, the cleaning apparatus configured for coverage re-planning of an environment with unknown obstacles, the method comprising the steps of:
 receiving a cleaning plan for an environment;   sending the cleaning plan to a coverage planner module of the navigation software, the coverage planner module configured to compute a coverage path;   sending the computed coverage path to a local planner module and a coverage replanner module, the local planner module configured to split the coverage plan into one or more executable paths and the coverage replanner module configured for replanning the coverage path; and   sending the executable paths to the local planner module, the local planner module configured to send instructions to move the apparatus along the executable path;   wherein the navigation software modules are configured to provide feedback to create coverage paths and replanned coverage paths.   
     
     
         15 . The method of  claim 14  wherein the coverage planner module configured to convert cleaning path plant to sectors or straight-line paths, avoid known obstacles and uses connection planner to connect sectors and compute a coverage path. 
     
     
         16 . The method of  claim 14  wherein the local planner module splits coverage path to executable path for the local controller and makes small changes to the path to go around detected obstacles. 
     
     
         17 . The method of  claim 14  wherein if larger changes to path are required a request is sent to conduct a coverage replan. 
     
     
         18 . A computer-implemented method for a semi-autonomous cleaning apparatus comprising a processor, hardware and navigation software, the cleaning apparatus configured for coverage re-planning of an environment with unknown obstacles by solving an Optimal Axis-Parallel Rank Partitioning (OARP) approach, the method comprising the steps of:
 decomposing the environment into grid cells;   using the decomposition to compute the minimum number of axis-parallel ranks; and   finding an optimal tour of the ranks to obtain the coverage path.   
     
     
         19 . The method of  claim 18  wherein the axis-parallel ranks further comprising horizontal and vertical ranks. 
     
     
         20 . The method of  claim 18  wherein the axis-parallel ranks further comprising long rectangles that match the width of the cleaning apparatus coverage tool while covering along a straight-line path.