Path planning method and biped robot using the same

Patent metadata

Field	Value
Publication number	US-12103187-B2
Application number	US-202117516729-A
Country	US
Kind code	B2
Filing date	Nov 2, 2021
Priority date	Dec 29, 2020
Publication date	Oct 1, 2024
Grant date	Oct 1, 2024

Abstract

A path planning method and a biped robot using the same are provided. The method includes: generating a candidate node set for a next foot placement based on a biped robot's own parameters and joint information of a current node, adding valid candidate nodes in the candidate node set to a priority queue so as to select optimal nodes for realizing next node expansion. These optimal nodes are output to generate a foot placement sequence from an initial node to a target node, which can greatly reduce the search amount for path nodes when the robot's legs intersect and touch the ground, thereby improving the efficiency of path planning.

First claim

What is claimed is:

1. A computer-implemented path planning method for a biped robot, comprising:
generating a candidate node set for a next foot placement based on one or more robot parameters of the biped robot and joint information of a current node;
adding one or more valid candidate nodes, not colliding with an obstacle, from the candidate node set to a priority queue based on obstacle information, and calculating a cost value of each of the valid candidate nodes in the priority queue and taking the valid candidate node with the smallest cost value as an optimal node to output;
determining whether the outputted optimal node and a target node meet a preset distance condition;
in response to the outputted optimal node and the target node not meeting the preset distance condition, returning to the step of generating the candidate node set for the next foot placement, to generate a candidate node set for a next foot placement of the outputted optimal node, until the outputted optimal node and the target node meet the preset distance condition; and
in response to the outputted optimal node and the target node meeting the preset distance condition, generating a sequence of optimal output nodes to approach the target node according to all the outputted optimal nodes, and controlling the biped robot to move to the target node from an initial node according to the sequence of optimal output nodes to approach the target node;
wherein the priority queue is a data structure comprising cost values of the candidate nodes in the priority queue calculated using a cost evaluation function, and the cost values are sorted from small to large; and
the method further comprises:
generating a global path from the initial node to the target node according to navigation information and a preset expansion radius of the biped robot using a preset path planning algorithm;
wherein the global path is for at least one of: optimizing the cost evaluation function, and reducing a number of the candidate nodes in the candidate node set;
wherein the cost evaluation function comprises: a heuristic value and a spent cost of each of the candidate nodes in the priority queue, the heuristic value refers to a predicted cost from a current candidate node in the priority queue to the target node, and the spent cost value refers to a spent cost from the initial node to the current candidate node;
wherein the cost evaluation function is optimized using the global path by calculating the heuristic value of each of the candidate nodes in the priority queue using the global path; and
wherein the heuristic value of the current candidate node is calculated by:
traversing all nodes on the global path from the initial node to the target node; and
in response to a line between a candidate node on the global path and the current candidate node being perpendicular to a tangent direction of the global path at the candidate node, calculating a length of the line, calculating a distance from the candidate node on the global path to the target node on the global path, calculating a sum of the length of the line and the distance, and taking the sum as the heuristic value of the current candidate node.

2. The method of claim 1 , wherein before the generating the candidate node set for the next foot placement based on the one or more robot parameters of the biped robot and the joint information of the current node, the method comprises:
receiving the navigation information, wherein the navigation information comprises a global map for the biped robot, and the global map comprises the obstacle information, the initial node, and the target node.

3. The method of claim 2 , wherein after the receiving the navigation information, the method further comprises:
adding the initial node to the priority queue as the first candidate node; and
directly outputting the initial node, and returning to the generating the candidate node set for the next foot placement based on the one or more robot parameters of the biped robot and the joint information of the current node.

4. The method of claim 2 , wherein the candidate node set comprises a plurality of footprints that can be reached by a current swinging leg of the biped robot, and each of the footprints is a candidate node for the next foot placement and corresponds to a node in the global map.

5. The method of claim 1 , wherein the number of the candidate nodes in the candidate node set is reduced using the global path by:
defining a first boundary and a second boundary on two sides of the global path based on body width information of the biped robot; and
taking the first boundary and the second boundary as constraint conditions, and generating the candidate node set of the next foot placement according to the one or more robot parameters of the biped robot, the joint information of the current node, and the constraint conditions.

6. The method of claim 1 , wherein the number of the candidate nodes in the candidate node set is reduced using the global path by:
defining a first boundary and a second boundary on two sides of the global path based on body width information of the biped robot; and
removing other candidate nodes except candidate nodes located between the first boundary and the second boundary, from the candidate node set.

7. The method of claim 1 , wherein information of each of the candidate nodes in the candidate node set comprises two-dimensional coordinates of the candidate node in the global map and an angle of the biped robot when touching a ground; and
wherein the number of the candidate nodes in the candidate node set is reduced using the global path by:
determining a unique angle of the candidate node with the two-dimensional coordinates based on the two-dimensional coordinates and a tangent direction of the global path at a corresponding node on the global path;
determining whether there is a candidate node with the two-dimensional coordinates and the determined unique angle in the candidate node set;
in response to there being no candidate node with the two-dimensional coordinates and the determined unique angle in the candidate node set, removing candidate nodes with the two-dimensional coordinates from the candidate node set, and adding the candidate node with the two-dimensional coordinates and the determined unique angle to the candidate node set; and
in response to there being the candidate node with the two-dimensional coordinates and the determined unique angle in the candidate node set, removing candidate nodes with the two-dimensional coordinates and a different unique angle from the candidate node set, wherein the different unique angle is different from the determined unique angle.

8. The method of claim 1 , wherein the preset distance condition comprises: a distance between the outputted optimal node and the target node being within a preset distance range.

9. The method of claim 1 , wherein when generating the global path, the biped robot is modeled as a circle of a specified radius centered on a point, and the specified radius is set based on a lateral size of the biped robot.

10. A biped robot, comprising:
a processor;
a memory coupled to the processor; and
one or more computer programs stored in the memory and executable on the processor;
wherein, the one or more computer programs comprise:
instructions for generating a candidate node set for a next foot placement based on one or more robot parameters of the biped robot and joint information of a current node;
instructions for adding one or more valid candidate nodes, not colliding with an obstacle, from the candidate node set to a priority queue based on obstacle information, and calculating a cost value of e

Assignees

• Ubtech Robotics Corp Ltd

Inventors

• Ma Xingxing
• Chen Chunyu
• Ge Ligang
• Liu Yizhang
• Wang Hongge
• Bai Jie
• Xie Zheng
• Zhou Jiangchen
• Zhang Meihui
• Zhang Shuo
• Xiong Youjun

Classifications

• G05D1/637

  using safety zones of adjustable size or shape · CPC title

• G05D2109/12

  with legs · CPC title

• G05D1/43

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

• G05D1/644

  Optimisation of travel parameters, e.g. of energy consumption, journey time or distance · 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