Method and apparatus to plan motion path of robot

• US 8,825,209 B2
• Filed: 07/21/2010
• Issued: 09/02/2014
• 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): Algahaim, Helal A
• Assistant Examiner(s): SMITH, JELANI A
• Application Number:
  US12/805,271
• Publication Number:
  US 20110035050A1
• Time in Patent Office: 1,504 Days
• Field of Search: 700/253, 700/245, 700/141, 700/247, 700/255, 701/22, 701/25, 701/408, 701/411, 701/455, 701/533
• 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, comprising:

planning a motion path of a robot by use of a processor through a first method before it is determined that local minima occur, the first method comprising a Best First Search And Rapidly Random Tree (BF-RRT), and the BF-RRT 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;

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

planning a motion path of a robot by use of a processor through a second method that is different from the first method when it is determined that the local minima occur, the second method comprising a Single-Rapidly Random Tree (Single-RRT), wherein the performing of the Single-RRT comprises selecting the certain point in the configuration space, selecting a node closest to the certain point in the tree, obtaining a sample satisfying the constraints 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.

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,

wherein the changing of the goal function includes at least one of selecting a directional vector having a predetermined angle between an obstacle and the goal point to change the goal function, and selecting 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.

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. An apparatus to plan a motion path of a robot, comprising:

a path planning generator using a processor to plan a motion path of a robot through a first method before it is determined that local minima occur, to determine whether the local minima occur when a tree is expanded, and to plan a motion path of a robot through a second method that is different from the first method when it is determined that the local minima occur, the first method comprising a Best First Search And Rapidly Random Tree (BF-RRT) and the second method comprising a Single-Rapidly Random Tree (Single-RRT),

wherein the BF-RRT comprises forming a configuration space having information about a start point, a goal point, constraints and a goal function, expanding the 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, and

wherein the Single-RRT comprises selecting the certain point in the configuration space, selecting a node closest to the selected certain point in the tree, obtaining a sample satisfying the constraints in a line between the certain point and the selected node, adding the obtained sample to the tree, and expanding the tree having the added obtained sample.

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

wherein the path planning generator performs at least one of selecting a directional vector having a predetermined angle between an obstacle and the goal point to change the goal function, and selecting 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.