Methods and systems for complete coverage of a surface by an autonomous robot
First Claim
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.
5 Assignments
0 Petitions
Accused Products
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.
126 Citations
19 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
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. - View Dependent Claims (16, 17, 18, 19)
-
Specification