METHOD AND SYSTEM FOR AUTOMATIC PATH PLANNING AND OBSTACLE/COLLISION AVOIDANCE OF AUTONOMOUS VEHICLES

• US 20090088916A1
• Filed: 06/04/2008
• Published: 04/02/2009
• Est. Priority Date: 09/28/2007
• Status: Abandoned Application

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Fregene, Kingsley O.C., Ariyur, Kartik B., Elgersma, Michael R., Pratt, Stephen G., Dajani-Brown, Samar
• Application Number:
  US12/133,321
• Publication Number:
  US 20090088916A1
• Time in Patent Office: Days
• US Class Current: 701/23
• CPC Class Codes: G05D 1/106 Change initiated in response to external conditions, e.g. avoidance of elevated terrain or of no-fly zones

Abstract

Method and systems of traversing through a domain is provided. One method comprises getting a set of widely spaced waypoints, assigning the next waypoint to be the goal, then using a Laplacian path planner to construct a desired finely detailed path towards the goal, through the domain that avoids boundaries and objects in the domain. Assigning a potential value of v(r)=0 for r on boundaries and obstacles. Assigning a potential value of v(r)=−1 for r on a goal region, wherein the goal is a point on a planned path. Obtaining a numerical solution to the desired path with a Laplace'"'"'s equation by gridding up the domain with a multi-sized cell grid, wherein the cells near an object are denser then the cells away from the objects. Iteratively setting a potential at each interior point equal to the average of its nearest neighbors and following the numerical solution provided by the Laplace'"'"'s equation to the goal region.

Claims

1. A method of traversing through a domain, the method comprising:

setting a set of waypoints to construct a desired path through the domain that avoids boundaries and objects in the domain;

assigning a potential value of v(r)=0 for r on boundaries and obstacles;

assigning a potential value of v(r)=−

1 for r on a goal region, wherein the goal is a point on a planned path;

obtaining a numerical solution to the desired path with a Laplace'"'"'s equation by gridding up the domain with a multi-sized cell grid, wherein the cells near an object are denser then the cells away from the objects;

iteratively setting a potential at each interior point equal to the average of its nearest neighbors; and

following the numerical solution provided by the Laplace'"'"'s equation to the goal region.

2. The method of claim 1, wherein when the domain to be traversed is a roadway, the method further comprising:

when encountering a stop sign at an intersection, observing other stop signs having associated queued traffic; and

waiting until at least one vehicle leaves its associated queue and clears the intersection for each associated occupied stop sign before traversing the intersection.

3. The method of claim 2, further comprising:

when a vehicle in an observed queue does not traverse the intersection in a select time, traversing the intersection.

4. The method of claim 1, wherein when the domain to be traversed is a roadway the method further comprising:

employing heading constraints that define the movements of the vehicle.

5. The method of claim 4, further comprising:

turning off heading constraints during select maneuvers.

6. The method of claim 1, wherein when the domain to be traversed is a roadway the method further comprising:

implementing at least one of a paint-on constraint, a waypoint-heading constraint and a turn constraint in traversing the roadway.

7. A method for automatic path planning and obstacle/collision avoidance of autonomous vehicles through a domain, the method comprising:

selecting a set of waypoints that construct a desired planned path from an initial point to a goal;

applying a computation box that is centered around the vehicle as the vehicle traverses through the path defined by the waypoints, the computation path allowing for a smaller window of forward computations as the vehicle traverses the path;

assigning a potential value of v(r)=0 for r on boundaries and obstacles;

assigning a potential value of v(r)=−

1 for r on a goal region, wherein the goal is a point on a planned path; and

solving Laplaces'"'"'s equation in an interior of the domain, guaranteeing no minima in the interior domain, leaving a global minimum of v(r)=−

1 for r on the goal region, and global maxima of v(r)=0 for r on any boundaries or obstacle in directing the vehicle to follow the path.

8. The method of claim 7, further comprising:

when the goal is outside the computational box, determining a straight line from the vehicle to the goal;

determining a projected goal at the intersection of the determined straight line and an edge of the computation box; and

traversing towards the projected goal.

9. The method of claim 8, further comprising:

if the projected goal is within an object, clearing out a portion of the parameter of the computation box so that the projected goal falls outside the object.

10. The method of claim 7, further comprising:

gridding up the domain with a multi-sized cell grid, wherein the cells near an object are denser then the cells away from the objects; and

using the gridded domain to obtain a numerical solution to the desired path with Laplace'"'"'s equation.

11. The method of claim 7, wherein when the domain to be traversed is a roadway, the method further comprising:

when encountering a stop sign at an intersection, observing other stop signs having associated queued traffic; and

waiting until at least one vehicle leaves its associated queue and clears the intersection for each associated occupied stop sign before traversing the intersection.

12. The method of claim 7, wherein when the domain to be traversed is a roadway the method further comprising:

implementing at least one of a paint-on constraint, a waypoint heading-constraint and a turn constraint in traversing the roadway.

13. An autonomous vehicle, comprising:

an input-path generating module configured to generate a planned path of an area to be traversed based on waypoints by applying a laplacian to a multi-sized cell grid of the area to be traversed;

sensors configured to generate sensing data;

a guidance module configured to generate guidance commands based at least in part on the planned path from the input-path generating module and the sensing data, the guidance module including,

a collision avoidance module configured to generate alternative paths to avoid unforeseen obstacles; and

a vehicle control module configured to control the dynamics of the vehicle based at least in part on the guidance command.

14. The vehicle of claim 13, wherein the input-path generating module is further configured to receive the planned path information remotely.

15. The vehicle of claim 13, wherein the sensors include at least one of an inertial measurement unit, a global positioning system and a barometric pressure sensor.

16. The vehicle of claim 13, wherein the sensors include a collision avoidance sensor.

17. The vehicle of claim 16, wherein the collision avoidance sensor is a laser detection and ranging (LADAR) device.

18. The vehicle of claim 13, wherein the collision avoidance module configured to generate alternative paths to avoid unforeseen obstacles further implements a laplacian algorithm to generate the alternative path.

19. The vehicle of claim 13, wherein the guidance module is further configured to apply traffic logic in an urban environment for a ground vehicle.

20. The vehicle of claim 13, wherein the collision avoidance module is configured to stop generating alternative paths when the vehicle is within a select distance of a goal.