| 摘要 |
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. |
| 主权项 |
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. |
