ROUTE PLANNER WITH AREA AVOIDANCE CAPABILITY

• US 20020183922A1
• Filed: 06/05/2001
• Published: 12/05/2002
• Est. Priority Date: 06/05/2001
• Status: Active Grant

• 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.
• Granted Patent: US 6,529,821 B2
• Time in Patent Office: Days
• 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 from the current source point to first and second tangents of each obstacle;

extending each of the bearing lines an incremental distance beyond its tangent with the obstacle to define a next possible way point; 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 its maneuverability, said testing of a next possible way point including, during each iteration, checking the path to the current source point and the 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 thereby to define the way point.

5. A method as recited in claim 3 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 its maneuverability, said testing of a next possible way point including, during each iteration, checking the path to the current source point and the 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 thereby to define the way point.

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 the 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 the successive one of the 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 testing and modifying steps extending the range of a next possible way point when the 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 the 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.

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 the range of a next possible way point when the 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 the 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 beyond its tangent by an incremental distance.

20. A method as recited in claim 19 comprising the additional step of modifying the path to reduce the 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 12 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 a polygon around a 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 a polygon around a 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 the distance to the next possible way point from a current source point exceeds the 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 distance from the initial way point to the current source point plus the distance from the current source point to the destination point exceeds the shortest possible path.

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 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 a polygon;

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

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.