Computing flight plans for UAVs while routing around obstacles having spatial and temporal dimensions

• US 8,082,102 B2
• Filed: 01/14/2008
• Issued: 12/20/2011
• Est. Priority Date: 01/14/2008
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Ravenscroft, Donald Lewis
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): MOYER, DALE S
• Application Number:
  US12/013,582
• Publication Number:
  US 20090210109A1
• Time in Patent Office: 1,436 Days
• Field of Search: 701 2- 3, 701/16, 701/23, 701/26, 701/206, 701/301
• US Class Current: 701/301
• 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, the computer-based method comprising:

receiving data representing a plurality of destinations to be visited by a UAV;

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

calculating, using a processor, a trajectory for the UAV, wherein the trajectory comprises at least two of the plurality of destinations and the trajectory is specified in at least three dimensions;

computing an initial flight plan for the UAV that incorporates at least the trajectory;

calculating an initial cost associated with the initial flight plan;

determining whether the trajectory intersects at least one of the plurality of obstacles;

when the trajectory intersects at least one of the plurality of obstacles,

computing an altered flight plan for the UAV, the altered flight plan incorporating an altered trajectory that avoids the at least one of the plurality of obstacles,

calculating an altered cost associated with the altered flight plan,

determining whether the altered cost exceeds a specified upper bound,

altered cost exceeds the specified upper bound,

computing a final flight plan for the UAV, the final flight plan incorporating a final trajectory that avoids the at least one of the plurality of obstacles,

calculating a final cost associated with the final flight plan, the final cost being less than the altered cost, and

selecting the final flight plan; and

when the altered cost does not exceed the specified upper bound,

selecting the altered flight plan; and

when the trajectory does not intersect at least one of the plurality of obstacles, selecting the initial flight plan.

2. The computer-based method of claim 1, further comprising generating a graph representation of the plurality of destinations, and wherein computing the initial flight plan, computing the altered flight plan, and computing the final flight plan each respectively includes executing a traveling salesman algorithm on the graph representation, the traveling salesman algorithm considering a weather factor in computing, respectively, the initial cost, the altered cost, and the final cost.

3. The computer-based method of claim 1, wherein receiving data representing the 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.

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

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

6. The computer-based method of claim 1, further comprising determining that at least one of the initial flight plan, the altered flight plan, and the final flight plan is not feasible, and reporting that at least one of the initial flight plan, the altered flight plan, and the final flight plan is not available.

7. A computer-based system for computing flight plans for unmanned aerial vehicles (UAVs) while rerouting around obstacles, the system comprising:

a processor;

a memory in communication with the processor, the memory comprising computer executable instruction which, when executed by the processor, cause the processor to

receive data representing a plurality of destinations to be visited by a UAV;

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

calculate a trajectory for the UAV, wherein the trajectory comprises the UAV visiting at least two of the plurality of destinations and the trajectory is specified in at least three dimensions;

compute an initial flight plan for the UAV that incorporates at least the trajectory;

calculate an initial cost associated with the initial flight plan;

determine whether the trajectory intersects at least one of the plurality of obstacles;

when the trajectory intersects at least one of the plurality of obstacles,

compute an altered flight plan for the UAV, the altered flight plan incorporating an altered trajectory that avoids the at least one of the plurality of obstacles,

calculate an altered cost associated with the altered flight plan,

determine whether the altered cost exceeds a specified upper bound,

altered cost exceeds the specified upper bound,

compute a final flight plan for the UAV, the final flight plan incorporating a final trajectory that avoids the at least one of the plurality of obstacles,

calculate a final cost associated with the final flight plan, the final cost being less than the altered cost, and

select the final flight plan, and

when the altered cost does not exceed the specified upper bound,

select the altered flight plan; and

when the trajectory does not intersect at least one of the plurality of obstacles, select the initial flight plan.

8. The computer-based system of claim 7, wherein the data representing the plurality of obstacles is defined in three spatial dimensions and in a fourth dimension representing time.

9. The computer-based system of claim 7, wherein the memory further comprises instructions which, when executed by the processor, cause the processor to updated obstacle data dynamically over time.

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

11. The computer-based system of claim 7, as incorporated into the UAV.

12. The computer-based system of claim 7, wherein the data representing the plurality of obstacles includes volumetric data representing restricted airspace.

13. The computer-based system of claim 7, wherein the data representing the plurality of obstacles include volumetric data representing weather phenomena.

14. The computer-based system of claim 7, wherein the memory further comprises instructions which, when executed by the processor, cause the processor to generate a graph representation of the plurality of destinations, and wherein the instructions to compute the initial flight plan, compute the altered flight plan, and compute the final flight plan include, respectively, instructions to execute a traveling salesman algorithm on the graph representation, the traveling salesman algorithm considering a weather factor in computing, respectively, the initial cost, the altered cost, and the final cost.

15. The computer-based system of claim 7, wherein the memory further comprises instructions which, when executed by the processor, cause the processor to determine that at least one of the initial flight plan, the altered flight plan, and the final flight plan is not feasible, and reporting that at least one of the initial flight plan, the altered flight plan, and the final flight plan is not available.

16. A computer-readable storage medium having computer-executable instructions stored thereon that, when executed by a computer, cause the computer to:

receive data representing a plurality of destinations to be visited by an unmanned aerial vehicle (UAV);

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

calculate a trajectory for the UAV, wherein the trajectory comprises the UAV visiting at least two of the plurality of destinations and the trajectory is specified in at least three dimensions;

compute an initial flight plan for the UAV that incorporates at least the trajectory;

calculate an initial cost associated with the initial flight plan;

determine whether the trajectory intersects at least one of the plurality of obstacles;

when the trajectory intersects at least one of the plurality of obstacles,

compute an altered flight plan for the UAV, the altered flight plan incorporating an altered trajectory that avoids the at least one of the plurality of obstacles,

calculate an altered cost associated with the altered flight plan,

determine whether the altered cost exceeds a specified upper bound,

if the altered cost exceeds the specified upper bound,

compute a final flight plan for the UAV, the final flight plan incorporating a final trajectory that avoids the at least one of the plurality of obstacles,

calculate a final cost associated with the final flight plan, the final cost being less than the altered cost, and

select the final flight plan, and

when the altered cost does not exceed the specified upper bound,

select the altered flight plan; and

when the trajectory does not intersect at least one of the plurality of obstacles, select the initial flight plan.

17. The computer-readable storage medium of claim 16, further having instructions to generate a graph representation of the plurality of destinations, and wherein the instructions to compute the initial flight plan, compute the altered flight plan, and compute the final flight plan include, respectively, instructions to execute a traveling salesman algorithm on the graph representation, the traveling salesman algorithm considering a weather factor in computing, respectively, the initial cost, the altered cost, and the final cost.

18. The computer-readable storage medium of claim 16, further having instructions to determine that at least one of the initial flight plan, the altered flight plan, and the final flight plan is not feasible, and report that at least one of the initial flight plan, the altered flight plan, and the final flight plan is not available.

19. The computer-readable storage medium of claim 16, wherein the data representing the plurality of obstacles includes volumetric data representing restricted airspace.

20. The computer-readable storage medium of claim 16, wherein the data representing the plurality of obstacles includes volumetric data representing weather phenomena.