The Satellite Mission Scheduling problem with Dynamic Tasking (SMS-DT) involves scheduling tasks for a satellite, where new task requests can arrive at any time, non-deterministically, and must be scheduled in real-time. The schedule is a time ordered sequence of activities (scheduled tasks) to be performed by the payload of a satellite. Each activity has a start time and duration. The duration of an activity is a function of its start time: it can be calculated based on such factors as target size, task type, and geometry (between target and satellite, or due to lighting conditions). The transition time between activities is instantaneous, provided the targets lie within the field of view of the payload.
In addition, the Satellite Mission Scheduling problem is priority based: a lower priority task should not adversely impact a higher priority task. A lower priority activity could cause a higher priority activity move to a new location on the schedule, but cannot bump the higher priority activity off of the schedule. However, a higher priority activity could bump a lower priority activity off of the schedule in order for it to get on the schedule. A priority of 0 (zero) is highest and a priority of 999 is lowest. Given a choice, it is preferable to complete a task as early as possible.
I have researched on monotonic algorithm and genetic algorithm. I would like to know what other algorithms are used in the past for this problem. And what are the pros and cons of them? Why do we still need to find or develop new or hybrid algorithm for this problem? Thank you.
1. I would like to know what other algorithms are used in the past for this problem. And what are the prosand cons of them?
a. Mathematical or Heuristic Algorithm Existing methods for scheduling activities under resource constraints have been using either mathematical programming or heuristic approaches. The former approach produces optimal schedules but suffers from combinatorial explosion so that solution time escalates exponentially as the number of activities increases. In practical size problems, heuristic methods are used which employ pre-determined priority rules to schedule activities, but they do not guarantee optimality.
b. Genetic Algorithm (GA) A new approach has been developed which overcomes the present drawbacks. The model, called the GA-Scheduler, is based on genetic algorithm (GA) which try to simulate, in an artificial system, the principles of evolution and adaptation occurring in nature. Through several cycles of evaluation, selection and recombination, the model is able to evolve good solutions within a very short time.
c. Others Algorithms in past research or proposed research on this problem see http://www-math.cudenver.edu/~billups/courses/ma5779/problem.html (attached for convenience). The goal of this research effort is the creation of an algorithm to determine an optimal or near-optimal sequence of tasks, allocated to a satellite payload over (discrete) time, with dynamic tasking considerations. Moving from a constraint-based algorithm-scheduling model http://www-2.cs.cmu.edu/afs/cs/project/ozone/www/PCP/integrated-ps.html to a new model see http://www-2.cs.cmu.edu/afs/cs/project/ozone/www/PCP/pcp.html.
d. Others Algorithms in past research For a fairly exhaustive literature review of past research and types of algorithms employed see http://www-math.cudenver.edu/~billups/courses/ma5779/papers/SatelliteTaskScheduling.pdf.
-For example, Bensana, et al extends their Multi-dimensional Knapsack to account for the uncertainties associated with cloud cover (p.2).
- Muraoka et al describes a simple greedy approach for scheduling subsets of tasks selected on the basis of priority (p. 3.)
e. Enumeration Algorithm see page 10 http://www-math.cudenver.edu/~billups/courses/ma5779/papers/SatelliteTaskScheduling.pdf. See results of the study starting on page 11 of the same.
f. Science algorithms
Since the dawn of the space age, unmanned spacecraft have flown blind with little or no ability to make autonomous decisions based on the content of the data they collect. The Autonomous Sciencecraft Experiment (ASE) will fly onboard the Earth Orbiter 1 mission in 2003. The ASE software uses onboard continuous planning, robust task and goal-based execution, and onboard machine learning and pattern recognition to radically increase science return by enabling intelligent downlink selection and autonomous retargeting. This software will demonstrate the potential for space missions to use onboard decision-making to detect, analyze, and respond to science events, and to downlink only the highest value science data. The ASE onboard flight software includes several autonomy software components:
Onboard science algorithms that will analyze the image data to detect trigger conditions such as science events, interesting features, changes relative to previous observations, and cloud detection for onboard image editing.
The onboard science algorithms will analyze the images to extract static features and detect changes relative to previous observations. Prototype software has already been demonstrated on EO-1 Hyperion data to automatically identify regions of interest including regions of change (such as flooding, ice melt, and lava flows). Using these algorithms onboard will enable retargeting and search, e.g., retargeting the instrument on a subsequent orbit cycle to identify and capture the full extent of a flood. On future interplanetary space missions, onboard science analysis will enable capture of short-lived science phenomena at the finest time-scales without overwhelming onboard memory or downlink capacities. Examples include: eruption of volcanoes on Io, formation of jets on comets, and phase transitions in ring systems. Generation of derived science products (e.g., boundary descriptions, catalogs) and change-based triggering will also reduce data volumes to a manageable level for extended duration missions that study ...
Referring to the problem, this solution (other than monotonic algorithm and genetic algorithm) discusses and provides information on other algorithms used in the past for this problem, including the pros and cons of them. It also explains why we still need to find or develop new or hybrid algorithm for this problem.