# US 2026/0036985 A1 · Topology Processing for Waypoint-based Navigation Maps

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2026/0036985 A1
- Document ID: US20260036985A1
- Status: Published application
- Kind: A1
- Application number: 19/356,803
- Filed: 2025-10-13
- Published: 2026-02-05
- Earliest claimed: 2021-06-04
- Assignees: Boston Dynamics, Inc.
- Applicants: Boston Dynamics, Inc.
- Inventors: Matthew Jacob Klingensmith
- Web page: https://patentgrep.com/patent/US20260036985A1

## CPC

- G05D 1/0219: {ensuring the processing of the whole working surface}
- G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)}
- G01C 22/00: Measuring distance traversed on the ground by vehicles, persons, animals or other moving solid bodies, e.g. using odometers, using pedometers
- G05D 1/0221: {involving a learning process}
- G05D 1/0248: {in combination with a laser (lasers per se H01S)}
- G05D 1/027: {comprising intertial navigation means, e.g. azimuth detector (inertial navigation G01C21/16; inertial navigation combined with non-inertial navigation instruments G01C21/165)}
- G05D 1/0272: {comprising means for registering the travel distance, e.g. revolutions of wheels (measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00)}
- G05D 1/243: Means capturing signals occurring naturally from the environment, e.g. ambient optical, acoustic, gravitational or magnetic signals (using passive navigation aids external to the vehicle G05D1/244; using signals from positioning sensors located off-board the vehicle G05D1/249)
- G05D 1/622: Obstacle avoidance (predicting or avoiding probable or impending collision of road vehicles B60W30/08)
- G05D 1/644: Optimisation of travel parameters, e.g. of energy consumption, journey time or distance
- G05D 1/6484: {by taking into account parameters or characteristics of the working area or space, e.g. size or shape}
- G06F 18/21345: {enforcing sparsity or involving a domain transformation}
- G06F 18/21355: {nonlinear criteria, e.g. embedding a manifold in a Euclidean space}
- G06V 20/58: Recognition of moving objects or obstacles, e.g. vehicles or pedestrians; Recognition of traffic objects, e.g. traffic signs, traffic lights or roads
- G05D 1/2469: {using a topologic or simplified map}
- G05D 2111/52: {generated by inertial navigation means, e.g. gyroscopes or accelerometers}
- G06F 18/21326: {involving optimisations, e.g. using regularisation techniques}
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

The operations of a computer-implemented method include obtaining a topological map of an environment including a series of waypoints and a series of edges. Each edge topologically connects a corresponding pair of adjacent waypoints. The edges represent traversable routes for a robot. The operations include determining, using the topological map and sensor data captured by the robot, one or more candidate alternate edges. Each candidate alternate edge potentially connects a corresponding pair of waypoints that are not connected by one of the edges. For each respective candidate alternate edge, the operations include determining, using the sensor data, whether the robot can traverse the respective candidate alternate edge without colliding with an obstacle and, when the robot can traverse the respective candidate alternate edge, confirming the respective candidate alternate edge as a respective alternate edge. The operations include updating, using nonlinear optimization and the confirmed alternate edges, the topological map.

## Claims

### Claim 1

A computer-implemented method comprising:
identifying, by data processing hardware of a robot, a topological map, wherein the topological map indicates a first route waypoint is directly connected to a second route waypoint via a first route edge, and wherein the topological map further indicates the first route waypoint is directly connected to a third route waypoint via a second route edge;
identifying, by the data processing hardware, a third route edge based on sensor data, wherein the third route edge directly connects the first route waypoint and a fourth route waypoint;
determining, by the data processing hardware, a navigation route based on the topological map and the third route edge; and
instructing, by the data processing hardware, navigation of the robot according to the navigation route.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
determining that the third route edge is traversable by the robot, wherein the navigation route comprises the third route edge based on determining that the third route edge is traversable by the robot.

### Claim 3 (depends on 1)

The method of claim 1, wherein determining the navigation route comprises:
updating a navigation route indicated by the topological map based on the third route edge.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
adjusting a location of the first route waypoint to obtain an adjusted location, wherein determining the navigation route is further based on the adjusted location.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
adjusting a location of the first route waypoint; and
updating the topological map based on adjusting the location of the first route waypoint.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
determining navigation according to the third route edge is associated with a collision; and
rejecting the third route edge based on determining the navigation according to the third route edge is associated with the collision.

### Claim 7 (depends on 1)

The method of claim 1, wherein the sensor data comprises a first portion of the sensor data obtained by a sensor of the robot at the first route waypoint, and wherein the sensor data comprises a second portion of the sensor data obtained by the sensor at the second route waypoint.

### Claim 8 (depends on 1)

The method of claim 1, wherein the sensor data comprises a first portion of the sensor data obtained by a sensor of the robot at the first route waypoint, and wherein the sensor data comprises a second portion of the sensor data obtained by the sensor at the second route waypoint, the method further comprising:
aligning the first portion of the sensor data and the second portion of the sensor data, wherein determining the navigation route is further based on aligning the first portion of the sensor data and the second portion of the sensor data.

### Claim 9 (depends on 1)

The method of claim 1, wherein the topological map further indicates the first route waypoint and the fourth route waypoint are not directly connected.

### Claim 10 (depends on 1)

The method of claim 1, wherein the topological map further indicates the fourth route waypoint is directly connected to a fifth route waypoint via a fourth route edge, and wherein the topological map further indicates the fourth route waypoint is directly connected to a sixth route waypoint via a fifth route edge.

### Claim 11 (depends on 1)

The method of claim 1, further comprising:
obtaining odometry data associated with the robot; and
generating at least a portion of the topological map based on the odometry data.

### Claim 12 (depends on 1)

The method of claim 1, further comprising:
determining a distance between the first route waypoint and the fourth route waypoint; and
generating the third route edge based on determining the distance between the first route waypoint and the fourth route waypoint.

### Claim 13 (depends on 1)

The method of claim 1, wherein the topological map is based on one or more locations of one or more obstacles in an environment of the robot.

### Claim 14 (depends on 1)

The method of claim 1, wherein the topological map further indicates one or more fiducial markers in an environment of the robot.

### Claim 15 (depends on 1)

The method of claim 1, further comprising:
determining a step plan indicating a set of footfall locations on a ground surface for a foot of the robot according to the third route edge, wherein instructing the navigation of the robot according to the navigation route is based on the step plan.

### Claim 16 (depends on 1)

The method of claim 1, wherein identifying the third route edge comprises generating the third route edge based on at least one of a fiducial marker or odometry data.

### Claim 17

A robot comprising:
a body;
two or more legs coupled to the body;
a sensor coupled to the body;
data processing hardware; and
memory hardware in communication with the data processing hardware, the memory hardware storing instructions, wherein, based on execution of the instructions, the data processing hardware is configured to:
identify a topological map, wherein the topological map indicates a first route waypoint is directly connected to a second route waypoint via a first route edge, and wherein the topological map further indicates the first route waypoint is directly connected to a third route waypoint via a second route edge;
identify a third route edge based on sensor data obtained from the sensor, wherein the third route edge directly connects the first route waypoint and a fourth route waypoint;
determine a navigation route based on the topological map and the third route edge; and
instruct navigation of the robot according to the navigation route.

### Claim 18 (depends on 17)

The robot of claim 17, wherein, based on the execution of the instructions, the data processing hardware is further configured to:
correlate the fourth route waypoint with a metric location.

### Claim 19

A computing system comprising:
data processing hardware; and
memory hardware in communication with the data processing hardware, the memory hardware storing instructions, wherein, based on execution of the instructions, the data processing hardware is configured to:
identify a topological map, wherein the topological map indicates a first route waypoint is directly connected to a second route waypoint via a first route edge, and wherein the topological map further indicates the first route waypoint is directly connected to a third route waypoint via a second route edge;
identify a third route edge based on sensor data, wherein the third route edge directly connects the first route waypoint and a fourth route waypoint;
determine a navigation route based on the topological map and the third route edge; and
instruct navigation of a robot according to the navigation route.

### Claim 20 (depends on 19)

The computing system of claim 19, wherein, based on the execution of the instructions, the data processing hardware is further configured to:
determine, using the topological map, a waypoint embedding; and
determine that the third route edge is traversable by the robot based on the waypoint embedding and a path collision checking algorithm.
