Advanced optimization framework for air-ground persistent surveillance using unmanned vehicles

• US 8,935,035 B1
• Filed: 12/21/2011
• Issued: 01/13/2015
• Est. Priority Date: 03/31/2011
• 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: Bogdanowicz, Zbigniew, Herc, George
• Primary Examiner(s): Algahaim, Helal A
• Assistant Examiner(s): CASTRO, PAUL A
• Application Number:
  US13/332,493
• Time in Patent Office: 1,119 Days
• Field of Search: None
• US Class Current: 701/26
• CPC Class Codes: G08G 1/20 Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles
• 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

Abstract

An optimization framework for air and ground based persistent surveillance using unmanned vehicles. The objective of the optimization framework is to maximize the coverage of a target area for given UVs, skeleton, and maintenance sites. The optimization framework is based on the generation of mini-cycles, and assigning them in a fractional manner to the given UVs. Subsequently, the optimization framework based on UV-Cross and UV-k-Swap transformations, followed by the cycle of fusion, integerization, and schedule synchronization.

Claims

1. An optimization process for persistent surveillance of a target coverage area, using a plurality of unmanned vehicles, the optimization process comprising:

identifying a skeleton, wherein said skeleton is a directed balanced graph, which skeleton includes a plurality of nodes, where each of said plurality of nodes corresponds to a waypoint, wherein the plurality of nodes are interconnected by a plurality of links, wherein each of said plurality of links is a directed leg;

wherein the skeleton characterizes the loitering pattern of the unmanned vehicles;

wherein each link has two ends, wherein a one end is an input to a node, and a second end is an output from a node;

wherein any of the plurality of nodes has, connected to it, a number of inputs to the node which are equal to a number of outputs from the node;

generating a plurality of mini-cycles that, individually, selectively cover at least some of the links and at least some of the nodes for the target coverage area, and which mini-cycles, in aggregate, cover all of the links, and all of the nodes for the target coverage area, using the skeleton;

assigning the plurality of unmanned vehicles to the generated mini-cycles;

iteratively transforming the generated mini-cycles into an derived cycles, and transforming said derived cycles into new said derived cycles, with assigned unmanned vehicles, by using UV-Cross transformation to split said mini cycles or said derived cycles, to obtain two smaller derived cycles, and also by using UV-k-Swap transformation;

wherein said UV-Cross transformation includes the following steps;

wherein link ends which are connected to a cross point node comprise inputs to a node A1 and A2, and outputs from a node B1 and B2;

wherein, where A1 had been assigned B2, B1 had been assigned to A2;

transforming the assignments so that A1 is now assigned to A2, and B1 is now assigned to B2;

wherein said UV-k-Swap transformation includes the following steps;

wherein a at least two mini cycles or derived cycles cross at at least two nodes;

simultaneously using a UV-Cross transformation on each of the nodes such that said the at least two mini cycles or derived cycles exchange at least one link;

fusing the derived cycles, using UV-Cross transformations, such that the derived cycles are fused into an fuzed derived cycles, with weights distributed to the assigned unmanned vehicles;

wherein the fusing of derived cycles preserves the sum of the distributed weights;

integerizing the distributed weights;

wherein integerizing the distributed weights preserves the sum of the distributed weights;

whereby said integerizing the distributed weights includes the following steps;

wherein m is an integer which represents a given number of unmanned vehicles;

wherein k is the number of fuzed derived cycles;

wherein ri1, ri2, . . . rik are real numbers, corresponding to said distributed weights, assigned respectively, to said k fuzed derived cycles;

wherein before integerization, ri1+ri2+ . . . +rik=m;

replacing said ri1, ri2, . . . , rik real number distributed weights with an integral assignments which correspond to an rounded integer values, but where rounding is modified so that, after rounding, the condition ri1+ri2+ . . . +rik=m remains true, and;

synchronizing the loitering schedule of the plurality of unmanned vehicles to maximize the surveillance of the target coverage area.

2. The optimization process according to claim 1, wherein the plurality of unmanned vehicles include unmanned aerial vehicles.

3. The optimization process according to claim 1, wherein the plurality of unmanned vehicles include unmanned ground vehicles.

4. The optimization process according to claim 1, wherein the plurality of unmanned vehicles include a combination of unmanned aerial vehicles and unmanned ground vehicles.

5. The optimization process according to claim 1, wherein the persistent surveillance includes an aerial loitering pattern.

6. The optimization process according to claim 1, wherein the persistent surveillance includes a ground loitering pattern.

7. The optimization process according to claim 1, wherein the plurality of mini-cycles include cycles with shortest links.

8. The optimization process according to claim 1, wherein assigning the plurality of unmanned vehicles to the generated mini-cycles includes assigning unmanned vehicles of the same type.

9. The optimization process according to claim 1, wherein using the UV-k-Swap transformation includes iteratively continuing the UV-k-Swap transformation until UV-k-Swaps have been exhausted.

10. The optimization process according to claim 1, wherein using the UV-k-Swap transformation includes iteratively continuing the UV-k-Swap transformation until a determination is made that the UV-k-Swap transformation has exceeded a predetermined length threshold.

11. The optimization process according to claim 1, wherein using the UV-Cross transformation includes iteratively continuing the UV-Cross transformation until all crosses are exhausted.