Methods and systems for complete coverage of a surface by an autonomous robot

• US 9,026,302 B2
• Filed: 11/05/2010
• Issued: 05/05/2015
• Est. Priority Date: 11/06/2009
• Status: Active Grant

• Current Assignee: iRobot Corporation
• Original Assignee: iRobot Corporation
• Inventors: Stout, Michael S., Brisson, Gabriel Francis, Di Bernardo, Enrico, Pirjanian, Paolo, Goel, Dhiraj, Case, James Philip, Dooley, Michael
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): MOYER, DALE S
• Application Number:
  US12/940,871
• Publication Number:
  US 20110167574A1
• Time in Patent Office: 1,642 Days
• Field of Search: 700/245, 700/263
• US Class Current: 701/25
• CPC Class Codes: B25J 5/00 Manipulators mounted on wheels or on carriages B25J1/00 takes precedence; programme-controlled manipulators B25J9/00 ; vehicle aspects B60, B62, e.g. remote-controlled steering for motor vehicles B62D1/24; control of position of vehicles G05D1/00
• CPC Class Codes: B25J 5/005 mounted on endless tracks or belts
• CPC Class Codes: B25J 5/007 mounted on wheels
• CPC Class Codes: B25J 9/163 learning, adaptive, model based, rule based expert control
• CPC Class Codes: B25J 9/1684 Tracking a line or surface by means of sensors
• CPC Class Codes: G05D 1/0219 ensuring the processing of the whole working surface
• CPC Class Codes: G05D 1/0234 using optical markers or beacons optical beacons per se G01S1/70
• CPC Class Codes: G05D 1/0238 using obstacle or wall sensors G05D1/0246 and G05D1/0289 take precedence; lidar systems designed for anti-collision purposes G01S17/93
• CPC Class Codes: G05D 1/0255 using acoustic signals, e.g. ultra-sonic singals sonar systems designed for anti-collision purposes G01S15/93
• CPC Class Codes: G05D 1/0257 using a radar radar systems designed for anti-collision purposes between land vehicles or between land vehicle and fixed obstacles G01S13/931
• CPC Class Codes: G05D 1/0263 using magnetic strips
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• 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
• CPC Class Codes: Y10S 901/46 Sensing device

Abstract

A robot configured to navigate a surface, the robot comprising a movement mechanism; a logical map representing data about the surface and associating locations with one or more properties observed during navigation; an initialization module configured to establish an initial pose comprising an initial location and an initial orientation; a region covering module configured to cause the robot to move so as to cover a region; an edge-following module configured to cause the robot to follow unfollowed edges; a control module configured to invoke region covering on a first region defined at least in part based at least part of the initial pose, to invoke region covering on least one additional region, to invoke edge-following, and to invoke region covering cause the mapping module to mark followed edges as followed, and cause a third region covering on regions discovered during edge-following.

Claims

1. A mobile device configured to navigate a surface, the mobile device comprising:

a movement mechanism configured to move the mobile device among poses on the surface, each pose comprising a device location and a device orientation;

a mapping module configured to update a map representing data about the surface, the map associating map locations with one or more properties sufficient to indicate unexplored, explored, and occupied locations, wherein a frontier indicates a boundary between an explored location and an unexplored location, and an edge indicates a boundary between an explored location and an occupied location;

an initialization module configured to establish an initial pose;

a first region-covering module configured to cause the movement mechanism to move the mobile device relative to one or more first frontiers discovered in a first direction of region discovery so as to cover a region of the surface and to cause the mapping module to update the map;

a second region-covering module configured to cause the movement mechanism to move the mobile device relative to one or more second frontiers discovered in a second direction of region discovery so as to cover at least one additional region of the surface and to cause the mapping module to update the map;

an edge-following module configured to cause the movement mechanism to move the mobile device along edges, and to cause the mapping module to extend edges and add frontiers discovered as the mobile device moves along edges, and

a third region-covering module configured to cause the movement mechanism to move the mobile device relative to third frontiers discovered in the course of moving the mobile device along edges,

wherein the edge-following module initiates after at least one of the first, second, or third region-covering modules completes discovering respective first, second, or third frontiers, and

wherein when no further frontiers are discovered by any of the first, second and third region-covering modules, the edge-following module causes the movement mechanism to again move the mobile device along at least some edges previously followed.

2. The mobile device of claim 1, wherein each of the modules comprises a computerized system.

3. The mobile device of claim 2, wherein the respective modules are comprised of a single common computerized system.

4. The mobile device of claim 1, wherein the movement mechanism comprises one or more wheels.

5. The mobile device of claim 1, wherein the movement mechanism comprises one or more tracks.

6. The mobile device of claim 1, wherein the movement mechanism comprises at least a rudder component and at least a propulsion component.

7. The mobile device of claim 1, wherein the mapping module associates a location with one or more properties based at least in part on information from one or more sensors associated with the mobile device.

8. The mobile device of claim 7, wherein the mapping module associates a location with traversed if the sensors indicate that the mobile device is in or has moved through that location.

9. The mobile device of claim 7, wherein the mapping module associates a location with occupied if the sensors indicate that mobile device cannot move into that location.

10. The mobile device of claim 7, wherein an edge comprises one or more locations associated with “

edge” and

one or more locations not associated with “

edge”

.

11. The mobile device of claim 7, wherein the edge-following module is further configured to rely at least in part on data from the sensors to follow the edge.

12. The mobile device of claim 11, wherein the edge-following module is further configured to cause the mapping module to remove an association between a location and “

edge”

.

13. The mobile device of claim 1, wherein the mapping module associates a location with edge if an adjacent location is occupied.

14. The mobile device of claim 1, wherein the mapping module associates a location with unexplored if the location is adjacent to a traversed location and is not occupied or traversed.

15. The mobile device of claim 1, wherein a region is covered if at least 90% of what is accessible to the mobile device is associated with a traversed location on the map.

16. The mobile device of claim 1, wherein a region is covered if at least 80% of what is accessible to the mobile device is associated with a traversed location on the map.

17. The mobile device of claim 1, wherein a region has a definition which is independent of properties of the surface.

18. The mobile device of claim 1, wherein each region is a proper subset of the surface.

19. The mobile device of claim 1, wherein a region has static dimensions.

20. The mobile device of claim 1, wherein a region has at least one dynamic dimension.

21. The mobile device of claim 20, wherein a region has at least one dynamic dimension determined at least in part by at least one dimension of a second region.

22. The mobile device of claim 1, wherein a first region and a second region are non-overlapping if less than 10% of the first region is in the second region.

23. The mobile device of claim 1, wherein a first region and a second region are non-overlapping if less than 25% of the first region is in the second region.

24. The mobile device of claim 1, wherein a first region and a second region are non-overlapping if less than 50% of the first region is in the second region.

25. The mobile device of claim 1, wherein the edge-following module is configured to cause the movement mechanism to move the mobile device so as to cover an edge-discovered region if, while following an unfollowed edge, at least one location not associated with “

edge”

is traversed.

26. A method for navigating a surface with a mobile device, the method comprising:

defining a reference frame using a computing device, based on at least a component of a first pose of a mobile device on a surface having one or more borders and containing one or more obstacles, the first pose comprising a first position and a first orientation;

exploring relative to one or more first frontiers discovered in a first direction of region discovery, by the mobile device, a first region of the surface so as to cover the first region of the surface, the first region determined based at least in part on a component of the first pose, wherein a frontier indicates a boundary between an explored location and an unexplored location;

exploring relative to one or more second frontiers discovered in a second direction of region discovery, by the mobile device, at least one first additional region of the surface, so as to cover the at least one first additional region of the surface after covering the first region;

maintaining a map of information about the surface in computer readable memory, wherein at least a portion of the information is obtained by exploring the first region and the additional region; and

perimeter-following one or more unfollowed perimeter portions to extend perimeters and add frontiers discovered as the mobile device moves along perimeters, wherein a perimeter corresponds to a boundary between an explored location and an occupied location, when analysis of the map indicates one or more unfollowed perimeter portions exists by;

navigating the mobile device to a first position on a first perimeter portion that is unfollowed;

following the first perimeter portion, relying at least in part on one or more sensors to determine how to follow the first perimeter portion;

updating the map to indicate that the followed first perimeter portion is followed; and

updating the map with additional information about one or more locations traversed while following the first perimeter portion;

wherein the perimeter-following initiates after discovery of the first frontier is complete, or after the discovery of the second frontier is complete, or after both the discovery of the first frontier and the second frontier is complete; and

exploring unexplored second additional surface regions discovered while perimeter-following;

wherein exploring a region comprises;

navigating the mobile device in the region;

updating the map to indicate one or more discovered perimeters, perimeters comprising surface borders and obstacle boundaries, when such are identified; and

updating the map to indicate that traversed portions of the surface have been explored

wherein when no further frontiers are discovered, moving the mobile device along at least one perimeter previously followed.

27. The method of claim 26, wherein the mobile device performs localization using a signal based localization system which uses detected signal information, wherein the signal is broadcast from a broadcast device.

28. The method of claim 26, wherein exploring unexplored additional surface regions discovered while following the first perimeter portion is performed when the map indicates no unfollowed perimeter portions exist.

29. The method of claim 26, wherein exploring unexplored additional surface regions discovered while following the first perimeter portion is performed while the map indicates unfollowed perimeter portions exist.

30. The method of claim 26, wherein the at least one additional region is determined based at least in part on a part of the first pose.

31. The method of claim 26, wherein the at least one additional region is determined based at least in part on the first region.

32. The method of claim 26, further comprising, after first performing the steps of claim 26:

configuring the mobile device on the surface with the first pose; and

performing the steps of claim 26 a second time;

wherein the behavior of the mobile device is substantially similar during the first performing and the second performing.

33. The method of claim 26, where the surface is the floor of a first room.

34. The method of claim 26, where the first region and all additional regions collectively comprise more than 90% of the surface.

35. The method of claim 26, wherein navigating the mobile device through a region comprises snaking through the region.

36. The method of claim 26, wherein navigating the mobile device through a region comprises spiraling through the region.

37. The method of claim 36, wherein navigating the mobile device through a region comprises outward spiraling through the region.

38. The method of claim 26, wherein there is substantially no portion of the surface that is in both the first region and a second region.

39. The method of claim 26, wherein there is substantially no portion of the surface that is in more than one region.

40. The method of claim 26, wherein no more than 10% of the first region is also in a second region.

41. The method of claim 26, wherein a first border of the surface is detected based on distance travelled by the mobile device.

42. The method of claim 26, wherein a first border of the surface is detected based on detection of an obstacle.

43. The method of claim 26, wherein a first border of the surface is not a physical border.

44. The method of claim 43, wherein the first border of the surface is detected based on comparing a value of a signal to a threshold.

45. The method of claim 26, wherein a first border of the surface is a wall of a room.

46. The method of claim 26, wherein the mobile device is a cleaning device.