COMPUTING ROUTE PLANS FOR ROUTING AROUND OBSTACLES HAVING SPATIAL AND TEMPORAL DIMENSIONS

• US 20120158280A1
• Filed: 11/18/2011
• Published: 06/21/2012
• Est. Priority Date: 01/14/2008
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Ravenscroft, Donald L.
• Granted Patent: US 9,513,125 B2
• Time in Patent Office: Days
• US Class Current: 701/400
• 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 a graph of a plurality of destinations to be visited by a vehicle;

defining segments of a route through the graph by;

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

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

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

defining the route through the graph by defining segments from a starting destination until all of the destinations are part of the route.

2. The method of claim 1, further comprising omitting the first destination and the second destination from the route, when the trajectory intersects the at least one obstacle.

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 indicating no route is available, when the route cannot be defined through the graph.

5. The method of claim 1, further comprising selecting segments of the route based on a cost of each of the segments.

6. The method of claim 5, further comprising rejecting segments of the route, when the cost exceeds a specified upper bound.

7. The method of claim 5, wherein the cost comprises 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.

8. The method of claim 1, wherein the obstacles and the trajectory are specified in at least three dimensions.

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

10. The method of claim 1, where in the step of defining segments of the route through the graph comprises calculating a Hamiltonian Circuit for the graph.

11. The method of claim 1, wherein the vehicle is an aircraft, and the obstacles comprise at least one member selected from the group consisting of:

volumetric data representing restricted airspace, and volumetric data representing weather phenomena.

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

a graph generation module operable to generate a graph of a plurality of destinations to be visited by a vehicle;

a route definition module operable to;

define segments of a route through the graph by;

selecting a first destination and a second destination from among the 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

define the route through the graph by defining segments from a starting destination until all of the destinations are part of the route.

13. The system of claim 12, 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.

14. The system of claim 12, wherein the route definition module is further operable to select segments of the route based on a cost of each of the segments.

15. The system of claim 14, wherein the route definition module is further operable to reject segments of the route, when the cost exceeds a specified upper bound.

16. A 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 a graph of a plurality of destinations to be visited by a vehicle;

defining segments of a route through the graph by;

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

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

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

defining the route through the graph by defining segments from a starting destination until all of the destinations are part of the route.

17. The computer-readable storage medium of claim 16, the method executed by the computer-executable instructions further comprising omitting the first destination and the second destination from the route, when the trajectory intersects the at least one obstacle.

18. The computer-readable storage medium of claim 16, 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.

19. The computer-readable storage medium of claim 16, the method executed by the computer-executable instructions further comprising, selecting segments of the route based on a cost of each of the segments.

20. The computer-readable storage medium of claim 19, the method executed by the computer-executable instructions further comprising rejecting segments of the route, when the cost exceeds a specified upper bound.