Abstract. The planning and scheduling of human space activities is an expensive and time-consuming task that seldom provides the crew with the control, flexibility, or insight that they need. During the past thirty years, scheduling software has seen only incremental improvements; however, software limitations continue to prevent even evolutionary improvements in the “operations concept” that is used for human space missions. Space missions are planned on the ground long before they are executed in space, and the crew has little input or influence on the schedule. In recent years the crew has been presented with a “job jar” of activities that they can do whenever they have time, but the contents of the jar is limited to tasks that do not use scarce shared resources and do not have external timing constraints. Consequently, the crew has no control over the schedule of the majority of their own tasks. As humans venture farther from earth for longer durations, it will become imperative that they have the ability to plan and schedule not only their own activities, but also the unattended activities of the systems, equipment, and robots on the journey with them. Significant software breakthroughs are required to enable the change in the operations concept. The crew does not have the time to build or modify the schedule by hand. They only need to issue a request to schedule a task and the system should automatically do the rest. Of course, the crew should not be required to build the complete schedule. Controllers on the ground should contribute the models and schedules where they have the better knowledge. The system must allow multiple simultaneous users, some on earth and some in space. The Mission Operations Laboratory at NASA’s Marshall Space Flight Center has been researching and prototyping a modeling schema, scheduling engine, and system architecture that can enable the needed paradigm shift – it can make the crew autonomous. This schema and engine can be the core of a planning and scheduling system that would enable multiple planners, some on the earth and some in space, to build one integrated timeline. Its modeling schema can capture all the task requirements; its scheduling engine can build the schedule automatically; and its architecture can allow those (on earth and in space) with the best knowledge of the tasks to schedule them. This paper describes the enabling technology and proposes an operations concept for astronauts autonomously scheduling their activities and the activities around them.
Mission planning for previous manned space programs, such as for the Space Shuttle and International Space Station, has typically involved extensive preflight mission planning along with real-time plan updates by a large cadre of mission planning experts. The onboard crew had minimal capabilities to update or maintain their own timelines in response to onboard events. This situation was largely driven by the limitations of the planning/scheduling software, onboard computing/storage capabilities, and the perception that onboard crew time was much too valuable to spend on plan maintenance. Given longer duration missions with communications delays, continuing improvements in technology, and the need to minimize the ground operations infrastructure, the time is ripe for a major paradigm shift in NASA’s mission planning philosophy. This paper proposes a significant paradigm shift in which the focus of planning is moved from a ground control center to a flight vehicle or a lunar/planetary base. This new planning paradigm has the potential to reduce ground operations costs while significantly increasing the ability of the onboard crew to manage their own time and respond quickly and effectively to real-time situations.
Why is a new planning paradigm needed for Lunar and Mars exploration? First of all, missions extending farther and farther from the earth will introduce progressively longer communications delays. Astronauts may not be able to rely on immediate information or assistance from the ground when faced with time-critical emergencies, other off-nominal situations, or even unexpected opportunities. The need for situational awareness with a robust ability to respond to and recover from real-time events becomes increasingly more important with ever increasing distance from the ground support infrastructure. A fundamental capability which the crew must be provided is the ability to manage, edit, and re-plan the onboard (vehicle or surface) timeline as necessary to maintain safe and effective operations.
These capabilities will be especially important given the anticipated complexity of the vehicle and surface systems in which humans, robots, and automated systems must function seamlessly as an integrated system-of-systems. Any crew-initiated changes to onboard timelines must consider the interactions and dependencies of all the underlying systems to ensure that the changes are feasible. Past programs allowed the crew to make simple timeline changes (e.g., delete a task, or add a “job jar” task) which did not require extensive resource or constraint checking. These capabilities will not be sufficient for the Exploration programs. The need for the onboard crew to perform more extensive re-planning also necessitates that they have the capabilities to verify their timeline changes with respect to onboard resource availabilities, system interdependencies, and other operating constraints.
Human factors issues must also be considered on long-duration manned missions. On short flights like those of the Space Shuttle, the activities of the crew are almost totally scheduled by the ground controllers. On the International Space Station (ISS), most activities are scheduled by the ground. On ISS, the astronauts are offered a “job jar” of discretionary activities from which they can choose when they have time. However the job jar content is very limited because it contains only optional activities and only those which use no other resources – this is long way from crew autonomy. Lack of crew planning autonomy has been a topic of discussion since the days of Skylab (Compton, 1983; Sherman, 1994; and Hagopian, 1998), and there is anecdotal consensus among astronauts that crew autonomy is a good way to mitigate the stress of long-duration missions. However, little progress has been made toward substantially increasing this autonomy in the past four decades of manned space flight. A mission to Mars will take more than two years, more than four times as long as current ISS missions.
This paper proposes an operations concept in which the focus of planning is moved from a ground control center to the flight vehicle or a lunar/planetary base itself. A graphical depiction of the concept is provided in Figure 1. Note that the scheduling system, most current timeline, and other associated data are located at the remote “extraterrestrial” site (e.g., exploration vehicle, lunar base) where the timeline is being executed. This architecture ensures that the astronauts will always have access to a complete set of up-to-date planning information, and that any changes they make are applied to the currently executing timeline.
FIGURE 1. Proposed Operations Concept.
However, this operations concept does not imply that the astronauts will be tasked with performing the entire mission planning job. Since crew time is extremely valuable, the prime task of developing and maintaining the baseline timeline will still fall on ground-based controllers. The level of astronaut participation in the planning process will be dictated by necessity (e.g., responding to real-time events) as well as by their personal preferences. In effect, the proposed architecture provides an infrastructure which allows multiple parties (crew, ground controllers, and even autonomous systems) to simultaneously contribute to the development/maintenance of a single timeline.
In this concept, Earth-based controllers will be responsible for collecting and entering into the scheduling system (a.k.a. “modeling”) the underlying information needed to build the timeline. This information includes resource availability predictions, flight trajectory information, equipment/system status, and other planning constraints. Examples of resources and constraints include shared equipment, electrical power, downlink bandwidth, thermal heat rejection, robotic systems, onboard computer resources, and consumables such as water, gases, or supplies. The earth-based planners will also work with other flight controllers, vehicle/systems experts, and payload providers to model the many “tasks” that must be scheduled on the timeline. If appropriate, they may also create an initial timeline for a future period of time. All this preliminary work can be performed on the ground and the results then uplinked to the extraterrestrial remote site, where the information becomes part of the data set associated with the currently active timeline.
 FIGURE 2. PDA Access. |
Once the planning information is within the scheduling system at the remote site, it will be available for use by the onboard crew. From a local console, the crew will be able to view/inspect their timelines, make timeline edits (e.g., move a task, delete a task), schedule additional “job jar” type tasks via an interface to the automatic scheduling engine, and even edit the modeled tasks (e.g., change a specified task duration). A PDA-type interface to the scheduling system might also be available to the crew; however, its capabilities would necessarily be more limited. Such an interface is depicted in Figure 2.
Earth-based controllers can also remotely access the onboard scheduling system to inspect/verify the most current timeline information or to contribute timeline changes. To preserve precious crew time, it is envisioned that most extensive re-planning efforts will be performed by the earth-based controllers, except in those cases where communications outages or delays preclude a timely ground response to a real-time event. The earth-based controllers may also perform simpler timeline edits at the crew’s request.
Providing the astronauts with the ability to manage the schedule will enable more autonomous crew/vehicle operations. Unlike today, the crew will be able to make a real-time schedule change and get immediate feedback that the change is feasible, thus supporting safe, reliable, and efficient crew operations.
The proposed concept can only be enabled by a new set of technologies. The keys to the technologies are a comprehensive modeling schema (for both tasks and resources) that represents all the constraints and an automatic scheduler that understands the models and produces a desired schedule. Other technologies that are required are a usable interface, a distributed architecture, timeline integration, and standard interfaces to the execution engines. Of course, these technologies must be implemented so as to be useable in the proposed operations concept; for example, the modeling schema and the modeling user interface must be usable by the astronauts.
The Mission Operation Laboratory at the Marshall Space Flight Center, which has over thirty years experience scheduling payload operations on manned space missions, recently undertook research into a new planning and scheduling technology to reduce the cost of planning and scheduling the operations of future space programs. This research showed that the key to reducing cost was to switch from manual scheduling to automatic scheduling. To date, all (for all nations and all missions) scheduling of tasks on human space flights has been done manually. There are many automatic schedulers which do a good job of handling the models designed for them; but the models can’t represent the complexity and interdependence of the tasks normally scheduled on human space flights. What is needed is a comprehensive modeling schema that can capture all the requirements quantitatively and a scheduling engine that can work with the models. Additionally the modeling schema must be easy to use – it must capture and represent the requirements in the way they are understood by those who know the requirements. These are also the prerequisites for a planning and scheduling system that will enable the proposed operations concept (Jaap & Davis, 2004).
To fulfill the needs indicated by this recent research, the Mission Operations Laboratory has developed a modeling schema that can capture all the requirements, the beginning of a scheduling engine that can automatically schedule the models (Jaap & Davis, 2004), and a remote-access (internet-based) architecture. Analysis of the resulting modeling schema and the scheduling engine indicates that they can enable the proposed planning paradigm. The modeling schema is discussed in the next section.
The necessary modeling schema is a synergy of technological advances and domain-specific innovations. To enable the operations concept proposed above, the modeling schema must capture all the requirements so that an automatic scheduler can function, and it must be easily used by various users including ground controllers and astronauts. Some of the key features of the proposed schema are given below (Jaap, Davis & Richardson, 2004):
Decomposition of the problem into salient components — Operations are decomposed into activities that define resource requirements and sequences that define relationships between activities. Sequences can also contain other sequences, repeated activities and sequences, and optional activities and sequences.
Activities define the resource requirements (with alternatives) and other quantitative constraints and requirements of the tasks to be performed. Activity requirements may be grouped into “all-of” groups or “one-of” groups. Groups may be hierarchical. For example: the housewife can use the oven or the stovetop to cook a roast; however, the duration would be different, and a different pan would be used (see Figure 3). Requirements include the specification of the minimum, maximum, and preferred duration of the activity.
Sequences define the temporal relationships between activities. Sequences may also define relationships with other sequences, as well as with events. A simple Thursday night sequence might be to have dinner, record a TV sitcom, help with homework, and watch the recording (see Figure 4). Temporal relationships include during, sequential, separated, overlap, standby, fragmentable, percent coverage, and (for repeated items) cyclic. Resource lock-in and one-to-one relationships are also included.
Graphical paradigms — Simple graphical paradigms such as outlines and networks are used to build and depict the models. Modeling itself is done using techniques such as drag-and-drop.
 FIGURE 3. Constraint Hierarchies. |
Hierarchies of groups of requirements best describe the constraints of most non-trivial activities. The outline paradigm is well-suited to modeling hierarchies of groups because it can be manipulated by a drag-and-drop interface and nested to any depth without ambiguity. Figure 3 compares two representations of the “cooking a roast” example; notice the similarity between the two. The implementation provides a list of predefined constraints; clicking on one of the constraints adds it to the activity model at the current cursor location. “One of” and “all of” headings are also added by clicking on their respective icons. Constraints are arranged into groups and hierarchies via drag-and-drop. Values are added by double-clicking on a constraint item and entering data into a dialog box.
Sequences use a “network” paradigm to define the relationships between tasks (activities and included sequences). The method consists of selecting tasks from a list and
 FIGURE 4. Network Paradigm. |
Modeling equipment modes — Implicit resource requirements are defined by equipment mode models. Equipment models are an important building block of the model and are discussed in the next section.
Intuitive and rich expression of the relationships between components — The schema employs common-sense representations of temporal relationships using everyday concepts like sequential, during, and overlap. Innovative enhancements to represent the continuance of resource usage between tasks, the interruption of tasks, minimal percent coverage, and temporal relationships to outside tasks are included in the modeling schema.
The sequence model may include one or more of the relationships listed below. As stated earlier, sequences may contain activities, other sequences, public services, and external events (such as earth rise and vehicle landing).
Sequential — Items follow each other. Minimum and maximum separations may be specified.
Separated — Items may not overlap, but the order of execution is not defined. Minimum and maximum separations may be specified.
Avoid — An item to be scheduled may not overlap any instance of the avoided item. This constraint is also enforced on not-yet-scheduled instances of the avoided item. Minimum before and after separations may be specified.
During — Items occur simultaneously; when items are of different durations, one contains the other. Which item is during the other may be specified. Minimum and maximum separations of both the start and end times may be specified.
Overlap — Items overlap; which item starts first may be defined. Minimum and maximum durations of the overlap may be specified.
Percent Coverage — One item must be scheduled during another item so that it covers a certain percentage of the duration of the other item. For example: an excursion on the moon might need communication with earth for 60% of the excursion. This coverage may be broken into reasonably short segments. The minimum coverage, the maximum number of segments, the minimum duration of a segment, and the maximum separation between segments may be specified.
Standby — During a delay between sequential or separated items, a standby item is scheduled to book (consume) the resources that are used during the delay.
Fragmentable — When an activity may be fragmented into parts, an activity or sequence is scheduled to book the resources that are used during the interruption. The maximum number of fragments, the minimum duration of a fragment, and the maximum duration of an interruption may be specified.
Cyclic — An item in a sequence may be repeated; minimum and maximum repetition counts may be specified. The frequency in hours, days or weeks may be specified. For the daily and weekly options, the time of day (with variation) may be specified. For the weekly option, days of the week may be specified. Additionally, the temporal relationship of the repetitions can also be separated or overlapped with time constraints. When the minimum repetition count is zero, the item is considered optional.
Lock-In — If two activities in a sequence contain identical “one-of” selection groups, then the same constraints must be chosen when scheduling the sequence.
One-to-One — When an item is to be done multiple times, and each repetition of this item is related to a pre-existing item in the timeline, but only one instance of the item is to be scheduled for each instance of the pre-existing item, then a one-to-one relationship is required
Relationships to internal items of embedded sequences — A sequence can specify that temporal relationships to it are to be applied to an item within itself.
Public services — The schema also includes the concept of public services – models that are scheduled at the request of another model.
Equipment modes are the basic building blocks of an activity model. Tasks are normally accomplished by using multiple pieces of equipment which, in turn, use resources. Most types of equipment have various operating modes: e.g., a microwave oven has modes such as defrost, reheat, and cook. The power requirements of each mode are predefined. On the lunar base, the characteristics of each piece of equipment will be known to those building and integrating the equipment into the Lunar Habitat. The equipment and the equipment modes can be modeled independently with respect to the tasks that will use the equipment. Equipment mode models use an outline paradigm like that used by activity models. Using equipment mode models as building blocks of task models means that the person doing the task modeling does not need to know how the equipment is integrated into the habitat/vehicle system and does not need to know the details of the resource requirements; for example, the task modeler only needs to know that the camera will downlink high-quality video, without knowing the bandwidth, data rate or power requirements. This concept was proposed in a paper by Hagopian & Maxwell (1996).
It is not enough to have good models with all the requirements expressed quantitatively; the scheduling engine must be able to process this data and produce the desired/expected schedule. The use of nested networks to capture temporal relationships, the complexity and the variety of the relationships makes all existing scheduling engines obsolete. A new scheduling engine designed specifically for the new modeling schema is being defined and prototyped as part of the on-going research.
The proposed operations concept requires an architecture which supports access to the scheduling engine from local and remote sites. Remote access must be designed so that the system is usable even with long light-time delays as will be experienced between the earth and Mars. The light-time delays can be mitigated by choosing which functions are remotely available and by carefully designing the user interfaces for those functions that are available. One type of remote access, using the internet, has been prototyped as part of the afore-mentioned research.
This paper proposes a new operations concept for lunar and Mars exploration, in which the focus of mission planning is moved from an earth-based control center to a vehicle or planetary base. The new concept provides the astronauts with much needed capabilities to manage the onboard timeline in response to real-time events, thus enabling more autonomous crew/vehicle operations. The paper also describes a set of enabling planning and scheduling technologies that are required to implement the concept, specifically in the areas of resource modeling, task modeling, automated scheduling, and distributed system architectures. These capabilities must be intelligent and robust enough to facilitate the fully automated scheduling of integrated vehicle, system, and crew operations; they must be accessible by astronauts, autonomous systems, and earth-based controllers; and they must be easily usable by the astronauts (e.g., have straightforward, intuitive user interfaces and perform robustly).
The current state-of-the-art in planning and scheduling technology for manned space missions does not satisfy these requirements. Today’s planning and scheduling systems are ground-based, fairly centralized, manpower-intensive to utilize, and must be run by planning “experts”. On past manned space programs, there has been a bias toward “manual” scheduling and an insufficient emphasis has been placed on autonomous scheduling technologies. To meet the needs of the exploration program, this bias will have to change.
Some research has been conducted in these key planning and scheduling technology areas, but much more research is required before the technologies are developed to the levels required to fully support the proposed concepts. Because they represent significant advances in automated planning and scheduling technology for manned missions, it is recommended that NASA aggressively pursue research in these areas in the near term to ensure that the enabling technologies are available in time to support the planned lunar and Mars exploration missions.
Resource Model = The data representation of the resources and constraints used by the equipment or by humans when a task is executed. Another resource model is the data representation of the resource abilities, availabilities and limitations
Scheduling Engine = The computer logic (algorithm or rule-based) which processes the task and resource models to produce a timeline which does not violate temporal and relational constraints of the tasks nor overbook resources.
Task Model = (Lexical) "a system of things and relations satisfying a set of rules that, when applied to the things and relations, produce certainty about the tasks that are being modeled.” Another way of defining a model is to say that it is a data representation of a set of tasks with their internal and external relationships and dependences which are quantified such that the model can be stored in a database
Timeline = A term used to refer to the results of scheduling. One usually thinks first of the timeline of tasks; but the time history of a resource usage, or even things such as the rising and setting of the sun are also called timelines.
Compton, W.D., and Benson, C.D., Living and Working in Space: A History of Skylab, National Aeronautics and Space Administration, Washington, D.C., 1983.
Hagopian, J., Maxwell, T.G., and Nahay, E., “NASA/MIR Phase 1: A Lesson in Long Duration Mission Planning and Operations,” in proceedings of Space Ops 98, the Fifth International Symposium on Space Mission Operations and Ground Data Systems, Tokyo, Japan, June 1998.
Hagopian, J., and Maxwell, T., “Explicit and Implicit Resources: A Simplified Approach to User Requirements Modeling,” in proceedings of Space Ops 96, Fourth International Symposium on Space Mission Operations and Ground Data Systems, September 1996.
Jaap, J., Davis, E., “An Enabling Technology for New Planning and Scheduling Paradigms,” in proceedings of SpaceOps 2004, Eight International Conference on Space Operations (17-21 May, 2004).
Jaap, J., Davis, E., and Richardson, L., “Maximally Expressive Modeling,” in proceedings of Fourth International Workshop on Planning and Scheduling for Space (23-25 June, 2004).
Sherman, J.D., and Maxwell, T.G., “Decentralizing Astronaut Flight Scheduling on the Space Station,” Business Case Journal, Volume 2, Issue 1, Summer 1994, pp. 95-103.