Engineering topics
Johnston, Mark
Publications and source records attributed to Johnston, Mark.
Utilizing Schedule Constraints to Improve Automated Scheduling in NASA's Deep Space Network
NASA’s Deep Space Network (DSN) is a mission critical facility that supports many different space missions,from LEO to deep space exploration. In recent years, as the network has suffered from increasing oversubscription, more restrictions have been added to reduce the amount of manual scheduling labor necessary to come to consensus. In this paper, we describe a new auto-mated scheduling tool which takes advantage of these restrictions to bring the scheduling problem closer to feasibility. In addition, we describe an algorithm to reduce problem inputs given a partially-solved problem,thereby bringing the problem even closer to feasibility
Towards Automated Scheduling of NASA’s Deep Space Network: A Mixed Integer Linear Programming Approach
No abstract provided
Integrating Space Communication Network Capabilities via Web Portal Technologies
No abstract available
Experiments with a Parallel Multi-Objective Evolutionary Algorithm for Scheduling
No abstract available
Automating Mid- and Long-range Scheduling for NASA's Deep Space Network
No abstract available
A Generalized Timeline Representation, Services, and Interface for Automating Space Mission Operations
Most use a timeline based representation for operations modeling. Most model a core set of state, resource types. Most provide similar capabilities on this modeling to enable (semi) automated schedule generation. In this paper we explore the commonality of : representation and services for these timelines. These commonalities offer potential to be harmonized to enable interoperability, re-use.
A Generalized Timeline Representation, Services, and Interface for Automating Space Mission Operations
Numerous automated and semi-automated planning & scheduling systems have been developed for space applications. Most of these systems are model-based in that they encode domain knowledge necessary to predict spacecraft state and resources based on initial conditions and a proposed activity plan. The spacecraft state and resources as often modeled as a series of timelines, with a timeline or set of timelines to represent a state or resource key in the operations of the spacecraft. In this paper, we first describe a basic timeline representation that can represent a set of state, resource, timing, and transition constraints. We describe a number of planning and scheduling systems designed for space applications (and in many cases deployed for use of ongoing missions) and describe how they do and do not map onto this timeline model.
Integrated Planning for Telepresence With Time Delays
A conceptual "intelligent assistant" and an artificial-intelligence computer program that implements the intelligent assistant have been developed to improve control exerted by a human supervisor over a robot that is so distant that communication between the human and the robot involves significant signal-propagation delays. The goal of the effort is not only to help the human supervisor monitor and control the state of the robot, but also to improve the efficiency of the robot by allowing the supervisor to "work ahead". The intelligent assistant is an integrated combination of an artificial-intelligence planner and a monitor of states of both the human supervisor and the remote robot. The novelty of the system lies in the way it uses the planner to reason about the states at both ends of the time delay. The purpose served by the assistant is to provide advice to the human supervisor about current and future activities, derived from a sequence of high-level goals to be achieved.
DSN Scheduling Engine
The DSN (Deep Space Network) Scheduling Engine targets all space missions that use DSN services. It allows clients to issue scheduling, conflict identification, conflict resolution, and status requests in XML over a Java Message Service interface. The scheduling requests may include new requirements that represent a set of tracks to be scheduled under some constraints. This program uses a heuristic local search to schedule a variety of schedule requirements, and is being infused into the Service Scheduling Assembly, a mixed-initiative scheduling application. The engine resolves conflicting schedules of resource allocation according to a range of existing and possible requirement specifications, including optional antennas; start of track and track duration ranges; periodic tracks; locks on track start, duration, and allocated antenna; MSPA (multiple spacecraft per aperture); arraying/VLBI (very long baseline interferometry)/delta DOR (differential one-way ranging); continuous tracks; segmented tracks; gap-to-track ratio; and override or block-out of requirements. The scheduling models now include conflict identification for SOA(start of activity), BOT (beginning of track), RFI (radio frequency interference), and equipment constraints. This software will search through all possible allocations while providing a best-effort solution at any time. The engine reschedules to accommodate individual emergency tracks in 0.2 second, and emergency antenna downtime in 0.2 second. The software handles doubling of one mission's track requests over one week (to 42 total) in 2.7 seconds. Further tests will be performed in the context of actual schedules.
Lights Out Operations of a Space, Ground, Sensorweb
We have been operating an autonomous, integrated sensorweb linking numerous space and ground sensors in 24/7 operations since 2004. This sensorweb includes elements of space data acquisition (MODIS, GOES, and EO-1), space asset retasking (EO-1), integration of data acquired from ground sensor networks with on-demand ground processing of data into science products. These assets are being integrated using web service standards from the Open Geospatial Consortium. Future plans include extension to fixed and mobile surface and subsurface sea assets as part of the NSF's ORION Program.
Improved CLARAty Functional-Layer/Decision-Layer Interface
Improved interface software for communication between the CLARAty Decision and Functional layers has been developed. [The Coupled Layer Architecture for Robotics Autonomy (CLARAty) was described in Coupled-Layer Robotics Architecture for Autonomy (NPO-21218), NASA Tech Briefs, Vol. 26, No. 12 (December 2002), page 48. To recapitulate: the CLARAty architecture was developed to improve the modularity of robotic software while tightening coupling between planning/execution and basic control subsystems. Whereas prior robotic software architectures typically contained three layers, the CLARAty contains two layers: a decision layer (DL) and a functional layer (FL).] Types of communication supported by the present software include sending commands from DL modules to FL modules and sending data updates from FL modules to DL modules. The present software supplants prior interface software that had little error-checking capability, supported data parameters in string form only, supported commanding at only one level of the FL, and supported only limited updates of the state of the robot. The present software offers strong error checking, and supports complex data structures and commanding at multiple levels of the FL, and relative to the prior software, offers a much wider spectrum of state-update capabilities.
Minimizing conflicts: A heuristic repair method for constraint-satisfaction and scheduling problems
This paper describes a simple heuristic approach to solving large-scale constraint satisfaction and scheduling problems. In this approach one starts with an inconsistent assignment for a set of variables and searches through the space of possible repairs. The search can be guided by a value-ordering heuristic, the min-conflicts heuristic, that attempts to minimize the number of constraint violations after each step. The heuristic can be used with a variety of different search strategies. We demonstrate empirically that on the n-queens problem, a technique based on this approach performs orders of magnitude better than traditional backtracking techniques. We also describe a scheduling application where the approach has been used successfully. A theoretical analysis is presented both to explain why this method works well on certain types of problems and to predict when it is likely to be most effective.
Long range science scheduling for the Hubble Space Telescope
Observations with NASA's Hubble Space Telescope (HST) are scheduled with the assistance of a long-range scheduling system (SPIKE) that was developed using artificial intelligence techniques. In earlier papers, the system architecture and the constraint representation and propagation mechanisms were described. The development of high-level automated scheduling tools, including tools based on constraint satisfaction techniques and neural networks is described. The performance of these tools in scheduling HST observations is discussed.
Spike: Artificial intelligence scheduling for Hubble space telescope
Efficient utilization of spacecraft resources is essential, but the accompanying scheduling problems are often computationally intractable and are difficult to approximate because of the presence of numerous interacting constraints. Artificial intelligence techniques were applied to the scheduling of the NASA/ESA Hubble Space Telescope (HST). This presents a particularly challenging problem since a yearlong observing program can contain some tens of thousands of exposures which are subject to a large number of scientific, operational, spacecraft, and environmental constraints. New techniques were developed for machine reasoning about scheduling constraints and goals, especially in cases where uncertainty is an important scheduling consideration and where resolving conflicts among conflicting preferences is essential. These technique were utilized in a set of workstation based scheduling tools (Spike) for HST. Graphical displays of activities, constraints, and schedules are an important feature of the system. High level scheduling strategies using both rule based and neural network approaches were developed. While the specific constraints implemented are those most relevant to HST, the framework developed is far more general and could easily handle other kinds of scheduling problems. The concept and implementation of the Spike system are described along with some experiments in adapting Spike to other spacecraft scheduling domains.