Systems and methods for robotic path planning

• US 10,293,485 B2
• Filed: 03/30/2017
• Issued: 05/21/2019
• Est. Priority Date: 03/30/2017
• Status: Active Grant

• Current Assignee: Brain Corporation
• Original Assignee: Brain Corporation
• Inventors: Sinyavskiy, Oleg, Passot, Jean-Baptiste, Gabardos, Borja Ibarz, Le, Diana Vu
• Primary Examiner(s): Sample, Jonathan L
• Application Number:
  US15/474,816
• Publication Number:
  US 20180281191A1
• Time in Patent Office: 782 Days
• Field of Search: 700245-264
• CPC Class Codes: A47L 11/283 the tools being disc brushes
• CPC Class Codes: A47L 11/4008 Arrangements of switches, indicators or the like
• 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 11/4061 Steering means; Means for avoiding obstacles; Details related to the place where the driver is accommodated
• CPC Class Codes: A47L 11/4066 Propulsion of the whole machine
• CPC Class Codes: B25J 11/0085 Cleaning
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G01C 21/3804 Creation or updating of map data
• CPC Class Codes: G05D 1/0214 in accordance with safety or protection criteria, e.g. avoiding hazardous areas monitoring the location of vehicles within a certain area, e.g. forbidden or allowed areas, in traffic control systems for road vehicles G08G1/13
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

Systems and methods for robotic path planning are disclosed. In some implementations of the present disclosure, a robot can generate a cost map associated with an environment of the robot. The cost map can comprise a plurality of pixels each corresponding to a location in the environment, where each pixel can have an associated cost. The robot can further generate a plurality of masks having projected path portions for the travel of the robot within the environment, where each mask comprises a plurality of mask pixels that correspond to locations in the environment. The robot can then determine a mask cost associated with each mask based at least in part on the cost map and select a mask based at least in part on the mask cost. Based on the projected path portions within the selected mask, the robot can navigate a space.

Claims

1. A method for path planning by a robot comprising:

generating a cost map associated with an environment of the robot, the cost map comprising a plurality of cost map pixels, each cost map pixel of the plurality corresponding to a respective location in the environment and each cost map pixel of the plurality having an associated cost;

generating a plurality of masks, each mask of the plurality having projected path portions for travel of the robot within the environment, each mask of the plurality comprising a plurality of mask pixels, wherein each mask pixel of the plurality corresponds to a respective location in the environment;

determining if a recovery condition applies based at least in part on a position of the robot relative to one or more obstacles in the environment, and, if the recovery condition applies, modifying at least one of (1) the cost map and/or (2) one or more of the plurality of masks;

determining a mask cost associated with each mask of the plurality based at least in part on the generated cost map;

selecting a first mask of the plurality of masks based at least in part on the determined mask cost of the first mask;

determining actuator commands for the robot to travel the projected path portions included in the first mask; and

actuating an actuator of the robot based at least in part on the determined actuator commands.

2. The method of claim 1, wherein determining the mask cost further comprises:

forming at least one matrix comprising one or more masks; and

taking a dot product between the at least one matrix and the generated cost map.

3. The method of claim 1, further comprising rotating the cost map and each mask so that the cost map and each mask are orientated substantially similarly relative to the robot.

4. The method of claim 3, wherein the rotating causes the generated cost map and each mask of the plurality of the masks to be robot centric.

5. The method of claim 1, further comprising generating a second cost map comprising a plurality of second cost map pixels, wherein each second cost map pixel of the plurality corresponds to a respective location in the environment and each second cost map pixel of the plurality includes a vector indicative at least in part of an orientation of the robot for a shortest path from a present location of the robot and the respective location associated with each second cost map pixel.

6. The method of claim 5, wherein determining the mask cost associated with each mask of the plurality of masks is further based at least in part on the generated second cost map.

7. The method of claim 1, wherein the recovery condition includes determining a motion restriction on the robot based at least in part on a presence of an obstacle.

8. The method of claim 1, further comprising implementing a cost penalty each time the first mask is selected, wherein the implemented cost penalty makes it less likely that the first mask will be selected again.

9. The method of claim 1, wherein a path portion of the projected path portions comprises a trajectory of the robot over time.

10. The method of claim 9, wherein the path portion of the projected path portions comprises a cleaning path of the robot.

11. A robot comprising:

one or more sensors configured to generate sensor data about an environment of the robot;

one or more actuators configured to propel travel of the robot;

a processor apparatus configured to;

generate a map of the environment based at least in part on the sensor data generated by the one or more sensors;

generate a cost map associated with at least a portion of the generated map of the environment, the generated cost map comprising a plurality of cost map pixels wherein each cost map pixel of the plurality corresponds to a respective location in the environment and each cost map pixel of the plurality has an associated cost;

generate a plurality of masks, each mask of the plurality having projected path portions for travel of the robot within the environment, each mask of the plurality comprising a plurality of mask pixels wherein each mask pixel of the plurality corresponds to a respective location in the environment;

determine if a recovery condition applies based at least in part on a position of the robot relative to one or more obstacles in the environment, and, if the recovery condition applies, modifying at least one of (1) the cost map and/or (2) one or more of the plurality of masks;

determine a mask cost associated with each mask of the plurality based at least in part on the generated cost map;

select a first mask of the plurality of masks based at least in part on the mask cost of the first mask; and

actuate the one or more actuators based at least in part on the first mask.

12. The robot of claim 11 further comprising one or more brush actuators that are configured to operate a cleaning brush of the robot.

13. The robot of claim 12, wherein the processor apparatus is further configured to actuate the one or more brush actuators based at least in part on the generated cost map.

14. The robot of claim 11, wherein the processor apparatus is further configured to update the mask cost associated with at least one mask of the plurality based at least in part on the robot encountering an obstacle in the environment.

15. The robot of claim 11, wherein the processor apparatus is further configured to implement a learning process that identifies one or more recovery conditions.

16. A method for path planning by a robot, comprising:

generating a cost map associated with an environment of the robot, the cost map comprising a plurality of cost map pixels, each cost map pixel of the plurality corresponding to a respective location in the environment and each cost map pixel of the plurality having an associated cost based at least in part on a desire to clean the respective location;

generating a plurality of masks having projected trajectories for travel from a pose of the robot within the environment, each mask of the plurality comprising a plurality of mask pixels, wherein each mask pixel of the plurality corresponds to a respective location in the environment for which the robot will clean should the robot select the mask;

determining a mask cost associated with each mask based at least in part on the generated cost map; and

selecting a first mask of the plurality of masks based at least in part on the mask cost of the first mask.

17. The method of claim 16, further comprising actuating one or more actuators of the robot to clean a first projected trajectory included in the first mask.

18. The method of claim 16, further comprising adjusting the generated cost map in response to user feedback.

19. The method of claim 16, wherein generating the plurality of masks further comprises:

receiving a footprint of the robot; and

generating the plurality of masks based at least in part on an avoidance of collisions between obstacles in the environment and the received footprint of the robot.

20. The method of claim 16, wherein generating the plurality of masks further comprises:

receiving one or more physical attributes of the robot, the one or more physical attributes restricting an ability of the robot to maneuver; and

generating the plurality of masks based at least in part on the received one or more physical attributes.