Alternate Route Finding for Waypoint-based Navigation Maps

Patent metadata

Field	Value
Publication number	US-2022388170-A1
Application number	US-202217805005-A
Country	US
Kind code	A1
Filing date	Jun 1, 2022
Priority date	Jun 4, 2021
Publication date	Dec 8, 2022
Grant date	—

Abstract

A computer-implemented method executed by data processing hardware of a robot causes the data processing hardware to perform operations including obtaining a topological map including waypoints and edges. Each edge connects adjacent waypoints. The waypoints and edges represent a navigation route for the robot to follow. Operations include determining, that an edge that connects first and second waypoints is blocked by an obstacle. Operations include generating, using image data and the topological map, one or more alternate waypoints offset from one of the waypoints. For each alternate waypoint, operations include generating an alternate edge connecting the alternate waypoint to a waypoint. Operations include adjusting the navigation route to include at least one alternate waypoint and alternate edge that bypass the obstacle. Operations include navigating the robot from the first waypoint to an alternate waypoint along the alternate edge connecting the alternate waypoint to the first waypoint.

First claim

1 . A computer-implemented method when executed by data processing hardware of a robot causes the data processing hardware to perform operations comprising:
obtaining a topological map comprising a series of route waypoints representative of a navigation route for the robot to follow from a start location to a destination location; receiving image data of an environment of the robot from an image sensor; determining, using the image data, that a route edge that connects a first route waypoint of the series of route waypoints to a second route waypoint of the series of route waypoints is at least partially blocked by an obstacle; generating, using the image data and the topological map, an alternate waypoint and an alternative edge connecting the alternate waypoint to the first route waypoint; and adjusting the navigation route to include the alternate waypoint and the alternate edge, the alternate waypoint and the alternate edge bypassing the route edge that is at least partially blocked by the obstacle.

2 . The method of claim 1 , wherein the operations further comprise navigating the robot from the first route waypoint to the alternate waypoint by traversing the robot along the alternate edge connecting the alternate waypoint to the first route waypoint.

3 . The method of claim 1 , wherein adjusting the navigation route comprises:
obtaining a cost for each route edge of a series of route edges of the topological map and each alternate edge of one or more alternate edges; and determining a route from a current location of the robot to the destination location using one or more route edges and/or alternate edges with an aggregate cost less than a cost threshold value.

4 . The method of claim 1 , wherein route edges that are not at least partially blocked by one or more obstacles have a cost less than a cost of alternate edges and route edges that are least partially blocked by one or more obstacles have a cost greater than or equal to the cost of alternate edges.

5 . The method of claim 1 , wherein the alternate waypoint is offset from at least one route waypoint of a series of route waypoints by an offset distance, and wherein the offset distance is less than or equal to an operational range of the image sensor.

6 . The method of claim 1 , wherein the operations further comprise generating a second alternate edge connecting the alternate waypoint and a second alternate waypoint.

7 . The method of claim 6 , wherein the operations further comprise:
determining that the second alternate edge connecting the alternate waypoint and the second alternate waypoint is blocked; and readjusting the navigation route to include a third alternate waypoint, the readjusted navigation route bypassing the second alternate edge.

8 . The method of claim 1 , wherein generating the alternate waypoint comprises using a polyline buffer algorithm to generate the alternate waypoint.

9 . The method of claim 1 , where generating the alternate waypoint comprises generating one or more alternative waypoints within a threshold distance of a current location of the robot.

10 . The method of claim 1 , wherein the topological map indicates one or more locations of one or more static obstacles within the environment.

11 . The method of claim 10 , wherein the topological map indicates a location of the alternate waypoint is free from static obstacles.

12 . The method of claim 1 , wherein generating the alternate waypoint comprises generating at least two alternate waypoints, the at least two alternate waypoints connected by a respective alternate edge.

13 . A system comprising:
data processing hardware of a robot; 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:
obtaining a topological map comprising a series of route waypoints representative of a navigation route for the robot to follow from a start location to a destination location;
receiving image data of an environment of the robot from an image sensor;
determining, using the image data, that a route edge that connects a first route waypoint of the series of route waypoints and a second route waypoint of the series of route waypoints is at least partially blocked by an obstacle;
generating, using the image data and the topological map, an alternate waypoint and an alternate edge connecting the alternate waypoint to the first route waypoint; and
adjusting the navigation route to include the alternate waypoint and the alternate edge, the alternate waypoint and the alternate edge bypassing the route edge that is at least partially blocked by the obstacle.

14 . The system of claim 13 , the operations further comprising navigating the robot from the first route waypoint to the alternate waypoint by traversing the robot along the alternate edge connecting the alternate waypoint to the first route waypoint.

15 . The system of claim 13 , wherein adjusting the navigation route comprises:
obtaining a cost for each route edge of a series of route edges of the topological map and each alternate edge of one or more alternate edges; and determining a route from a current location of the robot to the destination location using one or more route edges and/or alternate edges with an aggregate cost less than a cost threshold value.

16 . The system of claim 13 , wherein, route edges that are not at least partially blocked by one or more obstacles have a cost less than a cost of alternate edges and route edges that are at least partially blocked by one or more obstacles have a cost greater than or equal the cost of alternate edges.

17 . The system of claim 13 , wherein the alternate waypoint is offset from at least one route waypoint of the series of route waypoints by an offset distance, and wherein the offset distance is less than or equal to an operational range of the image sensor.

18 . The system of claim 13 , wherein the operations further comprise generating a second alternate edge connecting the alternate waypoint and a second alternate waypoint.

19 . The system of claim 18 , wherein the operations further comprise:
determining that the second alternate edge connecting the alternate waypoint and the second alternate waypoint is blocked; and readjusting the navigation route to include a third alternate waypoint, the readjusted navigation route bypassing the second alternate edge.

20 . The system of claim 13 , wherein generating the alternate waypoint comprises using a polyline buffer algorithm to generate the alternate waypoint.

21 . The system of claim 13 , where generating the alternate waypoint comprises generating one or more alternate waypoints within a threshold distance of a current location of the robot.

22 . The system of claim 13 , wherein the topological map indicates one or more locations of one or more static obstacles within the environment route.

23 . The system of claim 22 , wherein the topological map indicates a location of the alternate waypoint is free from static obstacles.

24 . The system of claim 13 , wherein generating the alternate waypoint comprises generating at least two alternate waypoints, the at least two alternate waypoints connected by a respective alternate edge.

25 .- 34 . (canceled)

Assignees

• Boston Dynamics Inc

Inventors

• Merewether Gene Brown

Classifications

• B25J9/1697

  Vision controlled systems · CPC title

• B25J19/023

  including video camera means · CPC title

• B25J9/162

  Mobile manipulator, movable base with manipulator arm mounted on it · CPC title

• B25J9/1664 Primary

  characterised by motion, path, trajectory planning · CPC title

• G01C21/20

  Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) · CPC title