Path planning apparatus of robot and method thereof

• US 8,666,548 B2
• Filed: 12/11/2009
• Issued: 03/04/2014
• Est. Priority Date: 01/07/2009
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lim, San
• Primary Examiner(s): HOLLOWAY, JASON R
• Application Number:
  US12/654,165
• Publication Number:
  US 20100174435A1
• Time in Patent Office: 1,544 Days
• Field of Search: 700/246, 700/250, 700/253, 700/258, 700/264, 700/262, 701/25, 901/1
• US Class Current: 700/250
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

Disclosed are a path planning apparatus of a robot, which generates a path plan to control movements of the robot, and a method thereof. An improved RRT algorithm is employed, when a tree is extended in a configuration space so as to satisfy a constraint, and thus steeply bent or roundabout portions of the tree are reduced.

Claims

1. A path planning apparatus of a robot, comprising:

a path plan generating unit configured to form a tree within a configuration space having information about an initial configuration and a final configuration, randomly sample a configuration in the configuration space, select, from a plurality of target nodes of the tree, a nearest node nearest to the sampled configuration in consideration of a distance and an angle between each of the plurality of target nodes and the sampled configuration, select a new node on a line connecting the nearest node and the sampled configuration, add the new node to the tree, and thus complete a path plan from the initial configuration to the final configuration; and

a robot control unit configured to control movements of the robot according to the path plan,

wherein the angle is an angle formed by a vector from the selected node to the sampled configuration and a vector from a parent node of the selected node to the selected node.

2. The path planning apparatus according to claim 1, wherein the path plan generating unit selects as the nearest node a node in which the total sum of weights of functions of the distance and the angle is minimum.

3. The path planning apparatus according to claim 2, wherein the path plan generating unit performs the selection of the nearest node by the following expression,

4. The path planning apparatus according to claim 1, wherein the path plan generating unit selects as the nearest node a node in which the multiplication of functions of the distance and the angle is minimum.

5. The path planning apparatus according to claim 4, wherein the path plan generating unit performs the selection of the nearest node by the following expression,

6. The path planning apparatus according to claim 3, wherein the path plan generating unit defines the angle-related function f(x) by the following expression,

f(x)=−

cos(x)+a

where, x is an angle formed by the tree and an edge connecting the ith node and the sampled configuration, and a is a constant.

10. The path planning apparatus according to claim 5, wherein the path plan generating unit defines the angle-related function f(x) by the following expression,

f(x)=−

cos(x)+a

where, x is an angle formed by the tree and an edge connecting the ith node and the sampled configuration, and a is a constant.

7. A path planning method of a robot comprising:

forming a tree within a configuration space having information about an initial configuration and a final configuration;

randomly sampling a configuration in the configuration space;

selecting, from a plurality of target nodes of the tree, a nearest node nearest to the sampled configuration in consideration of a distance and an angle between each of the plurality of target nodes and the sampled configuration;

selecting a new node on a line connecting the nearest node and the sampled configuration;

adding the new node to the tree to complete a path plan from the initial configuration to the final configuration; and

controlling, using a robot control unit, movements of the robot according to the path plan,

wherein the angle is an angle formed by a vector from the selected node to the sampled configuration and a vector from a parent node of the selected node to the selected node.

8. The path planning method according to claim 7, wherein selecting the nearest node comprises selecting one of the plurality of target nodes in which the total sum of weights of functions of the distance and the angle is minimum.

9. The path planning method according to claim 7, wherein selecting the nearest node comprises selecting one of the plurality of target nodes in which the multiplication of functions of the distance and the angle is minimum.

11. The path planning method according to claim 7, wherein determining the nearest node is performed by the following expression,

12. The path planning method according to claim 7, wherein determining the nearest mode is performed by the following expression,