Simultaneous mapping and planning by a robot

• US 10,093,021 B2
• Filed: 06/24/2016
• Issued: 10/09/2018
• Est. Priority Date: 12/02/2015
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Aghamohammadi, Aliakbar, Diaz Spindola, Serafin, Behabadi, Bardia Fallah, Lott, Christopher, Omidshafiei, Shayegan, Somasundaram, Kiran, Gibson, Sarah Paige, Wierzynski, Casimir Matthew, Agarwal, Saurav, Reitmayr, Gerhard
• Primary Examiner(s): Nguyen, Bao Long T
• Application Number:
  US15/192,719
• Publication Number:
  US 20170157769A1
• Time in Patent Office: 837 Days
• Field of Search: 700245, 700250, 700253, 700255, 700258, 901 1
• CPC Class Codes: B25J 9/1664 characterised by motion, path, trajectory planning
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3837 Data obtained from a single source
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G05B 2219/40512 Real time path planning, trajectory generation
• CPC Class Codes: G05B 2219/40519 Motion, trajectory planning
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G05D 1/0251 extracting 3D information from a plurality of images taken from different locations, e.g. stereo vision stereoscopic image analysis H04N13/00; depth recovery from images G06T7/593
• 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

Abstract

A method substantially simultaneously plans a path and maps an environment by a robot. The method determines a mean of an occupancy level for a location in a map. The method also includes determining a probability distribution function (PDF) of the occupancy level. The method further includes calculating a cost function based on the PDF. Finally, the method includes simultaneously planning the path and mapping the environment based on the cost function.

Claims

1. A method of substantially simultaneously planning a path and mapping an environment by a robot, comprising:

determining a mean of an occupancy level for a location in a map;

determining a probability distribution function (PDF) of the occupancy level;

calculating a cost function based on the mean occupancy level and a variance of the occupancy level obtained from the PDF; and

simultaneously planning the path and mapping the environment based on the cost function.

2. The method of claim 1, further comprising mapping the environment based on the mean occupancy level and the PDF.

3. The method of claim 1, in which the simultaneously planning further comprises evaluating a predicted density for each voxel along each of a plurality of candidate trajectories.

4. The method of claim 1, further comprising planning the path based on predicted maps.

5. The method of claim 1, further comprising selecting a trajectory based on the simultaneous planning and mapping.

6. An apparatus for substantially simultaneously planning a path and mapping an environment, the apparatus comprising:

a memory;

at least one processor coupled to the memory, the at least one processor configured;

to determine a mean of an occupancy level for a location in a map;

to determine a probability distribution function (PDF) of the occupancy level;

to calculate a cost function based on the mean occupancy level and a variance of the occupancy level obtained from the PDF; and

to simultaneously plan the path and map the environment based on the cost function.

7. The apparatus of claim 6, in which the at least one processor is further configured to map the environment based on the mean occupancy level and the PDF.

8. The apparatus of claim 6, in which the at least one processor is further configured to evaluate a predicted density for each voxel along each of a plurality of candidate trajectories.

9. The apparatus of claim 6, in which the at least one processor is further configured to plan the path based on predicted maps.

10. The apparatus of claim 6, in which the at least one processor is further configured to select a trajectory based on the simultaneous planning and mapping.

11. An apparatus for substantially simultaneously planning a path and mapping an environment, the apparatus comprising:

means for determining a mean of an occupancy level for a location in a map;

means for determining a probability distribution function (PDF) of the occupancy level;

means for calculating a cost function based on the mean occupancy level and a variance of the occupancy level obtained from the PDF; and

means for simultaneously planning the path and mapping the environment based on the cost function.

12. The apparatus of claim 11, further comprising means for mapping the environment based on the mean occupancy level and the PDF.

13. The apparatus of claim 11, further comprising means for evaluating a predicted density for each voxel along each of a plurality of candidate trajectories.

14. The apparatus of claim 11, further comprising means for planning the path based on predicted maps.

15. The apparatus of claim 11, further comprising means for selecting a trajectory based on the simultaneous planning and mapping.

16. A non-transitory computer-readable medium having program code recorded thereon for substantially simultaneously planning a path and mapping an environment for a robot, the program code being executed by a processor and comprising:

program code to determine a mean of an occupancy level for a location in a map;

program code to determine a probability distribution function (PDF) of the occupancy level;

program code to calculate a cost function based on the mean occupancy level and a variance of the occupancy level obtained from the PDF; and

program code to simultaneously plan the path and map the environment based on the cost function.

17. The non-transitory computer-readable medium of claim 16, in which the program code further comprises program code to map the environment based on the mean occupancy level and the PDF.

18. The non-transitory computer-readable medium of claim 16, in which the program code further comprises program code to evaluate a predicted density for each voxel along each of a plurality of candidate trajectories.

19. The non-transitory computer-readable medium of claim 16, in which the program code further comprises program code to plan the path based on predicted maps.

20. The non-transitory computer-readable medium of claim 16, in which the program code further comprises program code to select a trajectory based on the simultaneous planning and mapping.