Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.stsci.edu/institute/conference/iwpss/plenary-b2-commentary-bianchessi.pdf Дата изменения: Tue Mar 20 17:47:28 2012 Дата индексирования: Tue Feb 5 12:50:42 2013 Кодировка: Поисковые слова: trapezium

Commentary on: A Mathematical Programming Algorithm for Planning and Scheduling an Earth Observing SAR Constellation, by Nicola Bianchessi and Giovanni Righini
David Kortenkamp
TRACLabs Inc. at NASA Johnson Space Center ER2 Houston Texas 77058 kortenkamp@jsc.nasa.gov

Introduction
This paper describes a method for scheduling observations by earth-observing satellites. The underlying problem is translated into a directed acyclic graph for each satellite. Each arc in the graph has a profit related to the value associated with an image. Each arc of the graph also represents the constraints of the problem, including memory, time and orbits. The scheduling problem is solved by representing the problem such that it is a shortest path problem with resource constraints (SPPRC). Since each satellite is independent their solutions can be found independently. The authors discuss simplifying the problem to an "almost feasible solution" in which some constraints are relaxed. This produces a smaller set of possible answers that can lend themselves to further reduction with heuristic techniques. The approach discussed in the paper is interesting and innovative. I want to use my commentary to challenge the authors to find other space scheduling problems that can use the same or similar techniques. I'd like the authors' ideas on how suitable their approach is to these other problems and what extensions they might have to make to their approach.

Robotics
Robotics researchers have a long history of solving shortest path problems in order to determine the most efficient way (with respect to time, fuel, coverage, etc.) to move a robot around its environment. Some of these techniques include Voronoi Diagrams (Choset & Burdick 1995), Monte Carlo techniques (Barraquand & Latombe 1990) and various graph-based techniques that are similar to this paper (e.g., D* (Stentz 1995). Robotics has both similar problems to satellite scheduling (i.e., finding an optimal tra jectory through a known space with fixed waypoints) and differences (i.e., greater uncertainty in robot position and environment). Could similar techniques as described in the paper be used to solve robot scheduling problems, particilarly visiting a series of ob jects that need to be imaged/grabbed/examined? Would the approach in the paper be more effective than approaches that are currently being used?

Crew scheduling
Crew members' time on-board a spacecraft is a scarce commodity. Scheduling their time is complicated further by constriants with respect to power and communication demands for certain tasks. As the number of crew members on ISS grows (hopefully to a full complement of six) the scheduling problem will also grow. Currently, crew scheduling is a fairly manual process with little help from automated algorithms (Korth & LeBlanc 2002). Is there a way to represent crew members as commodities and the tasks they need to perform has arcs in the graph with time, communication, etc. constraints on those arcs? Could the solutions in this paper help this problem? What are the challenges?

Earth observing satellite networks
This approach is a good start on scheduling earth observing satellites. However, the paper is clear that this approach has only been tested in cases where each satellite can be treated independently and are homogeneous. NASA is starting to explore using networks of earth observing satellites that would be heterogeneous (Prescott, Smith, & Moe 2001). In this case you may very well want to schedule two different satellites with two different kinds of sensors to image the same feature at the same time or for one to lag behind another a fixed amount of time. This would require a significantly more complicated graph, probably requiring connections between different commodity's graphs. Could this type of problem be solved by extensions to the approach the authors' propose? What would the challenges be?

Conclusion
The techniques in this interesting paper have many potential applications, as I have outlined in this commentary. I would encourage the authors to look at other domains. I would also like to see the authors compare their approach against other competing scheduling algorithms. For example, uncrewed spacecraft have started using on-board science scheduling algorithms to


decide autonomously what they should do (Muscettola et al. 1998; et al 2003). Can the algorithms described in the paper complement these? Are these algorithms the type of "heuristic" approaches talked about in the paper? How can we best combine different types of scheduling algorithms to achieve optimal performance ­ both in terms of the final schedule and the computational requirements necessary to produce it?

References
Barraquand, J., and Latombe, J. 1990. A Monte-Carlo Algorithm for Path Planning with Many Degrees of Freedom. In IEEE Conference on Robotics and Automation, 1712­1717. Choset, H., and Burdick, J. 1995. Sensor Based Planning, Part I: The Generalized Voronoi Graph. In Proc. IEEE Int. Conf. on Robotics and Automation. et al, S. C. 2003. Autonomous science on the eo-1 mission. In Proceedings of International Symposium on Artificial Intel ligence Robotics and Automation in Space (i-SAIRAS). Korth, D., and LeBlanc, T. 2002. International space station alpha operations planning. In Proceedings of the 3rd International NASA Workshop on Planning and Scheduling for Space (available from The Institute for Advanced Interdisciplinary Research Houston Texas). Muscettola, N.; Nayak, P. P.; Pell, B.; and Williams, B. C. 1998. Remote Agent: to boldly go where no AI system has gone before. Artificial Intel ligence 103(1). Prescott, G.; Smith, S.; and Moe, K. 2001. Information system technology challenges for nasa's earth science enterprise. In Proceedings of the IEEE Geoscience and Remote Sensing Symposium (IGARSS). Stentz, A. 1995. Optimal and efficient path planning for unknown and dynamic environments. International Journal of Robotics and Automation 10.