Surface coverage optimization method for autonomous mobile machines

• US 10,613,541 B1
• Filed: 01/16/2017
• Issued: 04/07/2020
• Est. Priority Date: 02/16/2016
• Status: Active Grant

• Current Assignee: Ai Incorprated
• Original Assignee: Ai Incorprated
• Inventors: Ebrahimi Afrouzi, Ali, Mehrnia, Soroush, Schweigert, Sebastian
• Primary Examiner(s): Merlino, David P.
• Application Number:
  US15/406,890
• Time in Patent Office: 1,177 Days
• Field of Search: None
• CPC Class Codes: G05D 1/0219 ensuring the processing of the whole working surface
• CPC Class Codes: G05D 1/0221 involving a learning process
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0276 using signals provided by a source external to the vehicle involving a plurality of vehicles G05D1/0287; automatically controlling vehicle speed responsive to externally generated signals B60K31/0058

Abstract

A system and method for devising a surface coverage scheme within a workspace. Space within a two-dimensional map of the workspace is identified as free, occupied, or unknown. The map is divided into a grid of cells. A loop-free spanning tree is constructed within all free cells within the grid. The robotic device is programmed to drive along the outside edge of the spanning tree to cover all portions of each free cell at least once upon completing the path. The system monitors several performance parameters during each work session and assigns negative rewards based on these parameters. A large positive reward is assigned upon completion of the surface coverage. Spanning trees with at least slight differences are used to determine which spanning tree produces the highest reward. The system is programmed to attempt maximize rewards at all times, causing the system to learn the best eventual method or policy for servicing the workspace.

Claims

1. A method for covering a surface by a robotic device comprising:

establishing a two-dimensional map of a workspace using data received from an outside source or gathered from one or more laser rangefinders positioned on the robotic device;

dividing the two-dimensional map into a grid of cells of predetermined size;

orienting the cell grid within the two-dimensional map such that the maximum number of whole cells result;

identifying each cell as free, occupied, or unknown;

localizing the robotic device within the two-dimensional map;

completing the two-dimensional map by driving to cells identified as unknown and gathering more data by the one or more laser rangefinders until all unknown cells have been visited and identified as either occupied or free;

connecting the centers of all free cells to create a spanning tree, wherein the spanning tree is constructed with a minimum number of corners;

driving the robotic device along an outer edge of the spanning tree until all whole cells in the two-dimensional map are covered at least once by the robotic device;

monitoring a number of collisions incurred by the robotic device during a work session;

calculating a negative reward whenever a control or action executed by the robotic device results in a collision during the work session;

calculating a negative reward based on cells retraced by the robotic device during the work session, cells left uncovered at the end of the work session, and the amount of time taken to complete the work session;

calculating a positive reward upon completion of the work session; and

amalgamating all the rewards incurred during or upon completion of the work session to obtain a value metric for the spanning tree used during the work session.

2. The method of claim 1, further comprising:

multiplying the amalgamated rewards by a decay factor causing the absolute value of the amalgamated rewards to decrease as percent coverage of a work area increases to account for an inherent increase in the probability of retracing cells as work progresses during the work session.

3. The method of claim 1, further comprising:

creating and utilizing a new spanning tree during each of a predetermined number of work sessions, and thereafter selecting a spanning tree for use based on the value metric thereof.

4. The method of claim 1 wherein the cells are approximately twice the width of the robotic device or of a component thereof.

5. The method of claim 1, wherein driving to cells marked as unknown and gathering more data comprises:

determining at least one frontier between cells marked as unknown and cells marked as occupied or free; and

driving the robotic device to the at least one frontier to gather more data.

6. The method of claim 1, wherein the robotic device interrupts a work session to recharge a battery and after resumes the work session at a location of a last covered cell.

7. The method of claim 1, further comprising:

driving the robotic device along locations corresponding with the edges of the two-dimensional map.

8. A surface coverage method comprising:

establishing, with a central processing unit of a surface coverage robot, a two-dimensional map of a workspace using data received by the central processing unit from an outside source or gathered from one or more laser rangefinders positioned on the surface coverage robot;

dividing, with the central processing unit, the two-dimensional map into a grid of cells of predetermined size oriented such that the maximum number of whole cells result;

identifying, with the central processing unit, a cell as free when the central processing unit determines via sensor data that no obstacles are present in an area within the corresponding cell;

identifying, with the central processing unit, a cell as occupied when the central processing unit determines via sensors data that obstacles are present in an area within the corresponding cell;

identifying, with the central processing unit, a cell as unknown when the central processing unit is unable to determine whether or not obstacles are present in an area within the corresponding cell;

localizing, with the central processing unit, the surface coverage robot within the two-dimensional map;

creating, with the central processing unit, a loop-free spanning tree by connecting the centers of all free cells in the two-dimensional map, wherein a number of corners in the loop-free spanning tree is minimized;

instructing, with the central processing unit, the surface coverage robot to drive along an outer edge of the loop-free spanning tree;

monitoring, with the central processing unit, a number of collisions incurred by the surface coverage robot during a work session;

calculating, with the central processing unit, a negative reward whenever a control or action executed by the surface coverage robot results in a collision during the work session;

calculating, with the central processing unit, a negative reward based on cells retraced by the surface coverage robot during the work session, cells left uncovered at the end of the work session, and the amount of time taken to complete the work session;

calculating, with the central processing unit, a positive reward upon completion of the work session; and

amalgamating, with the central processing unit, all the rewards incurred during or upon completion of the work session to obtain a value metric associated with the loop-free spanning tree used during the work session.

9. The method of claim 8 further comprising:

instructing, with the central processing unit, the surface coverage robot to drive to cells identified as unknown and gather more data by the one or more laser rangefinders until all unknown cells have been visited and identified as either occupied or free.

10. The method of claim 8, further comprising:

multiplying, with the central processing unit, the amalgamated rewards by a decay factor causing the absolute value of the amalgamated rewards to decrease as percent coverage of a work area increases to account for an inherent increase in the probability of retracing cells as work progresses during the work session.

11. The method of claim 8, further comprising:

creating and utilizing, with the central processing unit, a new loop-free spanning tree during each of a predetermined number of work sessions, and thereafter selecting a loop-free spanning tree for use based on the calculated value metric thereof.

12. A system for covering a surface by a surface coverage robot comprising:

a tangible, non-transitory, machine readable medium storing instructions that when executed by a central processing unit of the surface coverage robot effectuates operations comprising;

establishing, with the central processing unit, a two-dimensional map of a workspace using data received from an outside source or gathered from one or more sensors positioned on the surface coverage robot;

dividing, with the central processing unit, the two-dimensional map into a grid of cells of predetermined size, the grid oriented such that the maximum number of whole cells result;

marking, with the central processing unit, a cell as free if no obstacles are present within the corresponding cell;

marking, with the central processing unit, a cell as occupied if obstacles are present within the corresponding cell;

marking, with the central processing unit, a cell as unknown if the central processing unit is unable to determine whether or not obstacles are present within the corresponding cell;

localizing, with the central processing unit, the surface coverage robot within the two-dimensional map;

creating, with the central processing unit, a spanning tree by connecting the centers of all free cells in the two-dimensional map;

instructing, with the central processing unit, the surface coverage robot to drive around the spanning tree such that one side of the surface coverage robot is adjacent to a part of the spanning tree at all times;

monitoring, with the central processing unit, a number of collisions incurred by the surface coverage robot during a work session;

calculating, with the central processing unit, a negative reward whenever a control or action executed by the surface coverage robot results in a collision during the work session;

calculating, with the central processing unit, a negative reward based on cells retraced by the surface coverage robot during the work session, cells left uncovered at the end of the work session, and the amount of time taken to complete the work session;

calculating, with the central processing unit, a positive reward upon completion of the work session; and

amalgamating, with the central processing unit, all the rewards incurred during or upon completion of the work session to obtain the value metric associated with the spanning tree used during the work session,

wherein the central processing unit creates a new spanning tree during each of a predetermined number of work sessions of the surface coverage robot, and thereafter selects a spanning tree for use based on the calculated value metrics thereof.

13. The system of claim 12 further comprising:

instructing, with the central processing unit, the surface coverage robot to drive to cells marked as unknown and gather more data by the one or more sensors until all cells marked as unknown have been visited and can be remarked as either occupied or free.

14. The system of claim 13, wherein driving to cells marked as unknown and gathering more data comprises:

determining, with the central processing unit, at least one frontier between cells marked as unknown and cells marked as occupied or free; and

instructing, with the central processing unit, the surface coverage robot to drive to the at least one frontier to gather more data.

15. The system of claim 12 wherein the spanning tree is loop-free and constructed in such a way as to minimize a number of corners in a path around the spanning tree.

16. The system of claim 12, further comprising:

multiplying, with the central processing unit, the amalgamated rewards by a decay factor causing the absolute value of the amalgamated rewards to decrease as percent coverage of a work area increases to account for an inherent increase in the probability of retracing cells as work progresses during the work session.

17. The system of claim 12, further comprising:

marking, with the central processing unit, cells covered by the surface coverage robot during a work session.

18. The system of claim 12, wherein the surface coverage robot interrupts a work session to recharge a battery and after resumes the work session at a location of a last covered cell.

19. The system of claim 12, further comprising:

driving the surface coverage robot along locations corresponding with the edges of the two-dimensional map.

20. The system of claim 12, wherein the cells are at least the width of the surface coverage robot or a component thereof.