Satellite Scheduling System

Patent metadata

Field	Value
Publication number	US-2016155073-A1
Application number	US-201615016851-A
Country	US
Kind code	A1
Filing date	Feb 5, 2016
Priority date	Aug 3, 2012
Publication date	Jun 2, 2016
Grant date	—

Abstract

Systems and methods are provided for scheduling objects having pair-wise and cumulative constraints. The systems and methods presented can utilize a directed acyclic graph to increase or maximize a utilization function. Violation of cumulative constraints can be identified at the moment of constraint violation such that events resulting in constraint violations can be removed from the schedule while the schedule is being determined. By removing the events triggering constraint violations at the point of constraint violation, the systems and methods provided can determine optimal or near-optimal schedules in a relatively quick and efficient manner compared to systems and methods that check for violations of cumulative constraints after determining a schedule. The objects can comprise satellites in a constellation of satellites. In some implementations, the satellites are imaging satellites, and the systems and methods for scheduling can use crowd-sourced data to determine events of interest for acquisition of images.

First claim

1 .- 20 . (canceled)

21 . A computer-implemented method to perform satellite scheduling, the method comprising:
obtaining, by one or more computing devices, data that describes a plurality of requested events, wherein each requested event comprises at least one task to be performed by at least one of a plurality of satellites; identifying, by the one or more computing devices, one or more constraints associated with at least one of the plurality of events and the plurality of satellites; building, by the one or more computing devices, a directed acyclic graph that represents the plurality of requested events, the directed acyclic graph comprising a plurality of nodes respectively connected by a plurality of directed edges, the plurality of nodes representative of the plurality of requested events, the plurality of directed edges representative of transitions between events; determining, by the one or more computing devices, at least one path through the directed acyclic graph that does not violate any of the one or more constraints; and creating, by the one or more computing devices, a schedule for the plurality of satellites to perform the plurality of requested events based at least in part on the at least one path through the directed acyclic graph.

22 . The computer-implemented method of claim 21 , wherein building, by the one or more computing devices, the directed acyclic graph comprises:
creating, by the one or more computing devices, the plurality of nodes that are representative of the plurality of requested events, wherein at least one of a start time and a duration is associated with each requested event and its representative node; and after creating the plurality of nodes, creating, by the one or more computing devices, the plurality of directed edges between respective pairs of nodes; wherein creating the plurality of directed edges comprises:
determining, by the one or more computing devices, whether a new directed edge between a first node and a second node would violate any of the one or more constraints; and
creating, by the one or more computing devices, the new directed edge between the first node and the second node only when it is determined that the new directed edge would not violate any of the one or more constraints.

23 . The computer-implemented method of claim 21 , wherein building, by the one or more computing devices, the directed acyclic graph comprises creating, by the one or more computing devices, the directed acyclic graph in which all acceptable paths pass through a first node of the plurality of nodes that is representative of a critical event.

24 . The computer-implemented method of claim 21 , wherein:
determining, by the one or more computing devices, at least one path through the directed acyclic graph comprises determining, by the one or more computing devices, a first path through the directed acyclic graph that results in a desired value of a utilization function and that does not violate any of the one or more constraints; and creating, by the one or more computing devices, the schedule comprises creating, by the one or more computing devices, the schedule for the plurality of satellites to perform the plurality of requested events based at least in part on the first path through the directed acyclic graph.

25 . The computer-implemented method of claim 24 , wherein determining, by the one or more computing devices, a first path through the directed acyclic graph that results in the desired value of the utilization function and that does not violate any of the one or more constraints comprises:
checking, by the one or more computing devices, for constraint violations at each node within the first path prior to inclusion of such node within the first path; and removing, by the one or more computing devices, any nodes from the directed acyclic graph upon detecting that inclusion of such node within the first path would violate any of the one or more constraints.

26 . The computer-implemented method of claim 24 , further comprising:
obtaining, by the one or more computing devices, priority information for the plurality of requested events, wherein the priority information describes a weight for each of the plurality of requested events; wherein the utilization function outputs a score for an input path, the score for the input path comprising a sum of the weights of the requested events that correspond to nodes traversed by input path.

27 . A satellite scheduling system, comprising:
one or more processors; and at least one non-transitory computer-readable medium that stores instructions that when executed by the one or more processors cause the satellite scheduling system to:
obtain data that describes a plurality of requested events, wherein each requested event comprises at least one task to be performed by at least one of a plurality of satellites;
identify one or more constraints associated with at least one of the plurality of events and the plurality of satellites, wherein the one or more constraints comprise at least one of one or more pair-wise constraints and one or more cumulative constraints; and
determine a schedule for the plurality of satellites to perform the plurality of requested events, wherein the schedule does not violate any of the one or more constraints.

28 . The satellite scheduling system of claim 27 , wherein execution of the instructions by the one or more processors further causes the satellite scheduling system to:
obtain priority information for the plurality of requested events, wherein the priority information describes a weight for each of the plurality of requested events; wherein the satellite scheduling system determines the schedule based at least in part on the priority information, such that events with relatively larger weights are selected for performance in favor of events with relatively smaller weights.

29 . The satellite scheduling system of claim 27 , wherein to determine the schedule, execution of the instructions by the one or more processors causes the satellite scheduling system to:
build a directed acyclic graph that represents the plurality of requested events; and perform at least one graph search technique on the directed acyclic graph to determine the schedule for the plurality of satellites to perform the plurality of requested events.

30 . The satellite scheduling system of claim 29 , wherein to perform the at least one graph search technique, execution of the instructions by the one or more processors causes the satellite scheduling system to maximize a utilization function.

31 . The satellite scheduling system of claim 29 , wherein to perform the at least one graph search technique, execution of the instructions by the one or more processors causes the satellite scheduling system to:
identify at least one event transition that results in a violation of at least one of the one or more constraints; and in response to identifying the at least one event transition that results in the violation, remove the at least one event transition from the directed acyclic graph as soon as the violation is identified.

32 . The satellite scheduling system of claim 29 , wherein to perform the at least one graph search technique, execution of the instructions by the one or more processors causes the satellite scheduling system to identify a path through the directed acyclic graph that does not violate any of the one or more constraints.

33 . The satellite scheduling system of claim 27 , wherein the plurality of satellites comprise a constellation of imaging satellites, and wherein each requested event comprises at l

Assignees

• Google Inc

Inventors

• Augenstein Sean
• Mann Julian M
• Berkenstock Daniel

Classifications

• B64G1/242

  Orbits and trajectories · CPC title

• G06Q10/06314 Primary

  Calendaring for a resource · CPC title

• B64G1/1085

  Swarms and constellations · CPC title

• B64G1/1021

  Earth observation satellites · CPC title

• G06F16/29

  Geographical information databases · CPC title