US 9,026,302 B2Granted

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

AssigneeiRobot Corporation

InventorsMichael S. Stout, Gabriel Francis Brisson, Enrico Di Bernardo, Paolo Pirjanian, Dhiraj Goel, James Philip Case, Michael Dooley

Life of this patent

Estimating the term…

patentgrep

Loading patent…

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.

Claims46

Dependent claims

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.

6 more elements

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.

17 more elements

Dependencies are inferred from the claim text.

Facts

Application: 12/940,871Filed 5 Nov 2010 · us provisional application
Priority: 6 Nov 2009
Published: US 2011/0167574 A114 Jul 2011
Granted: 5 May 2015
Term ends: Not estimatedThe source records don’t support an estimate.

Classification25 codes

B25J 9/1684
Characterised by the tasks executed: tracking a line or surface by means of sensors
G05D 1/2464
Using environment maps, e.g. simultaneous localisation and mapping [SLAM]: using an occupancy grid
B25J 5/00
Manipulators mounted on wheels or on carriages
B25J 5/005
Manipulators mounted on wheels or on carriages: mounted on endless tracks or belts