METHODS AND SYSTEMS FOR COMPLETE COVERAGE OF A SURFACE BY AN AUTONOMOUS ROBOT

• US 20140222279A1
• Filed: 04/11/2014
• Published: 08/07/2014
• Est. Priority Date: 11/06/2009
• Status: Active Grant

• Current Assignee: iRobot Corporation
• Original Assignee: iRobot Corporation
• Inventors: Stout, Michael S., Di Bernardo, Enrico, Pirjanian, Paolo, Goel, Dhiraj, Case, James Philip, Dooley, Michael, Brisson, Gabriel Francis
• Granted Patent: US 9,188,983 B2
• Time in Patent Office: Days
• 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 robot, comprising:

a motorized drive and a drive circuit connected thereto to move the mobile robot among robot poses on a surface;

an edge sensor configured to detect edges of obstacles on a surface traversed by the mobile robot;

a localizing sensor configured to detect robot pose on the surface traversed by the mobile robot;

a memory circuit that stores a map of the surface, wherein the map is expanded by adding explored locations, unexplored locations, and edge locations to the stored map according to the localizing sensor and the edge sensor, 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;

a region-covering routine that provides drive circuit instructions to follow a path tactic pattern to expand the map relative to one or more frontiers,

an edge-tracing routine that provides drive circuit instructions to trace along detected edges of obstacles, wherein the edge-tracing routine begins at edge locations discovered during the region-covering routine and extends tracing when new edges of obstacles are detected in real time by the edge sensor and expands the map with new frontiers discovered as the mobile robot moves along edges in the course of edge-tracing; and

a control circuit configured to monitor the edge sensor and localizing sensor, execute drive circuit instructions to move the mobile robot, and expand the map by;

executing the region-covering routine to expand the map outward from a non-edge origin location until no additional frontiers are discovered by alternately applying the path tactic pattern in at least two different directions of region discovery;

executing the edge-tracing routine to trace detected edges of obstacles; and

returning to the region-covering routine after new frontiers are discovered during an edge-tracing routine.

2. The mobile robot as defined in claim 1, further comprising a mapping routine configured to update the map by associating map locations with one or more properties sufficient to indicate unexplored, explored, and occupied locations.

3. The mobile robot as defined in claim 1, wherein when no further frontiers are discovered, the edge tracing routine is configured to cause the mobile robot to again trace one or more edges previously traced.

4. The mobile robot as defined in claim 1, wherein the edge tracing routine initiates after the region-covering routine completes discovering a first frontier.

5. The mobile robot as defined in claim 1, wherein the edge tracing routine is configured to remove an association between a location and an edge from the map stored in the memory circuit.

6. The mobile robot as defined in claim 1, wherein the edge tracing routine is configured to provide drive circuit instructions to move the mobile robot so as to cover an edge-discovered region if, while following an unfollowed edge, at least one location not associated with a mapped edge is traversed.

7. The mobile robot as defined in claim 1, wherein the region-covering routine and the edge-tracing routine comprise a computerized system comprising hardware.

8. A computer implemented method mapping a surface with a mobile device, the method comprising:

maintaining a map of the surface,

the map comprising explored locations, unexplored locations, and edge 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;

monitoring, by a computer system, a localizing sensor, the localizing sensor configured to detect a pose of the mobile device on the surface, and an edge sensor, configured to detect edges of obstacles on the surface;

using at least pose information provided by the localizing sensor, following, by the mobile device, a path tactic pattern to expand the map outward from a non-edge origin location relative to one or more frontiers, until no additional frontiers are discovered, by alternately applying the path tactic pattern in at least two different directions of region discovery;

using at least edge information provided by the edge sensor;

tracing, by the mobile device, along detected edges of obstacles, beginning at edge locations discovered while following the path tactic pattern;

extending tracing when new edges of obstacles are detected in real time by the edge sensor;

expanding the map with new frontiers discovered as the mobile device moves along edges in the course of edge-tracing; and

returning to the path tactic pattern after new frontiers are discovered during edge tracing.

9. The method as defined in claim 8, the method further comprising causing the mobile device to again trace one or more edges previously traced when no further frontiers are discovered during edge tracing.

10. The method as defined in claim 8, wherein the edge tracing is initiated after completion of discovery of a first frontier.

11. The method as defined in claim 8, the method further comprising removing an association between a location and an edge from the map.

12. The method as defined in claim 8, the method further comprising providing drive circuit instructions 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 a mapped edge is traversed.

13. The method as defined in claim 8, the method further comprising providing drive circuit instructions to follow the path tactic pattern.

14. The method as defined in claim 8, wherein the mobile device comprises the computer system.

15. A computer storage system comprising a non-transitory storage device, said computer storage system having stored thereon executable program instructions that direct a computer system to at least:

maintain a map of a surface on which a mobile device is navigating,

the map comprising explored locations, unexplored locations, and edge 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;

monitor a localizing sensor, the localizing sensor configured to detect a pose of the mobile device on the surface, and an edge sensor, configured to detect edges of obstacles on the surface;

use at least pose information received from the localizing sensor, causing the mobile device to follow a path tactic pattern to expand the map outward from a non-edge origin location relative to one or more frontiers, until no additional frontiers are discovered, by alternately applying the path tactic pattern in at least two different directions of region discovery;

use at least edge information provided by the edge sensor;

cause the mobile device to trace along detected edges of obstacles, beginning at edge locations discovered while following the path tactic pattern;

extend tracing when new edges of obstacles are detected in real time by the edge sensor;

expand the map with new frontiers discovered as the mobile device moves along edges in the course of edge-tracing; and

return to the path tactic pattern after new frontiers are discovered during edge tracing.

16. The computer storage system of claim 15, the executable program instructions further configured to direct the computer system to cause the mobile device to again trace one or more edges previously traced when no further frontiers are discovered during edge tracing.

17. The computer storage system of claim 15, the executable program instructions further configured to initiate the edge tracing after completion of discovery of a first frontier.

18. The computer storage system of claim 15, the executable program instructions further configured to remove an association between a location and an edge from the map.

19. The computer storage system of claim 15, the executable program instructions further configured to provide drive circuit instructions 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 a mapped edge is traversed.