Adaptive multi-vehicle area coverage optimization system and method
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G01C-022/00
G08G-001/123
출원번호
US-0547413
(2012-07-12)
등록번호
US-8620510
(2013-12-31)
발명자
/ 주소
Meuth, Ryan J.
Vian, John L.
Saad, Emad W.
Wunsch, Donald C.
출원인 / 주소
The Boeing Company
대리인 / 주소
Harness, Dickey & Pierce, P.L.C.
인용정보
피인용 횟수 :
36인용 특허 :
10
초록▼
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 mu
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.
대표청구항▼
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
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; andan 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; anda 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; andan 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; andan 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.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (10)
Meuth, Ryan J.; Vian, John L.; Saad, Emad W.; Wunsch, Donald C., Adaptive multi-vehicle area coverage optimization system and method.
Castillo-Effen, Mauricio; Johnson, Timothy Lee; Durling, Michael Richard, Method and system for mission planning via formal verification and supervisory controller synthesis.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.