Sudhakar Y. Reddy
Abstract
Flight controllers manage the orientation and modes of eight large solar arrays that power the International Space Station (ISS). The task requires generating plans that balance complex constraints and preferences. These considerations include context-dependent constraints on viable solar array configurations, temporal limits on transitions between configurations, and preferences on which considerations have priority. The Solar Array Constraint Engine (SACE) treats this operations planning problem as a sequence of tractable constrained optimization problems. SACE uses constraint management and automated planning capabilities to reason about the constraints, to find optimal array configurations subject to these constraints and solution preferences, and to automatically generate solar array operations plans. SACE further provides flight controllers with real-time situational awareness and what-if analysis capabilities. SACE is built on the Extensible Universal Remote Operations Planning Architecture (EUROPA) model-based planning system. EUROPA facilitated SACE development by providing model-based planning, built-in constraint reasoning capability, and extensibility. This article formulates the planning problem, explains how EUROPA solves the problem, and provides performance statistics from several planning scenarios. SACE reduces a highly manual process that takes weeks to an automated process that takes tens of minutes.
- Bresina, J., Jónsson, A., Morris, P., and Rajan, K. 2005. Activity planning for the Mars exploration rovers. In Proceedings of the 15th International Conference on Automated Planning and Scheduling. S. Biundo et al. Eds., AAAI, Menlo Park, CA, 40--49.Google Scholar
- Cesta, A., Cortellessa, G., Fratini, S., and Oddi, A. 2009. Developing an end-to-end planning application from a timeline representation framework. In Proceedings of the 21st Innovative Application of Artificial Intelligence Conference.Google Scholar
- Cesta, A., Cortellesa, G., Denis, M., Donati, A., Fratini, S., Oddi, A., Policella, N., Rabenau, E., and Schulster, J. 2007. MEXAR2: AI solves mission planner problems. IEEE Intell. Syst. 22, 12--19. Google ScholarDigital Library
- Chien, S., Rabideau, G., Knight, R., Sherwood, R., Engelhardt, B., Mutz, D., Estlin, T., Smith, B., Fisher, F., Barret, T., Stebbins, G., and Tran, D. 2000. ASPEN---Automated planning and scheduling for space missions operations. In Proceedings of the International Conference on Space Operations.Google Scholar
- Chien, S., Tran, D., Rabideau, G., Schaffer, S., Mandl, D., and Frye, S. 2010. Timeline-Based space operations scheduling with external constraints. In Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS'10). R. Brafman et al. Eds., AAAI, Menlo Park, CA, 34--41.Google Scholar
- Chouinard, C., Knight, R., Jones, G., Tran, D., and Koblick, D. 2008. Automated and adaptive mission planning for orbital express. In Proceedings of the SpaceOps‘08 Conference.Google Scholar
- Do, M. B., Ruml, W., and Zhou, R. 2008. Planning for modular printers: Beyond productivity. In Proceedings of the 18th International Conference on Automated Planning and Scheduling. J. Rintanen et al. Eds., AAAI, Menlo Park, CA, 68--75.Google Scholar
- Frank, J. and Jónsson, A. 2003. Constraint-Based attribute and interval planning. J. Constraints 8, 4, 339--364. Google ScholarDigital Library
- Fratini, S., Pecora, F., and Cesta, A. 2008. Unifying planning and scheduling as timelines in a component-based perspective. Archiv. Control Sci. 18, 2, 231--271.Google Scholar
- Freuder, E. 1982. A sufficient condition for backtrack free search. J. ACM 29, 1, 755--761. Google ScholarDigital Library
- Gerevini, A., Haslum, P., Long, D., Saetti, A., and Dimopoulos, Y. 2009. Deterministic planning in the Fifth International Planning Competition: PDDL3 and experimental evaluation of the planners. Artif. Intell. 173, 619--668. Google ScholarDigital Library
- Ghallab, M. and Laruelle, H. 1994. Representation and control in IxTeT, a temporal planner. In Proceedings of the 2nd International Conference on AI Planning Systems. K. Hammond Ed., AAAI, Menlo Park, CA, 61--67.Google Scholar
- Hoffmann, J. and Edelkamp, S. 2005. The deterministic part of IPC-4: An overview. J. Artif.Intell. Res. 24, 519--579. Google ScholarDigital Library
- Johnston, P. and Miller, G. 1994. SPIKE: Intelligent scheduling of hubble space telescope observations. In Intelligent Scheduling, Morgan Kauffmann, San Francisco, CA, 391--422.Google Scholar
- Jonsson, P. and Backstrom, C. 1998. State-Variable planning under structural restrictions: Algorithms and complexity. Artif. Intell. 100, 125--176. Google ScholarDigital Library
- Jónsson, A., Morris, P., Muscettola, N., Rajan, K., and Smith, B. 2000. Planning in interplanetary space: Theory and practice. In Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling. S. Chien et al. Eds., AAAI, Menlo Park, CA, 177--186.Google Scholar
- Knight, R., Schaffer. S., and Clement, B. 2009. Power planning in the international space station domain. In Proceedings of the 6th International Workshop on Planning and Scheduling for Space.Google Scholar
- Larrosa, J. and Dechter, R. 2003 Boosting search with variable elimination in constraint optimization and constraint satisfaction problems. J. Constraints 8, 3, 303--326. Google ScholarDigital Library
- Muscettola, N., Nayak, P., Pell, B., and Williams, B. 1998. Remote agent: To boldly go where no AI system has gone before. Artif. Intell. 103, 5--48. Google ScholarDigital Library
- Shriver, P., Gokhale, M., Briles, S., Kang, D., Cai, M., Mccabe, K., Crago, S., and Suh, J. 2002. A power-aware, satellite-based parallel signal processing scheme. In Power Aware Computing. R. Graybill and R. Melhem Eds., Springer. Google ScholarDigital Library
- Smith, B. D., Engelhardt, B. E., and Mutz, D. H. 2002. The RADARSAT-MAMM automated mission planner. AI Mag. 23, 2, 25--36.Google Scholar
- Stanley, J., Shendock, R., Witt, K., and Mandl, D. 2005. A model-based approach to controlling the ST-5 constellation lights out using the GMSEC message bus and Simulink. In Proceedings of the International Conference on Software Engineering Research and Practice. H. Arabnia and H. Reza Eds., CSREA Press, Las Vegas, NV, 29--35.Google Scholar
Index Terms
- Planning solar array operations on the international space station
Recommendations
Planning as constraint satisfaction: solving the planning graph by compiling it into CSP
The idea of synthesizing bounded length plans by compiling planning problems into a combinatorial substrate, and solving the resulting encodings has become quite popular in recent years. Most work to-date has however concentrated on compilation to ...
Introduction to planning, scheduling and constraint satisfaction
AbstractPlanning, scheduling and constraint satisfaction are important areas in artificial intelligence (AI). Many real-world problems are known as AI planning and scheduling problems, where resources must be allocated so as to optimize overall ...
Constraint satisfaction for planning and scheduling problems
The areas of planning and scheduling (from the Artificial Intelligence point of view) have seen important advances thanks to application of constraint satisfaction techniques. Currently, many important real-world problems require efficient constraint ...
Comments