# US 2021/0333804 A1 · Perception and Fitting for a Stair Tracker

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

- Number: US 2021/0333804 A1
- Document ID: US20210333804A1
- Status: Published application
- Kind: A1
- Application number: 16/877,721
- Filed: 2020-05-19
- Published: 2021-10-28
- Earliest claimed: 2020-04-22
- Assignees: Boston Dynamics, Inc.
- Applicants: Boston Dynamics, Inc.
- Inventors: Eric Cary Whitman; Gene Brown Merewether
- Web page: https://patentgrep.com/patent/US20210333804A1

## CPC

- G06V 20/10: Terrestrial scenes (scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59)
- B62D 57/02: with ground-engaging propulsion means, e.g. walking members
- G05D 1/10: Simultaneous control of position or course in three dimensions (G05D1/12 takes precedence)
- G05D 1/2247: {providing the operator with simple or augmented images from one or more cameras}
- G05D 1/2465: {using a 3D model of the environment}
- G05D 1/435: resulting in a change of level, e.g. negotiating lifts or stairs
- G06F 18/243: relating to the number of classes
- G06V 10/44: Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
- G06V 10/764: using classification, e.g. of video objects
- G05D 2101/20: using external object recognition
- G05D 2109/12: with legs
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- B62D: MOTOR VEHICLES; TRAILERS (steering, or guiding on a desired track, of agricultural machines or implements A01B69/00; wheels, castors, axles, increasing wheel adhesion B60B; vehicle tyres, tyre inflation or tyre changing B60C; connections between vehicles of a train or the like B60D; vehicles for use on rail and road, amphibious or convertible vehicles B60F; suspension arrangements B60G; heating, cooling, ventilating or other air treating devices B60H; windows, windscreens, non-fixed roofs, doors or similar devices, protective coverings for vehicles not in use B60J; propulsion plant arrangements, auxiliary drives, transmissions, controls, instrumentation or dashboards B60K; electric equipment or propulsion of electrically-propelled vehicles B60L; power supply for electrically-propelled vehicles B60M; passenger accommodation not otherwise provided for B60N; adaptations for load transportation or to carry special loads or objects B60P; arrangement of signalling or lighting devices, the mounting or supporting thereof or circuits therefor, for vehicles in general B60Q; vehicles, vehicle fittings or vehicle parts not otherwise provided for B60R; servicing, cleaning, repairing, supporting, lifting, or manoeuvring, not otherwise provided for, B60S; brake arrangements, brake control systems or parts thereof B60T; air-cushion vehicles B60V; motor-cycles, accessories therefor B62J, B62K; testing of vehicles G01M)
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for perception and fitting for a stair tracker includes receiving sensor data for a robot adjacent to a staircase. For each stair of the staircase, the method includes detecting, at a first time step, an edge of a respective stair of the staircase based on the sensor data. The method also includes determining whether the detected edge is a most likely step edge candidate by comparing the detected edge from the first time step to an alternative detected edge at a second time step, the second time step occurring after the first time step. When the detected edge is the most likely step edge candidate, the method includes defining, by the data processing hardware, a height of the respective stair based on sensor data height about the detected edge. The method also includes generating a staircase model including stairs with respective edges at the respective defined heights.

## Claims

### Claim 1

A method comprising:
receiving, at data processing hardware, sensor data for a robot adjacent to a staircase;
for each stair of the staircase:
detecting, by the data processing hardware at a first time step, an edge of a respective stair of the staircase based on the sensor data;
determining, by the data processing hardware, whether the detected edge is a most likely step edge candidate by comparing the detected edge from the first time step to an alternative detected edge at a second time step, the second time step occurring after the first time step; and
when the detected edge is the most likely step edge candidate, defining, by the data processing hardware, a height of the respective stair based on sensor data height about the detected edge; and
generating, by the data processing hardware, a staircase model comprising stairs with respective edges at the respective defined heights.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
for each stair of the staircase:
estimating, by the data processing hardware at a third time step, a wall location at an end of the detected edge of the respective stair of the staircase based on the sensor data;
determining, by the data processing hardware, whether the estimated wall location is a most likely wall location candidate by comparing the estimated wall location from the third time step to an alternative wall location at a fourth time step, the fourth time step occurring after the third time step; and
when the estimated wall location is the most likely wall location candidate, defining, by the data processing hardware, the estimated wall location as a respective wall location at an end of the respective stair, the respective wall location designating a boundary for the robot while traversing the staircase, and
wherein generating the staircase model comprises generating one or more walls at the respective defined wall location for each stair of the staircase.

### Claim 3 (depends on 2)

The method of claim 2, wherein the third time step for estimating the wall location coincides with the first time step for detecting the edge of the respective stair of the staircase.

### Claim 4 (depends on 1)

The method of claim 1, wherein defining the height of the respective stair comprises:
identifying points from a point cloud of the sensor data that exist about the detected edge; and
defining the height of the respective stair based on an average of heights of the identified points from the point cloud that exist about the detected edge.

### Claim 5 (depends on 1)

The method of claim 1, wherein detecting the edge of the respective stair of the staircase at the first time step comprises identifying points from a point cloud of sensor data that occur within a target detection box, the target detection box located at a position relative to a previously identified stair of the staircase.

### Claim 6 (depends on 5)

The method of claim 5, wherein detecting, at the first time step, the edge of the respective stair of the staircase comprises:
traversing, using a detection column, the identified points from the point cloud of sensor data that occur within the target detection box in an upwards direction towards the robot and at an angle with respect to a gravitational axis of the robot, the detection column traversing the target detection box based on columnar increments of the target detection box;
while traversing the identified points within the target detection box using the detection column, determining that the detection column is an empty set; and
identifying one or more respective points of a most recent non-empty set for the detection column as one or more points along the edge of the respective stair of the staircase, the one or more respective points within a cell of the detection column, the cell having the greatest height within the detection column and most towards the robot.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
generating an initial edge line from the one or more respective points identified using the detection column, the initial edge line generated using a least squares fit;
removing outlier sensor data associated with the initial edge line; and
generating a refined edge line from the one or more respective points of the initial edge line once the outlier sensor data is removed using the least squares fit.

### Claim 8 (depends on 1)

The method of claim 1, further comprising:
when the respective step is a first step of the staircase closest to a support surface of the staircase, detecting the edge of the respective stair of the staircase at the first time step comprises classifying points in a point cloud of the sensor data based on a height of a foot of the robot in contact with the support surface, the points classified as:
ground points at a first height range with respect to the height of the foot of the robot, and
first step points at a second height range with respect to the height of the foot of the robot, the second height range greater than the first height range.

### Claim 9 (depends on 1)

The method of claim 1, wherein the robot is initially located atop the staircase.

### Claim 10 (depends on 9)

The method of claim 9, further comprising, for a floor edge corresponding to a respective edge of a top stair of the staircase:
classifying, by the data processing hardware, the sensor data into height classifications, each height classification corresponding to a height along an axis parallel to a gravitational axis of the robot and classifying the height of the sensor data relative to a floor beneath the robot, the floor comprising the floor edge;
identifying, by the data processing hardware, a plurality of points along the floor edge based on a change in height classifications between portions of the sensor data, the change defined as either (i) a first transition from sensor data classified as a floor height to a portion of missing sensor data or (ii) a second transition from sensor data classified as a floor height to sensor data classified as below the floor height; and
generating, by the data processing hardware, a line fit to the plurality of points along the floor edge, and
wherein detecting the floor edge of the top stair of the staircase detects the line fit to the plurality of points along the floor edge as the detected edge.

### Claim 11 (depends on 10)

The method of claim 10, further comprising:
associating, by the data processing hardware, a respective height classification with each pixel within a two-dimensional (2D) image space representing the classified sensor data, and
wherein identifying the plurality of points along the floor edge comprises searching each pixel of the 2D image space for the change in height classifications.

### Claim 12 (depends on 9)

The method of claim 9, further comprising refining the line fit to the plurality of points along the floor edge by removing outlier points from the plurality of points.

### Claim 13

A robot comprising:
a body
two or more legs coupled to the body and configured to traverse an environment; and
a stair modeling system in communication with the robot, the modeling 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 perform operations comprising:
receiving sensor data for the robot adjacent to a staircase;
for each stair of the staircase:
detecting, at a first time step, an edge of a respective stair of the staircase based on the sensor data;
determining whether the detected edge is a most likely step edge candidate by comparing the detected edge from the first time step to an alternative detected edge at a second time step, the second time step occurring after the first time step; and
when the detected edge is the most likely step edge candidate, defining a height of the respective stair based on sensor data height about the detected edge; and
generating a staircase model comprising stairs with respective edges at the respective defined heights.

### Claim 14 (depends on 13)

The robot of claim 13, wherein the operations further comprise:
for each stair of the staircase:
estimating, at a third time step, a wall location at an end of the detected edge of the respective stair of the staircase based on the sensor data;
determining whether the estimated wall location is a most likely wall location candidate by comparing the estimated wall location from the third time step to an alternative wall location at a fourth time step, the fourth time step occurring after the third time step; and
when the estimated wall location is the most likely wall location candidate, defining the estimated wall location as a respective wall location at an end of the respective stair, the respective wall location designating a boundary for the robot while traversing the staircase, and
wherein generating the staircase model comprises generating one or more walls at the respective defined wall location for each stair of the staircase.

### Claim 15 (depends on 14)

The robot of claim 14, wherein the third time step for estimating the wall location coincides with the first time step for detecting the edge of the respective stair of the staircase.

### Claim 16 (depends on 13)

The robot of claim 13, wherein defining the height of the respective stair comprises:
identifying points from a point cloud of the sensor data that exist about the detected edge; and
defining the height of the respective stair based on an average of heights of the identified points from the point cloud that exist about the detected edge.

### Claim 17 (depends on 13)

The robot of claim 13, wherein detecting the edge of the respective stair of the staircase at the first time step comprises identifying points from a point cloud of sensor data that occur within a target detection box, the target detection box located at a position relative to a previously identified stair of the staircase.

### Claim 18 (depends on 17)

The robot of claim 17, wherein detecting, at the first time step, the edge of the respective stair of the staircase comprises:
traversing, using a detection column, the identified points from the point cloud of sensor data that occur within the target detection box in an upwards direction towards the robot and at an angle with respect to a gravitational axis of the robot, the detection column traversing the target detection box based on columnar increments of the target detection box;
while traversing the identified points within the target detection box using the detection column, determining that the detection column is an empty set; and
identifying one or more respective points of a most recent non-empty set for the detection column as one or more points along the edge of the respective stair of the staircase, the one or more respective points within a cell of the detection column, the cell having the greatest height within the detection column and most towards the robot.

### Claim 19 (depends on 18)

The robot of claim 18, further comprising:
generating an initial edge line from the one or more respective points identified using the detection column, the initial edge line generated using a least squares fit;
removing outlier sensor data associated with the initial edge line; and
generating a refined edge line from the one or more respective points of the initial edge line once the outlier sensor data is removed using the least squares fit.

### Claim 20 (depends on 13)

The robot of claim 13, wherein the operations further comprise:
when the respective step is a first step of the staircase closest to a support surface of the staircase, detecting the edge of the respective stair of the staircase at the first time step comprises classifying points in a point cloud of the sensor data based on a height of a foot of the robot in contact with the support surface, the points classified as:
ground points at a first height range with respect to the height of the foot of the robot, and
first step points at a second height range with respect to the height of the foot of the robot, the second height range greater than the first height range.

### Claim 21 (depends on 13)

The method of claim 13, wherein the robot is initially located atop the staircase.

### Claim 22 (depends on 21)

The robot of claim 21, wherein the operations further comprise, for a floor edge corresponding to a respective edge of a top stair of the staircase:
classifying the sensor data into height classifications, each height classification corresponding to a height along an axis parallel to a gravitational axis of the robot and classifying the height of the sensor data relative to a floor beneath the robot, the floor comprising the floor edge;
identifying a plurality of points along the floor edge based on a change in height classifications between portions of the sensor data, the change defined as either (i) a first transition from sensor data classified as a floor height to a portion of missing sensor data or (ii) a second transition from sensor data classified as a floor height to sensor data classified as below the floor height; and
generating a line fit to the plurality of points along the floor edge, and
wherein detecting the floor edge of the top stair of the staircase detects the line fit to the plurality of points along the floor edge as the detected edge.

### Claim 23 (depends on 22)

The robot of claim 22, wherein the operations further comprise:
associating a respective height classification with each pixel within a two-dimensional (2D) image space representing the classified sensor data, and
wherein identifying the plurality of points along the floor edge comprises searching each pixel of the 2D image space for the change in height classifications.

### Claim 24 (depends on 21)

The robot of claim 21, wherein the operations further comprise refining the line fit to the plurality of points along the floor edge by removing outlier points from the plurality of points.
