Method for determining projected obstacle areas for moving obstacles

• US 7,957,858 B1
• Filed: 02/25/2008
• Issued: 06/07/2011
• Est. Priority Date: 05/07/2007
• Status: Expired due to Fees

• Current Assignee: the united states of america as represented by the secretary of the navy
• Original Assignee: the united states of america as represented by the secretary of the navy
• Inventors: Bruch, Michael H., Larson, Jacoby R.
• Primary Examiner(s): Beaulieu; Yonel
• Application Number:
  US12/036,441
• Time in Patent Office: 1,198 Days
• Field of Search: 701/23, 701301-302, 701/96, 340435-436
• US Class Current: 701/23
• CPC Class Codes: G05D 1/0206 specially adapted to water vehicles

Abstract

A method involves calculating a closest point of approach (CPA) between a vehicle and a moving obstacle, determining the CPA is within a pre-determined distance from the vehicle at a point in time along the vehicle path, calculating a projected obstacle area (POA) for the moving obstacle, and modifying the vehicle path so the vehicle avoids the POA. The POA is a polygonal region between the boundaries calculated by determining a first point in time along the obstacle path that the moving obstacle is within the pre-determined distance, determining a second point in time along the obstacle path that the moving obstacle is within the pre-determined distance, creating a first line on one side of a midpoint line based upon a pre-determined angle of uncertainty, and creating a second line on the other side of the midpoint line based upon the pre-determined angle of uncertainty.

Claims

1. A method comprising the steps of:

determining a closest point of approach between a vehicle traveling along a vehicle path and at least one moving obstacle traveling along an obstacle path, the vehicle path having more than one vehicle path segments, the closest point of approach being along the obstacle path, the vehicle having a vehicle heading and a vehicle velocity and the moving obstacle having an obstacle heading and an obstacle velocity;

determining that the closest point of approach is within a pre-determined distance from the vehicle at a point in time along the vehicle path;

determining a projected obstacle area for the moving obstacle, the determination comprising

determining a first point in time along the obstacle path that the moving obstacle is within the pre-determined distance from the vehicle, the first point in time being farther from the vehicle than the closest point of approach,

determining a second point in time along the obstacle path that the moving obstacle is within the pre-determined distance from the vehicle, the second point in time being farther from the first point in time than the closest point of approach,

creating a first line on one side of a midpoint line based upon a pre-determined angle of uncertainty, the midpoint line extending from the first point in time through the closest point of approach to the second point in time, the pre-determined angle of uncertainty measured from the first point in time, and

creating a second line on the other side of the midpoint line based upon the pre-determined angle of uncertainty

wherein the projected obstacle area comprises the polygonal region between the closest point of approach, the second point in time, the first line, and the second line; and

modifying the vehicle path such that the vehicle avoids the projected obstacle area.

2. The method of claim 1, wherein the step of determining a closest point of approach comprises the steps of:

calculating an obstacle path segment for the moving obstacle using the obstacle heading, the obstacle velocity, and the time for the vehicle to complete a vehicle path segment;

finding two points, one point along the vehicle path and the other point along the obstacle path, in relation to the vehicle heading, the vehicle velocity, the obstacle heading, and the obstacle velocity, that return the shortest distance between the vehicle and the moving obstacle; and

selecting the point along the obstacle path, wherein the closest point of approach is the point along the obstacle path.

3. The method of claim 1 further comprising the step of, for each segment of the vehicle path, repeating the steps of determining a closest point of approach between a vehicle traveling along a vehicle path and at least one moving obstacle traveling along an obstacle path, determining that the closest point of approach is within a pre-determined distance from the vehicle at a point in time along the vehicle path, determining a projected obstacle area for the moving obstacle, and modifying the vehicle path such that the vehicle avoids the projected obstacle area.

4. The method of claim 1, wherein the vehicle path and the obstacle path do not intersect.

5. The method of claim 1 further comprising the step of modifying the projected obstacle area based on the rules of the vehicle'"'"'s operating environment.

6. The method of claim 5, wherein the vehicle'"'"'s operating environment is a water-based environment.

7. The method of claim 6, wherein the step of modifying the projected obstacle area based on the rules of the vehicle'"'"'s operating environment includes increasing the uncertainty angle on at least one side of the projected obstacle area.

8. The method of claim 6, wherein the step of modifying the projected obstacle area based on the rules of the vehicle'"'"'s operating environment includes increasing the ahead distance of the projected obstacle area.

9. The method of claim 6, wherein the step of modifying the projected obstacle area based on the rules of the vehicle'"'"'s operating environment includes increasing the astern distance of the projected obstacle area.

10. The method of claim 1, wherein the projected obstacle area is determined based upon the vehicle path and the time required by the vehicle to traverse the vehicle path.

11. The method of claim 1 further comprising the step of updating the projected obstacle area after a pre-determined time period.

12. The method of claim 1, wherein the first point in time is the first point in time in which the moving obstacle is within the pre-determined distance from the vehicle.

13. The method of claim 1, wherein the second point in time is the last point in time in which the moving obstacle is within the pre-determined distance from the vehicle.

14. The method of claim 1, wherein the step of modifying the vehicle path such that the vehicle path avoids the projected obstacle area includes modifying the vehicle path such that a vehicle region avoids the projected obstacle area, wherein the vehicle region comprises the region surrounding the vehicle and extending a distance comprised of the pre-determined distance.

15. A non-transitory computer readable storage medium having a method encoded thereon, the method represented by computer readable programming code, the method comprising the steps of:

determining a closest point of approach between a vehicle traveling along a vehicle path and at least one moving obstacle traveling along an obstacle path, the closest point of approach being along the obstacle path, the vehicle having a vehicle heading and a vehicle velocity and the moving obstacle having an obstacle heading and an obstacle velocity;

determining that the closest point of approach is within a pre-determined distance from the vehicle at a point in time along the vehicle path; and

determining a projected obstacle area for the moving obstacle, the determination comprising

determining a first point in time along the obstacle path that the moving obstacle is within the pre-determined distance from the vehicle, the first point in time being farther from the vehicle than the closest point of approach,

determining a second point in time along the obstacle path that the moving obstacle is within the pre-determined distance from the vehicle, the second point in time being farther from the first point in time than the closest point of approach,

creating a first line on one side of a midpoint line based upon a pre-determined angle of uncertainty, the midpoint line extending from the first point in time through the closest point of approach to the second point in time, the pre-determined angle of uncertainty measured from the first point in time, and

creating a second line on the other side of the midpoint line based upon the pre-determined angle of uncertainty

wherein the projected obstacle area comprises the polygonal region between the closest point of approach, the second point in time, the first line, and the second line.

16. The non-transitory computer readable storage medium of claim 15, wherein the step of determining a closest point of approach comprises the steps of:

calculating an obstacle path segment for the moving obstacle using the obstacle heading, the obstacle velocity, and the time for the vehicle to complete a vehicle path segment;

finding two points, one point along the vehicle path and the other point along the obstacle path, in relation to the vehicle heading, the vehicle velocity, the obstacle heading, and the obstacle velocity, that return the shortest distance between the vehicle and the moving obstacle; and

selecting the point along the obstacle path, wherein the closest point of approach is the point along the obstacle path.

17. The non-transitory computer readable storage medium of claim 15, wherein the method further comprises the step of modifying the projected obstacle area based on the rules of the vehicle'"'"'s operating environment.

18. The non-transitory computer readable storage medium of claim 17, wherein the vehicle'"'"'s operating environment is a water-based environment.

19. The non-transitory computer readable storage medium of claim 15, wherein the method further comprises the step of updating the projected obstacle area after a pre-determined time period.

20. The non-transitory computer readable storage medium of claim 15, wherein the first point in time is the first point in which the moving obstacle is within the pre-determined distance from the vehicle and the second point in time is the last point in which the moving obstacle is within the pre-determined distance from the vehicle.

21. The non-transitory computer readable storage medium of claim 15, wherein the method further comprises the step of modifying the vehicle path such that the vehicle avoids the projected obstacle area.

22. A system comprising:

a processor; and

a memory module operatively connected to the processor, the memory module having program instructions stored therein, wherein the program instructions are executable by the processor to perform a method comprising the steps of;

determining a closest point of approach between a vehicle traveling along a vehicle path and at least one moving obstacle traveling along an obstacle path, the closest point of approach being along the obstacle path, the vehicle having a vehicle heading and a vehicle velocity and the moving obstacle having an obstacle heading and an obstacle velocity;

determining that the closest point of approach is within a pre-determined distance from the vehicle at a point in time along the vehicle path; and

determining a projected obstacle area for the moving obstacle, the determination comprising

determining a first point in time along the obstacle path that the moving obstacle is within the pre-determined distance from the vehicle, the first point in time being farther from the vehicle than the closest point of approach,

determining a second point in time along the obstacle path that the moving obstacle is within the pre-determined distance from the vehicle, the second point in time being farther from the first point in time than the closest point of approach,

creating a first line on one side of a midpoint line based upon a pre-determined angle of uncertainty, the midpoint line extending from the first point in time through the closest point of approach to the second point in time, the pre-determined angle of uncertainty measured from the first point in time, and

creating a second line on the other side of the midpoint line based upon the pre-determined angle of uncertainty

wherein the projected obstacle area comprises the polygonal region between the closest point of approach, the second point in time, the first line, and the second line.

23. The system of claim 22, wherein the step of determining a closest point of approach comprises the steps of:

calculating an obstacle path segment for the moving obstacle using the obstacle heading, the obstacle velocity, and the time for the vehicle to complete a vehicle path segment;

finding two points, one point along the vehicle path and the other point along the obstacle path, in relation to the vehicle heading, the vehicle velocity, the obstacle heading, and the obstacle velocity, that return the shortest distance between the vehicle and the moving obstacle; and

selecting the point along the obstacle path, wherein the closest point of approach is the point along the obstacle path.

24. The system of claim 22, wherein the method further comprises the step of modifying the vehicle path such that the vehicle avoids the projected obstacle area.

25. The system of claim 24, wherein the step of modifying the vehicle path such that the vehicle path avoids the projected obstacle area comprises the step of causing a component to modify the vehicle path such that the vehicle path avoids the projected obstacle area.

26. The system of claim 24, wherein the step of modifying the vehicle path such that the vehicle path avoids the projected obstacle area includes modifying the vehicle path such that a vehicle region avoids the projected obstacle area, wherein the vehicle region comprises the region surrounding the vehicle and extending a distance comprised of the pre-determined distance.

27. The system of claim 22, wherein the method further comprises the step of modifying the projected obstacle area based on the rules of the vehicle'"'"'s operating environment, wherein the vehicle'"'"'s operating environment is a water-based environment.

28. A method comprising the steps of:

a) determining a closest point of approach between a vehicle traveling along a vehicle path and at least one moving obstacle traveling along an obstacle path, the vehicle path having more than one vehicle path segments each comprising at least one vehicle path portion, the closest point of approach being along the obstacle path, the vehicle having a vehicle heading and a vehicle velocity and the moving obstacle having an obstacle heading and an obstacle velocity;

b) determining that the closest point of approach is within a pre-determined distance from the vehicle at a point in time along the vehicle path;

c) determining a projected obstacle area for the moving obstacle, the determination comprising

determining a first point in time along the obstacle path that the moving obstacle is within the pre-determined distance from the vehicle, the first point in time being farther from the vehicle than the closest point of approach,

determining a second point in time along the obstacle path that the moving obstacle is within the pre-determined distance from the vehicle, the second point in time being farther from the first point in time than the closest point of approach,

creating a first line on one side of a midpoint line based upon a pre-determined angle of uncertainty, the midpoint line extending from the first point in time through the closest point of approach to the second point in time, the pre-determined angle of uncertainty measured from the first point in time, and

creating a second line on the other side of the midpoint line based upon the pre-determined angle of uncertainty

wherein the projected obstacle area comprises the polygonal region between the closest point of approach, the second point in time, the first line, and the second line;

d) repeating steps (a) through (c) for each vehicle path portion of a vehicle path segment;

e) modifying the vehicle path such that the vehicle avoids the projected obstacle areas determined for each vehicle path segment; and

f) repeating steps (a) through (e) for each vehicle path segment of the vehicle path.