Collisionless flying of unmanned aerial vehicles that maximizes coverage of predetermined region

Patent metadata

Field	Value
Publication number	US-9599994-B1
Application number	US-201514816653-A
Country	US
Kind code	B1
Filing date	Aug 3, 2015
Priority date	Aug 3, 2015
Publication date	Mar 21, 2017
Grant date	Mar 21, 2017

Abstract

Collisionless flight is achieved by overlaying a circulant digraph with certain characteristics over a model of the area to be flown. Each UAV then executes a flight path corresponding to a directed cycle of the circulant digraph where each vertex of the circulant digraph corresponds to two waypoints. The circulant digraph includes more vertices than the number of unmanned aerial vehicles and the number of vertices is divisible by the number of UAVs. Additionally, the circulant digraph has a first jump of 1, a second jump of one less than then number of UAVs. To maximize coverage, each of the vertices of the circulant digraph may then be individually updated such that they satisfy two tests: a convexity test and an isosceles avoidance test. The updated flight path of each UAV may then be relayed from a control station to each UAV.

First claim

We claim:

1. A method for ensuring collisionless flight of three or more unmanned aerial vehicles over an area, wherein the method comprises the steps of:
constructing a circulant digraph representing a portion of the area, wherein the circulant digraph comprises
a number of vertices such that the number of vertices is greater than the number of unmanned aerial vehicles and the number of vertices is divisible by the number of unmanned aerial vehicles and wherein each vertex represents two waypoints at differing altitudes,
a first jump size of one,
a second jump size of one less than the number of unmanned aerial vehicles, and
an independent directed cycle for each of the three or more unmanned aerial vehicles; and

assigning each of the three or more unmanned aerial vehicles a flight path corresponding to an independent directed cycle of the circulant digraph.

2. The method of claim 1 wherein the flight path for each unmanned aerial vehicle comprises a starting waypoint and two or more subsequent waypoints alternating between the first jump size and the second jump size.

3. The method of claim 2 wherein the starting waypoint of each flight path is at a first altitude and the two or more subsequent waypoints of the flight path alternate between a second altitude and the first altitude.

4. The method of claim 1 further comprising the step of assigning a waypoint to a maintenance point outside of the circulant digraph.

5. The method of claim 4 further comprising the steps of:
assigning a unique vertex ID to each vertex and the maintenance point; and
assigning a unique unmanned aerial vehicle ID to each unmanned aerial vehicle.

6. The method of claim 4 further comprising the step of:
flying each unmanned aerial vehicle from the maintenance point to the starting waypoint of its respective flight path.

7. The method of claim 1 further comprising the steps of:
constructing an updated digraph by modifying one or more vertices of the circulant digraph; and
updating the flight path of the three or more unmanned aerial vehicles according to the modified one or more vertices.

8. The method of claim 7 further comprising the step of performing a convexity test on the updated digraph.

9. The method of claim 7 further comprising the step of performing an isosceles avoidance test on the updated digraph.

10. The method of claim 7 wherein the step of updating the flight path of the unmanned aerial vehicles according to the modified one or more vertices further comprises the step of returning each unmanned aerial vehicle to the maintenance point.

11. A system for ensuring collisionless flight of three or more unmanned aerial vehicles over an area comprising
three or more unmanned vehicles, wherein each of the three or more unmanned vehicles is assigned a flight path corresponding to an independent directed cycle of a circulant digraph representing a portion of the area and wherein the circulant digraph further comprises:
a number of vertices such that the number of vertices is greater than the number of unmanned aerial vehicles and the number of vertices is divisible by the number of unmanned aerial vehicles and wherein each vertex represents two waypoints;
a first jump size of one; and
a second jump size of one less than then number of unmanned aerial vehicles.

12. The system of claim 11 wherein each of the three or more unmanned aerial vehicles comprises a central processing unit, a memory and a location sensor.

13. The system of claim 11 wherein each of the three or more unmanned aerial vehicles comprises a communication interface configured for receiving information comprising updated waypoints.

14. The system of claim 11 further comprising a maintenance point and wherein each flight path of the three or more unmanned aerial vehicles begins and ends at the maintenance point.

15. The system of claim 11 wherein the each vertex of the circulant digraph corresponds to a waypoint at a first altitude and a waypoint at a second altitude and each flight path of the three or more unmanned aerial vehicles comprises waypoints alternating between the first altitude and the second altitude.

16. The system of claim 11 further comprising a control station comprising a graphic user interface configured for displaying a representation of the circulant digraph over the area and receiving information for updating one or more vertices of the digraph.

17. The system of claim 16 wherein the control station is further configured for performing a convexity test on an updated digraph.

18. The system of claim 16 wherein the control station is further configured for performing an isosceles avoidance test on an updated digraph.

19. The system of claim 11 wherein each of the unmanned aerial vehicles further comprises a sensor element configured for sensing one or more characteristics of the portion of the area of interest.

20. The system of claim 19 wherein the sensor element is an infrared image sensor configured for sensing infrared radiation of the portion of the area of interest.

Assignees

• Bogdanowicz Zbigniew
• Patel Ketula
• Us Army

Inventors

• Bogdanowicz Zbigniew
• Patel Ketula

Classifications

• B64U2201/102

  adapted for flying in formations · CPC title

• B64D47/08

  Arrangements of cameras · CPC title

• G08G5/0043

  Physics · mapped topic

• G08G5/0034

  Physics · mapped topic

• B64C39/024

  of the remote controlled vehicle type, i.e. RPV · CPC title