Directed exploration for navigation in dynamic environments

Patent metadata

Field	Value
Publication number	US-12222723-B2
Application number	US-202217805135-A
Country	US
Kind code	B2
Filing date	Jun 2, 2022
Priority date	Jun 4, 2021
Publication date	Feb 11, 2025
Grant date	Feb 11, 2025

Abstract

A computer-implemented method when executed by data processing hardware causes the data processing hardware to perform operations. The operations include receiving a navigation route for a mobile robot. The navigation route includes a sequence of waypoints connected by edges. Each edge corresponds to movement instructions that navigate the mobile robot between waypoints of the sequence of waypoints. While the mobile robot is traveling along the navigation route, the operations include determining that the mobile robot is unable to execute a respective movement instruction for a respective edge of the navigation route due to an obstacle obstructing the respective edge, generating an alternative path to navigate the mobile robot to an untraveled waypoint in the sequence of waypoints, and resuming travel by the mobile robot along the navigation route. The alternative path avoids the obstacle.

First claim

What is claimed is:

1. A computer-implemented method comprising:
receiving, by data processing hardware of a legged robot, a navigation route of a topological map for the legged robot, the navigation route comprising a set of waypoints and a first waypoint edge connecting a first waypoint of the set of waypoints and a second waypoint of the set of waypoints;
identifying, by the data processing hardware, for a foot of the legged robot, a set of footfall placement locations based on the navigation route;
obtaining, by the data processing hardware, from a sensor of the legged robot, sensor data;
generating, by the data processing hardware, a local obstacle map based on the sensor data, wherein the local obstacle map is different from the topological map;
determining, by the data processing hardware, that an action to touch down the foot at a footfall placement location of the set of footfall placement locations is obstructed by an obstacle, wherein the footfall placement location corresponds to the first waypoint edge;
determining, by the data processing hardware, that the first waypoint edge of the navigation route is obstructed based on determining that the action is obstructed;
generating, by the data processing hardware, using the local obstacle map, a second waypoint edge connecting a position of the legged robot and a third waypoint based on determining that the first waypoint edge of the navigation route is obstructed, wherein the second waypoint edge generated using the local obstacle map avoids the obstacle and comprises a deviation from the navigation route; and
instructing, by the data processing hardware, the legged robot to navigate to the third waypoint via the second waypoint edge generated using the local obstacle map and back to the navigation route.

2. The method of claim 1 , wherein the local obstacle map comprises an occupancy grid, the occupancy grid comprising a plurality of cells, wherein each cell of the plurality of cells indicates a presence of one or more obstacles.

3. The method of claim 1 , further comprising:
identifying a subset of the set of waypoints are located in the local obstacle map; and
identifying the third waypoint from the subset of the set of waypoints based on identifying the subset of the set of waypoints are located in the local obstacle map, wherein generating the second waypoint edge is based on identifying the third waypoint.

4. The method of claim 1 , wherein the first waypoint edge of the navigation route and the second waypoint edge generated using the local obstacle map are generated using different maps.

5. The method of claim 1 , further comprising:
determining that the third waypoint is outside of a range of the local obstacle map;
generating a path in a direction towards the third waypoint based on determining that the third waypoint is outside of the range of the local obstacle map;
instructing the legged robot to navigate along the path to the position of the legged robot; and
generating an updated local obstacle map based on instructing the legged robot to navigate along the path, wherein generating the second waypoint edge comprises generating the second waypoint edge using the updated local obstacle map.

6. The method of claim 1 , wherein instructing the legged robot to navigate to the third waypoint via the second waypoint edge generated using the local obstacle map and back to the navigation route comprises:
instructing the legged robot to navigate to the third waypoint via the second waypoint edge generated using the local obstacle map; and
instructing the legged robot to navigate from the third waypoint to a fourth waypoint of the set of waypoints according to the navigation route.

7. The method of claim 1 , wherein the topological map represents an environment as a plurality of waypoints interconnected by a plurality of waypoint edges, wherein the topological map indicates a plurality of paths based on the plurality of waypoints and the plurality of waypoint edges, wherein each of the plurality of paths is at least partially obstructed by the obstacle.

8. The method of claim 1 , wherein one or more metric details of a map of an environment of the legged robot are removed to obtain the topological map.

9. The method of claim 1 , wherein the topological map and the local obstacle map correspond to different portions of an environment of the legged robot.

10. The method of claim 1 , further comprising:
instructing the legged robot to navigate through an environment and generate the topological map, wherein the topological map and the local obstacle map are generated based on different sensor data;
generating the set of waypoints based on a plurality of features identified by the legged robot; and
generating the navigation route based on the topological map and the set of waypoints.

11. The method of claim 1 , wherein the topological map indicates a first location of the obstacle and the local obstacle map indicates a second location of the obstacle, and wherein determining that the action is obstructed is based on determining the second location of the obstacle.

12. The method of claim 1 , wherein a third waypoint edge of the navigation route connects the second waypoint to the third waypoint and a fourth waypoint edge of the navigation route connects the third waypoint to a fourth waypoint, wherein instructing the legged robot to navigate to the third waypoint via the second waypoint edge generated using the local obstacle map and back to the navigation route comprises:
instructing the legged robot to navigate from the first waypoint to the third waypoint via the second waypoint edge generated using the local obstacle map; and
instructing the legged robot to navigate from the third waypoint to the fourth waypoint via the fourth waypoint edge of the navigation route.

13. The method of claim 1 , wherein the local obstacle map indicates one or more additional obstacles relative to the topological map, wherein the position of the legged robot and the third waypoint are unconnected in the navigation route and the topological map.

14. A legged robot comprising:
two or more legs; and
a navigation system configured to coordinate movement of the legged robot using the two or more legs, the navigation system comprising data processing hardware 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:
receive a navigation route of a topological map, the navigation route comprising a set of waypoints and a first waypoint edge connecting a first waypoint of the set of waypoints and a second waypoint of the set of waypoints;
identify, for a foot of a leg of the two or more legs, a set of footfall placement locations based on the navigation route;
obtain, from a sensor of the legged robot, sensor data;
generate a local obstacle map based on the sensor data, wherein the local obstacle map is different from the topological map;
determine that an action to touch down the foot at a footfall placement location of the set of footfall placement locations is obstructed by an obstacle, wherein the footfall placement location corresponds to the first waypoint edge;
determine that the first waypoint edge of the navigation route is obstructed based on determining that the action is obstructed;
generate, using the local obstacle map, a second waypoint edge connecting a position of the legged robot and a third waypoint based on determining that the first waypoint edge of the navigation route is obstructed, wherein the second waypo

Assignees

• Boston Dynamics Inc

Inventors

• Yamauchi Brian Masao

Classifications

• G05D1/246

  using environment maps, e.g. simultaneous localisation and mapping [SLAM] · CPC title

• G05D1/617

  Safety or protection, e.g. defining protection zones around obstacles or avoiding hazards (arrangements for controlling the position or course of two or more vehicles for avoiding collisions therebetween G05D1/693; arrangements for reacting to or preventing system or operator failure G05D1/80) · CPC title

• G01C21/3826

  Terrain data · CPC title

• G05D1/0274

  using mapping information stored in a memory device (navigation using map-matching G01C21/30) · CPC title

• G01C21/3415

  Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents · CPC title