Computing Flight Plans for UAVs While Routing Around Obstacles Having Spatial and Temporal Dimensions

• US 20090210109A1
• Filed: 01/14/2008
• Published: 08/20/2009
• Est. Priority Date: 01/14/2008
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Ravenscroft, Donald Lewis
• Granted Patent: US 8,082,102 B2
• Time in Patent Office: Days
• US Class Current: 701/26
• 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: G08G 5/0034 Assembly of a flight plan
• CPC Class Codes: G08G 5/006 in accordance with predefined flight zones, e.g. to avoid prohibited zones
• CPC Class Codes: G08G 5/0069 specially adapted for an unmanned aircraft

Abstract

This description provides tools and techniques for computing flight plans for unmanned aerial vehicles (UAVs) 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 computer-based method for computing flight plans for unmanned aerial vehicles (UAVs) while rerouting around obstacles, comprising:

receiving data representing a plurality of destinations to be visited by at least one of the UAVs;

receiving data representing a plurality of obstacles, wherein the obstacles are defined in at least three dimensions;

calculating at least one trajectory by which the UAV may travel from a first destination to a second destination, wherein the trajectory is specified in at least three dimensions;

attempting to compute at least one flight plan for the UAV that incorporates at least the trajectory; and

determining whether the trajectory intersects any of the obstacles.

2. The computer-based method of claim 1, further comprising attempting to reroute the trajectory around at least one of the obstacles.

3. The computer-based method of claim 1, further comprising calculating at least a further trajectory by which the UAV may travel from the second destination to at least a further destination, and wherein attempting to compute at least one flight plan includes incorporating at least the further trajectory into the flight plan.

4. The computer-based method of claim 3, further comprising determining whether the further trajectory intersects any of the obstacles, and further comprising attempting to reroute the further trajectory around at least one of the obstacles.

5. The computer-based method of claim 3, further comprising calculating respective costs associated with the trajectory and the further trajectory, and further comprising calculating a total cost of the flight plan as a sum of the respective costs associated with the trajectories.

6. The computer-based method of claim 1, further comprising generating a graph representation of the destinations, and wherein computing a flight plan includes executing a traveling salesman algorithm on the graph representation.

7. The computer-based method of claim 1, further comprising rerouting the trajectory around at least one of the obstacles, and further comprising updating the flight plan to incorporate the rerouted trajectory.

8. The computer-based method of claim 1, wherein receiving data representing a plurality of obstacles includes receiving data representing obstacles that are defined in three spatial dimensions, and that are defined in a fourth dimension representing time.

9. The computer-based method of claim 1, wherein receiving data representing a plurality of obstacles includes receiving volumetric data representing restricted airspace.

10. The computer-based method of claim 1, wherein receiving data representing a plurality of obstacles includes receiving volumetric data representing weather phenomena.

11. The computer-based method of claim 1, further comprising determining that the flight plan is not feasible, and further comprising reporting that the flight plan is not available.

12. At least one computer-readable storage medium having computer-executable instructions stored thereon that, when executed by a computer, cause the computer to perform the method of claim 1.

13. A flight planning system incorporating at least the computer-readable storage medium of claim 12.

14. A computer-based system for computing flight plans for UAVs while rerouting around obstacles, the system comprising:

at least one aircraft performance database for storing data representing respective performance capabilities of a plurality of different aircraft, wherein at least some of the aircraft include UAVs;

an aircraft performance module adapted to receive the aircraft performance data from the aircraft performance database;

a destination database storing at least coordinate information for a plurality of destinations to be visited by at least one of the UAVs;

a route computation module for receiving from the destination database coordinate information for the destinations, and for computing at least one flight plan, based on the coordinate information, by which the UAV visits the destinations;

a cost module for receiving from the destination database coordinate information for the destinations, and for cooperating with the route computation module to calculate costs associated with respective segments of the flight plan;

a trajectory module for cooperating with the aircraft performance module and the cost module to calculate respective trajectories by which the UAV may travel the segments;

at least one obstacle database for storing data representing a plurality of obstacles, wherein the obstacle database is for representing the obstacles using at least three-dimensional coordinate data;

an obstacle detection module for receiving obstacle data from the obstacle database, and for determining whether the trajectory intersects any of the obstacles;

a reroute module for receiving obstacle data from the obstacle database, and for rerouting the trajectory around any obstacles intersected by the trajectory; and

an aeronautical database for containing data representing a plurality of aeronautical features, wherein the reroute module, the obstacle detection module, and the trajectory module are adapted to receive inputs from the aeronautical database.

15. The computer-based system of claim 14, wherein the obstacle database contains data representing the obstacles in three spatial dimensions and in a fourth dimension representing time.

16. The computer-based system of claim 14, wherein the obstacle database is adapted to receive updated obstacle information dynamically over time.

17. The computer-based system of claim 14, wherein the reroute module is adapted to reroute the trajectory by changing the altitude of the trajectory or by changing the trajectory laterally.

18. The computer-based system of claim 14, as incorporated into a ground-based flight planning system.

19. The computer-based system of claim 14, as incorporated into at least one of the UAVs.

20. The computer-based system of claim 14, wherein the route computation module is for determining that the flight plan is not feasible, and for reporting that the flight plan is not available.