We describe the development of the Spaceport Throughput Analysis Resource (STAR), which evaluates Kennedy Space Center spaceport launch throughput. STAR integrates simulation and limited rescheduling, using a constraint programming model to check constraints and reschedule events. The outputs of STAR are launch delays, and the constraint violations leading to those delays, that can be used to inform infrastructure investments to reduce future delays. At STAR's core is a constraint program representing a limited horizon scheduling problem used to identify resource constraint violations, and revise schedules in the presence of unexpected events that disrupt the launch schedule. We describe the design and implementation of STAR using illustrative examples, and describe performance results on use cases showing how increased launch rates stress KSC infrastructure.

Behind the scenes of a remote sensing mission there are complex decision making and planning operations. Streamlining these operations, with a quantitative scientific value framework, aids efficient and optimized science data collection. While there have been previous efforts to quantify the science value for specific science scenarios, our work aims to develop a general framework which can be applied across different scenarios. We describe a pipeline of processes which combines model forecast and observation data, in computational forms, as dictated by the mission objectives set forth by subject matter experts. The framework is described with use cases involving the monitoring of nitrogen dioxide (NO2) concentrations over the Gulf of Mexico and methane concentrations over interior Alaska.

Scheduling under uncertainty is an area of interest in artificial intelligence. We study the problem of Dynamic Controllability (DC) of Disjunctive Temporal Networks with Uncertainty (DTNU), which seeks a reactive scheduling strategy to satisfy temporal constraints in response to uncontrollable action durations. We introduce new semantics for reactive scheduling: Time-based Dynamic Controllability (TDC) and a restricted subset of TDC, R-TDC. We present a tree search approach to determine whether or not a DTNU is R-TDC. Moreover, we leverage the learning capability of a Graph Neural Network (GNN) as a heuristic for tree search guidance. Finally, we conduct experiments on a known benchmark on which we show R-TDC to retain significant completeness with regard to DC, while being faster to prove. This results in the tree search processing fifty percent more DTNU problems in R-TDC than the state-of-the-art DC solver does in DC with the same time budget. We also observe that GNN tree search guidance leads to substantial performance gains on benchmarks of more complex DTNUs, with up to eleven times more problems solved than the baseline tree search.

Recent work suggests to explain trade-offs between soft-goals in terms of their conflicts, i.e., minimal unsolvable soft-goal subsets. But this does not explain the conflicts themselves: Why can a given set of soft-goals not be jointly achieved? Here we approach that question in terms of the underlying constraints on plans in the task at hand, namely resource availability and time windows. In this context, a natural form of explanation for a soft-goal conflict is a minimal constraint relaxation under which the conflict disappears (``if the deadline was 1 hour later, it would work''). We explore algorithms for computing such explanations. A baseline is to simply loop over all relaxed tasks and compute the conflicts for each separately. We improve over this by two algorithms that leverage information -- conflicts, reachable states -- across relaxed tasks. We show that these algorithms can exponentially outperform the baseline in theory, and we run experiments confirming that advantage in practice.

Probabilistic Simple Temporal Networks (PSTN) are used to represent scheduling problems under uncertainty. In a temporal network that is Strongly Controllable (SC) there exists a concrete schedule that is robust to any uncertainty. We solve the problem of determining Chance Constrained PSTN SC as a Joint Chance Constrained optimisation problem via column generation, lifting the usual assumptions of independence and Boole's inequality typically leveraged in PSTN literature. Our approach offers on average a 10 times reduction in cost versus previous methods.

We describe a suite of scalable software methods and frameworks to helps schedule payload operations of a large constellation, with multiple payloads per and across spacecraft, such that the collection of observational data and their downlink, constrained by the constellation constraints (orbital mechanics), resources (e.g., power) and subsystems (e.g., attitude control), results in maximum science value for a selected use case. Constellation topology, spacecraft and ground network characteristics can be imported from design tools or existing constellations and can serve as elements of an operations design tool. Our framework includes a science simulator to inform the scheduler of the predictive value of observations or operational decisions. Autonomous, realtime re-scheduling based on past observations needs improved data assimilation methods within the simulator.

The problem of compiling general quantum algorithms for implementation on near-term quantum processors has been introduced to the AI community. Previous work demonstrated that temporal planning is an attractive approach for part of this compilationtask, specifically, the routing of circuits that implement the Quantum Alternating Operator Ansatz (QAOA) applied to the MaxCut problem on a quantum processor architecture. In this paper, we extend the earlier work to route circuits that implement QAOA for Graph Coloring problems. QAOA for coloring requires execution of more, and more complex, operations on the chip, which makes routing a more challenging problem. We evaluate the approach on state-of-the-art hardware architectures from leading quantum computing companies. Additionally, we apply a planning approach to qubit initialization. Our empirical evaluation shows that temporal planning compares well to reasonable analytic upper bounds, and that solving qubit initialization with a classical planner generally helps temporal planners in finding shorter-makespan compilations for QAOA for Graph Coloring. These advances suggest that temporal planning can be an effective approach for more complex quantum computing algorithms and architectures.

D-SHIELD is a suite of scalable software tools that helps schedule payload operations of a large constellation, with multiple payloads per and across spacecraft, such that the collection of observational data and their downlink, constrained by the constellation constraints (orbital mechanics), resources (e.g., power) and subsystems (e.g., attitude control), results in maximum science value for a selected use case. Constellation topology, spacecraft and ground network characteristics can be imported from design tools or existing constellations and can serve as elements of an operations design tool. D-SHIELD will include a science simulator to inform the scheduler of the predictive value of observations or operational decisions. Autonomous, realtime re-scheduling based on past observations needs improved data assimilation methods within the simulator.

We investigate the application of temporal planners to the problem of compiling quantum circuits to emerging quantum hardware. While our approach is general, we focus our initial experiments on Quantum Approximate Optimization Algorithm (QAOA) circuits that have few ordering constraints and thus allow highly parallel plans. We report on experiments using several temporal planners to compile circuits of various sizes to a realistic hardware architecture. This early empirical evaluation suggests that temporal planning is a viable approach to quantum circuit compilation.

An effective approach to solving complex problems is to decompose them and integrate dedicated solvers for those subproblems. We introduce a hybrid decomposition that incorporates: (1) a quantum annealer that samples from the configuration space of a relaxed problem to obtain strong candidate solutions, and (2) a classical processor that maintains a global search tree and enforces constraints on the relaxed components of the problem. Our framework is the first to use quantum annealing as part of a complete search. We consider variants of our approach with differing amounts of guidance from the quantum annealer. We empirically test our algorithm and compare the variants on problems from three scheduling domains: graph-coloring-type scheduling, simplified Mars Lander task scheduling, and airport runway scheduling. While we were only able to test on problems of small sizes, due to the limitation of currently available quantum annealing hardware, the empirical results show that results obtained from the quantum annealer can be used for more effective search node pruning and to improve node selection heuristics when compared to a standard classical approach.

There are two complementary ways to evaluate planning algorithms: performance on benchmark problems derived from real applications and analysis of performance on parametrized families of problems with known properties. Prior to this work, few means of generating parametrized families of hard planning problems were known. We generate hard planning problems from the solvable/unsolvable phase transition region of well-studied NP-complete problems that map naturally to navigation and scheduling, aspects common to many planning domains. We observe significant differences between state-of-the-art planners on these problem families, enabling us to gain insight into the relative strengths and weaknesses of these planners. Our results confirm exponential scaling of hardness with problem size, even at very small problem sizes. These families provide complementary test sets exhibiting properties not found in existing benchmarks.

This paper presents a novel multi-agent reactive execution model that keeps track of the execution of an agent to recover from incoming failures. It is a domain-independent execution model, which can be exploited in any planning control application, embedded into a more general multi-agent planning framework. The multi-agent reactive execution model provides a mechanism allowing an agent to respond to failures that prevent completion of a task when another agent is not able to repair the failure by itself. The model exploits the reactive planning capabilities of agents to come up with a solution at runtime, thus preventing agents from having to resort to replanning. We show the application of the proposed model for the control of multiple autonomous space vehicles.

Mission planning is central to space mission operations, and has benefited from advances in model-based planning software. A model is a description of the objects, actions, constraints and preferences that the planner reasons over to generate plans. Developing, verifying and validating a planning model is, however, a difficult task. Mission planning constraints and preferences arise from many sources, including simulators and engineering specification documents. As mission constraints evolve, planning domain modelers must add and update model constraints efficiently using the available source data, catching errors quickly, and correcting the model. The consequences of erroneous models are very high, especially in the space operations environment. We first describe the space operations environment, particularly the role of the mission planning system. We then describe model-based planning, and briefly review the current state of the practice in designing model-based mission planning tools and the challenges facing model developers. We then describe an Interactive Model Development Environment (IMDE) approach to developing mission planning systems. This approach integrates modeling and simulation environments to reduce model editing time, generate simulations automatically to evaluate plans, and identify modeling errors automatically by evaluating simulation output. The IMDE approach was tested on a small subset of the Lunar Atmosphere and Dust Environment Explorer (LADEE) flight software to demonstrate how to develop the LADEE mission planning system.

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.

Automated planning is a combinatorial problem that is important to many NASA endeavors, including ground operations and control applications for unmanned and manned space flight. There is significant value to integrating planning and data mining to create better planners. We describe current work in this area, covering uses of data mining to speed up planners, improve the quality of plans returned by planners, and learn domain models for automated planners. The central contribution of this paper is a snap shot of the state of the art in integrating these technologies and a summary of challenges and open research issues

Scheduling astronomy observations for the Strato- spheric Observatory for Infrared Astronomy (SOFIA) requires assessing tradeoffs between the percentage of scheduled obser- vations, the Line Of Sight Water Vapor (LOS-WV) achieved on those observations, and fuel consumption. This trade space is complex, depending on time of year and specific mixes of observations, and cannot be effectively analyzed by hand. We demonstrate the complexity of these tradeoffs and show that an Automated Flight Planner (AFP) is a crucial part of trade space analysis during flight planning. The Stratospheric Observatory for Infrared Astronomy (SOFIA) is NASA's next generation airborne astronomical observatory. The facility consists of a 747-SP modified to accommodate a 2.5 meter telescope. SOFIA is expected to fly an average of 140 science flights per year over its 20 year lifetime, and will commence operations in early 2005. The SOFIA telescope is mounted aft of the wings on the port side of the aircraft and is articulated through a range of 20 ◦ to 60 ◦ of elevation. A significant problem in future SOFIA operations is that of scheduling Facility Instrument (FI) flights in support of the SOFIA General Investigator (GI) program. GIs are expected to propose small numbers of observations, and many observations must be grouped together to make up single flights. Approximately 70 GI flight per year are expected, with 5-15 observations per flight.

We explore an optical network architecture which employs dense wavelength division multiplexing (WDM) technology and passive waveguide grating routers (WGRs) to establish a virtual topology based on lightpath communication. We examine the motivation and the technical challenges involved in this approach, propose and examine the characteristics of a network design algorithm, and provide some illustrative performance results.

Local search algorithms for combinatorial search problems frequently encounter a sequence of states in which it is impossible to improve the value of the objective function; moves through these regions, called plateau moves, dominate the time spent in local search. We analyze and characterize plateaus for three different classes of randomly generated Boolean Satisfiability problems. We identify several interesting features of plateaus that impact the performance of local search algorithms. We show that local minima tend to be small but occasionally may be very large. We also show that local minima can be escaped without unsatisfying a large number of clauses, but that systematically searching for an escape route may be computationally expensive if the local minimum is large. We show that plateaus with exits, called benches, tend to be much larger than minima, and that some benches have very few exit states which local search can use to escape. We show that the solutions (i.e., global minima) of randomly generated problem instances form clusters, which behave similarly to local minima. We revisit several enhancements of local search algorithms and explain their performance in light of our results. Finally we discuss strategies for creating the next generation of local search algorithms.