Engineering topics

Bresina, John L.

Publications and source records attributed to Bresina, John L..

At least 19 records

NASA NTRS2017

Traverse Planning with Temporal-Spatial Constraints

We present an approach to planning rover traverses in a domain that includes temporal-spatial constraints. We are using the NASA Resource Prospector mission as a reference mission in our research. The objective of this mission is to explore permanently shadowed regions at a Lunar pole. Most of the time the rover is required to avoid being in shadow. This requirement depends on where the rover is located and when it is at that location. Such a temporal-spatial constraint makes traverse planning more challenging for both humans and machines. We present a mixed-initiative traverse planner which addresses this challenge. This traverse planner is part of the Exploration Ground Data Systems (xGDS), which we have enhanced with new visualization features, new analysis tools, and new automation for path planning, in order to be applicable to the Re-source Prospector mission. The key concept that is the basis of the analysis tools and that supports the automated path planning is reachability in this dynamic environment due to the temporal-spatial constraints.

temporal-spatial constraints↗

NASA NTRS2015

Activity Planning for a Lunar Orbital Mission

This paper describes a challenging, real-world planning problem within the context of a NASA mission called LADEE (Lunar Atmospheric Dust Environment Explorer). LADEEs science phase was performed in an equatorial, retrograde orbit around the Moon. The science observations were constrained with respect to key points in the spacecrafts orbit. We present the approach taken to reduce the complexity of the activity planning task in order to effectively perform it within the time pressures imposed by the mission requirements. One key aspect of this approach is the design of the activity planning process based on principles of problem decomposition and planning abstraction levels. The second key aspect is the mixed-initiative system developed for this task, called LASS (LADEE Activity Scheduling System). The primary challenge for LASS was representing and managing the orbit-based science constraints, given their dynamic nature due to the continually updated orbit determination solution.

Bresina, John L.↗

NASA NTRS2010

Flight Operations for the LCROSS Lunar Impactor Mission

The LCROSS (Lunar CRater Observation and Sensing Satellite) mission was conceived as a low-cost means of determining the nature of hydrogen concentrated at the polar regions of the moon. Co-manifested for launch with LRO (Lunar Reconnaissance Orbiter), LCROSS guided its spent Centaur upper stage into the Cabeus crater as a kinetic impactor, and observed the impact flash and resulting debris plume for signs of water and other compounds from a Shepherding Spacecraft. Led by NASA Ames Research Center, LCROSS flight operations spanned 112 days, from June 18 through October 9, 2009. This paper summarizes the experiences from the LCROSS flight, highlights the challenges faced during the mission, and examines the reasons for its ultimate success.

Tompkins, Paul D.↗

NASA NTRS2006

Architecture for Control of the K9 Rover

Software featuring a multilevel architecture is used to control the hardware on the K9 Rover, which is a mobile robot used in research on robots for scientific exploration and autonomous operation in general. The software consists of five types of modules: Device Drivers - These modules, at the lowest level of the architecture, directly control motors, cameras, data buses, and other hardware devices. Resource Managers - Each of these modules controls several device drivers. Resource managers can be commanded by either a remote operator or the pilot or conditional-executive modules described below. Behaviors and Data Processors - These modules perform computations for such functions as planning paths, avoiding obstacles, visual tracking, and stereoscopy. These modules can be commanded only by the pilot. Pilot - The pilot receives a possibly complex command from the remote operator or the conditional executive, then decomposes the command into (1) more-specific commands to the resource managers and (2) requests for information from the behaviors and data processors. Conditional Executive - This highest-level module interprets a command plan sent by the remote operator, determines whether resources required for execution of the plan are available, monitors execution, and, if necessary, selects an alternate branch of the plan.

Bresina, John L.↗

NASA NTRS2006

Mission Operations Planning with Preferences: An Empirical Study

This paper presents an empirical study of some nonexhaustive approaches to optimizing preferences within the context of constraint-based, mixed-initiative planning for mission operations. This work is motivated by the experience of deploying and operating the MAPGEN (Mixed-initiative Activity Plan GENerator) system for the Mars Exploration Rover Mission. Responsiveness to the user is one of the important requirements for MAPGEN, hence, the additional computation time needed to optimize preferences must be kept within reasonabble bounds. This was the primary motivation for studying non-exhaustive optimization approaches. The specific goals of rhe empirical study are to assess the impact on solution quality of two greedy heuristics used in MAPGEN and to assess the improvement gained by applying a linear programming optimization technique to the final solution.

Bresina, John L.↗

NASA NTRS2006

The K9 On-Board Rover Architecture

This paper describes the software architecture of NASA Ames Research Center s K9 rover. The goal of the onboard software architecture team was to develop a modular, flexible framework that would allow both high- and low-level control of the K9 hardware. Examples of low-level control are the simple drive or pan/tilt commands which are handled by the resource managers, and examples of high-level control are the command sequences which are handled by the conditional executive. In between these two control levels are complex behavioral commands which are handled by the pilot, such as drive to goal with obstacle avoidance or visually servo to a target. This paper presents the design of the architecture as of Fall 2000. We describe the state of the architecture implementation as well as its current evolution. An early version of the architecture was used for K9 operations during a dual-rover field experiment conducted by NASA Ames Research Center (ARC) and the Jet Propulsion Laboratory (JPL) from May 14 to May 16, 2000.

Bresina, John L.↗

NASA NTRS2005

Mixed-Initiative Planning in MAPGEN: Capabilities and Shortcomings

MAPGEN (Mixed-initiative Activity Plan GENerator) is a mixed-initiative system that employs automated constraint-based planning, scheduling, and temporal reasoning to assist the Mars Exploration Rover mission operations staff in generating the daily activity plans. This paper describes the mixed-initiative capabilities of MAPGEN, identifies shortcomings with the deployed system, and discusses ongoing work to address some of these shortcomings.

Bresina, John L.↗

NASA NTRS2004

Activity Planning for the Mars Exploration Rovers

Operating the Mars Exploration Rovers is a challenging, time-pressured task. Each day, the operations team must generate a new plan describing the rover activities for the next day. These plans must abide by resource limitations, safety rules, and temporal constraints. The objective is to achieve as much science as possible, choosing from a set of observation requests that oversubscribe rover resources. In order to accomplish this objective, given the short amount of planning time available, the MAPGEN (Mixed-initiative Activity Plan GENerator) system was made a mission-critical part of the ground operations system. MAPGEN is a mixed-initiative system that employs automated constraint-based planning, scheduling, and temporal reasoning to assist operations staff in generating the daily activity plans. This paper describes the adaptation of constraint-based planning and temporal reasoning to a mixed-initiative setting and the key technical solutions developed for the mission deployment of MAPGEN.

Bresina, John L.↗

NASA NTRS2000

Robustness via Run-Time Adaptation of Contingent Plans

In this paper, we discuss our approach to making the behavior of planetary rovers more robust for the purpose of increased productivity. Due to the inherent uncertainty in rover exploration, the traditional approach to rover control is conservative, limiting the autonomous operation of the rover and sacrificing performance for safety. Our objective is to increase the science productivity possible within a single uplink by allowing the rover's behavior to be specified with flexible, contingent plans and by employing dynamic plan adaptation during execution. We have deployed a system exhibiting flexible, contingent execution; this paper concentrates on our ongoing efforts on plan adaptation, Plans can be revised in two ways: plan steps may be deleted, with execution continuing with the plan suffix; and the current plan may be merged with an "alternate plan" from an on-board library. The plan revision action is chosen to maximize the expected utility of the plan. Plan merging and action deletion constitute a more conservative general-purpose planning system; in return, our approach is more efficient and more easily verified, two important criteria for deployed rovers.

Bresina, John L.↗

NASA NTRS2000

Expected Utility Distributions for Flexible, Contingent Execution

This paper presents a method for using expected utility distributions in the execution of flexible, contingent plans. A utility distribution maps the possible start times of an action to the expected utility of the plan suffix starting with that action. The contingent plan encodes a tree of possible courses of action and includes flexible temporal constraints and resource constraints. When execution reaches a branch point, the eligible option with the highest expected utility at that point in time is selected. The utility distributions make this selection sensitive to the runtime context, yet still efficient. Our approach uses predictions of action duration uncertainty as well as expectations of resource usage and availability to determine when an action can execute and with what probability. Execution windows and probabilities inevitably change as execution proceeds, but such changes do not invalidate the cached utility distributions, thus, dynamic updating of utility information is minimized.

Bresina, John L.↗

NASA NTRS1997

Automatic Generation of Heuristics for Scheduling

This paper presents a technique, called GenH, that automatically generates search heuristics for scheduling problems. The impetus for developing this technique is the growing consensus that heuristics encode advice that is, at best, useful in solving most, or typical, problem instances, and, at worst, useful in solving only a narrowly defined set of instances. In either case, heuristic problem solvers, to be broadly applicable, should have a means of automatically adjusting to the idiosyncrasies of each problem instance. GenH generates a search heuristic for a given problem instance by hill-climbing in the space of possible multi-attribute heuristics, where the evaluation of a candidate heuristic is based on the quality of the solution found under its guidance. We present empirical results obtained by applying GenH to the real world problem of telescope observation scheduling. These results demonstrate that GenH is a simple and effective way of improving the performance of an heuristic scheduler.

Morris, Robert A.↗

NASA NTRS1997

Optimizing Observation Scheduling Objectives

In this paper, we present an approach that enables the automatic generation of high quality schedules, with respect to a given objective function. The approach involves the combination of two techniques: GenH, which automatically generates a search heuristic specialized to the given problem instance, and HBSS, which employs the generated heuristic as a bias within a stochastic sampling method.

Bresina, John L.↗

NASA NTRS1994

Telescope loading: A problem reduction approach

This paper presents a problem reduction approach to telescope loading. To study time-varying celestial behavior, astronomers submit periodic observation campaigns which involve a sequence of observations at a given sampling frequency over months or years. The loader's task is to generate an assignment of observation tasks to each night in the time window such that resource demand does not exceed resource capacity and such that the observations usefully contribute to the campaigns' scientific purposes, in a manner that is fair to all participating astronomers.

Bresina, John L.↗

NASA NTRS1992

Purposive discovery of operations

The Generate, Prune & Prove (GPP) methodology for discovering definitions of mathematical operators is introduced. GPP is a task within the IL exploration discovery system. We developed GPP for use in the discovery of mathematical operators with a wider class of representations than was possible with the previous methods by Lenat and by Shen. GPP utilizes the purpose for which an operator is created to prune the possible definitions. The relevant search spaces are immense and there exists insufficient information for a complete evaluation of the purpose constraint, so it is necessary to perform a partial evaluation of the purpose (i.e., pruning) constraint. The constraint is first transformed so that it is operational with respect to the partial information, and then it is applied to examples in order to test the generated candidates for an operator's definition. In the GPP process, once a candidate definition survives this empirical prune, it is passed on to a theorem prover for formal verification. We describe the application of this methodology to the (re)discovery of the definition of multiplication for Conway numbers, a discovery which is difficult for human mathematicians. We successfully model this discovery process utilizing information which was reasonably available at the time of Conway's original discovery. As part of this discovery process, we reduce the size of the search space from a computationally intractable size to 3468 elements.

Sims, Michael H.↗

NASA NTRS1991

NASA TileWorld manual (system version 2.2)

The commands are documented of the NASA TileWorld simulator, as well as providing information about how to run it and extend it. The simulator, implemented in Common Lisp with Common Windows, encodes a particular range in a spectrum of domains, for controllable research experiments. TileWorld consists of a two dimensional grid of cells, a set of polygonal tiles, and a single agent which can grasp and move tiles. In addition to agent executable actions, there is an external event over which the agent has not control; this event correspond to a 'gust of wind'.

Philips, Andrew B.↗

NASA NTRS1991

The blind leading the blind: Mutual refinement of approximate theories

The mutual refinement theory, a method for refining world models in a reactive system, is described. The method detects failures, explains their causes, and repairs the approximate models which cause the failures. The approach focuses on using one approximate model to refine another.

Kedar, Smadar T.↗

NASA NTRS1991

A design rationale for NASA TileWorld

Automated systems that can operate in unrestricted real-world domains are still well beyond current computational capabilities. This paper argues that isolating essential problem characteristics found in real-world domains allows for a careful study of how particular control systems operate. By isolating essential problem characteristics and studying their impact on autonomous system performance, we should be able to more quickly deliver systems for practical real-world problems. For our research on planning, scheduling, and control, we have selected three particular domain attributes to study: exogenous events, uncertain action outcome, and metric time. We are not suggesting that studies of these attributes in isolation are sufficient to guarantee the obvious goals of good methodology, brilliant architectures, or first-class results; however, we are suggesting that such isolation facilitates the achievement of these goals. To study these attributes, we have developed the NASA TileWorld. We describe the NASA TileWorld simulator in general terms, present an example NASA TileWorld problem, and discuss some of our motivations and concerns for NASA TileWorld.

Philips, Andrew B.↗

NASA NTRS1991

The entropy reduction engine: Integrating planning, scheduling, and control

The Entropy Reduction Engine, an architecture for the integration of planning, scheduling, and control, is described. The architecture is motivated, presented, and analyzed in terms of its different components; namely, problem reduction, temporal projection, and situated control rule execution. Experience with this architecture has motivated the recent integration of learning. The learning methods are described along with their impact on architecture performance.

Drummond, Mark↗