Computing route plans for routing around obstacles having spatial and temporal dimensions

• US 9,513,125 B2
• Filed: 11/18/2011
• Issued: 12/06/2016
• Est. Priority Date: 01/14/2008
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Ravenscroft, Donald L.
• Primary Examiner(s): Amin, Bhavesh V
• Application Number:
  US13/300,444
• Publication Number:
  US 20120158280A1
• Time in Patent Office: 1,845 Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G05D 1/106 Change initiated in response to external conditions, e.g. avoidance of elevated terrain or of no-fly zones
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 5/0034 Assembly of a flight plan
• CPC Class Codes: G08G 5/0069 specially adapted for an unmanned aircraft

Abstract

This description provides tools and techniques for computing a route or flight plans for unmanned aerial vehicles (UAVs) or any vehicle while routing around obstacles having spatial and temporal dimensions. Methods provided by these tools may receive data representing destinations to be visited by the UAVs, and may receive data representing obstacles having spatial and temporal dimensions. These methods may also calculate trajectories spatial and temporal dimensions, by which the UAV may travel from one destination to another, and may at least attempt to compute flight plans for the UAVs that incorporate these trajectories. The methods may also determine whether these trajectories intersect any obstacles, and at least attempt to reroute the trajectories around the obstacles. These tools may also provide systems and computer-readable media containing software for performing any of the foregoing methods.

Claims

1. A method for computing a route for a vehicle, the method comprising:

generating, by action of a processor of a flight processing system, a graph of a plurality of destinations to be visited by the vehicle;

determining, by action of the processor, a route through the graph by;

calculating a Hamiltonian circuit for the graph by at least;

defining segments of the route through the graph by;

selecting by action of the processor a first destination and a second destination from among the plurality of destinations;

calculating by action of the processor a trajectory between the first destination and the second destination; and

adding by action of the processor the first destination and the second destination to the route, when the trajectory does not intersect at least one obstacle from among a plurality of obstacles;

determining whether the route is a valid route by action of the processor; and

after determining that the route is a valid route, loading the route into the vehicle sending by action of the flight planning system.

2. The method of claim 1, wherein calculating the trajectory between the first destination and the second destination comprises calculating the trajectory based on a performance model for the vehicle.

3. The method of claim 1, further comprising rerouting around the at least one obstacle, when the trajectory intersects the at least one obstacle.

4. The method of claim 1, further comprising after determining that the route is not a valid route, indicating no route is available.

5. The method of claim 1, wherein determining the route through the graph further comprises:

rejecting one or more segments of the route, when a cost for the route exceeds a specified upper bound.

6. The method of claim 1, further comprising determining by action of the processor a cost for the route based on at least one member selected from the group consisting of:

a weather factor, a wind factor, a traveling time, a speed, an amount of available cargo, an environmental factor, and a carbon output.

7. The method of claim 1, further comprising specifying the plurality of obstacles and the trajectory in at least three dimensions.

8. The method of claim 7, wherein the at least three dimensions comprise a fourth dimension representing time.

9. The method of claim 1, wherein defining the segments of the route comprises defining the segments of the route by executing a traveling salesman algorithm on the graph.

10. The method of claim 1, wherein the vehicle comprises an aircraft, and, wherein the plurality of obstacles comprise one or more of:

an obstacle related to restricted airspace and an obstacle related to weather phenomena.

11. A system for computing a route for a vehicle, the system comprising:

a flight planning system, comprising;

a processor; and

one or more non-transitory computer-readable storage media that include computer-readable instructions that, when executed by the processor, cause the processor to;

generate a graph of a plurality of destinations to be visited by the vehicle;

determine a route through the graph by;

calculating a Hamiltonian circuit for the graph by at least;

defining segments of the route through the graph by;

selecting a first destination and a second destination from among the plurality of destinations;

calculating a trajectory between the first destination and the second destination; and

adding the first destination and the second destination to the route, when the trajectory does not intersect at least one obstacle from among a plurality of obstacles; and

determine whether the route is a valid route; and

after determining that the route is a valid route, loading the route into the vehicle.

12. The system of claim 11, wherein the route definition module is further operable to reroute around the at least one obstacle, when the trajectory intersects the at least one obstacle.

13. The system of claim 11, wherein the route definition module is further operable to reject one or more segments of the route, when a cost for the route exceeds a specified upper bound.

19. The system of claim 11, wherein determining the route through the graph comprises selecting the segments of the route based on a cost of each of the segments.

20. The system of claim 11, wherein determining the route through the graph comprises determining the route by executing a traveling salesman algorithm on the graph.

14. A non-transitory computer-readable storage medium comprising computer-executable instructions for performing a method for computing a route for a vehicle, the method executed by the computer-executable instructions comprising:

generating by action of a processor of a flight processing system, a graph of a plurality of destinations to be visited by the vehicle;

determining a route through the graph by;

calculating a Hamiltonian Circuit of the graph by at least;

defining segments of the route through the graph by action of the processor by;

selecting by action of the processor a first destination and a second destination from among the plurality of destinations;

calculating by action of the processor a trajectory between the first destination and the second destination; and

adding by action of the processor the first destination and the second destination to the route, when the trajectory does not intersect at least one obstacle from among a plurality of obstacles;

determining whether the route is a valid route; and

after determining that the route is a valid route, loading the route into the vehicle.

15. The non-transitory computer-readable storage medium of claim 14, the method executed by the computer-executable instructions further comprising:

after determining that the route is not a valid route, indicating no route is available.

16. The non-transitory computer-readable storage medium of claim 14, the method executed by the computer-executable instructions further comprising, rerouting around the at least one obstacle, when the trajectory intersects the at least one obstacle.

17. The non-transitory computer-readable storage medium of claim 14, wherein determining the route through the graph comprises selecting the segments of the route based on a cost of each of the segments.

18. The non-transitory computer-readable storage medium of claim 17, wherein determining the route through the graph comprises rejecting one or more segments of the route, when a cost of the route exceeds a specified upper bound.