Method and system for robotic surface coverage

• US 10,343,280 B1
• Filed: 06/10/2017
• Issued: 07/09/2019
• Est. Priority Date: 12/16/2014
• Status: Active Grant

• Current Assignee: Bobsweep, Inc.
• Original Assignee: Bobsweep, Inc.
• Inventors: Ebrahimi Afrouzi, Ali
• Primary Examiner(s): Sample, Jonathan L
• Application Number:
  US15/619,449
• Time in Patent Office: 759 Days
• Field of Search: 700245-264, 31856812, 31856816, 31856819, 318580, 318587, 701 23- 26, 701400-411, 901 1, 901 46, 901 47
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: G05D 1/0219 ensuring the processing of the whole working surface
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: Y10S 901/01 Mobile robot

Abstract

Methods for minimizing redundancy of surface coverage of a workspace using a robotic device and a base station are presented, the methods including: creating a polar map of the workspace defined by a number of cells; creating a policy by dividing the workspace into a number of zones each defined by a portion of the number of cells and by ordering the number of zones for surface coverage; selecting a zone of the number of zones for surface coverage by the robotic device; creating a cell matrix of the portion of number of cells representing the selected zone; assigning the selected zone to the robotic device; covering the selected zone by the robotic device; reporting an actual zone coverage to the base station; updating a coverage matrix corresponding with the cell matrix of the selected zone to indicate coverage; and calculating a penalty.

Claims

1. A method for surface coverage of a workspace, the method comprising

creating a polar map of the workspace defined by a plurality of cells;

causing a base station to create a policy by dividing the workspace into a plurality of zones, the plurality of zones each defined by a portion of the plurality of cells and by an ordering of the plurality of zones for surface coverage by a plurality of robotic devices;

selecting a zone of the plurality of zones for surface coverage by one of the plurality of robotic devices;

creating a cell matrix of the portion of plurality of cells representing the selected zone;

assigning the selected zone to the one of the plurality of robotic devices; and

covering the selected zone by the one of the plurality of robotic devices.

2. The method of claim 1, further comprising:

reporting an actual zone coverage to the base station;

updating a coverage matrix corresponding to the cell matrix of the selected zone to indicate surface coverage by the robotic device; and

calculating a penalty based, at least in part, on a computed difference between the selected zone surface coverage and the actual zone coverage.

3. The method of claim 1, further comprising:

continuing to cover the plurality of zones until each of the plurality of cells of the workspace is covered at least once;

calculating a reward based on surface coverage of the workspace; and

assigning the reward to the policy.

4. The method of claim 3, further comprising:

iteratively creating a plurality of policies for surface coverage to maximize the reward thereby minimizing redundancy of the robotic surface coverage.

5. The method of claim 1, wherein the penalty is a product of an absolute difference between the selected zone and the actual zone coverage and a reward value and wherein the penalty is decreased by a decay factor to account for an inherent possibility of increased redundancy as additional zones in the workspace are covered.

6. The method of claim 1, wherein the policy is based on a zone division method of the plurality of zones and an order in which the plurality of zones are covered and wherein the zone division method is selected from the group consisting of:

a random zone division method, a largest possible zone division method, a smallest possible zone division method, an approximate area zone division method, an approximately equal size zone division method, a maximum area zone division method, and a minimum area zone division method.

7. A method for surface coverage of a workspace, the method comprising

causing a base station to divide the workspace into a plurality of zones, the plurality of zones each defined by a plurality of cells and by an ordering of the plurality of zones for surface coverage by a plurality of robotic devices;

selecting a zone of the plurality of zones for surface coverage by one of the plurality of robotic devices;

creating a cell matrix of the portion of plurality of cells representing the selected zone;

assigning the selected zone to the one of the plurality of robotic devices; and

covering the selected zone by the one of the plurality of robotic devices.

8. The method of claim 7, further comprising:

reporting an actual zone coverage to the base station;

updating a coverage matrix corresponding to the cell matrix of the selected zone to indicate surface coverage by the robotic device; and

calculating a penalty based, at least in part, on a computed difference between the selected zone surface coverage and the actual zone coverage.

9. The method of claim 7, further comprising:

continuing to cover the plurality of zones until each of the plurality of cells of the workspace is covered at least once;

calculating a reward based on surface coverage of the workspace; and

assigning the reward to the policy.

10. The method of claim 9, further comprising:

iteratively creating a plurality of policies for surface coverage to maximize the reward thereby minimizing redundancy of the robotic surface coverage.

11. The method of claim 7, wherein the penalty is a product of an absolute difference between the selected zone and the actual zone coverage and a reward value and wherein the penalty is decreased by a decay factor to account for an inherent possibility of increased redundancy as additional zones in the workspace are covered.

12. The method of claim 7, wherein the policy is based on a zone division method of the plurality of zones and an order in which the plurality of zones are covered and wherein the zone division method is selected from the group consisting of:

a random zone division method, a largest possible zone division method, a smallest possible zone division method, an approximate area zone division method, an approximately equal size zone division method, a maximum area zone division method, and a minimum area zone division method.