Methods and systems for determining fleet trajectories to satisfy a sequence of coverage requirements
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06Q-010/00
G08G-005/00
G08G-001/00
출원번호
US-0730867
(2012-12-29)
등록번호
US-9014957
(2015-04-21)
발명자
/ 주소
Bonawitz, Keith Allen
Treuille, Adrien
출원인 / 주소
Google Inc.
대리인 / 주소
McDonnell Boehnen Hulbert & Berghoff LLP
인용정보
피인용 횟수 :
7인용 특허 :
19
초록▼
Methods and systems for determining trajectories for vehicles of a fleet of vehicles are provided. In one example, a method comprises receiving an initial location of one or more vehicles, and receiving a sequence of coverage requirements for a region and an associated period of time. The region may
Methods and systems for determining trajectories for vehicles of a fleet of vehicles are provided. In one example, a method comprises receiving an initial location of one or more vehicles, and receiving a sequence of coverage requirements for a region and an associated period of time. The region may be divided into a plurality of landmarks and the period of time may be divided into a plurality of phases. The method also comprises determining for each of one or more phases and at least one respective landmark, a set of starting landmarks from which a vehicle could reach the respective landmark during the phase. The method further comprises determining which respective landmark that the vehicle should travel to during the one or more phases based on the sequence of coverage requirements and the set of starting landmarks for the one or more phases and the at least one respective landmark.
대표청구항▼
1. A method for a data network comprising: receiving an initial location of one or more vehicles of a fleet of vehicles;receiving a sequence of individual coverage requirements for a geographic region for the data network and an associated period of time, wherein the geographic region is divided int
1. A method for a data network comprising: receiving an initial location of one or more vehicles of a fleet of vehicles;receiving a sequence of individual coverage requirements for a geographic region for the data network and an associated period of time, wherein the geographic region is divided into a plurality of landmarks and the associated period of time is divided into a plurality of phases, and wherein each individual coverage requirement of the sequence of individual coverage requirements corresponds to at least one respective phase of the plurality of phases and is indicative of a desired number of vehicles of the fleet of vehicles for one or more of the plurality of landmarks at an end of the at least one respective phase;determining, by a processor, for each of one or more of the respective phases of the plurality of phases and for each of multiple respective ending landmarks of the plurality of landmarks, a set of starting landmarks corresponding to the respective phase and the respective ending landmark, wherein the set of starting landmarks comprises one or more landmarks of the plurality of landmarks from which the one or more vehicles of the fleet of vehicles could reach the respective ending landmark of the plurality of landmarks by traveling during the respective phase;based on the initial locations of the one or more vehicles of the fleet of vehicles, the sequence of individual coverage requirements for the geographic region for the data network, and the determined set of starting landmarks for each of the one or more respective phases and each of the multiple respective ending landmarks of the plurality of landmarks, determining, by the processor, which landmark of the plurality of landmarks for a particular vehicle of the one or more vehicles of the fleet of vehicles to travel to during a respective phase of the one or more respective phases; andinstructing the particular vehicle to travel to the determined landmark during the respective phase. 2. The method of claim 1, wherein the one or more vehicles of the fleet of vehicles include a balloon within the data network that is operable to provide data communication via optical or radio-frequency (RF) links. 3. The method of claim 2, wherein determining, for each of the one or more respective phases and each of the multiple respective ending landmarks of the plurality of landmarks, the set of starting landmarks comprises determining one or more landmarks of the plurality of landmarks from which the balloon could reach the respective ending landmark of the plurality of landmarks by following one or more estimated winds at one or more altitudes during the respective phase. 4. The method of claim 3, further comprising determining the one or more estimated winds based on wind data received from one or more balloons. 5. The method of claim 1, wherein determining, for each of the one or more respective phases and each of the multiple respective ending landmarks, the set of starting landmarks comprises: determining, by the processor, for each respective phase and each respective ending landmark of the plurality of landmarks, a minimum distance from the respective ending landmark of the plurality of landmarks that the one or more vehicles could reach when starting from each of multiple given landmarks of the plurality of landmarks respectively and traveling during the respective phase, anddetermining the set of starting landmarks for the respective phase and the respective ending landmark of the plurality of landmarks based on comparisons between the determined minimum distances for the respective ending landmark of the plurality of landmarks and a threshold distance. 6. The method of claim 5, further comprising determining, by the processor, which landmark of the plurality of landmarks for the particular vehicle to travel to during the respective phase based on the determined minimum distances for each respective ending landmark of the plurality of landmarks. 7. The method of claim 1, wherein determining, for each of the one or more respective phases and each of the multiple respective ending landmarks of the plurality of landmarks, the set of starting landmarks comprises: determining, by the processor, for each respective phase and each respective ending landmark of the plurality of landmarks, a confidence measure that is indicative of whether the one or more vehicles could reach the respective ending landmark of the plurality of landmarks when starting from each of multiple given landmarks of the plurality of landmarks respectively and traveling during the respective phase, anddetermining the set of starting landmarks for the respective phase and the respective ending landmark of the plurality of landmarks based on comparisons between the determined confidence measures for the respective ending landmark of the plurality of landmarks and a confidence threshold. 8. The method of claim 7, further comprising determining, by the processor, which landmark for the particular vehicle to travel to during the respective phase based on the determined confidence measures for each respective ending landmark of the plurality of landmarks. 9. The method of claim 1, wherein determining, for each of the one or more respective phases and each of the multiple respective ending landmarks of the plurality of landmarks, the set of starting landmarks comprises: determining, by the processor, for each respective phase and each respective ending landmark, a cost value associated with the one or more vehicles starting from each of multiple given landmarks of the plurality of landmarks respectively and traveling to the respective ending landmark of the plurality of landmarks during the respective phase; anddetermining the set of starting landmarks for the respective phase and the respective ending landmark of the plurality of landmarks based on comparisons between the determined cost values for the respective ending landmark of the plurality of landmarks and a cost threshold. 10. The method of claim 1, further comprising determining which landmark of the plurality of landmarks for the particular vehicle to travel to during the respective phase by minimizing a linear objective function. 11. A non-transitory computer-readable storage medium having stored therein instructions, that when executed by a computing device in a data network, cause the computing device to perform functions comprising: receiving an initial location of one or more vehicles of a fleet of vehicles;receiving a sequence of individual coverage requirements for a geographic region for the data network and an associated period of time, wherein the geographic region is divided into a plurality of landmarks and the associated period of time is divided into a plurality of phases, and wherein each individual coverage requirement of the sequence of individual coverage requirements corresponds to at least one respective phase of the plurality of phases and is indicative of a desired number of vehicles of the fleet of vehicles for one or more of the plurality of landmarks at an end of the at least one respective phase;determining for each of one or more of the respective phases of the plurality of phases and for each of multiple respective ending landmarks of the plurality of landmarks, a set of starting landmarks corresponding to the respective phase and the respective ending landmark of the plurality of landmarks, wherein the set of starting landmarks comprises one or more landmarks of the plurality of landmarks from which the one or more vehicles of the fleet of vehicles could reach the respective ending landmark of the plurality of landmarks by traveling during the respective phase;based on the initial locations of the one or more vehicles of the fleet of vehicles, the sequence of individual coverage requirements, and the determined set of starting landmarks for each of the one or more respective phases and each of the multiple respective ending landmarks of the plurality of landmarks, determining which landmark of the plurality of landmarks for a particular vehicle of the one or more vehicles of the fleet of vehicles to travel to during a respective phase of the one or more respective phases; andinstructing the particular vehicle of the one or more vehicles of the fleet of vehicles to travel to the determined landmark of the plurality of landmarks during the respective phase. 12. The non-transitory computer-readable storage medium of claim 11, wherein determining, for each of the one or more respective phases and each of the multiple respective ending landmarks of the plurality of landmarks, the set of starting landmarks comprises: determining for each respective phase and each respective ending landmark, a minimum distance from the respective ending landmark that the one or more vehicles could reach when starting from each of multiple given landmarks of the plurality of landmarks respectively and traveling during the respective phase, anddetermining the set of starting landmarks for the respective phase and the respective ending landmark based on comparisons between the determined minimum distances for the respective ending landmark of the plurality of landmarks and a threshold distance. 13. The non-transitory computer-readable storage medium of claim 11, wherein determining, for each of the one or more respective phases and each of the multiple respective ending landmarks of the plurality of landmarks, the set of starting landmarks comprises: determining for each respective phase and each respective ending landmark, a confidence measure that is indicative of whether the one or more vehicles could reach the respective ending landmark of the plurality of landmarks when starting from each of multiple given landmarks of the plurality of landmarks respectively and traveling during the respective phase, anddetermining the set of starting landmarks for the respective phase and the respective ending landmark based on comparisons between the determined confidence measures for the respective ending landmark of the plurality of landmarks and a confidence threshold. 14. The non-transitory computer-readable storage medium of claim 11, wherein determining, for each of the one or more respective phases and each of the multiple respective ending landmarks of the plurality of landmarks, the set of starting landmarks comprises: determining, for each respective phase and each respective ending landmark, a cost value associated with the one or more vehicles starting from each of multiple given landmarks of the plurality of landmarks respectively and traveling to the at lest one respective ending landmark of the plurality of landmarks during the respective phase; anddetermining the set of starting landmarks for the respective phase and the respective ending landmark based on comparisons between the determined cost values for the respective ending landmark of the plurality of landmarks and a cost threshold. 15. A system for a data network, comprising: at least one processor; anddata storage comprising program instructions executable by the at least one processor to cause the system to perform functions comprising: receiving an initial location of one or more vehicles of a fleet of vehicles;receiving a sequence of individual coverage requirements for a geographic region for the data network and an associated period of time, wherein the geographic region for the data network is divided into a plurality of landmarks and the associated period of time is divided into a plurality of phases, and wherein each individual coverage requirement of the sequence of individual coverage requirements corresponds to at least one respective phase of the plurality of phases and is indicative of a desired number of vehicles of the fleet of vehicles for one or more of the plurality of landmarks at an end of the at least one respective phase;determining for each of one or more of the respective phases of the plurality of phases and for each of multiple respective ending landmarks of the plurality of landmarks, a set of starting landmarks corresponding to the respective phase and the respective ending landmark of the plurality of landmarks, wherein the set of starting landmarks comprises one or more landmarks of the plurality of landmarks from which the one or more vehicles of the fleet of vehicles could reach the respective ending landmark of the plurality of landmarks by traveling during the respective phase;based on the initial locations of the one or more vehicles of the fleet of vehicles, the sequence of coverage requirements, and the determined set of starting landmarks for each of the one or more respective phases and each of the multiple respective ending landmarks of the plurality of landmarks, determining which landmark of the plurality of landmarks for a particular vehicle of the one or more vehicles of the fleet of vehicles to travel to during a respective phase of the one or more respective phases; andinstructing the particular vehicle of the one or more vehicles of the fleet of vehicles to travel to the determined landmark of the plurality of landmarks during the respective phase. 16. The system of claim 15, wherein the one or more vehicles of the fleet of vehicles include a balloon within the data network that is operable to provide data communication via optical or radio-frequency (RF) links. 17. The system of claim 16, wherein determining, for each of the one or more respective phases and each of the multiple respective ending landmarks of the plurality of landmarks, the set of starting landmarks comprises: determining for each respective phase and each respective ending landmark of the plurality of landmarks, a minimum distance from the respective ending landmark of the plurality of landmarks that the one or more vehicles could reach when starting from each of multiple given landmarks of the plurality of landmarks respectively and traveling during the respective phase, anddetermining the set of starting landmarks for the respective phase and the respective ending landmark based on comparisons between the determined minimum distances for the respective ending landmark of the plurality of landmarks and a threshold distance. 18. The system of claim 17, wherein the functions further comprise determining which landmark of the plurality of landmarks for the particular vehicle to travel to during the respective phase based on the determined minimum distances for each respective ending landmark of the plurality of landmarks.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (19)
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.
DeVaul, Richard Wayne; Teller, Eric; Biffle, Clifford L.; Weaver, Josh, Balloon network with free-space optical communication between super-node balloons and RF communication between super-node and sub-node balloons.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.