Graphical Timeline Editing

by Patrick Meyer and John Jaap 
National Aeronautics and Space Administration (NASA)
Marshall Space Flight Center, AL 35812
Phone (205) 544-2265    Fax (205) 544-5873
Email: Patrick.Meyer@msfc.nasa.gov
Presented to: 
3rd International Symposium on Artificial Intelligence, 
Robotics, and Automation for Space (i-SAIRAS 94)
October 18-20, 1994
Jet Propulsion Laboratory
Passadena, California, U.S.A.

ABSTRACT

Graphical Timeline Editing (GTE) will be an integral part of the experiment scheduling systems used for Spacelab and Space Station. The Experiment Scheduling Program (ESP), which is currently used for Spacelab payload operations, is expanding its horizon of capabilities with the addition of a GTE Clipboard. This new Clipboard will contain algorithms that provide anticipated information and, in the future, conflict resolution assistance using a popular click and drag Graphical User Interface (GUI) that will aid users in making quick, effective, and resource valid modifications to timelines.

GTE Graphic

KEY WORDS AND PHRASES

Outline and Cross Reference

INTRODUCTION

NASA's Experiment Scheduling Program (ESP), which has been used for approximately 12 Spacelab missions, is being enhanced with the addition of a Graphical Timeline Editor. The GTE Clipboard, as it is called, was developed to demonstrate new technology which will lead the development of International Space Station Alpha's Payload Planning System and support the remaining Spacelab missions.

ESP's GTE Clipboard is developed in C using MIT's X Windows System ® X11R5 and follows OSF/Motif ® Style Guide Revision 1.2.

Clipboard Concept

In ESP's GTE Clipboard concept, what is in the clipboard is not in the timeline. This reduces the permutations of potential conflict and allows for capabilities that would otherwise be too cumbersome or impossible. Activities to be edited must be moved to the clipboard, edited within the clipboard, and committed back to the timeline. When desired, a subset of the edited activities in the clipboard can be committed to the timeline. Activities from external sources can be added to the clipboard where possible conflicts can be resolved before they are moved to the timeline.

EDITING

Editing, the key word in Graphical Time line Editing, is a combination of rendering the timeline as graphics objects and supporting user manipulation of those objects. When rendering the data, pixel granularity inherent in graphic editors is overcome by using a high resolution screen. However, when manipulating data, the pixel granularity problem is exacerbated in the clipboard because ESP can have a scheduling horizon of 90 days or more and simultaneously maintain time accuracies to 1 second a ratio of 1 to 10 million. In addition, users of ESP frequently need to maintain scheduling granularity at 1 minute. An eloquent solution to both problems was found and implemented.

The clipboard provides two methods for addressing time granularity problems. First, time quantization is used to round modified times to the nearest multiple of a user-specified constant. During an activity modification, feedback provides the quantized placement times so the user is constantly aware of the modified value. Second, a mechanism which allows the user to make micro-adjustments is provided. Micro-adjustments are always made in a quantization unit even when the unit is smaller than a pixel.

With a solution to the granularity problem in hand, fundamental graphical editing features such as selecting, adding, deleting, moving, modifying, undoing, aligning, and commiting back to the timeline can be straightforwardly implemented.

Activity Selection

For the clipboard, three methods and two modes of selection were identified. The methods include selecting the lowest integral part of a scheduled activity (a step), selecting a whole activity (a performance), and selecting all steps within a user-bounded box. For each of these methods, the modes of selection are additive (extending) and toggle.

Selection order may be relevant for some manipulations. For instance, to temporally align, both the activity which is aligned to and the activity which is aligned with must be specified. By using selection order, the alignment can be made consecutively; i.e. a successor can align with its predecessor.

Selected activities are rendered with angled appendages because it provides optimum view ability for overlapping and/or extremely small steps. Figure 1 below illustrates the usability of this method. Steps 1, 2, and 4 are shown as selected.

Figure 1. Selected Activity.

Adding Activities

Activities can be added to the clipboard by moving them from the current timeline to the clipboard, copying from the current timeline, importing from an external timeline, including a template of a model, using the automatic scheduler, and keying in data.

Each of these methods has unique applications and advantages. Activities which could not be imported directly to the timeline may be imported to the clipboard, repaired, and then moved to the timeline. Adding a template of a model to the clipboard allows a user to start with a generic form of model and massage it to fit the timeline constraints. Adding to the clipboard via automatic scheduling provides conflict-free activities in the clipboard to which the user can make minor adjustments before moving them to the timeline. However, auto-scheduling into the clipboard checks constraints only against the timeline and not against the clipboard.

Deleting Activities

Activities may be deleted from the clipboard. After deletion they may be restored until they are purged or until the entire contents of the clipboard is successfully committed to the timeline. As a shortcut, activities may also be deleted directly from the timeline.

Moving Clipboard Activities

Moving activities is the most used manipulation of a timeline and therefore should be robust and easy to use. In the clipboard, moving selected steps is initiated with a mouse button press while the pointer is within one of the selected steps. The initiating step's new start time is fed back to the user during the modification to indicate where the step will be placed. Other selected steps are also moved.

Modifying Activities

After moving or adding activities, small conflicts usually arise that require simple modifications for them to validly schedule as a group. For example, activity duration changes will routinely introduce overlap conflicts. By proper definition of activity duration changes, the user can prevent overlap conflicts. The definition chosen for the clipboard takes all succeeding (for modified start time) or all preceding (for modified end time) activities which are selected and shifts them to maintain the original time delay between the changed activity and any other affected activity. In Figure 2 below, the duration of B was changed causing C to be shifted.

Figure 2. Duration Change.

However, when changing the duration of an activity, the durations of overlapping selected steps are also modifed rather than being shifted. This overlap may or may not be due to scheduling concurrency constraints (see Figure 3 below).

Figure 3. Overlapping Change.

Modifying Crew Usage

A portion of the display can be used to display crew usage data for both the timeline and clipboard. Graphical manipulations within this area can remove, add, or reassign crew on an activity.

Undoing Modifications

Undo, as the name implies, allows the user to undo the last edit made to the clipboard. The last edit may be either a simple (one item) or compound (multiple items) edit. In addition, undo can also restore activities to their unedited state until they are committed to the timeline.

Assisted Temporal Aligning

The clipboard can align selected activity steps or activity performances in four ways:
  • Start time to start time.
  • Start time to end time.
  • End time to start time.
  • End time to end time.
    •  Steps are aligned consecutively in the order in which they were selected.

    Committing to the Timeline

    As stated before, activities in the clipboard are not in the timeline and must be committed to the schedule. During committal to the time line, activities are validated and any conflicts that the user has not resolved are reported. If no conflicts are present, the activities are moved from the clipboard to the timeline with no report.

    USER INTERFACE

    While building the basic editing commands into a new timeline editor, concerns of leaving behind old, but good, ways of editing arose. Therefore, the clipboard brings forward text-based editing features similar to ESP's previous timeline editing buffers. These include a table and command line which allow the user to enter specific values for important aspects of an activity and enter commands that can affect ranges of activities.

    Tailorable Displays

    Each Spacelab mission ESP supports has different objectives and resource utilization. To accomodate the varying demands on the clipboard, a tailorable display allows users to hone in on the information which is important to the type of missions they are scheduling. Some of the options included are -
  • Activity Breakdown Using Digital's Structured Visual Navigation (SVN) widget the clipboard is able to present the graphical data to the user in an expandable outline form. With SVN, the user can expand an activity to a Gantt chart of its steps.
  • Optional Command Line For the expert graphical editing user, the command line may be removed from the visible display.
  • Optional Crew Data For missions where activities are not crew-based, the crew timeline data can be removed.
  • Optional Crew Timeline Data Since what is in the clipboard is not in the timeline, the crew timeline data can be displayed in the same crew area with clipboard data.
  • Paned Windows The clipboard utilizes Motif's PanedWindow widget which allow the user to subdivide the display and view the most desired information.
  • Toolboxes The clipboard toolbox provides quick access to copy, delete, undo, auto-schedule (generate), move (bias), temporally align and other useful commands.
    •

    CONFLICT RESOLUTION/PREVENTION

    The biggest drawback with many manual editors is their guess-again approach. When the user moves an activity, the scheduler response is to report resource constraint and scheduling conflicts and the user is forced to guess again where the activity can be validly placed to avoid the conflicts. The clipboard not only provides a report when edits are commit ted, it also displays graphics information to help the user eliminate existing conflicts and to avoid introducing conflicts when activities are manipulated. When fully implemented, the clipboard will also provide automatic scheduling assistance.

    Visual Aid for Crew Conflicts

    Since ESP enforces the Spacelab and International Space Station Alpha ground rule that a crewmember cannot be scheduled to do more than one task at a time, the clipboard provides a crew timeline area where the crew timeline data is displayed, the crew clipboard data is overlayed, and any conflicts are highlighted. Users can readily see where crewmembers are available or are in conflict and can modify crew usage for activities in the clipboard.

    Visual Aid for Temporal Constraints

    An activity can have temporal constraints relative to other performances of the same model or other models and can have fixed windows in which it must be performed. While other displays in ESP can show the data which determines where the temporal constraints are met, the clipboard can compute the feasibility windows and present them to the user so that temporal conficts can be avoided or removed. The clipboard uses an X Windows work procedure to compute and display these computationally-intense windows. Work procedures are executed when no events are pending execution; i.e., they use idle computer time. The clipboard re-launches the work procedure whenever the timeline is changed; therefore, the windows remain current.

    Visual Aid for Resource Constraints

    Each step of an activity can have many constraints which limit where on the timeline a step can be validly placed. In addition to crew requirements, these constraints include other shared resources and windows of opportunity. For each step, the clipboard can compare each requirement to the current timeline state, consolidate all the individual results, and present feasibility windows on a single line of the display. Windows which are not as long as the minimum step duration are not shown. By adhering to the feasibility windows, the user can easily avoid introducing conflicts or remove existing conflicts. A work procedure is also used for these feasibility windows. Figure 4 shows a step which is too long for its nearest feasibility window but which will fit within the next window.

    Figure 4. Feasibility Windows.

    Users may request that feasibilities for a step be presented on an individual requirements basis. This separate display will show each requirement of the selected step and the time periods when that requirement is met. The composite feasibility windows are also shown.

    Automatic Assistance to Editing

    As an enhancement of the manual editing process, the clipboard provides automatic assistance. In this mode, the user selects a performance that is in the clipboard but conflicts with some constraints. The user specifies a horizon over which scheduling is to take place, and an automatic scheduler adjusts step start times, durations, and crew assignments to avoid conflicts. An explanation facility which graphically explains what the scheduler did allows the user to understand what conflicts were addressed or why a solution was not found.

    A future enhancement of automatic rescheduling is to allow the user to specify another horizon over which the program may automatically adjust activities already on the timeline. This process may proceed without user interaction, or user approval may be required for every change to the timeline. There are several strategies for directly modifying the existing timeline:

  • Reassignment of crew.
  • Adjusting step durations or delays.
  • Substituting an alternate scenario of the same activity.
  • Moving activities to non-conflicting times.
  • Moving activities to new times where conflicts can be easily resolved.
  • Deleting activities based on priorities or based on least impact to schedule.
    •

    Advanced techniques such as simulated annealing are also candidates for automatic assistance.

    SUMMARY

    The X Windows Graphical Timeline Editor currently being added to the Experiment Scheduling Program is based on a clipboard concept. Because activities which are in the clipboard are not on the timeline, robust capabilities which may not have been otherwise practical are being incorporated. The GTE Clipboard is being implemented using Motif® and other widgets and includes a complete suite of graphic manipulation features and a complete suite of timeline editing features relative to Spacelab and International Space Station Alpha. The GTE Clipboard is much more than a guess-again editor in that it provides graphical assistance for conflict resolution. Future plans will implement automated conflict resolution.