Planning approach for obstacle avoidance in complex environment using articulated redundant robot arm

• US 8,204,623 B1
• Filed: 10/13/2009
• Issued: 06/19/2012
• Est. Priority Date: 02/13/2009
• Status: Active Grant

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Bhattacharyya, Rajan, Srinivasa, Narayan
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): Jen, Ian
• Application Number:
  US12/587,922
• Time in Patent Office: 980 Days
• Field of Search: None
• US Class Current: 700/245
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 2219/40317 For collision avoidance and detection
• CPC Class Codes: G05B 2219/40367 Redundant manipulator
• CPC Class Codes: G05B 2219/40437 Local, directly search robot workspace
• CPC Class Codes: G05B 2219/40448 Preprocess nodes with arm configurations, c-space and planning by connecting nodes

Abstract

A planning approach for obstacle avoidance for a robot arm is disclosed. In particular, the invention relates to a planning approach for obstacle avoidance in complex environments for an articulated redundant robot arm which uses a set of via points surrounding an obstacle as an intermediary point between initial and target arm positions. Via points are generated using visual perception, and possible trajectories through the via points and to the target are rehearsed prior to execution of movement. The disclosed planning method solves the “local minima” problem in obstacle avoidance; a situation in which the obstacle avoidance vectors prevent the arm from making progress toward the target.

Claims

1. A computer implemented method for planning a path by a processor to reach a target in a complex obstacle environment using an articulated redundant robot arm, comprising:

generating possible trajectories for the robot arm from an initial point to a target point;

searching for a successful trajectory among the possible trajectories, where a trajectory is determined to be successful if the robot arm reaches the target while maintaining a certain minimum distance from obstacles along the entire trajectory and within a prescribed time limit;

when a successful trajectory is found, executing movement to the target point;

when a successful trajectory is not found;

generating a set of via points surrounding an obstacle using visual perception, each via point being an intermediary point in a path of movement of the robot arm from the initial point to the target point;

selecting an arm posture of the robot arm when positioned at each via point;

generating possible trajectories from;

each of the set of via points to the target point;

the initial point to each of the set of via points; and

each of the set of via points to each of the other set of via points;

whereby a successful trajectory from the initial point to one or more via points and to the target is found.

2. The method of claim 1, where in the act of generating a set of via points, an attention shroud is generated surrounding the obstacle using visual perception of the obstacle, and points from within the generated attention shroud are selected as via points.

3. The method of claim 2, where in the act of selecting an arm posture for each via point, each arm posture is selected from a group consisting of:

a highest scoring of a set of candidate postures recalled from a learned forward model, where the candidate postures are scored based on proximity of the via point to the arm endpoint and proximity of the arm joint angles to the mean joint angles; and

an unlearned computed posture.

4. The method of claim 3, further comprising an act of arranging the set of via points in an order prior to generating possible trajectories, the order being selected from a group consisting of:

a random order; and

an ascending order according to the magnitude of the difference in the distance between;

the via point and the initial point; and

the via point and the target point.

5. The method of claim 4, wherein the act of generating possible trajectories more specifically comprises acts of:

generating proposed trajectories from a via point of highest order to the target, the via point of highest order serving as a primary via point;

when a successful trajectory from the primary via point to the target point is found, generating possible trajectories from the initial point to the primary via point;

when a successful trajectory from the primary via point to the target point is not found, generating possible trajectories from the via point of next-highest order to the target point, the via point of next highest order serving as the new primary via point, repeating this step until a successful trajectory to the target point is found, and then generating possible trajectories from the initial point to the primary via point;

when a successful trajectory from the initial point to the primary via point is found, executing movement from the initial point to the primary via point and then to the target;

when a successful trajectory from the initial point to the primary via point is not found;

selecting another via point to act as an intermediary via point and generating possible trajectories from the intermediary via point to the primary via point;

when a successful trajectory from the intermediary via point to the primary via point is found, generating possible trajectories from the initial point to the intermediary via point;

when a successful trajectory from the initial point to the intermediary via point is found, executing movement from the initial point to the intermediary via point to the primary via point and then to the target;

when a successful trajectory from the initial point to the intermediary via point is not found, selecting another intermediary via point and repeating the process from the act of generating possible trajectories from the intermediary via point to the primary via point;

when a successful trajectory from the intermediary via point to the primary via point is not found, selecting another intermediary via point and generating possible trajectories from the intermediary via point to the primary via point, repeating this process until a successful trajectory from an intermediary via point to the primary via point is found, and then executing movement from the initial point to the intermediary via point to the primary via point and then to the target; and

when all intermediary via points have been exhausted, restarting the process from the act of generating a set of via points, by generating a new set of via points.

6. The method of claim 1, where in the act of selecting an arm posture for each via point, each arm posture is selected from a group consisting of:

a highest scoring of a set of candidate postures recalled from a learned forward model, where the candidate postures are scored based on proximity of the via point to the arm endpoint and proximity of the arm joint angles to the mean joint angles; and

an unlearned computed posture.

7. The method of claim 1, further comprising an act of arranging the set of via points in an order prior to generating possible trajectories, the order being selected from a group consisting of:

a random order; and

an ascending order according to the magnitude of the difference in the distance between;

the via point and the initial point; and

the via point and the target point.

8. The method of claim 1, wherein the act of generating possible trajectories more specifically comprises acts of:

generating possible trajectories from a via point of highest order to the target, the via point of highest order serving as a primary via point;

when a successful trajectory from the primary via point to the target point is found, generating possible trajectories from the initial point to the primary via point;

when a successful trajectory from the primary via point to the target point is not found, generating possible trajectories from the via point of next-highest order to the target point, the via point of next highest order serving as the new primary via point, repeating this step until a successful trajectory to the target point is found, and then generating possible trajectories from the initial point to the primary via point;

when a successful trajectory from the initial point to the primary via point is found, executing movement from the initial point to the primary via point and then to the target;

when a successful trajectory from the initial point to the primary via point is not found;

selecting another via point to act as an intermediary via point and generating possible trajectories from the intermediary via point to the primary via point;

when a successful trajectory from the intermediary via point to the primary via point is found, generating possible trajectories from the initial point to the intermediary via point;

when a successful trajectory from the initial point to the intermediary via point is found, executing movement from the initial point to the intermediary via point to the primary via point and then to the target;

when a successful trajectory from the initial point to the intermediary via point is not found, selecting another intermediary via point and repeating the process from the act of generating possible trajectories from the intermediary via point to the primary via point;

when a successful trajectory from the intermediary via point to the primary via point is not found, selecting another intermediary via point and generating possible trajectories from the intermediary via point to the primary via point, repeating this process until a successful trajectory from an intermediary via point to the primary via point is found, and then executing movement from the initial point to the intermediary via point to the primary via point and then to the target; and

when all intermediary via points have been exhausted, restarting the process from the act of generating a set of via points, by generating a new set of via points.

9. A data processing system for planning a path by a processor to reach a target in a complex obstacle environment using an articulated redundant robot arm, comprising one or more processors configured to perform operations of:

generating possible trajectories for the robot arm from an initial point to a target point;

searching for a successful trajectory among the possible trajectories, where a trajectory is determined to be successful if the robot arm reaches the target while maintaining a certain minimum distance from obstacles along the entire trajectory and within a prescribed time limit;

when a successful trajectory is found, executing movement to the target point;

when a successful trajectory is not found;

generating a set of via points surrounding an obstacle using visual perception, each via point being an intermediary point in a path of movement of the robot arm from the initial point to the target point;

selecting an arm posture of the robot arm when positioned at each via point;

generating possible trajectories from;

each of the set of via points to the target point;

the initial point to each of the set of via points; and

each of the set of via points to each of the other set of via points;

whereby a successful trajectory from the initial point to one or more via points and to the target is found.

10. The data processing system of claim 9, where in the operation of generating a set of via points, an attention shroud is generated surrounding the obstacle using visual perception of the obstacle, and points from within the generated attention shroud are selected as via points.

11. The data processing system of claim 10, where in the operation of selecting an arm posture for each via point, each arm posture is selected from a group consisting of:

a highest scoring of a set of candidate postures recalled from a learned forward model, where the candidate postures are scored based on proximity of the via point to the arm endpoint and proximity of the arm joint angles to the mean joint angles; and

an unlearned computed posture.

12. The data processing system of claim 11, further configured to perform an operation of arranging the set of via points in an order prior to generating possible trajectories, the order being selected from a group consisting of:

a random order; and

an ascending order according to the magnitude of the difference in the distance between;

the via point and the initial point; and

the via point and the target point.

13. The data processing system of claim 12, wherein the operation of generating possible trajectories more specifically comprises acts of:

generating possible trajectories from a via point of highest order to the target, the via point of highest order serving as a primary via point;

when a successful trajectory from the primary via point to the target point is found, generating possible trajectories from the initial point to the primary via point;

when a successful trajectory from the primary via point to the target point is not found, generating possible trajectories from the via point of next-highest order to the target point, the via point of next highest order serving as the new primary via point, repeating this step until a successful trajectory to the target point is found, and then generating possible trajectories from the initial point to the primary via point;

when a successful trajectory from the initial point to the primary via point is found, executing movement from the initial point to the primary via point and then to the target;

when a successful trajectory from the initial point to the primary via point is not found;

selecting another via point to act as an intermediary via point and generating possible trajectories from the intermediary via point to the primary via point;

when a successful trajectory from the intermediary via point to the primary via point is found, generating possible trajectories from the initial point to the intermediary via point;

when a successful trajectory from the initial point to the intermediary via point is found, executing movement from the initial point to the intermediary via point to the primary via point and then to the target;

when a successful trajectory from the initial point to the intermediary via point is not found, selecting another intermediary via point and repeating the process from the act of generating possible trajectories from the intermediary via point to the primary via point;

when a successful trajectory from the intermediary via point to the primary via point is not found, selecting another intermediary via point and generating possible trajectories from the intermediary via point to the primary via point, repeating this process until a successful trajectory from an intermediary via point to the primary via point is found, and then executing movement from the initial point to the intermediary via point to the primary via point and then to the target; and

when all intermediary via points have been exhausted, restarting the process from the act of generating a set of via points, by generating a new set of via points.

14. The data processing system of claim 9, where in the operation of selecting an arm posture for each via point, each arm posture is selected from a group consisting of:

a highest scoring of a set of candidate postures recalled from a learned forward model, where the candidate postures are scored based on proximity of the via point to the arm endpoint and proximity of the arm joint angles to the mean joint angles; and

an unlearned computed posture.

15. The data processing system of claim 9, further configured to perform an operation of arranging the set of via points in an order prior to generating possible trajectories, the order being selected from a group consisting of:

a random order; and

an ascending order according to the magnitude of the difference in the distance between;

the via point and the initial point; and

the via point and the target point.

16. The data processing system of claim 9, wherein the operation of generating possible trajectories more specifically comprises acts of:

generating possible trajectories from a via point of highest order to the target, the via point of highest order serving as a primary via point;

when a successful trajectory from the primary via point to the target point is found, generating possible trajectories from the initial point to the primary via point;

when a successful trajectory from the primary via point to the target point is not found, generating possible trajectories from the via point of next-highest order to the target point, the via point of next highest order serving as the new primary via point, repeating this step until a successful trajectory to the target point is found, and then generating possible trajectories from the initial point to the primary via point;

when a successful trajectory from the initial point to the primary via point is found, executing movement from the initial point to the primary via point and then to the target;

when a successful trajectory from the initial point to the primary via point is not found;

selecting another via point to act as an intermediary via point and generating possible trajectories from the intermediary via point to the primary via point;

when a successful trajectory from the intermediary via point to the primary via point is found, generating possible trajectories from the initial point to the intermediary via point;

when a successful trajectory from the initial point to the intermediary via point is found, executing movement from the initial point to the intermediary via point to the primary via point and then to the target;

when a successful trajectory from the initial point to the intermediary via point is not found, selecting another intermediary via point and repeating the process from the act of generating possible trajectories from the intermediary via point to the primary via point;

when a successful trajectory from the intermediary via point to the primary via point is not found, selecting another intermediary via point and generating possible trajectories from the intermediary via point to the primary via point, repeating this process until a successful trajectory from an intermediary via point to the primary via point is found, and then executing movement from the initial point to the intermediary via point to the primary via point and then to the target; and

when all intermediary via points have been exhausted, restarting the process from the act of generating a set of via points, by generating a new set of via points.

17. A computer program product for planning a path by a processor to reach a target in a complex obstacle environment using an articulated redundant robot arm, the computer program product comprising computer-readable instruction means stored on a computer-readable medium that are executable by a computer having a processor for causing the processor to perform operations of:

generating possible trajectories for the robot arm from an initial point to a target point;

searching for a successful trajectory among the possible trajectories, where a trajectory is determined to be successful if the robot arm reaches the target while maintaining a certain minimum distance from obstacles along the entire trajectory and within a prescribed time limit;

when a successful trajectory is found, executing movement to the target point;

when a successful trajectory is not found;

generating a set of via points surrounding an obstacle using visual perception, each via point being an intermediary point in a path of movement of the robot arm from the initial point to the target point;

selecting an arm posture of the robot arm when positioned at each via point;

generating possible trajectories from;

each of the set of via points to the target point;

the initial point to each of the set of via points; and

each of the set of via points to each of the other set of via points;

whereby a successful trajectory from the initial point to one or more via points and to the target is found.

18. The computer program product of claim 17, where in the operation of generating a set of via points, an attention shroud is generated surrounding the obstacle using visual perception of the obstacle, and points from within the generated attention shroud are selected as via points.

19. The computer program product of claim 18, where in the operation of selecting an arm posture for each via point, each arm posture is selected from a group consisting of:

a highest scoring of a set of candidate postures recalled from a learned forward model, where the candidate postures are scored based on proximity of the via point to the arm endpoint and proximity of the arm joint angles to the mean joint angles; and

an unlearned computed posture.

20. The computer program product of claim 19, further configured to perform an operation of arranging the set of via points in an order prior to generating possible trajectories, the order being selected from a group consisting of:

a random order; and

an ascending order according to the magnitude of the difference in the distance between;

the via point and the initial point; and

the via point and the target point.

21. The computer program product of claim 20, wherein the operation of generating possible trajectories more specifically comprises acts of:

generating possible trajectories from a via point of highest order to the target, the via point of highest order serving as a primary via point;

when a successful trajectory from the primary via point to the target point is found, generating possible trajectories from the initial point to the primary via point;

when a successful trajectory from the primary via point to the target point is not found, generating possible trajectories from the via point of next-highest order to the target point, the via point of next highest order serving as the new primary via point, repeating this step until a successful trajectory to the target point is found, and then generating possible trajectories from the initial point to the primary via point;

when a successful trajectory from the initial point to the primary via point is found, executing movement from the initial point to the primary via point and then to the target;

when a successful trajectory from the initial point to the primary via point is not found;

selecting another via point to act as an intermediary via point and generating possible trajectories from the intermediary via point to the primary via point;

when a successful trajectory from the intermediary via point to the primary via point is found, generating possible trajectories from the initial point to the intermediary via point;

when a successful trajectory from the initial point to the intermediary via point is found, executing movement from the initial point to the intermediary via point to the primary via point and then to the target;

when a successful trajectory from the initial point to the intermediary via point is not found, selecting another intermediary via point and repeating the process from the act of generating possible trajectories from the intermediary via point to the primary via point;

when a successful trajectory from the intermediary via point to the primary via point is not found, selecting another intermediary via point and generating possible trajectories from the intermediary via point to the primary via point, repeating this process until a successful trajectory from an intermediary via point to the primary via point is found, and then executing movement from the initial point to the intermediary via point to the primary via point and then to the target; and

when all intermediary via points have been exhausted, restarting the process from the act of generating a set of via points, by generating a new set of via points.

22. The computer program product of claim 17, where in the operation of selecting an arm posture for each via point, each arm posture is selected from a group consisting of:

a highest scoring of a set of candidate postures recalled from a learned forward model, where the candidate postures are scored based on proximity of the via point to the arm endpoint and proximity of the arm joint angles to the mean joint angles; and

an unlearned computed posture.

23. The computer program product of claim 17, further configured to perform an operation of arranging the set of via points in an order prior to generating possible trajectories, the order being selected from a group consisting of:

a random order; and

an ascending order according to the magnitude of the difference in the distance between;

the via point and the initial point; and

the via point and the target point.

24. The computer program product of claim 17, wherein the operation of generating possible trajectories more specifically comprises acts of:

generating possible trajectories from a via point of highest order to the target, the via point of highest order serving as a primary via point;

when a successful trajectory from the primary via point to the target point is found, generating possible trajectories from the initial point to the primary via point;

when a successful trajectory from the primary via point to the target point is not found, generating possible trajectories from the via point of next-highest order to the target point, the via point of next highest order serving as the new primary via point, repeating this step until a successful trajectory to the target point is found, and then generating possible trajectories from the initial point to the primary via point;

when a successful trajectory from the initial point to the primary via point is found, executing movement from the initial point to the primary via point and then to the target;

when a successful trajectory from the initial point to the primary via point is not found;

selecting another via point to act as an intermediary via point and generating possible trajectories from the intermediary via point to the primary via point;

when a successful trajectory from the intermediary via point to the primary via point is found, generating possible trajectories from the initial point to the intermediary via point;

when a successful trajectory from the initial point to the intermediary via point is found, executing movement from the initial point to the intermediary via point to the primary via point and then to the target;

when a successful trajectory from the initial point to the intermediary via point is not found, selecting another intermediary via point and repeating the process from the act of generating possible trajectories from the intermediary via point to the primary via point;

when a successful trajectory from the intermediary via point to the primary via point is not found, selecting another intermediary via point and generating possible trajectories from the intermediary via point to the primary via point, repeating this process until a successful trajectory from an intermediary via point to the primary via point is found, and then executing movement from the initial point to the intermediary via point to the primary via point and then to the target; and

when all intermediary via points have been exhausted, restarting the process from the act of generating a set of via points, by generating a new set of via points.