Adaptive multi-vehicle area coverage optimization system and method

• US 8,620,510 B1
• Filed: 07/12/2012
• Issued: 12/31/2013
• Est. Priority Date: 04/26/2007
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Meuth, Ryan J., Vian, John L., Saad, Emad W., Wunsch, Donald C.
• Primary Examiner(s): Shafi, Muhammad
• Application Number:
  US13/547,413
• Time in Patent Office: 537 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, 701/98, 701400-541, 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 mission planning system for determining an optimum use of a plurality of vehicles in searching a predefined geographic area (PGA). A discretizer subsystem may be used for sensing the capabilities of each vehicle to produce a point set defining a number of points within the PGA that the vehicles must traverse to completely search the PGA. A task allocator subsystem may determine an optimum division of the PGA into different subregions to be handled by specific ones of the vehicles, thus to minimize an overall time needed to search the PGA. A path optimizer subsystem may determine an optimum path through a particular vehicle'"'"'s assigned subregion to minimize the time needed for each specific vehicle to traverse its associated subregion.

Claims

1. A mission planning system for determining an optimum use of a plurality of vehicles in searching a predefined geographic area, said system comprising:

a discretizer subsystem including hardware and software components, configured to use sensing capabilities of each said vehicle to produce a point set defining a number of points within the predefined geographic area that said vehicles must traverse to completely search the predefined geographic area, the number of points taking into consideration a topography of the predefined geographic area and weather conditions affecting visibility in the predefined geographic area during the searching, and coordinates of areas of impeded visibility within the predefined geographic area;

a task allocator subsystem including a second hardware component and a second software component running on the second hardware component, configured to determine an optimum division of the predefined geographic area into different subregions to be handled by specific ones of said vehicles based on the point sets produced by said discretizer subsystem, to minimize an overall time needed to search the predefined geographic area region by said vehicles;

a path optimizer subsystem including hardware and software components, for determining an optimum path, for each one of said vehicles through a particular subregion determined by said task allocator subsystem to be handled by said one of said vehicles to minimize the time needed to traverse said particular subregion; and

an arbitrator subsystem that determines needed changes to the subregions to be handled by each of said vehicles based upon changes to both an operational status of each said vehicle and changing environmental conditions within said predefined geographic area.

2. The system of claim 1, wherein the discretizer subsystem further is configured to convert the predefined geographic area into a plurality of discrete search regions.

3. The system of claim 2, wherein the discretizer subsystem further is configured to use at least one of the following before generating the point set:

locations of known obstacles within the predefined geographic area; and

a topography of the predefined geographic area.

4. The system of claim 1, wherein the discretizer subsystem is configured to:

make use of an algorithm to initialize the point set to generate a grid having a triangular arranged collection of anchor points;

to create a Voronoi diagram for the point set that produces a plurality of hexagonal shaped cells that each define one the specific subregions within the predefined geographic area, and with each one of the hexagonally shaped cells having a vertex at each one of its corners and each said subregion having an anchor point at a geometric center thereof.

5. The system of claim 4, wherein the discretizer subsystem is further configured to examine each of the vertexes of each said subregion and the anchor point within each said subregion, and to determine whether each said vertex meets a probability of detection based on known visibility conditions, and to add any one of the vertexes that does not meet the probability of detection to the grid as a new anchor point.

6. The system of claim 1, further comprising an arbitrator subsystem that determines needed changes to searching responsibilities of each of said vehicles, based upon changes to an operational status of the vehicle.

7. The system of claim 1, further comprising an arbitrator subsystem that determines needed changes to searching responsibilities of each of said vehicles, based upon environmental changes that occur within said predefined geographic area.

8. The system of claim 1 wherein said arbitrator comprises a clustering algorithm that takes into account an operational status of each said vehicle and changing environmental conditions within said predefined geographic area to modify said number of points to re-map the predefined geographic area into a new plurality of subregions.

9. The system of claim 1, wherein said vehicles comprise heterogeneous vehicles having different operational capabilities.

10. A mission planning system for determining an optimum use of a plurality of vehicles in searching a predefined geographic area, said system comprising:

a discretizer subsystem including hardware and software components, for that defines a number of points within said predefined geographic area that said vehicles must traverse to completely search the predefined geographic area, taking into consideration weather conditions affecting visibility in the predefined geographic area during searching performed by said vehicles;

a task allocator subsystem including hardware and second softwares, for determining an optimum division of said predefined geographic area into different subregions to be handled by specific ones of said vehicles, using an iterative process;

a path optimizer subsystem including hardware and software components, for determining a path through a particular vehicle'"'"'s assigned said subregion that minimizes a search time required for the vehicle to search its associated said subregion; and

an arbitrator subsystem, including hardware and software components, that determines needed changes to searching responsibilities of each of said vehicles, based upon changes to an operational status of each of the vehicles and changing environmental conditions in the predefined geographic area.

11. The system of claim 10, wherein the task allocator subsystem is configured to use the iterative process to consider a number of the vehicles initially randomly assigned to subregions of the predefined geographic regions, and to iteratively divide the subregions with a goal toward equalizing a total load between two or more vehicles that are assigned to any of the subregions.

12. The system of claim 11, wherein the task allocator subsystem uses a particle swarm optimization (PSO) computation technique to assist in determining assignments of each of the vehicles to specific subregions within the predefined geographic area.

13. The system of claim 10, wherein the path optimizer subsystem is configured to use a clustered Lin-Kernighan stochastic method to find a shortest time path for each given one of the vehicles through its associated subregion or subregions.

14. The system of claim 10, wherein the arbitrator subsystem is configured to use Adaptive Resonance Theory clustering to maintain two sets of clusters, a first set of clusters for the vehicles, and a second set of clusters for the points in the predefined geographic area.

15. The system of claim 14, wherein the first set of clusters for the vehicles is based on conditions and capabilities of the vehicles.

16. The system of claim 14, wherein the second set of clusters for the predefined geographic area is based on environmental factors including at least one of weather, terrain and vegetation within the predefined geographic area.

17. A mission planning system for determining an optimum use of a plurality of vehicles in searching a predefined geographic area, said system comprising:

a discretizer subsystem, including hardware and software components, configured to use for using sensing capabilities of each said vehicle to produce a point set defining a number of points within said predefined geographic area that said vehicles must traverse to completely search the predefined geographic area, taking into account weather conditions affecting visibility within the predefined geographic area that affect the sensing capabilities of each said vehicle;

a path optimizer subsystem, including hardware and software components, for determining an optimum path through a particular one of a plurality of subregions of the predefined geographic area by a particular one of said vehicles, and in a manner that minimizes a time needed for each said specific vehicle to traverse its associated said subregion; and

an arbitrator subsystem that determines needed changes to searching responsibilities of each of said vehicles, based upon changes to an operational status of each said vehicle and changing environmental conditions within the predefined geographic area.

18. The system of claim 17, further comprising a task allocator subsystem for determining an optimum division of said predefined geographic area into said subregions to be handled by specific ones of said vehicles, to minimize an overall time needed to search said predefined geographic area by said vehicles.