Path planning apparatus of robot and method and computer-readable medium thereof

• US 8,483,874 B2
• Filed: 10/13/2010
• Issued: 07/09/2013
• Est. Priority Date: 11/02/2009
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kim, Myung Hee, Lim, San, Roh, Kyung Shik, Lim, Bok Man
• Primary Examiner(s): Tran, Dalena
• Application Number:
  US12/903,653
• Publication Number:
  US 20110106306A1
• Time in Patent Office: 1,000 Days
• Field of Search: 700/246, 700/255, 700/262, 700/250, 700/253, 341/79, 701/400, 701408-411, 701/479, 701/300, 701/301, 318/567, 318/568.21, 318/568.22
• US Class Current: 700/246
• CPC Class Codes: B25J 9/1664 characterised by motion, path, trajectory planning
• CPC Class Codes: G05B 2219/40519 Motion, trajectory planning

Abstract

A path planning apparatus of a robot smoothes a motion path while satisfying a constraint. In a configuration space where a manipulator of a robot performs a task, a Rapidly-exploring Random Tree (RRT) path which extends from a start point and reaches a goal point may be smoothed while satisfying a constraint to generate a stable motion path. Accordingly, path planning performance is improved and an optimal path satisfying a kinematic constraint may be rapidly obtained.

Claims

1. A method of planning a path of a robot, the method comprising:

forming, by at least one processor, a configuration space having a start point, a goal point and a constraint to generate a motion path of a manipulator of the robot;

generating, by the at least one processor, a Rapidly-exploring Random Tree (RRT) path connecting the start point and the goal point while satisfying the constraint on the configuration space;

selecting first and second points from the RRT path;

generating, by the at least one processor, an intermediate path connecting the first and second points selected from the RRT path;

projecting, by the at least one processor, the intermediate path and determining when the constraint on the configuration space is satisfied; and

storing, by the at least one processor, the two certain points in the RRT path to smooth the RRT path if the constraint on the configuration space is satisfied.

2. The method according to claim 1, wherein the start point is a node obtained by forming a configuration on the configuration space at an initial position before the manipulator of the robot performs a task.

3. The method according to claim 1, wherein the goal point is a node obtained by forming a configuration on the configuration space at a goal position where the manipulator of the robot performs a task.

4. The method according to claim 1, wherein the projecting of the intermediate path includes:

obtaining a constraint on a working space of the manipulator of the robot;

comparing the constraint on the working space with the constraint on the configuration space to calculate an error on the working space; and

projecting nodes of the intermediate path to correct the error on the working space.

5. The method according to claim 4, wherein the nodes of the intermediate path are a plurality of nodes obtained by dividing the intermediate path by a constant interval.

6. The method according to claim 5, wherein the determining of whether the constraint on the configuration space is satisfied includes determining whether the nodes of the intermediate path satisfy the constraint on the configuration space.

7. At least one non-transitory computer readable medium comprising computer readable instructions that control at least one processor to implement the method of claim 1.

8. A method of planning a path of a robot, the method comprising:

forming, by at least one processor, a configuration space having a start point, a goal point and a constraint to generate a motion path of a manipulator of the robot;

generating, by the at least one processor, a Rapidly-exploring Random Tree (RRT) path connecting the start point and the goal point while satisfying the constraint on the configuration space;

low-pass filtering, by the at least one processor, the overall RRT path;

projecting, by the at least one processor, the low-pass filtered path and determining if the constraint on the configuration space is satisfied; and

storing, by the at least one processor, the projected path in the RRT path to smooth the RRT path if the constraint on the configuration space is satisfied.

9. The method according to claim 8, wherein the projecting of the low-pass filtered path includes:

obtaining a constraint on a working space of the manipulator of the robot;

comparing the constraint on the working space with the constraint on the configuration space to calculate an error on the working space; and

projecting nodes of the low-pass filtered path to correct the error on the working space.

10. The method according to claim 9, wherein the nodes of the low-pass filtered path are all nodes on the low-pass filtered path.

11. At least one non-transitory computer readable medium comprising computer readable instructions that control at least one processor to implement the method of claim 8.

12. An apparatus planning a path of a robot, the apparatus comprising:

a recognizer configured to recognize a start point and a goal point respectively corresponding to an initial configuration and a goal configuration of a manipulator of the robot; and

a path planning generator configured to form a configuration space to generate a motion path of the manipulator of the robot, to generate a Rapidly-exploring Random Tree (RRT) path connecting the start point and the goal point while satisfying a constraint on the configuration space, and to project the RRT path on a working space of the manipulator of the robot to smooth the RRT path,

wherein the path planning generator selects first and second points from the RRT path and generates an intermediate path connecting the first and second points selected from the RRT path.

13. The apparatus according to claim 12, wherein the path planning generator further projects nodes obtained by dividing the intermediate path by a constant interval responsive to the constraint on the configuration space, and stores the two certain points in the RRT path to smooth the RRT path if the nodes of the intermediate path satisfy the constraint on the configuration space.

14. The apparatus according to claim 13, wherein the path planning generator obtains a constraint on a working space of the manipulator of the robot, compares the constraint on the working space with the constraint on the configuration space to calculate an error on the working space, and projects nodes of the intermediate path to correct the error on the working space.

15. The apparatus according to claim 12, wherein the path planning generator low-pass filters the overall RRT path to produce a low-pass filtered path, projects the low-pass filtered path responsive to the constraint on the configuration space, and stores the projected path in the RRT path to smooth the RRT path if the projected path satisfies the constraint on the configuration space.

16. The apparatus according to claim 15, wherein the path planning generator obtains a constraint on a working space of the manipulator of the robot, compares the constraint on the working space with the constraint on the configuration space to calculate an error on the working space, and projects nodes of the low-pass filtered path to correct the error on the working space.