Discovering and plotting the boundary of an enclosure

• US 10,612,929 B2
• Filed: 10/17/2018
• Issued: 04/07/2020
• Est. Priority Date: 10/17/2017
• Status: Active Grant

• Current Assignee: Ai Incorprated
• Original Assignee: Ai Incorprated
• Inventors: Afrouzi, Ali Ebrahimi, Schweigert, Sebastian, Zhang, Chen, Fath, Lukas
• Primary Examiner(s): Oh, Harry Y
• Application Number:
  US16/163,541
• Publication Number:
  US 20190120633A1
• Time in Patent Office: 538 Days
• CPC Class Codes: A47L 11/4011 Regulation of the cleaning machine by electric means; Control systems and remote control systems therefor
• CPC Class Codes: A47L 2201/022 Recharging of batteries
• CPC Class Codes: A47L 2201/04 Automatic control of the travelling movement; Automatic obstacle detection
• CPC Class Codes: G01C 21/165 combined with non-inertial navigation instruments
• CPC Class Codes: G01C 21/1652 with ranging devices, e.g. LIDAR or RADAR
• CPC Class Codes: G01C 21/1656 with passive imaging devices, e.g. cameras
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G01S 7/4808 Evaluating distance, position or velocity data
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/0219 ensuring the processing of the whole working surface
• CPC Class Codes: G05D 1/0242 using non-visible light signals, e.g. IR or UV signals
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• 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/027 comprising intertial navigation means, e.g. azimuth detector inertial navigation G01C21/16; inertial navigation combined with non-inertial navigation instruments G01C21/165
• 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: G05D 1/228 Command input arrangements located on-board unmanned vehicles
• CPC Class Codes: G05D 1/246 : using environment maps, e.g. simultaneous localisation and mapping [SLAM]
• CPC Class Codes: G05D 1/2467 : using a semantic description of the environment
• CPC Class Codes: G05D 1/247 : using signals provided by artificial sources external to the vehicle, e.g. navigation beacons
• CPC Class Codes: G05D 1/249 : from positioning sensors located off-board the vehicle, e.g. from cameras
• CPC Class Codes: G05D 1/648 : Performing a task within a working area or space, e.g. cleaning
• CPC Class Codes: G06T 2207/10028 : Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 3/14 : Transformations for image registration, e.g. adjusting or mapping for alignment of images
• CPC Class Codes: G06T 7/11 : Region-based segmentation
• CPC Class Codes: G06T 7/30 : Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06T 7/521 : from laser ranging, e.g. using interferometry; from the projection of structured light
• CPC Class Codes: G06T 7/55 : from multiple images
• CPC Class Codes: G06T 7/62 : of area, perimeter, diameter or volume
• CPC Class Codes: H04N 23/00 : Cameras or camera modules comprising electronic image sensors; Control thereof

Abstract

Provided is a process that includes: obtaining a first version of a map of a workspace; selecting a first undiscovered area of the workspace; in response to selecting the first undiscovered area, causing the robot to move to a position and orientation to sense data in at least part of the first undiscovered area; and obtaining an updated version of the map mapping a larger area of the workspace than the first version.

Claims

1. An apparatus, comprising:

a tangible, non-transitory, machine-readable medium storing instructions that when executed by one or more processors effectuate operations comprising;

obtaining, with one or more processors of a robot or of a system configured to communicate with a robot, a first version of a map of a workspace, wherein;

the robot carries one or more sensors that sense data indicative of locations of physical objects within a sensed area, and

the first version of the map is based at least in part on data sensed by the one or more sensors in a first position and orientation and is obtained by;

capturing a plurality of images of the workspace, at least some of the images having overlapping fields of view,

spatially aligning data from respective pairs of the images based on the overlapping fields of view, and

creating the first version of the map of the workspace based on the spatially aligned data, and

the robot is configured to move in the workspace to change a location of the sensed area as the robot moves;

selecting, with the one or more processors of the robot or of the system configured to communicate with the robot, a first undiscovered area of the workspace;

determining, with the one or more processors of the robot or of the system configured to communicate with the robot, that the sensed area overlaps with at least part of the workspace in the first undiscovered area;

updating, with the one or more processors of the robot or of the system configured to communicate with the robot, the first version of the map to indicate that different portions of the overlapped sensed area with at least part of the workspace have different mapping confidence scores;

in response to selecting the first undiscovered area, causing, with the one or more processors of the robot or of the system configured to communicate with the robot, the robot to move to a second position and orientation to sense data in at least part of the first undiscovered area; and

obtaining, with the one or more processors of the robot or of the system configured to communicate with the robot, a second version of the map, the second version of the map being a larger area of the workspace than the first version of the map and based at least in part on data sensed from the second position and orientation and movement measured from the first position and orientation to the second position and orientation and the second version of the map is obtained by;

capturing a plurality of images of the workspace, at least some of the images having overlapping fields of view,

spatially aligning data from respective pairs of the images based on the overlapping fields of view, and

creating the second version of the map of the workspace based on the spatially aligned data.

2. The apparatus of claim 1, wherein:

the apparatus comprises the robot;

the robot is a floor-cleaning robot;

the first version of the map maps a first subset of the workspace in response to the first subset of the workspace being within the sensed area of the one or more sensors of the robot;

the one or more processors of the robot or of the system configured to communicate with the robot determines that the undiscovered area separates an unmapped area from a mapped area; and

the first version of the map indicates boundaries of the workspace sensed by the one or more sensors in response to the robot positioning the robot to place the boundaries in the sensed area of the one or more sensors.

3. The apparatus of claim 1, wherein:

the operations are executed by the one or more processors of the robot; and

the operations comprise causing the robot to clean a floor within the workspace.

4. The apparatus of claim 1, wherein:

the operations are executed by the one or more processors of a system configured to communicate with the robot via a network.

5. The apparatus of claim 1, wherein the operations comprise:

separating a second undiscovered area of the workspace by a virtual boundary specified by user input or a light beam; and

in response to separating, disregarding the second undiscovered area when determining areas to explore or clean with the robot.

6. The apparatus of claim 1, wherein:

the one or more sensors comprise a camera or an optical sensor having a field of view that at least partially defines the sensed area.

7. The apparatus of claim 1, wherein:

the one or more sensors comprise a depth sensor that at least partially defines a distance that the sensed area extends from the robot.

8. The apparatus of claim 1, wherein:

the first version of the map designates;

at least one area of the workspace as explored by virtue of having fallen within the sensed area of the robot,

at least one area of the workspace as beyond the perimeter of the first version of the map, and

at least one area of the workspace as being a physical boundary of the workspace and as having been explored.

9. The apparatus of claim 1, wherein the operations comprise:

determining a given mapping confidence score based on multiple mapping confidence scores of the sensed area in which the sensed area overlaps a given location in the workspace.

10. The apparatus of claim 1, wherein the operations comprise:

determining a value for at least part of the workspace by a value function of a reinforcement learning model based on the sensed data.

11. The apparatus of claim 10, wherein the reinforcement learning model is a Markov decision process.

12. The apparatus of claim 1, wherein the operations comprise:

causing the robot to clean a floor while the robot moves to the second position and orientation.

13. The apparatus of claim 1, wherein:

the operations comprise determining that the first undiscovered area is greater than a threshold size before selecting the first undiscovered area.

14. The apparatus of claim 1, wherein the operations comprise:

determining a first shape of the sensed area based on a first location of the robot and based on a first location of an obstacle sensed by the one or more sensors that block line-of-sight from the one or more sensors;

determining a second shape of the sensed area based on a second location of the robot and based on a second location of the obstacle;

the first shape is different from the second shape; and

updating which areas of the working area have been mapped in the second version of the map based on both the first shape of the sensed area and the second shape of the sensed area.

15. The apparatus of claim 1, wherein:

obtaining the first version of the map comprises steps for determining boundaries of a workspace.

16. The apparatus of claim 1, wherein the operations comprise:

receiving a human-readable name for an area of the workspace obtained via user input in a graphical user interface; and

associating the name with the area of the map in memory.

17. The apparatus of claim 1, wherein:

causing the robot to move to the second position and the orientation that positions at least part of the sensed area in the undiscovered area comprises steps for determining a path for the robot to follow; and

selecting the first undiscovered area comprises steps for determining undiscovered areas.

18. The apparatus of claim 1, comprising:

the robot, wherein the robot comprises;

an actuator configured to move the robot in the workspace; and

a vacuum configured to clean a floor under the robot.

19. The apparatus of claim 1, wherein the operations comprise:

obtaining user input designating different subsets of the workspace as different rooms;

obtaining user input designating a sequence to clean the different rooms; and

causing the robot to clean the different rooms in the sequence.

20. The apparatus of claim 1, wherein the operations comprise:

determining, based on detected boundaries, that the workspace contains a doorway; and

segmenting the workspace into rooms based on the doorway.

22. The apparatus of claim 1, wherein the operations comprise:

identifying a gap in a perimeter of the workspace in the second version of the map;

comparing the identified gap to a threshold distance; and

in response to a result of the comparison, segmenting a subset of the workspace into a plurality of rooms partially bounded by the gap.

23. The apparatus of claim 22, wherein the operations further comprise:

cleaning a first room prior to cleaning a next room of the plurality of rooms partially bounded by the gap.

24. The apparatus of claim 1, wherein the operations comprise:

steps for detecting a doorway; and

steps for detecting rooms.

25. The apparatus of claim 1, wherein the operations comprise:

separating a discovered area of the workspace into at least two regions by a virtual boundary specified by user input or a light beam; and

in response to separating, disregarding at least one region of the discovered area when determining areas to explore or clean with the robot.

26. The apparatus of claim 1, wherein the operations comprise:

determining a location of the robot using the first and second versions of the map of the workspace, wherein accuracy of the location of the robot increases with the use of the second version of the map.

21. A method, comprising:

obtaining, with one or more processors of a robot or of a system configured to communicate with a robot, a first version of a map of a workspace, wherein;

the robot carries one or more sensors that sense data indicative of locations of physical objects within a sensed area, and

the first version of the map is based at least in part on data sensed by the one or more sensors in a first position and orientation is obtained by;

capturing a plurality of images of the workspace, at least some of the images having overlapping fields of view,

spatially aligning data from respective pairs of the images based on the overlapping fields of view, and

creating the first version of the map of the workspace based on the spatially aligned data, and

the robot is configured to move in the workspace to change a location of the sensed area as the robot moves;

selecting, with the one or more processors of the robot or of the system configured to communicate with the robot, a first undiscovered area of the workspace;

determining, with the one or more processors of the robot or of the system configured to communicate with the robot, that the sensed area overlaps with at least part of the workspace in the first undiscovered area;

updating, with the one or more processors of the robot or of the system configured to communicate with the robot, the first version of the map to indicate that different portions of the overlapped sensed area with at least part of the workspace have different mapping confidence scores;

in response to selecting the first undiscovered area, causing, with the one or more processors of the robot or of the system configured to communicate with the robot, the robot to move to a second position and an orientation to sense data in at least part of the first undiscovered area; and

obtaining, with the one or more processors of the robot or of the system configured to communicate with the robot, a second version of the map, the second version of the map being a larger area of the workspace than the first version of the map and based at least in part on data sensed from the second position and orientation and movement measured from the first position and orientation to the second position and orientation and the second version of the map is obtained by;

capturing a plurality of images of the workspace, at least some of the images having overlapping fields of view,

spatially aligning data from respective pairs of the images based on the overlapping fields of view, and

creating the second version of the map of the workspace based on the spatially aligned data.

27. An apparatus, comprising:

a tangible, non-transitory, machine-readable medium storing instructions that when executed by one or more processors effectuate operations comprising;

obtaining, with one or more processors of a robot or of a system configured to communicate with a robot, a first version of a map of a workspace, wherein;

the robot carries one or more sensors that sense data indicative of locations of physical objects within a sensed area, wherein the one or more sensors comprise a depth sensor that at least partially defines a distance that the sensed area extends from the robot;

the first version of the map is based at least in part on data sensed by the one or more sensors in a first position and orientation, wherein a first shape of the sensed area is determined based on the first position and orientation and based on a first location of an obstacle sensed by the one or more sensors that block line-of-sight from the one or more sensors; and

the robot is configured to move in the workspace to change a location of the sensed area as the robot moves;

selecting, with the one or more processors of the robot or of the system configured to communicate with the robot, a first undiscovered area of the workspace, wherein the first undiscovered area is greater than a threshold size before selecting the first undiscovered area;

in response to selecting the first undiscovered area, causing, with the one or more processors of the robot or of the system configured to communicate with the robot, the robot to move to a second position and orientation to sense data in at least part of the first undiscovered area, wherein a second shape of the sensed area is determined based on the second position and orientation the robot and based on a second location of the obstacle while the first shape is different from the second shape;

separating a second undiscovered area of the workspace by a virtual boundary specified by user input or a light beam;

in response to separating, disregarding the second undiscovered area when determining areas to explore with the robot;

receiving a human-readable name for an area of the workspace obtained via user input in a graphical user interface;

associating the name with the area of the map in memory; and

obtaining, with the one or more processors of the robot or of the system configured to communicate with the robot, a second version of the map, the second version of the map being a larger area of the workspace than the first version of the map and based at least in part on data sensed from the second position, both the first shape of the sensed area and the second shape of the sensed area, and orientation and movement measured from the first position and orientation to the second position and orientation.