Methods and systems for decomposing fleet planning optimizations via spatial partitions
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06Q-010/00
G08G-005/00
출원번호
US-0748708
(2013-01-24)
등록번호
US-8874356
(2014-10-28)
발명자
/ 주소
Bonawitz, Keith Allen
출원인 / 주소
Google Inc.
대리인 / 주소
McDonnell Boehnen Hulbert & Berghoff LLP
인용정보
피인용 횟수 :
12인용 특허 :
18
초록▼
Example methods and systems for decomposing fleet planning optimizations via spatial partitions are described. An example method includes receiving information indicating a sequence of coverage requirements for a region over a period of time. The region is characterized by a plurality of landmarks a
Example methods and systems for decomposing fleet planning optimizations via spatial partitions are described. An example method includes receiving information indicating a sequence of coverage requirements for a region over a period of time. The region is characterized by a plurality of landmarks and the period of time is divided into a plurality of phases. An individual coverage requirement indicates a desired number of vehicles of a plurality of vehicles for respective landmarks at a given phase. The method also includes dividing the region into a plurality of sub-regions, and determining sub-region fleet plans for the plurality of sub-regions based on estimates of one or more vehicles entering respective sub-regions and estimates of one or more vehicles leaving respective sub-regions. The method also includes combining the sub-region fleet plans to produce a fleet plan responsive to the sequence of coverage requirements for the region.
대표청구항▼
1. A method comprising: receiving information from a control system indicative of a sequence of coverage requirements for a data network for a region over a period of time, wherein the region is characterized by a plurality of landmarks and the period of time is divided into a plurality of phases, a
1. A method comprising: receiving information from a control system indicative of a sequence of coverage requirements for a data network for a region over a period of time, wherein the region is characterized by a plurality of landmarks and the period of time is divided into a plurality of phases, and wherein a given coverage requirement of the sequence of coverage requirements is indicative of a desired number of vehicles of a plurality of vehicles for respective landmarks at a given phase;dividing the region into a plurality of sub-regions;determining, by a processor of the control system, sub-region fleet plans for the plurality of sub-regions based on both estimates of one or more vehicles entering respective sub-regions and estimates of one or more vehicles leaving the respective sub-regions, wherein a given sub-region fleet plan of the determined sub-region fleet plans is indicative of one or more landmarks for the one or more vehicles to travel to during one or more phases of the plurality of phases, and indicates both a first number value of vehicles entering the given sub-region and a second number value of vehicles leaving the given sub-region during respective phases, and wherein the first number value of vehicles is different than the second number value of vehicles;combining, by the processor of the control system, the determined sub-region fleet plans to produce a fleet plan responsive to the sequence of coverage requirements for the region; andproviding, by the processor of the control system, instructions to the one or more vehicles to travel according to the fleet plan. 2. The method of claim 1, further comprising: for the plurality of sub-regions, determining for one or more respective landmarks of the plurality of landmarks estimated landmarks of the plurality of landmarks that can be reached by a vehicle starting from the one or more respective landmarks; andbased on the sequence of coverage requirements, determining which landmarks of the estimated landmarks for the vehicle to travel to during a respective phase to generate the sub-region fleet plans. 3. The method of claim 1, wherein combining the sub-region fleet plans to produce the fleet plan comprises: for sub-region fleet plans corresponding to a first sub-region and a second sub-region of the plurality of sub-regions that are adjacent regions, at a boundary of the adjacent regions resolving a number of vehicles traversing the boundary to be a given number of vehicles that are estimated to be leaving the first sub-region at the boundary. 4. The method of claim 1, wherein a first sub-region and a second sub-region of the plurality of regions are adjacent regions, and wherein vehicles traverse from the first sub-region to the second sub-region, and wherein combining the sub-region fleet plans to produce the fleet plan responsive to the sequence of coverage requirements for the region comprises: at a boundary of the adjacent regions, resolving a number of vehicles traversing the boundary to be a smaller of a number of vehicles leaving the first sub-region at the boundary and a number of vehicles entering the second sub-region at the boundary. 5. The method of claim 1, wherein combining the sub-region fleet plans to produce the fleet plan comprises: providing the sub-region fleet plans to a linear solver as inputs for an initial configuration of vehicles of the plurality of vehicles; andperforming one or more iterations using the linear solver to produce the fleet plan for the region. 6. The method of claim 1, wherein the region includes Earth, and wherein dividing the region into a plurality of sub-regions comprises dividing the Earth into regions comprising continents. 7. The method of claim 1, wherein vehicles of the plurality of vehicles include a balloon within a data network that is operable to provide data communication via optical or radio-frequency (RF) links. 8. The method of claim 7, further comprising: for the plurality of sub-regions, determining for one or more respective landmarks of the plurality of landmarks estimated landmarks of the plurality of landmarks that can be reached by the balloon starting from the one or more respective landmarks and by following one or more estimated winds at one or more altitudes. 9. A non-transitory computer readable storage medium having stored therein instructions, that when executed by a computing device, cause the computing device to perform functions comprising: receiving information from a control system indicative of a sequence of coverage requirements for a data network for a region over a period of time, wherein the region is characterized by a plurality of landmarks and the period of time is divided into a plurality of phases, and wherein a given coverage requirement of the sequence of coverage requirements is indicative of a desired number of vehicles of a plurality of vehicles for respective landmarks at a given phase;dividing the region into a plurality of sub-regions;determining sub-region fleet plans for the plurality of sub-regions based on both estimates of one or more vehicles entering respective sub-regions and estimates of one or more vehicles leaving the respective sub-regions, wherein a given sub-region fleet plan of the determined sub-region fleet plans is indicative of one or more landmarks for the one or more vehicles to travel to during one or more phases of the plurality of phases, and indicates both a first number value of vehicles entering the given sub-region and a second number value of vehicles leaving the given sub-region during respective phases, and wherein the first number value of vehicles is different than the second number value of vehicles;combining the determined sub-region fleet plans to produce a fleet plan responsive to the sequence of coverage requirements for the region; andproviding instructions to the one or more vehicles to travel according to the fleet plan. 10. The non-transitory computer readable storage medium of claim 9, wherein the functions further comprise: for the plurality of sub-regions, determining for one or more respective landmarks of the plurality of landmarks estimated landmarks of the plurality of landmarks that can be reached by a vehicle starting from the one or more respective landmarks; andbased on the sequence of coverage requirements, determining which landmarks of the estimated landmarks for the vehicle to travel to during a respective phase to generate the sub-region fleet plans. 11. The non-transitory computer readable storage medium of claim 9, wherein combining the sub-region fleet plans to produce the fleet plan comprises: for sub-region fleet plans corresponding to a first sub-region and a second sub-region of the plurality of sub-regions that are adjacent regions, at a boundary of the adjacent regions resolving a number of vehicles traversing the boundary to be a given number of vehicles that are estimated to be leaving the first sub-region at the boundary. 12. The non-transitory computer readable storage medium of claim 9, wherein a first sub-region and a second sub-region of the plurality of regions are adjacent regions, and wherein vehicles traverse from the first sub-region to the second sub-region, and wherein combining the sub-region fleet plans to produce the fleet plan responsive to the sequence of coverage requirements for the region comprises: at a boundary of the adjacent regions, resolving a number of vehicles traversing the boundary to be a smaller of a number of vehicles leaving the first sub-region at the boundary and a number of vehicles entering the second sub-region at the boundary. 13. The non-transitory computer readable storage medium of claim 9, wherein combining the sub-region fleet plans to produce the fleet plan comprises: providing the sub-region fleet plans to a linear solver as inputs for an initial configuration of vehicles of the plurality of vehicles; andperforming one or more iterations using the linear solver to produce the fleet plan for the region. 14. The non-transitory computer readable storage medium of claim 9, wherein the region includes Earth, and wherein dividing the region into a plurality of sub-regions comprises dividing the Earth into regions comprising continents. 15. A system, comprising: at least one processor; anddata storage comprising program instructions executable by the at least one processor to cause the at least one processor to perform functions comprising: receiving information from a control system indicative of a sequence of coverage requirements for a data network for a region over a period of time, wherein the region is characterized by a plurality of landmarks and the period of time is divided into a plurality of phases, and wherein a given coverage requirement of the sequence of coverage requirements is indicative of a desired number of vehicles of a plurality of vehicles for respective landmarks at a given phase;dividing the region into a plurality of sub-regions;determining sub-region fleet plans for the plurality of sub-regions based on both estimates of one or more vehicles entering respective sub-regions and estimates of one or more vehicles leaving the respective sub-regions, wherein a given sub-region fleet plan of the determined sub-region fleet plans is indicative of one or more landmarks for the one or more vehicles to travel to during one or more phases of the plurality of phases, and indicates both a first number value of vehicles entering the given sub-region and a second number value of vehicles leaving the given sub-region during respective phases, and wherein the first number value of vehicles is different than the second number value of vehicles;combining the determined sub-region fleet plans to produce a fleet plan responsive to the sequence of coverage requirements for the region; andproviding instructions to the one or more vehicles to travel according to the fleet plan. 16. The system of claim 15, wherein vehicles of the plurality of vehicles include a balloon within a data network that is operable to provide data communication via optical or radio-frequency (RF) links. 17. The system of claim 16, wherein the functions further comprise: for the plurality of sub-regions, determining for one or more respective landmarks of the plurality of landmarks estimated landmarks of the plurality of landmarks that can be reached by the balloon starting from the one or more respective landmarks and by following one or more estimated winds at one or more altitudes. 18. The system of claim 15, wherein combining the sub-region fleet plans to produce the fleet plan comprises: providing the sub-region fleet plans to a linear solver as inputs for an initial configuration of vehicles of the plurality of vehicles; andperforming one or more iterations using the linear solver to produce the fleet plan for the region.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (18)
Meuth, Ryan J.; Vian, John L.; Saad, Emad W.; Wunsch, Donald C., Adaptive multi-vehicle area coverage optimization system and method.
Gross, Jonathan H.; Emmons, Jr., Thomas Peter; Tessler, Michael A., Apparatus and methods for controlling a cellular communications network having airborne transceivers.
Korb, C. Laurence; Korb, Andrew Robert, Methods for optimizing the performance, cost and constellation design of satellites for full and partial earth coverage.
Coffee, John R.; Rudow, Richard W.; Allen, Robert F.; Billings, Mark; Dye, David A.; Kirchner, Mark L.; Lewis, Robert W.; Marvin, Kevin M.; Sleeper, Robert D.; Tekniepe, William A., Vehicle tracking, communication and fleet management system.
Frolov, Sergey V.; Cyrus, Michael; Bruce, Allan J.; Moussouris, John Peter, Methods and apparatus for a distributed airborne wireless communications fleet.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.