Adaptive multi-vehicle area coverage optimization system and method

• US 8,260,485 B1
• Filed: 09/18/2007
• Issued: 09/04/2012
• Est. Priority Date: 04/26/2007
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Vian, John L., Saad, Emad W., Wunsch, Donald C., Meuth, Ryan J.
• Primary Examiner(s): Trammell, James
• Assistant Examiner(s): Shafi, Muhammad
• Application Number:
  US11/857,217
• Time in Patent Office: 1,813 Days
• Field of Search: 701 1- 3, 701 9- 11, 701/17, 701 23- 27, 701/58, 701/68, 701/77, 701/81, 701/89, 701200-226, 701/302, 701/98, 701400-540, 340988-996
• US Class Current: 701/26
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/063 Operations research, analysis or management

Abstract

A system and method for dividing a predefined search region into a map of a plurality of subregions to be searched by a plurality of mobile platforms, taking into account the capabilities of the mobile platforms and varying environmental conditions within the subregions, while minimizing the time needed to search each of the subregions. The system and method updates the map of the subregions as needed, in real time, to account for changing environmental conditions and changes in the capabilities of the mobile platforms being used. The subregions may also be determined using a desired level of probability for detecting targets within the subregions in a desired number of passes through the subregion. The system optimizes coverage time while insuring a desired probability of coverage (i.e., observability) for heterogeneous mobile platforms.

Claims

1. A method for optimizing a mission involving the search of a predefined geographic area by at least one vehicle, to minimize the time needed to search the predefined geographic area while ensuring that an entirety of said predefined geographic area is fully searched, said method comprising:

considering a sensing footprint of said vehicle produced by a sensor carried by said vehicle;

considering a visibility within said predefined geographic region, the visibility being controlled at least in part by weather related factors within the predefined geographic region;

from said sensing footprint and said visibility, generating a point set that defines a plurality of subregions within said predefined geographic region that said vehicle must traverse to fully search said predefined geographic region; and

using said points to determine an optimum path of travel within each said subregion for said vehicle, taking into account weather related factors that affect a sensing ability of said vehicle within each said subregion, that enables said vehicle to fully search all of said subregions in a minimum amount of time.

2. The method of claim 1, further comprising:

monitoring operation of said vehicle to determine if a change in an operational status of said vehicle occurs, and

if a change in said operational status occurs, determining an updated point set that defines an updated plurality of subregions that said vehicle must traverse to fully search said predefined geographic region.

3. The method of claim 1, further comprising:

monitoring visibility conditions within said predefined geographic region; and

if a change in said visibility conditions occurs that impedes an ability of said vehicle to search said subregions, then determining an updated point set that defines an updated plurality of subregions that said vehicle must traverse to fully search said predefined geographic region.

4. The method of claim 1, wherein a plurality of vehicles are used to search said predefined geographic region, and

further comprising considering a search footprint of each said vehicle in determining said point set for said predetermined geographic region, said point set defining a minimum number of subregions needed to be traversed by said vehicles to fully search said predefined geographic region.

5. The method of claim 4, further comprising considering a visibility available to the sensor of each said vehicle operating in each of said subregions, and using said visibility and said search footprint of each said vehicle to define a minimum number of subregions needed to be traversed by said vehicles to fully search said predefined geographic regions.

6. The method of claim 4, further comprising determining a specific path within each said subregion that defines a path requiring a minimum time for the vehicle associated with a given said subregion to traverse said subregion.

7. The method of claim 6, wherein determining said specific path within each said subregion comprises first performing a search for globally optimum paths, and then performing a local search for possible path improvements.

8. The method of claim 1, further comprising using a probability algorithm to determine a probability that a target within a particular said subregion will be detected in a given number of times that said vehicle searches said particular subregion.

9. A method for optimizing a mission involving the search of a predefined geographic area by a plurality of vehicles, to minimize the time needed to search the predefined geographic area while ensuring that an entirety of said predefined geographic area is fully searched, said method comprising:

considering a sensing footprint of each said vehicle provided by a sensor being carried by each said vehicle;

considering a visibility within said predefined geographic region, with the visibility being affected at least in part by weather conditions within the predefined geographic region;

from said sensing footprint and said visibility, generating a minimum point set that defines a minimum plurality of subregions within said predefined geographic region that said vehicles must traverse to fully search said predefined geographic region; and

for each said vehicle assigned to search a given said subregion, determining an optimum path of travel through each said subregion for said vehicle that enables each said vehicle to fully search its associated said subregion in a minimum amount of time.

10. The method of claim 9, further comprising:

monitoring operation of said vehicles; and

if an operational status of any of said vehicles occurs, then re-determining said minimum point set to define an updated, minimum plurality of subregions that must be traversed by remaining ones of said vehicles to fully search said predefined geographic region.

11. The method of claim 9, further comprising:

monitoring said visibility within said predefined geographic region; and

if said visibility changes, then re-determining said minimum point set to define an updated, minimum plurality of subregions that must be traversed by remaining ones of said vehicles to fully search said predefined geographic regions.

12. The method of claim 9, further comprising:

for a given one of said subregions, determining a probability that a target within said given subregion will be detected by said vehicle responsible for searching said given subregion, with a given number of travels through said given subregion.

13. The method of claim 9, wherein the operation of determining an optimum path of travel comprises using a modified Lin-Kernighan algorithm comprising at least one genetic algorithm for performing a search for globally optimum paths.

14. The method of claim 13, wherein the operation of determining an optimum path of travel further comprises using said modified Lin-Kernighan algorithm to perform a local search for possible path improvements and to obtain modifications to said optimum path of travel in real time based on changes in an operational status of a given one of said vehicles or a change in said visibility.

15. The method of claim 9, wherein the operation of determining an optimum path of travel for each said subregion comprises:

clustering selected points of said point;

using at least one genetic algorithm to perform a search for globally optimum paths; and

using said Lin-Kernighan algorithm to determine said optimum path of travel through said subregion.

16. A method for optimizing a mission involving the search of a predefined geographic area by at least one vehicle, to minimize the time needed to search the predefined geographic area while ensuring that an entirety of said predefined geographic area is fully searched, said method comprising:

considering a sensing footprint of said vehicle produced by a sensor carried by said vehicle;

considering a visibility within said predefined geographic region, the visibility being controlled at least in part by environmental related factors within the predefined geographic region;

from said sensing footprint and said visibility, generating a point set that defines a plurality of subregions within said predefined geographic region that said vehicle must traverse to fully search said predefined geographic region; and

using said points to determine an optimum path of travel within each said subregion for said vehicle, taking into account the environmental related factors that affect a sensing ability of said vehicle within each said subregion, that enables said vehicle to fully search all of said subregions in a minimum amount of time.