Generating a mission plan for capturing aerial images with an unmanned aerial vehicle

• US 9,508,263 B1
• Filed: 10/20/2015
• Issued: 11/29/2016
• Est. Priority Date: 10/20/2015
• Status: Active Grant

• Current Assignee: Skycatch, Inc.
• Original Assignee: Skycatch, Inc.
• Inventors: Teng, Yifei, Stuart, Patrick, Chen, David
• Primary Examiner(s): Sample, Jonathan L
• Application Number:
  US14/887,954
• Time in Patent Office: 406 Days
• US Class Current: 1/1
• CPC Class Codes: B64C 39/024 of the remote controlled vehicle type, i.e. RPV
• CPC Class Codes: B64U 10/14 with four distinct rotor axes, e.g. quadcopters
• CPC Class Codes: B64U 2101/30 for imaging, photography or videography
• CPC Class Codes: G05D 1/0094 involving pointing a payload, e.g. camera, weapon, sensor, towards a fixed or moving target
• CPC Class Codes: G05D 1/0202 specially adapted to aircraft
• 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
• CPC Class Codes: G08G 5/0086 for monitoring terrain radar or analogous systems specially adapted for terrain avoidance G01S13/935

Abstract

Systems and methods are disclosed for generating a digital flight path within complex mission boundaries. In particular, in one or more embodiments, systems and methods generate flight legs that traverse a target site within mission boundaries. Moreover, one or more embodiments include systems and methods that utilize linking algorithms to connect the generated flight legs into a flight path. Moreover, one or more embodiments include systems and methods that generate a mission plan based on the flight path. In one or more embodiments, the generated mission plan enables a UAV to traverse a flight area within mission boundaries and capture aerial images with regard to the target site.

Claims

1. A computer-implemented method comprising:

identifying a mission boundary defining a UAV flight area from a prohibited UAV flight area, the mission boundary encompassing a target site for capturing a plurality of aerial images by a UAV;

generating, by at least one processor, flight legs within the UAV flight area and excluding the prohibited flight area, the flight legs being separated by a leg spacing based on one or more characteristics of the UAV, and each flight leg intersecting the mission boundary at two endpoints;

identifying flight vertices, the flight vertices comprising corners of the mission boundary and the endpoints for each of the flight legs;

building, by the at least one processor, a flight path within the UAV flight area and avoiding the prohibited UAV flight area by combining the flight legs utilizing the flight vertices, wherein the flight path does not extend beyond the mission boundary; and

generating a mission plan based on the flight path, the mission plan comprising computer-executable instructions for causing the UAV to capture aerial images of the target site in accordance with the flight path without entering the prohibited flight area.

2. The method of claim 1, wherein identifying a mission boundary defining a UAV flight area comprises:

accessing digital flight area information, the digital flight area information comprising at least one of;

a digital flight zone, a digital property boundary, a digital aerial image, or a digital survey; and

transforming the digital flight area information to at least a portion of the mission boundary.

3. The method of claim 1, wherein generating flight legs further comprises:

generating each flight leg at a flight angle; and

calculating the flight angle applicable to the flight legs such that the angle maximizes an average length of the flight legs.

4. The method of claim 1, wherein building the flight path further comprises:

calculating a plurality of shortest connections by;

for a plurality of pairs of the endpoints, calculating the shortest connection within the UAV flight area between each pair of endpoints.

5. The method of claim 4, further comprising:

determining that the mission boundary is concave; and

based on the determination that the mission boundary is concave, building a flight path by applying

a cheapest-edge linking algorithm that utilizes the flight legs and the plurality of shortest connections to combine flight legs based on a determination of the shortest connection available between unused flight leg endpoints that does not create a cycle or a three-degree vertex.

6. The method of claim 4, further comprising:

determining that the mission boundary is convex; and

based on the determination that the mission boundary is convex, building a flight path by applying a nearest-neighbor linking algorithm that utilizes the flight legs and the plurality of shortest connections to combine a second flight leg to an initial flight leg based on a determination that the second flight leg and the initial flight leg are closest in proximity.

7. The method of claim 1, wherein the one or more characteristics of the UAV comprises at least one of the following:

a resolution of a camera affixed to the UAV, a resolution of images resulting from use of the camera, a lens angle of the camera, a width of images resulting from use of the camera, or a maximum flight altitude of the UAV.

8. The method of claim 1, wherein generating a mission plan further comprises:

identifying digital elevation data with regard to the target site; and

defining UAV flight altitudes within the mission plan based on the digital elevation data and the one or more characteristics of the UAV.

9. The method of claim 8, wherein identifying elevation data comprises:

capturing a plurality of aerial images of the target site utilizing a UAV; and

calculating elevation data with regard to the target site based on the plurality of aerial images.

10. The method of claim 8, wherein identifying elevation data comprises:

accessing a digital image, the digital image comprising elevation data transformed into RGB values within the digital image; and

transforming a plurality of the RGB values into elevation data.

11. The method of claim 1, further comprising:

identifying an obstacle, the obstacle corresponding to an obstacle elevation; and

wherein building a mission plan further comprises;

creating a first waypoint at a first altitude, the first altitude lower than the obstacle elevation;

creating a second waypoint at a second altitude, the second waypoint higher than the obstacle elevation; and

adding the first waypoint and the second waypoint to the mission plan such that the first waypoint and the second waypoint correspond to a location of the obstacle.

12. A system comprising:

at least one processor; and

at least one non-transitory computer readable storage medium storing instructions thereon that, when executed by the at least one processor, cause the system to;

identify a mission boundary defining a UAV flight area from a prohibited UAV flight area, the mission boundary encompassing a target site for capturing a plurality of aerial images by a UAV;

generate flight legs within the UAV flight area and excluding the prohibited flight areas, the flight legs being separated by a leg spacing based on one or more characteristics of the UAV, and each flight leg intersecting the mission boundary at two endpoints;

build a flight path within the UAV flight area and avoiding the prohibited UAV flight area by combining the flight legs utilizing flight vertices, wherein the flight path does not extend beyond the mission boundary; and

generate a mission plan based on the flight path, the mission plan comprising computer-executable instructions for causing the UAV to capture aerial images of the target site in accordance with the flight path without entering the prohibited flight area.

13. The system of claim 12, further comprising instructions that, when executed by the at least one processor, cause the system to:

calculate a plurality of shortest connections by;

for a plurality of pairs of the endpoints, calculating the shortest connection within the UAV flight area between each pair of endpoints.

14. The system of claim 12, wherein building a flight path further comprises:

identifying digital elevation data with regard to the target site by;

capturing a plurality of aerial images of the target site utilizing a UAV; and

calculating elevation data with regard to the target site based on the plurality of aerial images; and

defining UAV flight altitude within the mission plan based on the elevation data and the one or more characteristics of the UAV.

15. The system of claim 13, further comprising instructions that, when executed by the at least one processor, cause the system to:

determine that the mission boundary is concave; and

based on the determination that the mission boundary is concave, build a flight path by applying a cheapest-edge linking algorithm that utilizes the flight legs and the plurality of shortest connections to combine flight legs based on a determination of the shortest connection available between unused flight leg endpoints that does not create a cycle or a three-degree vertex.

16. A computer-implemented method comprising:

identifying a first mission boundary defining a UAV flight area and a second mission boundary defining a second UAV flight area;

generating, by at least one processor, first flight legs for the first UAV flight area, the first flight legs contained within the first UAV flight area;

generating, by the at least one processor, second flights legs for the second UAV flight area, the second flights legs contained within the second UAV flight area;

determining that the first mission boundary is convex;

determining that the second mission boundary is concave;

based on the determination that the first mission boundary is convex, building a first flight path by applying a first flight leg linking algorithm to the first flight legs; and

based on the determination that the second mission boundary is concave, building a second flight path by applying a second flight leg linking algorithm different from the first flight leg linking algorithm to the second flight legs.

17. The method of claim 16, wherein each flight leg of the first flight legs intersects the mission boundary at two endpoints and further comprising:

calculating, utilizing a Floyd-Warshall algorithm, the shortest connections within the UAV flight area between a plurality of endpoints.

18. The method of claim 17, wherein building the first flight path by applying the first flight leg linking algorithm comprises:

identifying a starting point comprising a first endpoint corresponding to an initial flight leg, the initial flight leg having both the first endpoint and a second endpoint;

identifying a third endpoint corresponding to a second flight leg, the third endpoint being closest to the second endpoint of the initial flight leg along a first shortest connection from the shortest connections within the permissible UAV flight area; and

building the first flight path by combining the first flight leg, the first shortest connection, and the second flight leg.

19. The method of claim 18, wherein building the first flight path by applying the first flight leg linking algorithm further comprises:

identifying a plurality of additional starting points, each additional starting point comprising a different endpoint;

building a plurality of additional flight paths based on the plurality of additional starting points; and

selecting the first flight path based on a comparison between the length of the first flight path and the length of each additional flight path.

20. The method of claim 16, wherein building the second flight path by applying the second flight leg linking algorithm different from the first flight leg linking algorithm comprises:

adding each flight leg to the second flight path;

identifying the shortest connection from the calculated shortest connections within the UAV flight area between the plurality of the endpoints;

adding the identified shortest connection to the second flight path;

identifying the next shortest connection from the remaining shortest connections within the permissible UAV flight area between a plurality of the endpoints; and

based upon a determination that adding the next shortest connection to the second flight path does not create a cycle and does not result in a three-degree vertex, adding the next shortest connection to the second flight path.