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

• US 9,599,994 B1
• Filed: 08/03/2015
• Issued: 03/21/2017
• Est. Priority Date: 08/03/2015
• Status: Active Grant

• Current Assignee: United States Secretary of the Army
• Original Assignee: The United States Of America As Represented By The Secretary Of The Army
• Inventors: Patel, Ketula, Bogdanowicz, Zbigniew
• Primary Examiner(s): Figueroa, Jaime
• Application Number:
  US14/816,653
• Time in Patent Office: 596 Days
• Field of Search: 701/1, 701/3
• US Class Current: 1/1
• CPC Class Codes: B64U 2101/30 for imaging, photography or videography
• CPC Class Codes: B64U 2201/00 UAVs characterised by their flight controls
• CPC Class Codes: B64U 2201/102 adapted for flying in formations
• CPC Class Codes: G05D 1/104 involving a plurality of aircrafts, e.g. formation flying traffic control systems for aircraft G08G5/00
• CPC Class Codes: G08G 5/0034 Assembly of a flight plan
• CPC Class Codes: G08G 5/0043 Traffic management of multiple aircrafts from the ground G08G5/003 takes precedence; data processing specially designed for resource management, e.g. scheduling or allocating time, human or machine resources G06Q10/06
• CPC Class Codes: G08G 5/0069 specially adapted for an unmanned aircraft
• CPC Class Codes: G08G 5/0082 for monitoring traffic from a ground station radar or analogous systems specially adapted for traffic control G01S13/91
• CPC Class Codes: G08G 5/045 Navigation or guidance aids, e.g. determination of anti-collision manoeuvers radar or analogous systems specially adapted for anti-collision between aircraft G01S13/933

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.

Claims

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.