A CONSTRAINT-BASED APPROACH TO TASK SCHEDULING FOR OBSERVING SATELLITES

摘要

Task scheduling for observing satellites is a problem of optimally assigning resources (observing satellites, ground stations, etc.) and executing times to satellite observing tasks (observations, downlinks, etc.). The problem has some specific features that make it more difficult than other scheduling problems. For example, observing satellites have limited short opportunities (the visible time-windows) for imaging a given target area; the real problem often involves multiple satellites, hundreds of tasks, and many complex constraints including non-linear and logic ones; furthermore, it is often over-constrained. For these reason, the satellite scheduling problem can hardly be dealt with mathematical programming, except that we made some unpractical assumptions. While in some industrial scheduling systems, an approach as constraint-based scheduling are well used. Its main idea is to model scheduling problems as a class of CSPs, and to solve them by using constraint programming (CP) techniques rooting in AI. Its most advantage is the ability to model scheduling problems and their complex constraints naturally and easily, in addition, there exist a set of mature constraint reasoning and constraint solving algorithms for choose. In this paper, we discuss how to solve the task scheduling problem for observing satellites using constraint-based scheduling approach. We describe the problem modeling process and lay emphasis on the method to handle those specific features of satellite scheduling problems. Finally, we give a demonstrational example to test our approach. The result shows that although the solution is not the optimal one, it is a satisfactory one. It do avoid the resource using conflict and those tasks with high priority are scheduled first.