# US 2011/0035051 A1 · Path planning apparatus and method for robot

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

- Number: US 2011/0035051 A1
- Document ID: US20110035051A1
- Status: Published application
- Kind: A1
- Application number: 12/805,514
- Filed: 2010-08-03
- Published: 2011-02-10
- Earliest claimed: 2009-08-10
- Assignees: Samsung Electronics Co., Ltd.
- Inventors: Myung Hee Kim; Kyung Shik Roh; San Lim; Bok Man Lim; Guo Chunxu
- Web page: https://patentgrep.com/patent/US20110035051A1

## CPC

- B25J 9/1666: {Avoiding collision or forbidden zones}
- G05B 2219/40264: Human like, type robot arm
- B25J: MANIPULATORS; CHAMBERS PROVIDED WITH MANIPULATION DEVICES ({manipulators specially adapted for use in surgery A61B34/70; manipulators used in cleaning hollow articles B08B9/04}; manipulators associated with rolling mills B21B39/20; manipulators associated with forging machines B21J13/10; {manipulators associated with picking-up and placing mechanisms B23P19/007}; means for holding wheels or parts thereof B60B30/00; {vehicles with ground-engaging propulsion means, e.g. walking members B62D57/02, B62D57/032; devices for picking-up and depositing articles or materials between conveyors B65G47/90, B65G47/91; manipulators with gripping or holding means for transferring packages B65H67/065}; cranes B66C; {manipulators used in the protection or supervision of pipe-line installations F17D5/00; walking equipment adapted for nuclear steam-generators F22B37/006}; manipulators specially adapted for, or associated with, nuclear reactors G21C; {apparatus used for handling wafers during manufacture or treatment of semiconductor H10P72/50})
- G05B: CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS (systems for controlling or regulating non-electric variables G05D; systems for regulating electric or magnetic variables G05F; control devices or systems insofar as characterised by mechanical features only G05G)

## Abstract

Disclosed herein are a path planning apparatus and a method for a robot to plan an optimal path along which a manipulator of a robot moves to a goal point from a start point. An obstacle within a prescribed angle on a straight line connecting a start point and a goal point is recognized as a middle point in a configuration space and arbitrary points separated from the middle point by a prescribed distance are selected. Among the selected points, arbitrary points which can directly connect the start point and the goal point without passing the obstacle are selected as waypoints to map a new middle node. A path is extended via the middle node and extension of a tree in a wrong direction is minimized so that the manipulator is not struck at local minima without depending greatly on a goal score, thereby improving the performance of path planning and rapidly searching for a path.

## Claims

### Claim 1

A path planning method for a robot, comprising:
forming a configuration space to generate a moving path of a manipulator of the robot;
selecting at least one waypoint based on an obstacle recognized as a middle point in the configuration space when the obstacle is present between a start point and a goal point of the configuration space;
generating a search graph by extending a tree so that a node generated at the start point reaches the goal point via the at least one waypoint;
generating an optimal path to avoid the obstacle by connecting the start point and the goal point through the search graph.

### Claim 2 (depends on 1)

The path planning method according to claim 1, wherein the start point is a node which forms, in the configuration space, a configuration at an initial position before the manipulator performs work.

### Claim 3 (depends on 1)

The path planning method according to claim 1, wherein the goal point is a node which forms, in the configuration space, a configuration at a goal position in which the manipulator performs work or a point having a position of the goal point and orientation information.

### Claim 4 (depends on 1)

The path planning method according to claim 1, wherein the obstacle recognized as the middle point in the configuration space is an obstacle within a prescribed angle on a straight line connecting the start point and the goal point.

### Claim 5 (depends on 4)

The path planning method according to claim 4, wherein the selecting the at least one waypoint includes selecting arbitrary points separated from the middle point by a prescribed distance to connect the arbitrary points to the start point and to the goal point and selecting at least one of the selected arbitrary points having no obstacle between the selected arbitrary points and the start and goal points as the at least one waypoint.

### Claim 6 (depends on 5)

The path planning method according to claim 5, wherein the selecting the at least one waypoint includes selecting a nearest waypoint to a randomly sampled configuration, starting from the start point, as a goal waypoint.

### Claim 7 (depends on 1)

The path planning method according to claim 1, wherein the extending the tree includes searching for a nearest node to a randomly sampled configuration based on a goal function varied according to probability and connecting the sampled configuration to the nearest node.

### Claim 8 (depends on 7)

The path planning method according to claim 7, wherein the extending the tree includes extending the tree to the at least one waypoint when a goal score of the extended tree is less than a goal score of the at least one waypoint.

### Claim 9 (depends on 7)

The path planning method according to claim 7, wherein the extending the tree includes extending the tree by searching for a new node through a variation of a goal function when a goal score of the extended tree is not less than a goal score of the at least one waypoint.

### Claim 10

A path planning method for a robot, comprising:
recognizing a start point and a goal point corresponding respectively to an initial configuration and a goal configuration, in a configuration space, of a manipulator of the robot;
mapping at least one waypoint by recognizing an obstacle as a middle point when the obstacle is present between the start point and the goal point;
searching for a node nearest to a randomly sampled point in the configuration space to connect the randomly sampled point to the node;
generating a search graph by extending a tree so that the node reaches the goal point via the at least one waypoint; and
generating an optimal path to avoid the obstacle by connecting the start point to the goal point through the search graph,
wherein at least one of the recognizing, the mapping, the searching, the generating the search graph and the generating the optimal path are performed using a processor.

### Claim 11 (depends on 10)

The path planning method according to claim 10, wherein the mapping of the at least one waypoint includes selecting the at least one waypoint in consideration of a goal function.

### Claim 12 (depends on 10)

The path planning method according to claim 10, wherein the obstacle recognized as the middle point in the configuration space is an obstacle within a prescribed angle on a straight line connecting the start point and the goal point.

### Claim 13 (depends on 12)

The path planning method according to claim 12, wherein the mapping the at least one waypoint includes selecting arbitrary points separated from the middle point by a prescribed distance to connect the selected arbitrary points to the start point and to the goal point and selecting at least one of the selected arbitrary points having no obstacle between the selected arbitrary points and the start and goal points as the at least one waypoint.

### Claim 14 (depends on 13)

The path planning method according to claim 13, wherein the mapping the waypoint includes extending the tree by selecting a nearest waypoint to a randomly sampled configuration, starting from the start point, as a goal waypoint.

### Claim 15

A path planning apparatus of a robot, comprising:
a processor;
a recognizer to recognize a start point and a goal point corresponding respectively to an initial configuration and a goal configuration, in a configuration space, of a manipulator of the robot, and an obstacle between the start point and the goal point in the configuration space; and
a path planning generator to form the configuration space utilized to generate a moving path of the manipulator, to select at least one waypoint by recognizing the obstacle as a middle point based on the configuration space, and to generate an optimal path by connecting the start point and the goal point using the at least one waypoint,
wherein at least one of the recognizer and the path planning generator are implemented using the processor.

### Claim 16 (depends on 15)

The path planning apparatus according to claim 15, wherein the obstacle recognized as the middle point is an obstacle within a prescribed angle on a straight line connecting the start point and the goal point.

### Claim 17 (depends on 15)

The path planning apparatus according to claim 15, wherein the path planning generator selects arbitrary points separated from the middle point by a prescribed distance to connect the arbitrary points to the start point and to the goal point and selects at least one of the selected arbitrary points having no obstacle between the selected arbitrary points and the start and goal points as the at least one waypoint.

### Claim 18 (depends on 15)

The path planning apparatus according to claim 15, wherein the path planning generator searches for a node nearest to a randomly sampled point in the configuration space to connect the randomly sampled point and the node and generates a search graph by extending a tree so that the node reaches the goal point via the at least one waypoint.

### Claim 19 (depends on 18)

The path planning apparatus according to claim 18, wherein the path planning generator extends the tree by connecting a newly sampled point and a nearest node to the newly sampled point and selects a nearest waypoint to the newly sampled point as a goal waypoint.
