# PRODUCTS

# Planning and scheduling

**What is planning and scheduling**

**sub-areas/research issues**: optimization, continuous planning &
execution, contingency planning, robustness, etc.

**Supported Capabilities (matrix?)**

ASPEN

The Automated Scheduling and Planning ENvironment (ASPEN) is a flexible,
reusable, application framework for developing automated planning
systems. ASPEN automatically generates plans of activities to achieve
desired goals while respecting operations constraints involving states,
resources, and timing. ASPEN has been applied to ground-based and
onboard planning problems such as: antenna ground station automation,
autonomous spacecraft, rovers, and unpiloted aerial vehicles.

The role of a planner is to generate low-level activities that
accomplish goals and maximize objectives within the operational
constraints of the system. Current research in automated planning has
more focus on managing constraints and less on maximizing objectives.
However, for many applications, many of the requirements are preferences
rather than constraints, and increasing plan quality is a dominant part
of the planning process.

We are developing structured representation of plan quality that is
capable of encoding preferences that are common in NASA planning
problems. This includes preferences for maximizing science in a
restricted window and minimizing time spent in particular undesirable
states. We have shown that the structure of the preferences can be
exploited to efficiently reason about improvements. We are currently
extending this framework to integrate shallow and deep improvement
methods.

CASPER

An autonomous spacecraft must be able to plan ahead to avoid
shortsighted decisions that can lead to failure, yet it must also
respond in a timely fashion to dynamic and unpredictable environments.
CASPER (Continuous Activity Scheduling Planning Execution and
Replanning) uses iterative repair to support continuous modification and
updating of a current working plan in light of changing operating
context. This continuous planning approach enables CASPER to respond to
anomalies or opportunities in a rapid timescale (tens of seconds on a
flight processor).

Distributed Planning & Execution

Over the next 10 years NASA plans to fly ever-increasing numbers of
probes to observe both the Earth and Mars with sensors that have
over-lapping functionalities. Managing these over-laps among multiple
autonomous spacecraft involves assigning observation goals to spacecraft
and continually reassigning goals as anomalies and new observation
opportunities arise. In order to facilitate this form of loose
coordination, this research focuses on goal migration using continual
goal distribution planning and the interface between continual planners
and contract networks. In order to facilitate this form of goal
migration we are developing two complementary techniques. *Goal
Distribution Planning* will let a designated lead spacecraft/rover plan
with an abstract model of all followers in order to assign goals across
the population. *Contract Networks* will let any spacecraft/rover serve
as an auctioneer to distribute goals. These two approaches are actually
two points in a spectrum of approaches where the leader gives its
followers progressively more autonomy in deciding who satisfies which
goals and how to satisfy a goal. In addition to extending these
approaches to work with continual planners, this research explores the
spectrum by developing a hybrid system that uses both approaches.

From a terrestrial planet imager to robots helping each other scale
cliffs on Mars, many future NASA mission concepts involve teams of
tightly coordinated spacecraft/rovers in dynamic, partially under-stood
environments. Since environmental uncertain-ties often obstruct
pre-planned coordination, this task is about developing distributed
autonomy in the face of tight coordination requirements. Continual
coherent team planning involves using high-level team goals to command a
team of agents that collectively manages the creation and execution of a
shared team plan. In order to facilitate this form of tightly
coordinated autonomy this research focuses on three innovations.
*Dynamic Team Planning* will let agents delete, reschedule, and add team
activities to adapt a shared team plan to the dynamic, partially
understood environment. *Negotiation by argumentation* will let agents
negotiate to overcome incompatible models of their environment.
*Negotiation strategy adaptation* will let the agents alter their
negotiation approaches to come to agreement over their models of the
environment and changes in the team plan within real-time deadlines.
Each of these innovations involves extending the state of the art in
continual distributed planning due to complexity of planning coordinated
activities in the face of hard resource constraints and deadlines.

Adaptive Problem Solving

Proposed missions to explore comets and moons will encounter
environments that are hostile and unpredictable. Any successful explorer
must be able to adapt to a wide range of possible operating conditions
in order to survive. The traditional approach of constructing
special-purpose control methods requires information about the
environment, which is not available a priori for these missions.
Adaptive planning uses a flexible problem-solver with significant
capability to adapt its behavior. Using adaptive problem solving, a
spacecraft uses reinforcement learning to learn an environment-specific
search method.

Adaptive planning algorithms use reinforcement learning to evaluate a
set of control strategies so that they can be ranked in terms of their
utility for problem instances. A search method will generate new control
strategies based on the highest scoring control strategies of the
previous cycle. The cycle then repeats with this new algorithm.

Portfolio Planning Algorithms

Algorithm Portfolios are sets of algorithms designed to work
synergistically to solve a problem. In a synergistic portfolio the whole
is greater than the sum of its parts: the probability of at least one
algorithm succeeding is greater than the sum of the independent success
probabilities, due to negative correlations. Algorithms can be combined
within a single run to enable multiple algorithms to solve a single
problem instance (approaching multi-strategy cooperative
problem-solving). Portfolios containing stochastic algorithms can
exploit rapid restarts, which is beneficial for certain problem classes.
This research investigates the use of stochastic combinations of search
heuristics in the ASPEN planner using the iterative repair framework to
improve local search on a wide range of problem domains.

Combinatorial Optimizers for use with Planning

Automated mission planning systems have already demonstrated the ability
to reduce mission planning effort, improve mission quality, and reduce
operations costs. There are a number of important NASA planning
problems, however, for which current general-purpose planning systems
cannot produce high quality solutions to large real-world sized problems
within reasonable time bounds. Many of these problems contain
combinatorial optimization sub-problems that interact with the overall
planning problem.

This work provides the capability for significantly improving planner
performance by integrating specialized solvers into general purpose
planning systems. It will enable general purpose planners, which are at
the core of autonomy, to solve these difficult classes of planning
problems better and faster than they can now, and in many cases enable
them to solve problems that are currently intractable. It will also
provide optimization algorithms for two planning problems, observation
scheduling and swath selection, that are critical to sky survey and
planetary mapping missions such as NGST, SIRTF, SIM, TPF, Jason-1,
Europa Orbiter, and LightSAR. These capabilities are expected to reduce
operations costs by enabling planning systems to automatically generate
high quality solutions to these large problems, and improve science
return for these heavily oversubscribed facilities by producing plans
that utilize these resources far more efficiently.

# Autonomy architectures

The CLARAty Software Architecture for Robotic Autonomy

Future missions are looking at rovers that require high-levels of
autonomous capabilities to support mission goals such as long-range
traversals, complex science experiments, reduced ground operations, and
longer mission durations. Much of the operations for these rovers will
be done autonomously without communication from ground and thus requires
autonomy software to work closely with onboard-control mechanisms. This
technology provides a robotic architecture (called CLARAty -- Coupled
Layer Architecture for Robotic Autonomy) that improves the modularity of
robot-system software while more tightly coupling the interaction of
autonomy and controls.

The CLARAty architecture is divided into two layers. The top "Decision
Layer" is a framework for utilizing AI planning and executive
capabilities, providing autonomous command generation and re-planning of
rover command sequences. The bottom "Functional Layer" provides standard
robot capabilities in a modular framework to control and operate
heterogeneous robotic platforms. These layers are closely coupled
together so that the decision-making capabilities of the Decision Layer
can be used in varying degrees and so that the Decision Layer can easily
obtain updated information from the Functional Layer about current rover
state.

We are currently working with the NASA robotics and autonomy communities
to expand the scope and participation in this architecture. In addition
to planning and execution capabilities, this technology also provides
the infrastructure and functionality for rover motion control,
intelligent navigation, and manipulation operations which are core needs
for a Mars 2007 type mission. This technology is current at TRL 3.
Current funding for this research comes from the Mars Technology Program
and the Intelligent Systems Program.

Mission Data Systems (MDS)

The Mission Data System (MDS) core product is a unified architectural
framework for building end-to-end flight and ground software systems.
This framework includes the necessary elements for building
goal-oriented, autonomous commanding; intelligent data management and
transport; integrated guidance, navigation, and control, and most other
capabilities needed for mission software. Externally, MDS takes goals as
input and interacts with hardware to achieve the goals. Internally, the
architecture emphasizes the central role of state knowledge and related
models. Together they give a disciplined structure for closed-loop
control, both at the traditional real-time level and at a deliberative
level. The same elements that support nominal system operations also
support fault protection.

The MDS technology directly meets several needs of future science space
missions. Many future missions involve *in situ* exploration that
involves unpredictable events. The MDS enables closed-loop software that
can react intelligently both to low-level happenings, such as a rover's
wheel slipping, and to situations that require re-planning, such as
interrupting on-going activity to perform a science observation
opportunistically. The MDS framework enables representation of intended
state of the spacecraft, affording the basis of autonomy. The generality
and multi-mission nature of the MDS framework allows shared software
structure across spacecraft, in particular the several spacecraft that
will be working together in some future missions. The shared structure
can also be used in the ground software. This uniformity eases the job
of an operations team working on multiple spacecraft.

# Health Management

Adaptive Envelopes

TECHNOLOGY: automated methods for learning upper and lower bounding
functions, for predicting nominal ranges for each engineering sensor
over time.  Exploits available historic data (e.g. early mission or
simulation data), to cheaply learn and adaptive predictive models with
minimal manual effort. Bounding function inputs include other sensors,
yielding bounds which are very context-sensitive (i.e. compared to
traditional red-line limit-sensing). Methods include advances in
large-scale support vector machines and high-dimensional nearest-neigbor
search.

RELEVANCE: automated novelty (event/anomaly/fault) detection, useful
especially for fault detection of the spacecraft engineering mission
data of many NASA missions (i.e. HEDS (e.g. Shuttle), Space Science
(e.g. NGST, Mars Rover) and Earth Science (e.g. MISR)).

BEAM/PRISM

[B]{.underline}eacon-based [E]{.underline}xception
[A]{.underline}nalysis for [M]{.underline}ulti-missions (BEAM) is a
novel spacecraft-independent, event-based, signal monitoring methodology
which combines advances in adaptive wavelet theory, nonlinear
information filtering (NIF), neuro-fuzzy system identification and
stochastic modeling. It is intended for deployment as part of an
autonomous self-diagnosis and monitoring system on-board any spacecraft.
With the exception of neuro-fuzzy diagnostic algorithms, none of the
other techniques have been previously applied for integrated real-time
spacecraft health assessment. From an algorithmic standpoint, BEAM
provides an extremely formal and robust approach to spacecraft analysis
at the system level, that goes well beyond traditional red-lining and
trending filters endemic to telemetry-based monitoring systems. Several
by-products have also resulted from BEAM development, in the form of new
design-for-operability and design-for-testability tools.

Primary research objective is to develop BEAM in the framework of a new
Fault Detection and Isolation (FDI) paradigm called, an Active State
Model. This model is one which will possess a degree of autonomy from
the environment that allows it to perform purposeful transitions not
directly controlled from the outside. It must possess
self-identification, self-awareness, and self-intelligence capabilities.
BEAM will be expanded in the areas of self-identification and
self-awareness. To accomplish this, software and demonstrations to
develop this concept will be constructed, adding to the theoretical
development completed under last years "gray box" effort.

Data Summarization / Beacon operations

TECHNOLOGY: automated selection and prioritization of the most useful
data, using statistic summaries and machine learning techniques to
identify interesting events in the data.  Interesting events include not
only \"unusual\" behavior, but also when behavior becomes more normal
again.  Includes novel methods for low-dimensional visualization of
high-dimensional multivariate data.

RELEVANCE: suitable for automated downlink determination under limited
band-width (e.g. Deep Space missions) or other resource-limited (e.g.
time, available crew) situations (e.g. focus of attention during
time-critical HEDS diagnosis analysis).

Time-Series Pattern Matching

TECHNOLOGY: a hybrid of novel probabilistic andgenerative methods for
efficiently searching for query patterns in large time-series databases.
Loosely speaking, the goal is a \"Google-like\" search engine for NASA
time-series data sets, exploiting and handling the special nature of
such data. Proposed methods include support vector
machines, high-dimensional kernel-distance indexing trees, and novel
hidden Markov model methods.

RELEVANCE: NASA mission operations generates volumes of engineering
data.  This historic data can often be of great importance, for example,
in determining that a situation similar to a current problem occurred
before (and indexing into associated logs of analysis and corrective
actions taken in that previous case).  Existing search techniques are
inadequate for the demands of such data, due to the large time scale
(e.g. multi-year missions) and high dimensionality (e.g. thousands of
sensors).

# Robust execution and control

Integrated Planning & Execution

CLEaR (Closed Loop Execution and Recovery) is a research effort to
develop a robust commanding framework to benefit automation of a variety
of robotic entities: spacecraft, DSN ground stations and rovers. While
an initial CLEaR prototype has been developed and is being integrated
into the DSSC task, the ongoing research performed under the CLEaR task
is applicable to other applications. As planning and execution are rich
areas, CLEaR is expected to repeat this cycle of develop new ideas,
prototype them, pass them on, and start back with fresh new ideas (much
in the vane of S/W Eng. Communities spiral development model).

Coordinated Team Sequence Execution

Current missions control multiple spacecraft by either giving one
spacecraft a control sequence and having it treat the others as if they
were virtually connected or giving each spacecraft its own command
sequence with inserted communications actions for coordination between
spacecraft. Neither approach scales as populations increase nor as
members become more capable. While the first requires too much
bandwidth, the second suffers from instabilities that lead to a variety
of coordination failures. This research will develop an integrated
cluster management system that controls a cluster of spacecraft with a
single hierarchical team plan instead of explicit command sequences for
each spacecraft. Developing this system involves inventing new
mechanisms for commanding a team of spacecraft as well as mechanisms for
distributed command fusion across the team to perform multiple
activities in parallel. The mechanisms must facilitate a spacecraft's
selecting actions that not only benefit itself, but also benefit the
group as a whole. The cooperation of a team of spacecraft in partially
known settings poses complex control problems, which require solutions
that guarantee a suitable trade-off between a multitude of (potentially)
conflicting task objectives within and among the robots.

Deep Space Network (DSN) Automation

The Common Automation Engine work involves the development and
implementation of a software control architecture designed for multiple
aspects of Deep Space Network (DSN) automation. While the initial
prototype effort is to develop an autonomous software controller for
goal-driven station centric DSN antenna automation, the architecture is
designed such that the same architecture and many of the same software
components can be used to perform both subsystem and complex level
automation as well. This approach would create a Common Automation
Engine solution across all the levels of DSN automation. The CAE is a
model driven system utilizing general purpose reasoning engines for:
goal expansion and constraint checking, resulting in a command sequence;
execution; monitoring and replanning. The CAE consist of the CLEaR
(Closed Loop Execution and Recovery) component and the FDI (Fault
Detection and Isolation) component. The CLEaR component is built on the
CASPER (Continuous Activity Scheduling Planning Execution and
Replanning) system and TDL (Task Description Language) deliberative and
reactive control engines, while the FDI component is built on the BEAM
(Beacon-based Exception Analysis for Multi-missions) and SHINE
(Spacecraft Health Inference Engine) diagnostics and monitoring engines.
The deployment of the CAE for station control will enable reduced
operations cost. These savings will be realized through greater
utilization of the DSN by increasing the responsiveness to anomalies and
by enabling operators to monitor more than one track at a time.
Deployment at the subsystem and complex level will provide more robust
operations. JPL's Interplanetary Network Information Systems Directorate
(IPN-ISD) funds this work.

ESL---Executive System Language

# Intelligent sensing and reflexive behavior (includes machine vision)

Machine Vision for EDL and Small-body Navigation

Exploration of the solar system will require robotic systems that can
navigate and land safely on planets and small bodies. Due to the small
size, irregular shape and variable surface properties of small bodies,
accurate position estimation and hazard avoidance are needed for safe
and precise small body landing and sample return.  Because of the
communication delay induced by the large distances between the earth and
targeted small bodies, landing on small bodies must be done autonomously
using onboard sensors and algorithms. Machine vision technologies are
being developed that can recognize landmarks for navigation, estimate
spacecraft motion by tracking surface features, and identify safe
landing sites. These technologies are being combined with guidance
navigation and control algorithms on existing real-time testbeds to
provide an integrated capability for precise navigation, landing, and
hazard avoidance.

**Hazard Detection**---A lander must be able to detect safe landing
sites from hazardous ones. We use motion stereo vision to generate dense
3D topographic maps of a small body surface from monocular image
streams. Image-based motion estimation is applied to determine the
spacecraft motion between each frame, then each image is rectified to a
fixed plane and stereo vision techniques are used to match image pixels
to obtain pixel level depth estimates. Terrain hazards are then
extracted from the surface map.

**Position Estimation**---Our research combines two complementary
methods for position estimation: feature tracking and landmark
recognition. Feature tracking detects and tracks image features through
a sequence of images enabling the six degree-of-freedom (DoF) relative
motion of the spacecraft to be determined for each frame. Landmark
recognition first detects landmarks during 3-D modeling of the body and
stores them in a database along with their positions. To estimate
position, landmarks are detected and matched against the database to
obtain the absolute position of the spacecraft relative to the body. By
combining the continuous updates of relative position from feature
tracking with the occasional updates of absolute position from landmark
recognition, continuous estimates of spacecraft position in absolute
body centered coordinates can be obtained.

**Autonomous Landing**---This research will develop a closed-loop
image-based safe and precise landing capability by integrating position
estimation, hazard detection, and 3D surface reconstruction algorithms
with an aerial test bed composed of a commercial model-helicopter
chassis, onboard processing and multiple navigation sensors.

Machine Vision for Safe and Precise Landing

NASA\'s plan for solar system exploration is filled with missions that
require landing on planets, moons, comets and asteroids (Mars Smart
Lander, Mars Sample Return, Europa Lander, Comet Nucleus Sample Return).
Each mission has its own criteria for success, but all will require some
level of safe and precise landing capability. Because of the
communication delay induced by the large distances between the earth and
targeted bodies, landing must be done autonomously using onboard sensors
and algorithms. Currently, many scientifically interesting landing sites
must be excluded during mission design because landing systems are not
robust enough to land safely in hazardous terrain. To increase access,
improve safety margins and enable autonomous landing, new landing
techniques must be investigated. Machine vision and passive image-based
control algorithms are being developed that enable safe and precise
landing on hazardous terrain. These algorithms will provide estimates of
motion and position used to guide a lander during precision landing.
They will also enable hazard avoidance by providing estimates of 3-D
surface topography through processing of monocular image streams
followed by real-time decision making to assess hazards and select a
safe landing site. Currently algorithms are being designed and tested in
controlled laboratory settings (TRL 1-3). However in the near future,
closed-loop image-based safe and precise landing will be demonstrated by
integrating the above algorithms with an aerial testbed composed of a
commercial model-helicopter chassis, onboard processing and multiple
navigation sensors (TRL 4-6). The Intelligent Systems Program and
Interplanetary Network Technology (TMOD) are funding this work.

MISUS---Multi-rover Science Exploration

Autonomous systems will play a large role in future rover and robotic
missions, especially for missions that require intelligent coordination
of multiple robotic agents. The MISUS (Multi-Rover Integrated Science
Understanding System) system integrates AI planning and machine learning
techniques to autonomously provide both scientific direction and
distributed control for a team of rovers. A distributed data-analysis
component analyzes science data and generates new science exploration
goals for the rover team to achieve. A distributed planning component
assigns goals to rovers in a fashion that minimizes total traverse time,
and then creates the required command sequence for each rover to
efficiently achieve its assigned goals. New research using this
framework addresses the problems of 1) determining and achieving
interdependent science goals and 2) performing continuous science where
science goals and plans are continually modified based on new data. The
resulting onboard system will provide a novel "onboard scientist"
capability to a team of rovers and will enable the team to investigate
science goals and hypotheses in a closed-loop fashion with little or no
ground communication.

Autonomous retargeting & downlink selection

The Autonomous Sciencecraft Constellation (ASC) experiment will use
onboard software for science data analysis, replanning, and
constellation management to enable onboard decisions to: downlink or
discard science data, retarget instruments to acquire further science
data, recover from anomalies to quickly resume operations, and to use
execution feedback to reduce observation setup time. ASC allows
spacecraft operators to command using high-level goals and respond to
dynamic events such as volcanic eruptions, flooding, or planetary
surface change. ASC can also take advantage of using several spacecraft
to coordinate science operations as a single virtual instrument.

Any mission with limited bandwidth constraints or dynamic science events
could benefit from using the ASC software. Onboard science data
processing as defined in this report has been identified by the NASA
Space Science Technology Steering Group as an enabling technology for
several Exploration of the Solar System (ESS) missions including Europa
Orbiter (EO), Pluto Express (PE), Neptune Orbiter (NO), and Saturn Ring
Observer (SRO). ASC is at TRL-5 and will be at TRL-7 by early 2002.
Funding sources include the New Millennium Program, the IPN-ISD
Technology Program, and the Cross Enterprise Technology Development
Program.

# Collaborative decision making

WITS Rover control workstation

Web Interface for Telescience (WITS) has provided a "front-end" for the
science community to the commanding process. This front end will lower
operations costs by enabling science team members to participate from
home institutions using readily available internet-based tools. This
task will extend the existing remote user capabilities to include a
collaborative environment wherein scientists from several institutions
can examine/plan integrated science observations while looking at a
common set of views of the data. Task will provide the tools to support
rapid conflict-resolution by the distributed science team. These tools
may be technical or organizational. Future missions are likely to
require that rover activity requests be generated within 1 hour of
telemetry receipt thereby requiring that consensus-building tools be
available to make such rapid decision making possible.

In the future we wish to explore moving an automatic command sequence
generation capability on board the rover to enable multi-day (e.g. sol
for Mars) autonomous operations. In this situation, science activity
requests would be uplinked to the rover which in turn would be capable
of re-scheduling activities based on available resources or anomalous
conditions. Since the rover would often be able to re-plan rather than
"phone home" in the event of anomalies, the potential increase of
science return per command opportunity could be significant, while
reducing the load on an over committed DSN resource.

Integrate a resource modeler/activity scheduler with the Rover Control
Workstation and the WITS "front-end". The addition of the
modeler/scheduler will enable rapid determinations of activity request
and command sequence feasibility. This will be a key to shortening
command turnaround times. It would be the objective of this effort to
generate rover command sequences automatically from activity requests.
Depending on the processing resources required, this has the potential
to significantly reduce command turnaround time, and would allow
sequence planners to review and modify existing sequences rather than
being required to build them from scratch.

# Machine Learning Systems

SkiCat -- clustering and cataloging of astronomical sky surveys

A collaboration among the JPL Machine Learning Systems Group, Caltech
Astronomy, and the Palomar Observatory developed a powerful software
system called SKy Image Cataloging and Analysis Tool (SKICAT). The
system incorporates the latest in AI technology, including machine\
learning and knowledge discovery that automatically catalogs and
measures sources detected in thousands of digitized photographic plates
from Digital Palomar Sky Survey (over 3 terabytes of raw image data). 
The system can be trained by an astronomer to perform the
knowledge-intensive and labor-intensive task of finding, measuring, and
objectively classifying the sky objects as stars or galaxies, and to
assist an astronomer in performing scientific analyses of the resulting
object catalogs.

The enabling autonomy technology behind SKICAT is a state-of-the-art
decision-tree induction algorithm that learns highly-accurate
star/galaxy classification rules from astronomer-supplied training
data.  SKICAT produced the comprehensive Palomar-Norris Sky Catalog
containing an estimated fifty million galaxies and two billion stars,
with each detection reliably classified one full magnitude fainter than
previous comparable surveys to date (a 200% increase in size of data
usable in analysis).  Additional unsupervised clustering algorithms have
been applied to assist the astronomers in discovering distant quasars
and other rare types of cosmic objects of an unknown nature.\
\
SKICAT is TRL 5.

StarTool -- solar feature recognition & tracking

This image analysis technology automatically recognizes scientifically
relevant features in multi-spectral images, with emphasis on solar
imagery. System operation begins by using images labeled by scientists
to learn a statistical model automatically for the features of interest.
As new images are acquired, this model is coupled to general-purpose
image-analysis software that integrates the resulting spatial cues to
define local, pixel-level assessments of activity. These pixel-level
cues are then progressively linked into a coherent, object-level scene
description of the phenomenon of concern. The result is a directly
interpretable summary of scientifically relevant information in the
image. Our use of open standards for structured data (e.g., object
models and datasets in XML with suitable schemata) ensures portability
across applications and future extensibility.

Hypothesis-driven onboard science

Although a very successful mission, Mars Pathfinder demonstrates the
limitations of existing capabilities of surface robotic exploration. The
finite lifetime of the rover, together with restricted communications
bandwidths, lead to a reduction in the amount of science return. One way
to increase the amount of science return is to make rovers more
autonomous. This requires converting the rover into an "intelligent
field assistant" by equipping the rover with the necessary tools to make
autonomous decisions while in route. We are developing an innovative
encoding and onboard encapsulation of geological process information,
coupled with machine learning data analysis techniques, to enable the
rover to efficiently collect and assimilate scientific data. Algorithms
which allow the rover to observe and interpret, sensed geological data,
are currently under development. A preliminary result of this effort is
a novel clustering algorithm for mutually constraining heterogeneous
features applied to a geologic rock-patch-facies-deposit model. Our team
consists of machine learning experts as well as planetary geologists.
The project is currently at TRL level 2. This effort is funded by the
Intelligent Systems program. Previous funding was provided by the Cross
Enterprise Technology Development program.

DiamondEye -- data mining & discovery

The Diamond Eye Project targets development of a suite of algorithms
that will enable both scientists and remote systems to find, analyze,
and catalog spatial objects and dynamic events in large scientific
datasets and real-time image streams. The algorithms are integrated
within an innovative image data mining architecture that is also being
developed within the project.

This research is developing algorithms to find, analyze, and catalog
spatial objects and dynamic events in large scientific datasets and
real-time image streams. These algorithms include *adaptive recognition*
algorithms that are trained from user-provided examples and can be
easily customized to new domains without reprogramming; novel techniques
that enable a user to formulate and execute *queries* for objects within
large image collections based on models that are bootstrapped from
single examples and/or sketches; generic *discovery algorithms* that can
autonomously identify \"interesting\" objects with no prior model; and
processing techniques based on *temporal motion coherence* for change
detection.

Applications of this technology have included automated crater detection
in Viking data, artificial satellite detection (NEAR), and detection of
Venusian volcanoes. These pattern recognition techniques are also the
core onboard processing technology for the Autonomous Sciencecraft
(ASC), a New Millennium ST6 technology validation mission now in the
study phase. If selected for phase B funding ASC will fly onboard
TechSAT-21, an Air Force Research Laboratory satellite constellation
scheduled for launch in 2004. ASC will demonstrate autonomous onboard
recognition and retargeting of fast-breaking science events, and
intelligent onboard science data selection and reduction to make the
best use of limited downlink bandwidth. ASC is a collaboration including
JPL, the Air Force Research Laboratory, Interface & Control Systems,
Princeton Satellite Systems, Arizona State University, the University of
Arizona, and MIT.

Temporal & Spectral Data Mining / super-resolution

This software enables scientists to automatically extract from vast
satellite image databases scientific information that would otherwise be
effectively unavailable due to the enormous manual analysis and search
effort required. Application of these methods has identified fault lines
at sub-pixel resolutions in satellite imagery, and identified a possible
quake-precursor signature. The software technologies underlying this
system include novel algorithms for veneer (snow, haze, vegetation)
removal, and 'super-resolution' algorithms that can detect planetary
surface motion at sub-pixel resolutions (e.g., 3m motion in 10m
imagery). Although these algorithms have primarily been applied to
Earth-science data, they are equally applicable to space science data
such as multi-temporal MGS data sets.

Knowledge Discovery from Simulators

Simulators play a fundamental role in investigations by scientists and
engineers across NASA, DoE, DoD, FAA, industry, and academia, in many
cases, providing the means to examine processes that would be infeasible
or impossible to study otherwise. We are developing data mining and
knowledge discovery techniques to enable efficient, in-depth exploration
and exploitation of such large-scale numerical simulators, emphasizing
two science applications: (1) origins of the planets and long-term
behavior of Solar System bodies and (2) magnetospheric dynamics. Unlike
traditional data mining, a unique aspect of this work is that the
analysis is not confined to a static dataset; instead, the simulators
can be used to generate new data leading to rich opportunities for
active learning. This work is being performed in collaboration with the
South West Research Institute.

TECHNOLOGY: new practical large-scale active learning data mining
methods, for automated adaptive discovery of the most informative ways
to drive a simulator to support science discovery (e.g. which initial
states and which knob settings to try next).

RELEVANCE: exploit recent advances of high-performance parallel
computing, which now produce large, accurate simulators, but do not
address the problem of how to harness these simulators with minimal
manual effort. Our approach initially focuses on demonstration on a
couple of science problems: identifying boundary conditions of different
types of planetary formation and magnetosphere-based prediction of space
weather. Our results will be relevant to improving the science
throughput and lowering the costs for many other existing and planned
NASA \"science by simulation\" efforts as well.

Knowledge Discovery Support Systems

The vast amounts of data that NASA has collected and continues to
collect via remote Earth monitoring contains a wealth of information
about the changing nature of our planet. Current methods for extracting
information on many ongoing processes are very time consuming and labor
intensive. Even more difficult is the synthesis of data from the vast
array of available sources into a coherent understanding of events.
Therefore the objective of this task is to develop a discovery support
system that generates, test, and actively exploits models appropriate to
a scientific domain. For this purpose a wide variety of leading edge
data mining and machine learning techniques are being integrated,
adapted, tested, and validated on multiple scientific data sets
including MISR. The discovery support system will move from a pure data
mining approach for analysis of large data sets to a predictive modeling
approach via inference algorithms such as SVMs, MRFs, stochastic
grammars, generalizations of Bayes nets, multiscale methods, and
objective function optimization. Benefits to NASA include software
interfaces for reusing, recombining, and extending existing algorithms
to solve new scientific data understanding problems. We will have the
ability to directly compare a variety of competing algorithms under the
same test conditions. The project is currently at TRL level 2. This
effort is funded by the Intelligent Systems program.

Sensor network data fusion & data mining (Donnellan)

WINDS (Autonomous Feature Identification and Data Compression)

The Autonomous Feature Identification and Data Compression -- WINDS task
creates a capability for tracking dynamic features autonomously. Current
autonomous tracking systems for spacecraft operations have no ability to
track dynamic features, and may miss the target body completely during
close encounter geometry, high instrument pointing rate sequences, like
DS1. Successful feature tracking systems still use a human operator to
identify common features. Unfortunately, this is inconsistent with
autonomous operations. This task develops a non-linear Gruen correlator
automatic on-board feature tracker, with the unique ability to track
small-scale features in complex image sequences. For dynamic image
sequences, the correlator will achieve a 100x data compression factor;
autonomously  compute wind speeds, vorticity, and divergence; and vastly
improve our science ground data processing and analysis. Adaptive data
compression algorithms are required to return the ever-increasing volume
of data from remote spacecraft. This task also develops software for
creating simulated images from a small set of observations.  This
capability will be useful in developing simulated mission environments
and animation sequences. In the case of animation sequences, WINDS
velocity-based interpolation should be able to create hundreds of
simulated images from a handful of original observations.

CANAL (image processing & localization for rover traverses)

CANAL (Canyon Access Navigation and Autonomous Localization) will
provide an end-to-end demonstration of the image processing and
localization technology required to traverse a canyon environment.
Current work in rover localization utilizes landmarks for identifying
the current position of the rover but these algorithms have been
primarily developed and tested in flatter terrain with features on the
horizon visible from many if not all locations. The limited horizon and
reduced range that occur when operating in canyons and valleys creates
new challenges for technology developers. In one of these operations
scenarios, a rover might travel one or two hundred meters and be out of
sight of all previously known landmarks. This will require more
continuous monitoring and analysis of features in the vicinity of the
rover with specific emphasis on the vertical features and striations on
canyon walls and cliff faces. Such data may be nearly invisible to
orbital or descent imagers and thus not in a baseline landmark database.
An additional constraint is that being in a canyon might reduce the
communication window with ground stations thus increasing the level of
autonomy required by the rover. Key features to be demonstrated are
tracking of features on canyon walls, higher rates of tracking due to
reduced range to the features, and integration of tracked data into
baseline 3D terrain models for science visualization and mission
planning. Additional key technologies to be demonstrated include an
incremental bundle adjustment for optimizing the feature tracking, the
generation of 3D terrain models from the feature tracking process, and
the merging of the terrain models into a coregistered, multi-resolution
model of the entire sortie area (through coordination with the SUMMIT
task).

SUMMIT (three-dimensional terrain models with multi-resolution data)

The goal of the SUMMIT task is to develop a capability for creating
three-dimensional terrain models with multi-resolution data. Although
various sources of data and imagery associated with typical missions
have been used to create 3D terrain models, to date, there has been no
unifying direction in this area. The technology product will merge data
from various sources into a single, multi-resolution data set
representing the three-dimensional topology of the terrain with each
piece in the correct, georeferenced position. The models generated via
this integrated tool suite will be output in a variety of formats to
promote easy interfacing with JPL legacy software. The primary
innovation in SUMMIT is in the co-registration and merging of multiple
resolutions from multiple missions and instruments. Current industry
practice is limited to multiple views at a single resolution. This type
of model is necessary to provide smooth exploration of large terrain
areas for planning rover landed operations over multiple kilometers.

Progressive Transmission (downlink prioritization)

3-D Characterization and Progressive Transmission of Geological Surfaces
on Mars is developing techniques for extracting important geometric and
morphologic information from the images taken by Rover cameras so they
can be transmitted to Earth using a tiny fraction of the available
bandwidth. This information will allow a ground-based user to
reconstruct the geometry and morphology of isolated rocks in a virtual
environment. Geometry information will also be used to improve the
performance of visual-based geology classification algorithms. The
proposed technology will add considerable value to Mars missions, since
the geometry data can be integrated into 3-D maps obtained from other
sources (lander-based stereo cameras, descending imagery, etc.),
improving the effectiveness of navigable immersive virtual environments
of the Mars surface.

Sensor network data fusion & data mining

In recent years emphasis has been placed on networks of instruments
termed sensor networks or sensorwebs. By using multiple sensors it is
possible to gain a greater understanding of the region in study.
However, this results in growing amounts of data that must be analyzed
and interpreted. Datamining techniques such as pattern recognition and
feature extraction and classification make it possible to rigorously
characterize and interpret the data. For example, it may be possible to
map out various geologic regions by having a network of sensors, for
which the data can be classified. Sensor networks may produce time
series or spatial data and the datamining techniques can be applied to
both. These data may be noisy, sparse, or irregularly sampled. An
investment in algorithms is necessary to handle these types of data.

# Quantum Computing

Quantum Computing Algorithms & Hardware

As we move out into the next century, NASA envisions a huge increase in
the number of concurrent space missions. In such a climate the
computational demands we will face will become significant factors
impeding progress. Moreover, as our spacecraft become more remote from
Earth, the speed of light limited communication delays force us to place
more autonomy on-board. To function autonomously, such as to re-plan a
series of observations, and data analyses in real-time during a fly-by
of an astronomical body, we need to bring massive computational power to
bear under extreme constraints on allowed mass, time and power. We have
designed quantum algorithms, which run on a quantum computer, and that
solve hard NASA problems.

Quantum Lithography: It has been known for some time that entangled
photon pairs, such as generated by spontaneous parametric down
conversion, have unusual imaging characteristics with sub-shot-noise
interferometric phase measurement. What we show is that this type of
effect is possible not only in coincidence counting experiments, but
also in real two-photon absorbing systems, such as those used in
classical interferometric lithography. In particular, we have
demonstrated that quantum entanglement is the resource that allows
sub-diffraction limited lithography.

# Autonomous Navigation & Integrated GNC

Autonomous Maneuver planning

ADAPTIVE INTERPLANETARY NAV focuses on developing and testing algorithms
and software that can be used during cruise and potentially in real-time
environments to autonomously sense and detect anomalies and mismatches
in navigation models and estimators. Such capabilities will lower
operations costs and lower risk by enabling better, more consistent, and
earlier anomaly detection (and correction).

AUTO MANEUVER OPT is developing and performing proof of concept for new
algorithms and software to automatically plan and optimize multiple
maneuvers over an entire mission. The main thrust of this effort is to
lower overall mission costs for navigation.

SEMI-AUTO AEROBRAKING OPS is a task that is raising the TRL for
readiness of autonomous operations for the delicate process of
aerobraking at a planet like Mars. This task should enable JPL to
operate autonomously during aerobraking phases, which have in the past
required extremely expensive round the clock operations at DSN sites and
at JPL