Method and apparatus to plan motion path of robot

• US 20110035050A1
• 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 8,825,209 B2
• Time in Patent Office: Days
• US Class Current: 700/246
• 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: G05D 1/0214 in accordance with safety or protection criteria, e.g. avoiding hazardous areas monitoring the location of vehicles within a certain area, e.g. forbidden or allowed areas, in traffic control systems for road vehicles G08G1/13

Abstract

If a manipulator of a robot falls in local minima when expanding a node to generate a path, the manipulator may efficiently escape from local minima by any one of a random escaping method and a goal function changing method or a combination thereof to generate the path. When the solution of inverse kinematics is not obtained due to local minima or when the solution of inverse kinematics is not obtained due to an inaccurate goal function, an optimal motion path to avoid an obstacle may be efficiently searched for. The speed to obtain the solution may be increased and thus the time consumed to search for the optimal motion path may be shortened.

Claims

1. A method of planning a motion path of a robot, the method including forming a configuration space having information about a start point, a goal point, constraints and a goal function, expanding a tree using a certain point selected in the configuration space and a node having a smallest goal score in the tree, and planning the path of a manipulator of the robot, the method comprising:

determining whether local minima occur when the tree is expanded using a processor;

selecting the certain point in the configuration space when it is determined that the local minima occur using the processor;

selecting a node closest to the certain point in the tree using the processor; and

obtaining a sample satisfying the constraints and a predetermined goal score condition in a line between the selected certain point and the selected node, adding the obtained sample to the tree, and expanding the tree having the added obtained sample, using the processor.

2. The method according to claim 1, wherein the determining of whether the local minima occur includes determining whether a goal score of a next node is greater than that of a previous node, and determining that the local minima occur when a number of times of repeating determining that a goal score of a next node is greater than that of a previous node is equal to or greater than a predetermined number.

3. The method according to claim 2, wherein the obtaining of the sample satisfying the predetermined goal score condition includes comparing the goal score of the sample with the goal score of the previous node and determining that the sample satisfies the predetermined goal score condition when the goal score of the sample is less than that of the previous node.

4. A method of planning a path of a robot, the method including forming a configuration space having information about a start point, a goal point, constraints and a goal function, expanding a tree using a certain point selected in the configuration space and a node having a smallest goal score in the tree, and planning the path of a manipulator of the robot, the method comprising:

determining whether local minima occur when the tree is expanded using a processor;

changing the goal function to a new goal function when the local minima occur, using the processor;

applying the changed goal function and selecting a node having a smallest goal score in the tree using the processor;

selecting the certain point in the configuration space using the processor; and

obtaining a sample satisfying the constraints and a predetermined goal score condition in a line between the selected certain point and the selected node, adding the obtained sample to the tree, and expanding the tree having the added obtained sample, using the processor.

5. The method according to claim 4, wherein the determining of whether the local minima occur includes determining whether a goal score of a next node is greater than that of a previous node, and determining that the local minima occur when a number of times of repeating determining that a goal score of a next node is greater than that of a previous node is equal to or greater than a predetermined number.

6. The method according to claim 5, wherein the changing of the goal function includes at least one of changing a directional vector having a predetermined angle between an obstacle and the goal point to change the goal function, and changing a directional vector having a predetermined angle between the goal point and an end effector of the manipulator falling in the local minima to change the goal function.

7. An apparatus to plan a motion path of a robot, the apparatus forming a configuration space having information about a start point, a goal point, constraints and a goal function, expanding a tree using a certain point selected in the configuration space and a node having a smallest goal score in the tree, and planning the path of a manipulator of the robot, the apparatus comprising:

a path planning generator using a processor to determine whether local minima occur when the tree is expanded, to select the certain point in the configuration space when the local minima occur, to select a node closest to the selected certain point in the tree, and to obtain a sample satisfying the constraints and a predetermined goal score condition in a line between the certain point and the selected node to add the obtained sample to the tree such that the tree having the added obtained sample is expanded.

8. An apparatus to plan a path of a robot, the apparatus forming a configuration space having information about a start point, a goal point, constraints and a goal function, expanding a tree using a certain point selected in the configuration space and a node having a smallest goal score in the tree, and planning the path of a manipulator of the robot, the apparatus comprising:

a path planning generator using a processor to determine whether local minima occur when the tree is expanded, to change the goal function to a new goal function when the local minima occur, to apply the changed goal function to select a node having a smallest goal score in the tree, to select the certain point in the configuration space, and to obtain a sample satisfying the constraints and a predetermined goal score condition in a line between the selected certain point and the selected node to add the obtained sample to the tree such that the tree is expanded.

9. The apparatus according to claim 8, wherein the path planning generator performs at least one of changing a directional vector having a predetermined angle between an obstacle and the goal point to change the goal function, and changing a directional vector having a predetermined angle between the goal point and an end effector of the manipulator falling in the local minima to change the goal function.