System and method for adaptive path planning

• US 7,447,593 B2
• Filed: 03/26/2004
• Issued: 11/04/2008
• Est. Priority Date: 03/26/2004
• Status: Expired due to Fees

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Tinker, Peter A., Estkowski, Regina I.
• Primary Examiner(s): Black; Thomas G.
• Assistant Examiner(s): Behncke; Christine M
• Application Number:
  US10/811,460
• Publication Number:
  US 20050216181A1
• Time in Patent Office: 1,684 Days
• Field of Search: 341/79, 701/200, 701/201, 701/301, 700/250, 700/253
• US Class Current: 701/301
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G05D 1/0212 with means for defining a desired trajectory involving a plurality of land vehicles G05D1/0287
• CPC Class Codes: G08G 1/164 Centralised systems, e.g. external to vehicles
• CPC Class Codes: G08G 1/166 for active traffic, e.g. moving vehicles, pedestrians, bikes

Abstract

A path planning system and method for an object, such as a vehicle, provides a randomized adaptive path planning that handles real-time path planning for a vehicle operating under kinodynamic constraints in dynamically changing and uncertain environments with probabilistic knowledge of vehicle and obstacle movement.

Claims

1. A method of planning at least one path for a vehicle in a state space from a starting position to a goal position to avoid a plurality of static and/or dynamic objects, comprising:

associating predetermined attributes with the plurality of static objects and/or the plurality of dynamic objects located in the state space;

generating a probabilistic tree in the state space including a plurality of branches extending from the starting position of the vehicle towards the goal position located in the state space, generating the probabilistic tree in the state space comprises extending each of a first plurality of edges a first predetermined distance and direction from the starting position in the state space to each of a corresponding first plurality of nodes based on the plurality of random tree extension rules and the plurality of deterministic tree extension rules for forming first segments of each of the plurality of branches of the probabilistic tree;

extending the plurality of branches of the probabilistic tree towards the goal position located in the state space based on at least one of a plurality of random tree extension rules and a plurality of deterministic tree extension rules until satisfying a predetermined stopping condition;

evaluating at least a first branch of the plurality of branches of the probabilistic tree for determining whether the first branch of the plurality of branches of the probabilistic tree satisfies predetermined trajectory path constraints;

extending at least one of a next successive plurality of edges from each of the first plurality of nodes a second predetermined distance and direction in the state space to each of a corresponding next successive plurality of nodes based on the plurality of random tree extension rules and the plurality of deterministic tree extension rules for forming next successive segments of each branch of the plurality of branches of the probabilistic tree;

repeating cyclically extension of each branch of the plurality of branches of the probabilistic tree until at least the first branch of the plurality of branches of the probabilistic tree satisfies the stopping condition;

evaluating whether extension of one or more branches of the plurality of branches of the probabilistic tree violate object avoidance constraints;

suspending further extension of the one or more branches of the plurality of branches if a determination is made that extension of the one or more branches of the plurality of branches of the probabilistic tree violate the object avoidance constraints; and

resuming extension of the one or more branches of the plurality of branches if a determination is made that extension of the one or more branches of the plurality of branches of the probabilistic tree no longer violates the object avoidance constraints.

2. The method of claim 1, wherein if the first branch of the plurality of branches of the probabilistic tree conforms to the predetermined trajectory path constraints, the method further includes:

declaring the first branch of the plurality of branches of the probabilistic tree as the at least one preferred trajectory path for the vehicle in the state space; and

controlling the vehicle to follow the at least one preferred trajectory path in the state space for moving the vehicle from the starting position towards the goal position in the state space.

3. The method of claim 2, wherein if the first branch of the plurality of branches of the probabilistic tree fails to conform to the predetermined trajectory path constraints, the method further includes:

extending the plurality of branches of the probabilistic tree further based on the at least one of the plurality of random tree extension rules and the plurality of deterministic tree extension rules until at least one branch of the plurality of branches of the probabilistic tree satisfies the predetermined stopping condition and conforms to the predetermined trajectory path constraints.

4. The method of claim 3, further including:

declaring the at least one branch of the plurality of branches of the probabilistic tree that couples the starting position to the goal position and that conforms to the predetermined trajectory path constraints as the at least one preferred trajectory path for the vehicle in the state space; and

controlling the vehicle to follow the at least one preferred trajectory path in the state space for moving the vehicle from the starting position towards the goal position in the state space.

5. The method of claim 1, wherein satisfying the predetermined stopping condition includes at least one of satisfying a predetermined time constraint and satisfying a predetermined travel distance constraint.

6. The method of claim 1, wherein associating predetermined attributes with the plurality of static objects and the plurality of dynamic objects located in the state space includes associating at least one of a position value, a velocity value, a direction value, an acceleration value and a time value.

7. The method of claim 1, wherein extending the plurality of branches of the probabilistic tree based on the plurality of random tree extension rules includes at least one of extending each branch into the state space that is void of the plurality of static objects and the plurality of dynamic objects and extending each branch into the state space that is void of other branches of the plurality of branches of the probabilistic tree.

8. The method of claim 1, wherein the first deterministic rule to add a linear path comprises a rule to add a linear path such that a heading and speed of the vehicle are constant.

9. The method of claim 1, wherein determining whether the first branch of the plurality of branches of the probabilistic tree satisfies the predetermined trajectory path constraints includes determining whether the first branch of the plurality of branches of the probabilistic tree satisfies at least one of a maximum travel distance value, a maximum turn angle value, a minimum distance value to the plurality of static objects and the plurality of dynamic objects.