Method and system for robotic surface coverage

• US 9,701,020 B1
• Filed: 08/04/2015
• Issued: 07/11/2017
• 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:
  US14/817,952
• Time in Patent Office: 707 Days
• 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 minimizing redundancy of surface coverage of a workspace using a robotic device and a base station, the method comprising

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

causing the 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

ordering the plurality of zones for surface coverage by the robotic device;

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

creating a cell matrix of the portion of plurality 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 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.

2. 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, at least in part, on a computed absolute value of a difference between the surface coverage of the workspace and a surface area estimated to be covered; and

assigning the reward to the policy.

3. The method of claim 2, further comprising:

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

4. 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.

5. The method of claim 4, 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 each of the plurality of cells are defined by an ordered pair wherein a first value represents an angle and a second value represents a distance from the base station.

7. 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.

8. The method of claim 7, 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.

9. The method of claim 1, wherein covering the selected zone by the robotic device further comprises measuring the selected zone utilizes a measuring method selected from the group consisting of:

dead reckoning measuring, and odometer measuring.

10. The method of claim 1, further comprising:

utilizing a plurality of base stations in coordination with the robotic device.

11. The method of claim 10, wherein the plurality of base stations are synchronized to coordinate the robotic device movement.

12. The method of claim 1, further comprising:

utilizing a plurality of robotic devices in coordination with the base station.

13. The method of claim 1, further comprising:

maintaining communication between the base station and the robotic device by utilizing a keep alive signal such that when the keep alive signal is lost, the robotic device returns to the base station.

14. A system for minimizing redundancy of surface coverage of a workspace comprising:

a robotic device; and

a base station, wherein

the base station is configured to;

create a polar map of the workspace defined by a plurality of cells,

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 ordering the plurality of zones for surface coverage by the robotic device,

select a zone of the plurality of zones for surface coverage by the robotic device,

create a cell matrix of the portion of plurality of cells representing the selected zone,

assign the selected zone to the robotic device,

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

calculate a penalty based, at least in part, on a computed difference between the selected zone surface coverage and an actual zone coverage, and wherein

the robotic device is configured to;

cover the selected zone by the robotic device, and

report the actual zone coverage to the base station.

15. The system of claim 14, wherein

the robotic device is further configured to continue to cover the plurality of zones until each of the plurality of cells of the workspace is covered at least once, and wherein

the base station is further configured to calculate a reward based, at least in part, on a computed absolute value of a difference between the surface coverage of the workspace and a surface area estimated to be covered, and assign the reward to the policy.

16. The system of claim 15, wherein the base station is further configured to iteratively create a plurality of navigation policies for surface coverage to maximize the reward thereby minimizing redundancy of the robotic surface coverage.

17. The system of claim 14, wherein the penalty is a product of an absolute difference between the selected zone and the actual zone coverage and a reward value.

18. The system of claim 17, wherein the penalty is decreased by a decay factor to account for an inherent possibility of increased redundancy as additional zones in the workspace arc covered.

19. A computing device program product for minimizing redundancy of surface coverage of a workspace using a robotic device and a base station, the computing device program product comprising:

a non-transitory computer readable medium;

first programmatic instructions for creating a polar map of the workspace defined by a plurality of cells;

second programmatic instructions for causing the 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 ordering the plurality of zones for surface coverage by the robotic device;

third programmatic instructions for selecting a zone of the plurality of zones for surface coverage by the robotic device;

fourth programmatic instructions for creating a cell matrix of the portion of plurality of cells representing the selected zone;

fifth programmatic instructions for assigning the selected zone to the robotic device;

sixth programmatic instructions for covering the selected zone by the robotic device;

seventh programmatic instructions for reporting an actual zone coverage to the base station;

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

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

20. The program product of claim 19, further comprising:

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

eleventh programmatic instructions for calculating a reward based, at least in part, on a computed absolute value of a difference between the surface coverage of the workspace and a surface area estimated to be covered; and

twelfth programmatic instructions for assigning the reward to the policy.