Method and apparatus to plan motion path of robot

• US 20110035087A1
• Filed: 07/21/2010
• Published: 02/10/2011
• 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, Bok Man, Lim, San, Guochunxu
• Granted Patent: US 9,411,335 B2
• Time in Patent Office: Days
• US Class Current: 701/25
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 2219/40264 Human like, type robot arm
• CPC Class Codes: G05B 2219/40476 Collision, planning for collision free path
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

A suitable waypoint is selected using a goal score, a section from a start point to a goal point through the waypoint is divided into a plurality of sections based on the waypoint with a solution of inverse kinematics, and trees are simultaneously expanded in the sections using a Best First Search & Rapidly Random Tree (BF-RRT) algorithm so as to generate a path. By this configuration, a probability of local minima occurring is decreased compared with the case where the waypoint is randomly selected. In addition, since the trees are simultaneously expanded in the sections each having the waypoint with a solution of inverse kinematics, the solution may be rapidly obtained. A time consumed to search for an optimal motion path may be shortened and path plan performance may be improved.

Claims

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

forming a configuration space to generate a motion path of a manipulator of the robot using a processor;

recognizing an obstacle as an intermediate point and selecting a waypoint having a smallest goal score from a plurality of waypoints located at predetermined distances from the intermediate point, when there is an obstacle between a start point and a goal point of the configuration space, using the processor;

dividing a section from the start point to the goal point into a plurality of sections based on the selected waypoint, using the processor;

determining whether a solution of inverse kinematics of the selected waypoint is present, using the processor;

simultaneously expanding trees with respect to sections each having a waypoint with a solution of inverse kinematics, and expanding a tree, after the expansion of the trees is finished in the sections each having the waypoint with the solution of inverse kinematics, with respect to a section having a waypoint without a solution of inverse kinematics, to generate a search graph, using the processor; and

connecting the start point and the goal point using the search graph to generate an optimal path to avoid the obstacle, using the processor.

2. The method according to claim 1, wherein the start point is a node where a configuration at an initial position before the manipulator performs a task is formed in the configuration space.

3. The method according to claim 2, wherein the goal point is a node where a configuration at a goal position where the manipulator performs a task is formed in the configuration space.

4. The method according to claim 1, wherein the intermediate point is an obstacle located within a predetermined angle from a straight line connected between the start point and the goal point.

5. The method according to claim 4, wherein the selecting of the waypoint includes selecting certain points separated from the intermediate point by predetermined distances, respectively connecting the certain points to the start point and the goal point, and selecting a certain point, in which the obstacle is not present, as the waypoint.

6. An apparatus to plan a motion path of a robot, the apparatus comprising:

a recognizer using a processor to recognize a start point and a goal point respectively corresponding to an initial configuration and a goal configuration of a manipulator, and an obstacle located between the start point and the goal point; and

a path planning generator using the processor to recognize the obstacle as an intermediate point when there is an obstacle between a start point and a goal point of a configuration space, to select a waypoint having a smallest goal score from a plurality of waypoints located at predetermined distances from the intermediate point, to divide a section from the start point to the goal point into a plurality of sections based on the selected waypoint, to simultaneously expand trees with respect to sections each having a waypoint with a solution of inverse kinematics and to expand a tree after the expansion of the trees is finished in the sections each having the waypoint with the solution of inverse kinematics, with respect to a section having a waypoint without a solution of inverse kinematics, to generate a search graph, and to connect the start point and the goal point using the search graph to generate an optimal path to avoid the obstacle.

7. The apparatus according to claim 6, wherein the intermediate point is located within a predetermined angle from a straight line connected between the start point and the goal point.

8. The apparatus according to claim 7, wherein the path planning generator selects certain points separated from the intermediate point by predetermined distances, respectively connects the certain points to the start point and the goal point, and selects a certain point, in which the obstacle is not present, as the waypoint.

9. The apparatus according to claim 8, wherein the path planning generator randomly samples a certain point in the configuration space, searches for a node having a smallest goal score, connects the certain sampled point with the node, expands a tree such that the node reaches the target point through the waypoint, and generates a search graph.