Engineering topics

Morris, Paul

Publications and source records attributed to Morris, Paul.

At least 19 records

NASA NTRS2016

The Mathematics of Dispatchability Revisited

Dispatchability is an important property for the efficient execution of temporal plans where the temporal constraints are represented as a Simple Temporal Network (STN). It has been shown that every STN may be reformulated as a dispatchable STN, and dispatchability ensures that the temporal constraints need only be satisfied locally during execution. Recently it has also been shown that Simple Temporal Networks with Uncertainty, augmented with wait edges, are Dynamically Controllable provided every projection is dispatchable. Thus, the dispatchability property has both theoretical and practical interest. One thing that hampers further work in this area is the underdeveloped theory. The existing definitions are expressed in terms of algorithms, and are less suitable for mathematical proofs. In this paper, we develop a new formal theory of dispatchability in terms of execution sequences. We exploit this to prove a characterization of dispatchability involving the structural properties of the STN graph. This facilitates the potential application of the theory to uncertainty reasoning.

control↗

NASA NTRS2016

The Mathematics of Dispatchability, Revisited

Dispatchability is an important property for the efficient execution of temporal plans where the temporal constraints are represented as a Simple Temporal Network (STN). It has been shown that every STN may be reformulated as a dispatchable STN, and dispatchability ensures that the temporal constraints need only be satisfied locally during execution. Recently, it has also been shown that Simple Temporal Networks with Uncertainty, augmented with wait edges, are Dynamically Controllable provided every projection is dispatchable. Thus, dispatchability has considerable theoretical as well as practical significance. One thing that hampers further work in this area is the underdeveloped theory. Moreover, the existing foundation is inadequate in certain respects. In this paper, we develop a new mathematical theory of dispatchability and its relationship to execution. We also provide several characterizations of dispatchability, including characterizations in terms of the structural properties of the STN graph. This facilitates the potential application of the theory to other areas.

mathematical models↗

NASA NTRS2015

From Diagnosis to Action: An Automated Failure Advisor for Human Deep Space Missions

The major goal of current space system development at NASA is to enable human travel to deep space locations such as Mars and asteroids. At that distance, round trip communication with ground operators may take close to an hour, thus it becomes unfeasible to seek ground operator advice for problems that require immediate attention, either for crew safety or for activities that need to be performed at specific times for the attainment of scientific results. To achieve this goal, major reliance will need to be placed on automation systems capable of aiding the crew in detecting and diagnosing failures, assessing consequences of these failures, and providing guidance in repair activities that may be required. We report here on the most current step in the continuing development of such a system, and that is the addition of a Failure Response Advisor. In simple terms, we have a system in place the Advanced Caution and Warning System (ACAWS) to tell us what happened (failure diagnosis) and what happened because that happened (failure effects). The Failure Response Advisor will tell us what to do about it, how long until something must be done and why its important that something be done and will begin to approach the complex reasoning that is generally required for an optimal approach to automated system health management. This advice is based on the criticality and various timing elements, such as durations of activities and of component repairs, failure effects delay, and other factors. The failure advice is provided to operators (crew and mission controllers) together with the diagnostic and effects information. The operators also have the option to drill down for more information about the failure and the reasons for any suggested priorities.

spacecraft health maintenance↗

NASA NTRS2014

Determining Mission Effects of Equipment Failures

NASA plans call for long duration deep space missions with human crews. Because of light-time delay and other considerations, increased autonomy is needed. Crews on next-generation missions will likely be small, perhaps with as few as four members. A small crew is not likely to possess the full range of expertise needed to deal with unexpected failures and anomalies. Applied artificial intelligence technologies have developed decision support tools with the potential to fill the gap, but these tools need to be integrated to provide a smooth operational capability. In this paper we describe such an integration involving anomaly detection, diagnosis, system effect propagation, and plan repair.

Morris, Paul↗

NASA NTRS2013

Embedding Temporal Constraints For Coordinated Execution in Habitat Automation

Future NASA plans call for long-duration deep space missions with human crews. Because of light-time delay and other considerations, increased autonomy will be needed. This will necessitate integration of tools in such areas as anomaly detection, diagnosis, planning, and execution. In this paper we investigate an approach that integrates planning and execution by embedding planner-derived temporal constraints in an execution procedure. To avoid the need for propagation, we convert the temporal constraints to dispatchable form. We handle some uncertainty in the durations without it affecting the execution; larger variations may cause activities to be skipped.

Morris, Paul↗

NASA NTRS2006

A Structural Characterization of Temporal Dynamic Controllability

An important issue for temporal planners is the ability to handle temporal uncertainty. Recent papers have addressed the question of how to tell whether a temporal network is Dynamically Controllable, i.e., whether the temporal requirements are feasible in the light of uncertain durations of some processes. Previous work has presented an O(N5) algorithm for testing this property. Here, we introduce a new analysis of temporal cycles that leads to an O(N4) algorithm.

Morris, Paul↗

NASA NTRS2005

Mixed-Initiative Activity Planning for Mars Rovers

One of the ground tools used to operate the Mars Exploration Rovers is a mixed-initiative planning system called MAPGEN. The role of the system is to assist operators building daily plans for each of the rovers, maximizing science return, while maintaining rover safety and abiding by science and engineering constraints. In this paper, we describe the MAPGEN system, focusing on the mixed-initiative planning aspect. We note important challenges, both in terms of human interaction and in terms of automated reasoning requirements. We then describe the approaches taken in MAPGEN, focusing on the novel methods developed by our team.

Bresina, John↗

NASA NTRS2005

Constraint-based Temporal Reasoning with Preferences

Often we need to work in scenarios where events happen over time and preferences are associated to event distances and durations. Soft temporal constraints allow one to describe in a natural way problems arising in such scenarios. In general, solving soft temporal problems require exponential time in the worst case, but there are interesting subclasses of problems which are polynomially solvable. In this paper we identify one of such subclasses giving tractability results. Moreover, we describe two solvers for this class of soft temporal problems, and we show some experimental results. The random generator used to build the problems on which tests are performed is also described. We also compare the two solvers highlighting the tradeoff between performance and robustness. Sometimes, however, temporal local preferences are difficult to set, and it may be easier instead to associate preferences to some complete solutions of the problem. To model everything in a uniform way via local preferences only, and also to take advantage of the existing constraint solvers which exploit only local preferences, we show that machine learning techniques can be useful in this respect. In particular, we present a learning module based on a gradient descent technique which induces local temporal preferences from global ones. We also show the behavior of the learning module on randomly-generated examples.

Khatib, Lina↗

NASA NTRS2004

Strategies for Global Optimization of Temporal Preferences

A temporal reasoning problem can often be naturally characterized as a collection of constraints with associated local preferences for times that make up the admissible values for those constraints. Globally preferred solutions to such problems emerge as a result of well-defined operations that compose and order temporal assignments. The overall objective of this work is a characterization of different notions of global preference, and to identify tractable sub-classes of temporal reasoning problems incorporating these notions. This paper extends previous results by refining the class of useful notions of global temporal preference that are associated with problems that admit of tractable solution techniques. This paper also answers the hitherto open question of whether problems that seek solutions that are globally preferred from a Utilitarian criterion for global preference can be found tractably.

Morris, Paul↗

NASA NTRS2004

MAPGEN: Mixed-Initiative Activity Planning for the Mars Exploration Rover Mission

This document describes the Mixed initiative Activity Plan Generation system MAPGEN. This system is one of the critical tools in the Mars Exploration Rover mission surface operations, where it is used to build activity plans for each of the rovers, each Martian day. The MAPGEN system combines an existing tool for activity plan editing and resource modeling, with an advanced constraint-based reasoning and planning framework. The constraint-based planning component provides active constraint and rule enforcement, automated planning capabilities, and a variety of tools and functions that are useful for building activity plans in an interactive fashion. In this demonstration, we will show the capabilities of the system and demonstrate how the system has been used in actual Mars rover operations. In contrast to the demonstration given at ICAPS 03, significant improvement have been made to the system. These include various additional capabilities that are based on automated reasoning and planning techniques, as well as a new Constraint Editor support tool. The Constraint Editor (CE) as part of the process for generating these command loads, the MAPGEN tool provides engineers and scientists an intelligent activity planning tool that allows them to more effectively generate complex plans that maximize the science return each day. The key to the effectiveness of the MAPGEN tool is an underlying constraint-based planning and reasoning engine.

Ai-Chang, Mitchell↗

NASA NTRS2003

Software for Planning Scientific Activities on Mars

Mixed-Initiative Activity Plan Generator (MAPGEN) is a ground-based computer program for planning and scheduling the scientific activities of instrumented exploratory robotic vehicles, within the limitations of available resources onboard the vehicle. MAPGEN is a combination of two prior software systems: (1) an activity-planning program, APGEN, developed at NASA s Jet Propulsion Laboratory and (2) the Europa planner/scheduler from NASA Ames Research Center. MAPGEN performs all of the following functions: Automatic generation of plans and schedules for scientific and engineering activities; Testing of hypotheses (or what-if analyses of various scenarios); Editing of plans; Computation and analysis of resources; and Enforcement and maintenance of constraints, including resolution of temporal and resource conflicts among planned activities. MAPGEN can be used in either of two modes: one in which the planner/scheduler is turned off and only the basic APGEN functionality is utilized, or one in which both component programs are used to obtain the full planning, scheduling, and constraint-maintenance functionality.

Ai-Chang, Mitchell↗

NASA NTRS2003

MAPGEN : mixed initiative planning and scheduling for the Mars '03 MER mission

The Mars Exploration Rovers Mars '03 mission is one of NASA's most ambitious science missions to date. The rovers will be launched in the summer of 2003 with each rover carrying instruments to conduct remote and in-situ observation to elucidate the planet's past climate, water activity, and habitability. Science is the primary driver of MER and, as a consequence, making best use of the scientific instruments, within the available resources, is a crucial aspect of the mission. To address this critically, the MER project has selected MAPGEN (Mixed-Initiative Activity Plan GENerator) as an activity planning tool. MAPGEN combines two exiting systems, each with a strong heritage: APGEN the Activity Planning tool from the Jet Propulsion Laboratory and the Europs Planning/Scheduling system from NASA Ames Research Center. This paper discusses the issues arising from combining these tools in the context of this mission.

planning and scheduling↗

NASA NTRS2003

Tractable Pareto Optimization of Temporal Preferences

This paper focuses on temporal constraint problems where the objective is to optimize a set of local preferences for when events occur. In previous work, a subclass of these problems has been formalized as a generalization of Temporal CSPs, and a tractable strategy for optimization has been proposed, where global optimality is defined as maximizing the minimum of the component preference values. This criterion for optimality, which we call 'Weakest Link Optimization' (WLO), is known to have limited practical usefulness because solutions are compared only on the basis of their worst value; thus, there is no requirement to improve the other values. To address this limitation, we introduce a new algorithm that re-applies WLO iteratively in a way that leads to improvement of all the values. We show the value of this strategy by proving that, with suitable preference functions, the resulting solutions are Pareto Optimal.

Morris, Robert↗

NASA NTRS2003

MAPGEN Planner: Mixed-Initiative Activity Planning for the Mars Exploration Rover Mission

This document describes the Mixed-initiative Activity Plan Generation system MAPGEN. The system is be- ing developed as one of the tools to be used during surface operations of NASA's Mars Exploration Rover mission (MER). However, the core technology is general and can be adapted to different missions and applications. The motivation for the system is to better support users that need to rapidly build activity plans that have to satisfy complex rules and fit within resource limits. The system therefore combines an existing tool for activity plan editing and resource modeling, with an advanced constraint-based reasoning and planning framework. The demonstration will show the key capabilities of the automated reasoning and planning component of the system, with emphasis on how these capabilities will be used during surface operations of the MER mission.

Ai-Chang, Mitch↗

NASA NTRS2003

Constraint Maintenance with Preferences and Underlying Flexible Solution

This paper describes an aspect of the constraint reasoning mechanism. that is part of a ground planning system slated to be used for the Mars Exploration Rovers mission, where two rovers are scheduled to land on Mars in January of 2003. The planning system combines manual planning software from JPL with an automatic planning/scheduling system from NASA Ames Research Center, and is designed to be used in a mixed-initiative mode. Among other things, this means that after a plan has been produced, the human operator can perform extensive modifications under the supervision of the automated. system. For each modification to an activity, the automated system must adjust other activities as needed to ensure that constraints continue to be satisfied. Thus, the system must accommodate change in an interactive setting. Performance is of critical importance for interactive use. This is achieved by maintaining an underlying flexible solution to the temporal constraints, while the system presents a fixed schedule to the user. Adjustments are then a matter of constraint propagation rather than completely re-solving the problem. However, this begs the important question of which fixed schedule (among the ones sanctioned by the underlying flexible solution) should be presented to the user.Our approach uses least-change and other preferences as a prism through which the user views the flexible solution.

Bresina, John↗

NASA NTRS2001

Dynamic Control of Plans with Temporal Uncertainty

Certain planning systems that deal with quantitative time constraints have used an underlying Simple Temporal Problem solver to ensure temporal consistency of plans. However, many applications involve processes of uncertain duration whose timing cannot be controlled by the execution agent. These cases require more complex notions of temporal feasibility. In previous work, various "controllability" properties such as Weak, Strong, and Dynamic Controllability have been defined. The most interesting and useful Controllability property, the Dynamic one, has ironically proved to be the most difficult to analyze. In this paper, we resolve the complexity issue for Dynamic Controllability. Unexpectedly, the problem turns out to be tractable. We also show how to efficiently execute networks whose status has been verified.

Morris, Paul↗

NASA NTRS2001

Temporal Constraint Reasoning With Preferences

A number of reasoning problems involving the manipulation of temporal information can naturally be viewed as implicitly inducing an ordering of potential local decisions involving time (specifically, associated with durations or orderings of events) on the basis of preferences. For example. a pair of events might be constrained to occur in a certain order, and, in addition. it might be preferable that the delay between them be as large, or as small, as possible. This paper explores problems in which a set of temporal constraints is specified, where each constraint is associated with preference criteria for making local decisions about the events involved in the constraint, and a reasoner must infer a complete solution to the problem such that, to the extent possible, these local preferences are met in the best way. A constraint framework for reasoning about time is generalized to allow for preferences over event distances and durations, and we study the complexity of solving problems in the resulting formalism. It is shown that while in general such problems are NP-hard, some restrictions on the shape of the preference functions, and on the structure of the preference set, can be enforced to achieve tractability. In these cases, a simple generalization of a single-source shortest path algorithm can be used to compute a globally preferred solution in polynomial time.

Khatib, Lina↗

NASA NTRS2000

Executing Temporal Networks With Uncertainty

Simple Temporal Networks (STNs) have proved useful in applications that involve metric time. However, many applications involve events whose timing is uncertain in the sense that it is not controlled by the execution agent. In this paper we consider execution algorithms for temporal networks with events of uncertain duration. We present two such algorithms. The first retains maximum flexibility, but requires potentially costly updates during execution. The second surrenders some flexibility in order to obtain a fast execution comparable to that available for ordinary STNs.

Morris, Paul↗