Route planner with area avoidance capability

• US 6,529,821 B2
• Filed: 06/05/2001
• Issued: 03/04/2003
• Est. Priority Date: 06/05/2001
• 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: Benevides, Karen, Tomasi, Steven W.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Marc-Coleman, Marthe Y.
• Application Number:
  US09/874,464
• Publication Number:
  US 20020183922A1
• Time in Patent Office: 637 Days
• Field of Search: 701/23, 701/202, 701/300, 701/301, 701/302, 342/65, 342/69, 244/3.1, 244/3.15, 102/501, 89/11
• US Class Current: 701/202
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence

Abstract

A method for establishing a path from a launch point to a destination point that can include multiple way points while avoiding landmass areas. Launch points and destination points can lie outside or inside the particular landmass areas. The method includes steps for defining tangents path areas to be avoided, extending those tangents to define way points and testing the individual way points to assure conformance to various conditions and constraints. A subset of paths are optimized. The shortest of the optimized paths becomes a final path.

Claims

1. A method for establishing a route with at least one way point by which a steerable vehicle will maneuver between a current source point and a destination point that avoids at least one intermediate obstacle, said method comprising the steps of:

defining first and second bearing lines extending from the current source point to first and second tangents, respectively, of each of the at least one intermediate obstacle;

extending each of the defined bearing lines an incremental distance beyond the tangent thereof with a corresponding obstacle and thereby defining a next possible way point along that bearing line; and

converting each next possible way point to a way point for the route.

2. A method as recited in claim 1 wherein a plurality of obstacles are intermediate a current source point and the destination point requiring a plurality of way points along the route, said steps of defining bearing lines and extending bearing lines being performed iteratively by substituting each next possible way point as a current source point until a route to the destination point is defined.

3. A method as recited in claim 2 wherein the iterative process of defining bearing lines and extending bearing lines produces a plurality of paths to the destination point, said method additionally comprising the step of selecting the shortest path to the destination point as the route.

4. A method as recited in claim 3 wherein the steerable vehicle is characterized by a constraint on the maneuverability thereof, said defining of a next possible way point including, during each iteration, checking a path to the current source point and a path from the current source point to the next possible way point for compliance with the constraint and modifying the next possible way point to conform to the constraint.

5. A method as recited in claim 3 wherein each of the plurality of paths has a total length, said method comprising the additional step of modifying the path to reduce the total length thereof.

6. A method as recited in claim 5 wherein each intermediate way point in a path is moved, in sequence starting from the way point most proximate the destination point, along the bearing thereto until a line from the intermediate way point being moved to the successive one of the way point and destination point becomes tangent an obstacle.

7. A method as recited in claim 5 wherein a given way point is eliminated from the path if there exists a straight line path between adjacent ones of the way or destination points that avoids any obstacle.

8. A method as recited in claim 2 wherein the steerable vehicle is characterized by a constraint on the maneuverability thereof, said defining of a next possible way point including, during each iteration, checking a path to the current source point and a path from the current source point to the next possible way point for compliance with the constraint and modifying the position of the next possible way point to conform to the constraint.

9. A method as recited in claim 8 wherein the iterative process of defining bearing lines and extending bearing lines produces a plurality of paths between the starting and destination points, said method additionally comprising the step of selecting the shortest path between the starting and destination points.

10. A method as recited in claim 9 comprising the additional step of modifying the path to reduce a total length thereof.

11. A method as recited in claim 10 wherein each intermediate way point in a path is moved, in sequence starting from the way point most proximate the destination point, along the bearing thereto until a line from the intermediate way point being moved to one of the next possible way point and destination point becomes tangent an obstacle.

12. A method as recited in claim 10 wherein a given way point is eliminated from the path if there exists a straight line path between the adjacent ones of the way or destination points that avoids any obstacle.

13. A method as recited in claim 10 wherein one of the constraints is a minimum travel distance, said checking and modifying steps extending a range to a next possible way point when a range from the current source point to the next possible way point is less than the minimum travel distance.

14. A method as recited in claim 10 wherein one of the constraints is a turning angle constraint, said modifying step modifying a turning angle from a path to the current source point and the path from the current source point to the next possible way point when that turning angle is fails to meet the turning angle constraint.

15. A method for establishing a route for a missile between a launch point and a destination point that avoids at least one intermediate landmass, said method comprising the steps of:

establishing a data base of landmasses that circumscribe the each landmass within a polygon defined by a plurality of data points;

defining an initial current source point relative to the launch point and a final way point relative to the destination point;

defining, by iterative processing, a plurality of rough paths between the initial current source point and the final way point by;

generating first and second bearing lines from the current source point to first and second tangents of the polygons surrounding each intermediate landmass;

defining a next possible way point relative to the tangent of each bearing line to one of the polygons;

converting each next possible way point to an intermediate way point for the rough path; and

substituting an intermediate way point as the current source point; and

selecting one of the rough paths as the route for the missile between the launching and destination points.

16. A method as recited in claim 15 wherein the missile is characterized by at least one maneuvering constraint and said conversion of each next possible way point to a way point includes the step of modifying the position of next possible way point if the path to the next possible way point fails to meet a maneuvering constraint.

17. A method as recited in claim 16 wherein one of the maneuvering constraints is a minimum travel distance after a turning movement, said modifying step extending a range to a next possible way point when a range from the current source point to the next possible way point is less than the minimum travel distance.

18. A method as recited in claim 16 wherein one of the maneuvering constraints is a turning angle constraint, said modifying step modifying a turning angle from a path to the current source point and the path from the current source point to the next possible way point when that turning angle fails to meet the turning angle constraint.

19. A method as recited in claim 15 wherein said step of defining a next possible way point includes extending the bearing line beyond a corresponding tangent by an incremental distance.

20. A method as recited in claim 19 comprising the additional step of modifying the path to reduce a total length thereof.

21. A method as recited in claim 20 wherein each intermediate way point in a path is moved, in sequence starting from the way point most proximate the destination point, along the bearing thereto until a line from the intermediate way point being moved to the successive one of the way point and destination point becomes tangent an obstacle.

22. A method as recited in claim 20 wherein a given way point is eliminated from the path if there exists a straight line path between adjacent ones of the way and destination points that avoids any obstacles.

23. A method as recited in claim 19 comprising the additional step of reducing the incremental distance if the extended bearing line intersects a polygon.

24. A method as recited in claim 15 wherein the missile is characterized by flight maneuver constraints and said conversion of each next possible way point to a way point includes the step of modifying the position of next possible way point if the path to the next possible way point violates the maneuvering constraint.

25. A method as recited in claim 24 wherein the iterative process of defining way points produces a plurality of rough paths between the initial and final way points, said method additionally comprising the step of selecting the shortest rough path and thereafter modifying the position of each way point if the selected rough path to the way point fails to meet the maneuvering constraints.

26. A method as recited in claim 15 wherein the launch point lies within the polygon around a corresponding landmass and said step of defining the initial current source point includes. the steps of:

defining a shortest path from the launch point to a segment on the polygon; and

incrementally increasing the shortest path to define the initial current source point.

27. A method as recited in claim 15 wherein the destination point lies within the polygon around a corresponding landmass and said step of defining the final way point includes the steps of:

defining a shortest path from the destination point to a segment on the polygon; and

incrementally increasing the shortest path to define the final way point.

28. A method as recited in claim 15 wherein each landmass is further defines by a rectangle circumscribing a polygon, said method additionally testing, during each iteration, whether the destination point lies within the rectangle but outside the polygon associated with a landmass, said method comprising an alternative step for generating the first and second bearing lines to that landmass based upon the relative positions of the current source point, the destination point the corners of the polygon.

29. A method as recited in claim 15 wherein said step of connecting a next possible way point to an intermediate way point includes testing the next possible way point against predetermined criteria.

30. A method as recited in claim 29 wherein said step of connecting a next possible way point to an intermediate way point includes determining whether the total number of way points in the rough path exceeds a maximum.

31. A method as recited in claim 29 wherein said step of connecting a next possible way point to an intermediate way point includes determining whether a distance to the next possible way point from a current source point exceeds a distance from the current source point to the destination point.

32. A method as recited in claim 29 wherein said step of connecting a next possible way point to an intermediate way point includes, after a first rough path exists, whether the sum of a distance from the initial way point to the current source point plus a distance from the current source point to the destination point exceeds the shortest possible path.