Methods and systems for determining a cyclical fleet plan satisfying a recurring set of coverage requirements
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G08G-005/00
G08G-009/00
출원번호
US-0771361
(2013-02-20)
등록번호
US-8880326
(2014-11-04)
발명자
/ 주소
Bonawitz, Keith Allen
Rhodes, Bradley James
Piponi, Dan
Treuille, Adrien
출원인 / 주소
Google Inc.
대리인 / 주소
McDonnell Boehnen Hulbert & Berghoff LLP
인용정보
피인용 횟수 :
7인용 특허 :
19
초록▼
Methods and systems for determining a cyclical pattern of trajectories for a fleet of vehicles are provided. In one example, a method comprises receiving a sequence of coverage requirements for a region and an associated period of time. For each of one or more phases of the period of time, possible
Methods and systems for determining a cyclical pattern of trajectories for a fleet of vehicles are provided. In one example, a method comprises receiving a sequence of coverage requirements for a region and an associated period of time. For each of one or more phases of the period of time, possible routes that a vehicle located at one or more respective landmarks at a beginning of the phase could follow to reach one or more additional landmarks by an end of the phase are determined. Further, a cyclical pattern of trajectories for vehicles of a fleet of vehicles that minimizes a difference between a distribution of the fleet at a beginning of the period of time and a distribution of the fleet at an end of the period of time is determined.
대표청구항▼
1. A method comprising: receiving a sequence of coverage requirements for a region and an associated 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 individual coverage requirements of the seque
1. A method comprising: receiving a sequence of coverage requirements for a region and an associated 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 individual coverage requirements of the sequence of coverage requirements are indicative of a desired number of vehicles of a fleet of vehicles for one or more of the plurality of landmarks at an end of a given phase of the plurality of phases;determining, by a processor, for each of one or more phases of the plurality of phases, possible routes that a vehicle of the fleet of vehicles located at one or more respective landmarks of the plurality of landmarks at a beginning of the phase could follow to reach one or more additional landmarks of the plurality of landmarks by an end of the phase; andbased on the sequence of coverage requirements and the determined possible routes, determining, by the processor, a cyclical pattern of trajectories for vehicles of the fleet of vehicles that minimizes a difference between a distribution of vehicles in the fleet of vehicles at a beginning of the period of time and a distribution of vehicles in the fleet of vehicles at an end of the period of time. 2. The method of claim 1, wherein vehicles of the fleet of vehicles include a balloon within a data network that is operable to provide data communication via optical or radio-frequency (RF) links. 3. The method of claim 2, further comprising determining the possible routes based on one or more estimated winds at one or more altitudes. 4. The method of claim 1, wherein the cyclical pattern of trajectories indicates which route of the determined possible routes for a given vehicle starting at an individual landmark of the plurality of landmarks to follow during a given respective phase. 5. The method of claim 1, further comprising determining the cyclical pattern of trajectories by minimizing a linear objective function, wherein the linear objective function includes a deficit term that is indicative of a number of vehicles by which one or more of the coverage requirements are under-satisfied. 6. The method of claim 1, further comprising transmitting, using one or more optical or radio-frequency (RF) links, instructions to the fleet of vehicles to cause the fleet of vehicles to follow the cyclical pattern of trajectories. 7. The method of claim 1, wherein determining, for each of the one or more phases, the possible routes that a vehicle located at the one or more respective landmarks could follow comprises: determining, for each of the one or more phases and each of the one or more respective landmarks of the plurality of landmarks, a minimum distance from each additional landmark of the plurality of landmarks that a vehicle starting from the respective landmark could reach during the phase; anddetermining the possible routes for the phase and the respective landmark based on a comparison between minimum distances associated with the additional landmarks and a threshold distance. 8. The method of claim 1, wherein determining, for each of the one or more phases, the possible routes that a vehicle located at the one or more respective landmarks could follow comprises: determining, for each of the one or more phases and each of the one or more respective landmarks of the plurality of landmarks, confidence measures that are indicative of whether a vehicle starting from the respective landmark could reach each additional landmark of the plurality of landmarks during the phase; anddetermining the possible routes for the phase and the respective landmark based on a comparison between confidence measures associated with the additional landmarks and a confidence threshold. 9. The method of claim 1, wherein determining, for each of the one or more phases, the possible routes that a vehicle located at the one or more respective landmarks could follow comprises: determining, for each of the one or more phases and each of the one or more respective landmarks of the plurality of landmarks, cost values associated with a vehicle traveling to each additional landmark of the plurality of landmarks during the phase; anddetermining the possible routes for the phase and the respective landmark based on a comparison between cost values associated with the additional landmarks and a cost threshold. 10. The method of claim 1, wherein determining the cyclical pattern of trajectories for vehicles of the fleet of vehicles further comprises determining an initial distribution for vehicles in the fleet of vehicles at the beginning of the period of time. 11. The method of claim 10, further comprising: determining a current distribution of vehicles of the fleet of vehicles at a current time period prior to the period of time; anddetermining trajectories for vehicles of the fleet of vehicles to follow between the current time and the period of time to cause the vehicles of the fleet of vehicles to be arranged in the initial distribution at the beginning of the period of time. 12. 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 a sequence of coverage requirements for a region and an associated 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 individual coverage requirements of the sequence of coverage requirements are indicative of a desired number of vehicles of a fleet of vehicles for one or more of the plurality of landmarks at an end of a given phase of the plurality of phases;determining for each of one or more phases of the plurality of phases possible routes that a vehicle of the fleet of vehicles located at one or more respective landmarks of the plurality of landmarks at a beginning of the phase could follow to reach one or more additional landmarks of the plurality of landmarks by an end of the phase; andbased on the sequence of coverage requirements and the determined possible routes, determining a cyclical pattern of trajectories for vehicles of the fleet of vehicles that minimizes a difference between a distribution of vehicles in the fleet of vehicles at a beginning of the period of time and a distribution of vehicles in the fleet of vehicles at an end of the period of time. 13. The non-transitory computer-readable storage medium of claim 12, wherein vehicles of the fleet of vehicles include a balloon within a data network that is operable to provide data communication via optical or radio-frequency (RF) links. 14. The non-transitory computer-readable storage medium of claim 13, wherein the functions further comprise determining the possible routes based on one or more estimated winds at one or more altitudes. 15. The non-transitory computer-readable storage medium of claim 10, wherein the cyclical pattern of trajectories indicates which route of the determined possible routes for a given vehicle starting at an individual landmark of the plurality of landmarks to follow during a given respective phase. 16. A system, comprising: at least one processor;data storage comprising program instructions executable by the at least one processor to cause the system to perform functions comprising: receiving a sequence of coverage requirements for a region and an associated 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 individual coverage requirements of the sequence of coverage requirements are indicative of a desired number of vehicles of a fleet of vehicles for one or more of the plurality of landmarks at an end of a given phase of the plurality of phases;determining for each of one or more phases of the plurality of phases possible routes that a vehicle of the fleet of vehicles located at one or more respective landmarks of the plurality of landmarks at a beginning of the phase could follow to reach one or more additional landmark of the plurality of landmarks by an end of the phase; andbased on the sequence of coverage requirements and the determined possible routes, determining a cyclical pattern of trajectories for vehicles of the fleet of vehicles that minimizes a difference between a distribution of vehicles in the fleet of vehicles at a beginning of the period of time and a distribution of vehicles in the fleet of vehicles at an end of the period of time. 17. The system of claim 16, wherein vehicles of the fleet of vehicles include a balloon within a data network that is operable to provide data communication via optical or radio-frequency (RF) links. 18. The system of claim 17, wherein the functions further comprise determining the possible routes based on one or more estimated winds at one or more altitudes. 19. The system of claim 16, wherein the cyclical pattern of trajectories indicates which route of the determined possible routes for a given vehicle starting at an individual landmark of the plurality of landmarks to follow during a given respective phase. 20. The system of claim 16, wherein the functions further comprise instructing the fleet of vehicles to follow the cyclical pattern of trajectories.
연구과제 타임라인
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.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.