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

Patent metadata

Field	Value
Publication number	US-9513125-B2
Application number	US-201113300444-A
Country	US
Kind code	B2
Filing date	Nov 18, 2011
Priority date	Jan 14, 2008
Publication date	Dec 6, 2016
Grant date	Dec 6, 2016

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.

First claim

The invention claimed is:

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.

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.

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.

Assignees

• Ravenscroft Donald L
• Boeing Co

Inventors

• Ravenscroft Donald L

Classifications

• G08G5/57

  for unmanned aircraft · CPC title

• G08G5/55

  for a single aircraft · CPC title

• G08G5/32

  for flight plan preparation · CPC title

• G05D1/106

  Change initiated in response to external conditions, e.g. avoidance of elevated terrain or of no-fly zones · CPC title

• G01C21/005 Primary

  with correlation of navigation data from several sources, e.g. map or contour matching (G01C21/30 takes precedence) · CPC title