Path planning apparatus and method for robot

• US 9,044,862 B2
• Filed: 08/03/2010
• Issued: 06/02/2015
• Est. Priority Date: 08/10/2009
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kim, Myung Hee, Roh, Kyung Shik, Lim, San, Lim, Bok Man, Chunxu, Guo
• Primary Examiner(s): Zeender, Ryan
• Assistant Examiner(s): Amsdell, Dana
• Application Number:
  US12/805,514
• Publication Number:
  US 20110035051A1
• Time in Patent Office: 1,764 Days
• US Class Current: 1/1
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 2219/40264 Human like, type robot arm

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

1. A path planning method for a robot, comprising:

forming a configuration space, by a processing device, to generate a moving path of a manipulator of the robot;

selecting at least one waypoint by recognizing an obstacle 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, by 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 by selecting at least one of the selected arbitrary points having no obstacle between the selected arbitrary points and the start point and between the selected arbitrary points and the goal point as the at least one waypoint;

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; and

generating an optimal path to avoid the obstacle by connecting the start point and the goal point through the search graph.

2. 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.

3. 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.

4. 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.

5. The path planning method according to claim 1, 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.

6. 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.

7. The path planning method according to claim 6, 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.

8. The path planning method according to claim 6, 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.

9. 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, by 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 by 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;

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.

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

11. The path planning method according to claim 9, 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.

12. The path planning method according to claim claim 11, 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.

13. 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, to select 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 to select 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,

wherein at least one of the recognizer and the path planning generator are implemented using the processor.

14. The path planning apparatus according to claim 13, 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.

15. The path planning apparatus according to claim 13, 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.

16. The path planning apparatus according to claim 15, 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.