Intermediate waypoint generator

Patent metadata

Field	Value
Publication number	US-11268816-B2
Application number	US-201916569885-A
Country	US
Kind code	B2
Filing date	Sep 13, 2019
Priority date	Aug 6, 2019
Publication date	Mar 8, 2022
Grant date	Mar 8, 2022

Abstract

A method for generating intermediate waypoints for a navigation system of a robot includes receiving a navigation route. The navigation route includes a series of high-level waypoints that begin at a starting location and end at a destination location and is based on high-level navigation data. The high-level navigation data is representative of locations of static obstacles in an area the robot is to navigate. The method also includes receiving image data of an environment about the robot from an image sensor and generating at least one intermediate waypoint based on the image data. The method also includes adding the at least one intermediate waypoint to the series of high-level waypoints of the navigation route and navigating the robot from the starting location along the series of high-level waypoints and the at least one intermediate waypoint toward the destination location.

First claim

What is claimed is:

1. A method comprising:
receiving, at data processing hardware of a robot, a navigation route, the navigation route comprising a series of high-level waypoints that begin at a starting location and end at a destination location, and the navigation route based on high-level navigation data representative of locations of static obstacles in an area the robot is to navigate;
receiving, at the data processing hardware, image data of an environment about the robot from an image sensor;
generating, by the data processing hardware, at least one intermediate waypoint based on the image data;
adding, by the data processing hardware, the at least one intermediate waypoint to the series of high-level waypoints of the navigation route; and
navigating, by the data processing hardware, the robot from the starting location along the series of high-level waypoints and the at least one intermediate waypoint toward the destination location,
wherein each high-level waypoint and each intermediate waypoint of the at least one intermediate waypoint comprises two coordinates indicating a position on a plane, a yaw value, and a time value, the time value indicating an estimated amount of time for the robot to navigate to the respective waypoint.

2. The method of claim 1 , further comprising maintaining, by the data processing hardware, each of the series of high-level waypoints on the navigation route.

3. The method of claim 1 , further comprising receiving, at the data processing hardware, a body obstacle map, the body obstacle map comprising a map of obstacles that a body of the robot cannot traverse, and
wherein generating the at least one intermediate waypoint comprises:
generating a sparse graph based on the body obstacle map, the sparse graph comprising a list of nodes and edges, the nodes and edges representative of paths the robot may travel in the environment;
planning a coarse path from a first node from the list of nodes to a second node from the list of nodes, the first node and the second node each representative of a space in the environment;
determining a point along the coarse path where line of sight by the image sensor is lost; and
generating one of the at least one intermediate waypoint at the point where line of sight is lost.

4. The method of claim 3 , wherein generating the sparse graph comprises:
generating a full configuration space map based on the body obstacle map, the full configuration space map comprising a two-dimensional grid of elements, each element of the grid representing a space of the environment, and each element of the full configuration space map comprising a respective set of yaw configurations, each yaw configuration classified as valid or invalid, wherein a valid yaw configuration represents a yaw configuration of the robot that is safe from contacting obstacles at the space associated with the respective element and an invalid yaw configuration represents a yaw configuration of the robot that is not safe from contacting obstacles at the space associated with the respective element;
generating a compressed configuration space map from the full configuration space map, the compressed configuration space map comprising a second two-dimensional grid of elements, and each element of the second grid representing a space of the environment, and each element of the second grid categorized as one of (i) a yaw collision zone, (ii) a yaw free zone, or (iii) a yaw constrained zone; and
generating the sparse graph from the compressed configuration space map.

5. The method of claim 4 , wherein planning the coarse path from the first node to the second node comprises:
generating a dense graph from the compressed configuration space map, the dense graph comprising elements categorized as yaw free zone; and
linking edges from the sparse graph with elements from the dense graph.

6. The method of claim 5 , wherein linking the edges with elements from the dense graph comprises:
combining the sparse graph and the dense graph to generate a final graph; and
executing an A* search algorithm on the final graph.

7. The method of claim 4 , wherein generating the sparse graph further comprises overlaying a plurality of Voronoi cells onto the compressed configuration space map, each Voronoi cell categorized as yaw constrained zone on the sparse graph, and each Voronoi cell equidistant from at least two elements categorized as yaw collision zone.

8. The method of claim 7 , wherein generating the sparse graph further comprises classifying each Voronoi cell as either an edge or a node.

9. The method of claim 8 , wherein classifying each Voronoi cell comprises executing a flood fill algorithm.

10. The method of claim 4 , wherein planning the coarse path from the first node to the second node comprises pruning edges, each pruned edge comprising elements under a threshold length and categorized as either yaw collision zone or yaw constrained zone.

11. The method of claim 3 , wherein determining the point along the coarse path where line of sight by the image sensor is lost comprises:
determining a minimum allowable yaw and a maximum allowable yaw at each element along the planned coarse path;
determining a smallest envelope based on the minimum allowable yaw and the maximum allowable yaw; and
determining that a required yaw at a point on the coarse path is outside the smallest envelope.

12. The method of claim 1 , further comprising sending, by the data processing hardware, the navigation route with the high-level waypoints and the at least one intermediate waypoint to a low-level path generator.

13. A method comprising:
receiving, at data processing hardware of a robot, a navigation route, the navigation route comprising a series of high-level waypoints that begin at a starting location and end at a destination location, and the navigation route based on high-level navigation data representative of locations of static obstacles in an area the robot is to navigate;
receiving, at the data processing hardware, image data of an environment about the robot from an image sensor;
generating, by the data processing hardware, at least one intermediate waypoint based on the image data;
adding, by the data processing hardware, the at least one intermediate waypoint to the series of high-level waypoints of the navigation route;
navigating, by the data processing hardware, the robot from the starting location along the series of high-level waypoints and the at least one intermediate waypoint toward the destination location;
sending, by the data processing hardware, the navigation route with the high-level waypoints and the at least one intermediate waypoint to a low-level path generator;
determining, by the data processing hardware, whether to add the at least one intermediate waypoint to the navigation route; and
in response to determining not to add at the at least one intermediate waypoint to the navigation route, passing, by the data processing hardware, the navigation route unaltered to the low-level path generator.

14. A robot comprising:
a body;
legs coupled to the body and configured to maneuver the robot about an environment;
data processing hardware in communication with the legs; and
memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising:
receiving a navigation route, the navigation route comprising a series of high-level waypoints that begin at a starting location and end at a destination location, and the navigation rou

Assignees

• Boston Dynamics Inc

Inventors

• Fay Gina Christine
• Rizzi Alfred

Classifications

• G05B2219/40519

  Motion, trajectory planning · CPC title

• B62D57/032

  with alternately or sequentially lifted supporting base and legs; with alternately or sequentially lifted feet or skid (B62D57/024 takes precedence) · CPC title

• B25J9/1697

  Vision controlled systems · CPC title

• B25J9/1664

  characterised by motion, path, trajectory planning · CPC title

• G05D1/43

  Control of position or course in two dimensions [2D] · CPC title