Projects

Automated Reasoning for Autonomous Systems

Deep space exploration requires significant advances in artificial intelligence to support the needed capabilities for autonomous systems. RIACS scientists and visitors have been collaborating with NASA researchers in a number of areas:

• Spatial Statistics and Forecasting for Earth Science Data
• Event Analysis for the Gammy-ray Large Area Space Telescope
• Robust Execution for Planetary Rovers
• Planning for Mars Exploration Rovers (MERS)
• Verification and Validation
• Automated Software Synthesis
• Framework for Distributed Computing
• Automatic design and rugged terrain mobility of a four-legged robot, via reinforement learning
• Autonomous Rotorcraft Project
  ----
• Automated Software Engineering
• Planning and Scheduling
• 3-D SuperResolution

Autonomous Systems

Spatial Statistics and Forecasting for Earth Science Data

      RIACS Contributors: Robin Morris
      Visiting Contributors: Dr. D.G. Luchinsky, University of Lancaster, UK

Work in this task covers two areas: quantum inspired algorithms and nonlinear dynamical system modeling.

Quantum Inspired Algorithms

The complexity of combinatorial optimization algorithms is of great theoretical and practical importance; a holy grail of computer science is a resolution of the P=NP question. While we make no claim to solve this problem, we do address the computational complexity of certain quantum computing algorithms applied to certain NP complete problems, and the derivation of classical algorithms that are inspired by, and share some of the characteristics of, these quantum algorithms.

The main algorithm studied is the quantum adiabatic evolution algorithm, where during the time-evolution of a quantum system the system Hamiltonian is changed gradually from a simple form, to one, which has as its ground state the solution to the desired optimization problem. We study the complexity of this algorithm.


Nonlinear Dynamical Systems

Many physical systems can be modeled as nonlinear dynamical systems. For example, the oscillations of the human cardiovascular system can be so modeled, as can the dynamics of disease epidemics and animal populations. However, the inference of the parameters and structure of these models is a topic of ongoing research, and is what we address here.

We are developing Bayesian inference techniques for these problems. Initially we will develop methods to infer the parameters of a model from data, when the system is driven by a stochastic input, and also when measurement noise is present. We will study the trade offs between various approximations that must be made to make the methods practicable. We will also study the problem of learning the structure of the nonlinear dynamical system models. This is a much harder problem, as the number of possible models grows rapidly as the type of complexity considered increases. For example, for models with a polynomial basis, the number of possible models grows rapidly with the dimensionality of the problem (the number of independent variables in the dynamical system) and the order of the polynomial basis.

We will study this problem, and develop practical methods of solution. These will be based on search methods for combinatorial optimization problems, but we can include domain knowledge to guide the search and make it more efficient.

The work in this task is focused on statistical prediction. It addresses two main application areas.
1. Issues of uncertainty in biospheric parameters derived from satellite and other observations (so-called "data products"), and the incorporation of these measures of uncertainty into biospheric predictions;
2. Inference of nonlinear dynamical system models from observational data, and the use of these models to predict failure modes and events.
The Earth Science community relies extensively on satellite observations as a primary source of data. From these observations, a large number of "data products" are derived. For example, data from the MODIS satellite are used to generate over 30 derived data products, which give information about quantities which are either impossible to measure directly, or unfeasible to measure directly over the large areas of interest. These secondary data sources are used to infer the behavior of the ecological system under study. In this work we study the uncertainty in these derived quantities. For more info visit:
http://www.ntsg.umt.edu/MODISCon/


Event Analysis for the Gamma-ray Large Area Space Telescope

      RIACS Contributors: Robin Morris

An international collaboration, including NASA, is building the Gamma-Ray Large Area Space Telescope (GLAST) for launch in 2006. The main instrument on the spacecraft is the Large Area Telescope (LAT). This detector functions by converting incoming gamma rays into electron-positron pairs, and detecting the trajectories of these particles, and any secondaries produced, as they traverse the detector. From these sampled trajectories the direction and energy of the incident photon must be estimated.

This task is focused on the development of a proof-of-concept of a statistical analysis methodology for the LAT instrument. The methodology is based on sequential importance sampling and Markov chain Monte Carlo (MCMC) methods, and incorporates a detailed, accurate description of the physics of the detector – the production and scattering of the primary electron and positron, and the action of the detector microstrips.

Initially, work has been focused on two areas. A simulation of a simplified version of the detector, which has enabled studies to be made of the statistics of the physical processes that occur in the detector, and enable importance sampling distributions tuned to those processes and the geometry of the detector to be developed. The second area is the development of the analysis methodology, which has been demonstrated for carefully chosen events (in which no secondary particles were produced).

 

Automated Reasoning

Robust Execution for Planetary Rovers

      RIACS Contributors: Emmanuel Benazera

This task focuses on robust and flexible plan execution mechanisms, planning and execution under uncertainty, plan revision to adapt to changing situations, and runtime state estimation algorithms. The work in this project is focused on the requirements for autonomous planetary rovers. The goal of the rover autonomy work is to demonstrate, within NASA and the larger scientific community, the integration of planning, execution and diagnosis technologies and the vital role they play in intelligent control of autonomous vehicles, and other complex systems, such as rovers.

A rover operates in a complex and only imprecisely known environment. The rover must be able to cope with deviations from its preliminary expectations. In addition, today’s best planners have difficulty handling the complexity that is due to the domain uncertainty. Therefore they produce plans that do not take into account numerous situations, such as faults or other changes in the domain (models of rover behavior, etc...). For this reason, a rover must make decisions and perform actions despite and imprecise model of its situation. The objective of this task is to develop robust plan execution techniques for planetary rovers and demonstrate these capabilities in service of requirements for future missions.

Here we are concentrating on methods that retain the original plan topology, potentially adding and merging pre-computed plan fragments for reacting to common, specific or dangerous situations. These methods have been proved working on rovers and are now enhanced to significantly increase the envelope of possible rover behaviors, safety and efficiency (increased science return).

 

The major directions of the project and the associated collaborations are as follows:

Rover Execution:

The major research focus of this task is to investigate techniques for enhancing the effectiveness and reliability of autonomous operations, in particular applied to planetary robotics. First, we have concentrated on a utility-based approach, and we have explored on-board plan adaptation and plan merging techniques, which lie somewhere between simple execution and full-scale planning (Dr. R. Washington). Based on state estimation and fault diagnosis research also performed in this task (see below), we explored the combined use of these techniques for increasing plan execution robustness and safety (also see below). The core software product of this research is the CRL Executive. The CRL Executive is responsible for interpretation of the contingent plan coming from the ground and generated by the contingent planner. The CRL Executive is designed to be more capable than traditional sequence execution engines; it can handle the expressive plans generated by the contingent planner and can perform limited plan adaptation itself.

Runtime State Estimation and Diagnosis for planetary rovers:

The general goal of this research is to provide a diagnosis system capable of being applied to a broad class of diagnosis problems (Dr. R. Dearden). We built on our past work on tracking the state of a partially observable hybrid system based on particle filtering. Bringing these algorithms to planetary rovers led to a new set of problems that this task helped solving. Namely, the modeling of complex systems with hybrid dynamics due to the numerous switches in the system control, and the asynchronous nature of observations on-board a rover where observations from different subsystems arrive at different rates, and occasionally out of order, leading to large amounts of uncertainty in the state of the system.

Integrating Diagnosis and Execution:

On-board state estimation affects the execution of contingency plans (i.e. plans that are trees of conditioned plan branches), during which the rover has to decide on which branches of the plan to execute given the current estimate. As conditions on branches are pre-computed by a contingency planner on ground accordingly to a certain model of the rover (also referred to as the planning domain), these conditions can become invalid when the state of the rover significantly deviates from this model. Also, the probabilistic nature of the estimates complexifies the evaluation of these conditions. Typically, plan re-evaluation is a very computational operation that in theory should be performed almost continually, and thus is intractable as is. Our research has been to get a precise understanding of when and under which hypothesis branch conditions had to be re-evaluated (at runtime, on the rover) so to minimize the computational overhead, and to explore and implement the most efficient techniques to do so (Dr. R.Washington and Dr. E. Benazera).

IS Level 1 Milestone / Single cycle instrument placement:

In collaboration with the K9 Rover project (M. Bualat, NASA, Navigation and Instrument Placement project (L. Perdersen, QSS), Visualization project (L. Edwards, NASA), and Contingency Planning project (D. Smith, NASA), we produced an integrated rover planning an execution system for the NASA Ames K9 planetary rover prototype in service of demonstrating single-cycle instrument placement, which is a level-one milestone for the Intelligent System (IS) program. The demonstration took place in November 2004.


Planning for Mars Exploration Rovers (MER)

      RIACS Contributors: Ari K. Jónsson

The daily operations of the Mars Exploration Rover are characterized by limited time between downlink and uplink, high expectations for science return, and complex limitations on safe rover operations and on-board resources. Specifically, during the nominal mission, each of the two rovers is operated every sol, which means that the time to develop a complete command sequence for the next sol is restricted to the 14 hours from downlink of status data to uplink of command sequence. Only a small portion of this limited time is devoted to deciding on the science activity for the upcoming sol, which involves choosing among competing science needs and desires, while also taking into account operations limitations, resources, and engineering constraints. To address this problem, an intelligent, mixed-initiative science activity planner, called MAPGEN, is being used during ground operations. This tool helps users to make informed decisions more quickly and provide better visibility into applicable resources and operations constraints.

The key objective of this work was to develop, deliver, and support the intelligent mixed-initiative science activity planning tool MAPGEN for ground operations during the Mars Exploration Rover mission. The work was done in collaboration with other members of the MER planning tool team, as well as a number of MER mission team members at JPL. The MAPGEN tool is designed to assist scientists and engineers to build science activity plans that accomplish as much science as possible while satisfying resource limitations and operational constraints. The tool allows users to visualize a current plan, modify it while constraints are actively enforced, request assistance from an automated planning algorithm, and get explanatory information about the plan. The core objective of this task, in particular, was to complete the development of the tool, deliver it to the mission, and support its use during the mission. This support involved both hands-on support during operations, and software update support as needed. For additional information, see: http://www.arc.nasa.gov/exploringtheuniverse-mapgen.cfm

Looking beyond the MER mission operations, the goal is to then build on the techniques developed for MAPGEN and the experience gained in the MER participation, to bring automated reasoning to future mission support applications and to other space related applications, such as on-board rover automation.

 

Software Engineering

Verification and Validation

      RIACS Contributors: Dimitra Giannakopoulou, Charles Pecheur, Willem Visser

The main objective of this task in verification and validation (V&V) is to improve the reliability of software developed at NASA, which in turn will reduce the risk of mission failure. A second (and often equally important) goal is to improve software development by employing techniques from theoretical computer science, specifically Formal Methods, to reduce software development costs.

In order to accomplish these goals, the group is investigating the use of model checking to automatically analyze either software already in use at NASA, or new systems under development. Specifically, they are analyzing autonomous systems currently being developed at NASA Ames and JPL on both the architectural and code level as well as avionics software systems for both space flight and commercial aviation.

Under this task, the group has been one of the pioneering research groups applying model checking to real software - a field that has been flourishing the last couple of years. Some of their most notable successes have been finding errors in the Remote Agent autonomous system before and after its space flight (as part of NASA’s Deep-Space 1 mission) and rediscovering a known problem in the DEOS real-time operating system used in certain business aircraft. In both cases they applied model checking directly to the code for these systems, hence showing the viability of this approach.

Automated Software Synthesis

      RIACS Contributors: Bernd Fischer, Julian Richardson, Johann, Schumann

The main focus of this research task is the development of advanced program synthesis tools for the automatic generation of reliable, high-quality code from a high-level specification. From a user’s point of view, such a synthesis system can be seen as a very smart compiler. In this task, synthesis tools and approaches for several NASA-relevant domains, such as science data-analysis, spacecraft and aircraft state-estimation are developed, as are techniques, which facilitate the certification of the generated code.

Visiting Staff:

• Tomas Bures, MCT summer intern
• Jeff Green, QSS intern
• Joe Hendrix, MCT summer intern
• Eugen Nistor, MCT summer intern
• Christos Sofronis, MCT summer intern
• Amber Telfer, MCT summer intern

Project Description:

 AutoBayes: Automatic Synthesis of Data Analysis Programs

AutoBayes is an automatic program synthesis system for the data analysis domain. It can compile a high-level statistical model describing an analysis problem into a custom algorithm design and then further down into a fully documented program (currently C and C++) implementing that design. The system is intended to automate the application of known algorithmic principles in novel contexts; it provides much more flexibility than a fixed code repository and allows the fully automatic implementation of efficient new algorithms. AutoBayes uses a schema-based approach to program synthesis that combines aspects of Bayesian networks, automated theorem proving, symbolic-algebraic computation and generic programming.

AutoFilter: Automatic Synthesis of certifiable Software for State Estimation

AutoFilter is a tool for the automatic generation of software for state estimation using Kalman filters. Given a high-level description of the system (as a set of process and measurements differential equations), the system can automatically perform all the intermediate steps (e.g., linearization or discretization) to finally produce code for the state estimation problem. This tool is based on the architecture and symbolic subsystem of AutoBayes.

Frameworks for Distributed Computing

      RIACS Contributors: Robert E. Filman

Intelligent Publish-and-Subscribe Mechanisms for Airspace Information

This work examines "intelligent" publish-and-subscribe mechanisms as a foundation for transforming national airspace information management. The airspace system generates and consumes much information, such as plane intentions and locations, weather and air turbulence conditions, specific passenger and baggage itineraries. The current information architecture is based on vertical applications where information sharing often comes only either through considerable additional engineering or by inserting human intelligence into the communication path. A publish-and-subscribe mechanism, where information generators publish "interesting" information, where information consumers present "subscriptions" that describe what information they are interested in, and the underlying system arranges for the just right information to flow from the publishers to the subscribes seems a good basis for creating an efficient, expressive and evolvable airspace system. This work includes development and analysis of a hierarchy of possible subscription languages, and development of a matchmaking process for matching up publishers and subscribers.


Trinity: Event-based Aspect-Oriented Programming

This work examines the notion of aspect-oriented programming as quantification over events in the context of developing a system, Trinity, for transforming programs with respect to interesting event descriptions. This work divides the kinds of things which a programmer might want to say about a program into three sets: things relating to the syntactic structure of the program, conclusions from static semantic analysis, and the events of program execution, and recognizes that one can want to either structurally transform a program or dynamically perform an action in response to the occurrence of such things. (Though structural transformation based on dynamic events is precluded). Work continues on building a system for realizing these ideas.

NASA has a major problem in coordinating the distribution of and collaboration about scientific and engineering data and information among widely separated scientists and engineers. This appears in activities such as spacecraft design and scientific data dissemination for space operations. Examples of current NASA projects of this kind include the Darwin distributed wind-tunnel data system (http://www-darwin.arc.nasa.gov/docs/ ), and the Mars Exploratory Rover/Collaborative Information Portal (MER/CIP).
The goal of this task is to research mechanisms to ease the construction of such distributed information systems. This includes developing frameworks for distributed systems, mechanisms for the creation, development, debugging, and evolution of software systems, and tools for the distributed analysis of data. Accomplishments under this activity have included design and implementation of the Object Infrastructure Framework for distributed applications, creation of a theory of aspect-oriented programming (AOP), and the current creation of a generic AOP program transformation system.
For more information:
http://www-darwin.arc.nasa.gov/docs

Automatic design and rugged terrain mobility of a four-legged robot, via reinforcement learning

      RIACS Contributors: Doron Tal

This project aims to build a four-legged robot and teach it how to walk on uneven outdoor terrains. The second goal is to develop a general methodology for rapidly and automatically learning robotic controllers. This project is funded out of a NASA Director’s Discretionary Fund grant (for more info, see http://armstrong.arc.nasa.gov/~dtal/RTQ) and funds 50% of the PI’s time.

Current robotic controller design methods are human-intensive, slow and expensive, lasting up to months for training a single robot to move about in difficult outdoor terrains. We aim at (and have already simulated) methods that take on the order of hours to teach a robotic controller various walking behaviors. Our methods are general enough to be useful, with little or no modifications, in multiple ways: i) optimizing robot shape parameters for a particular environment, e.g. optimizing the leg lengths of a walking robot for walking in sandy terrain, so that the optimal-length legs can be swapped-in for better performance; ii) re-learning a robotic controller upon a component failure, so that the robot can continue to move even if a leg fails to respond as expected; iii) continuously adapting the robot’s gait behavior to its environmental conditions, as sensed by its limited and noisy sensors, in order to maximize some quantity, e.g. maximizing walking speed or minimizing power consumption in a particular terrain.

NASA critically needs methods to i) rapidly and inexpensively design controllers at initial robot development phase, and ii) continuously adapt operational robots to their changing conditions, including partial hardware failures. To date, highly sophisticated robots (e.g. with variable suspension, combinations of legs and wheels, hyper-redundant designs such as serpentine robots or humanoid robots) have not been deployed in many NASA missions even though the hardware is readily available, due to the high software and operations costs. Controller design for such robots is too slow and expensive, and fault recovery for high DOF robots is poorly understood. These vehicles, however, are much more capable than today’s robots in traversing rugged terrains and in negotiating obstacles that are large (relative to the robot’s size). Their multiple redundant modes also increase the chance that they remain useful even after a component failure. Our project uses an automated and fast learning architecture that will make this possible.

Autonomous Rotorcraft Project

      RIACS Contributors: Doron Tal

This task began in March 2004. Doron Tal is a member of a 5-10 person team dedicated to this project.

 

The Autonomous Rotorcraft Project (ARP) is developing an all-inclusive autonomous helicopter research platform using unique in-house skills in helicopter guidance and flight control, robotics planning and scheduling, and emerging UAV sensor technology. Unlike part-task research platforms, the comprehensive ARP autonomous helicopter system will be capable of identifying and addressing those weaknesses that most impact mission effectiveness. This will be done so that ARP can provide the needed design guidance to future NASA and Army system development efforts (for more info, albeit somewhat outdated, please see http://armstrong.arc.nasa.gov/~dtal/ARP).

ARP is motivated by needs formally originating within the NASA Computing, Information, and Communications Technology Program (CICT, Ref. 1), the NASA Bioinspired Engineering for Exploration Systems Project (BEES, Refs. 2 and 3), and the US Army Precision Autonomous Landing Adaptive Control Experiment (PALACE, Ref. 4). The NASA CICT program was established in 2001 to ensure NASA's continuing leadership in developing and deploying key enabling technologies for a broad range of missioncritical tasks. ARP is primarily motivated by and funded under the Intelligent Systems (IS) portion of CICT, a key objective of which is to develop systems that make decisions with limited intervention. To address this objective, ARP intends to develop, demonstrate, and assess the capabilities of automated reasoning technologies in the context of the complex rotorcraft environment. A rotorcraft serves as an ideal platform for developing and demonstrating automated reasoning software for Mars landers, aircraft or satellite clusters, and other NASA flight applications. The complex high-bandwidth dynamics and cluttered, unpredictable operational environment provide an excellent surrogate for the kinds of challenges likely to be faced in a remote robotic explorer mission. The vision of the BEES program is that small, mechanical platforms, which mimic the mobility of biological systems, can be built at low cost, instrumented and used as platforms for carrying scientific instruments. ARP will support the BEES program by providing a platform on which to flight test surface feature recognition sensor technologies currently under development (Ref. 5). The US Army plans to address a broad range of vertical takeoff and landing (VTOL) UAV topics in the coming years. Under the PALACE Science and Technology Objective (STO) it has identified accurate, reliable autonomous landing at remote un-instrumented sites as a challenging and critical capability. ARP will contribute to meeting the goals of the PALACE STO by providing a platform for the demonstration and integration of the various technologies. This will include developing and flight demonstrating autonomous landing on a slope, in moderate wind, and in the presence of obstacles.

To address the above objectives, ARP has adopted the following project goals: 1) close integration of a reactive planner with navigation, flight control, and mission systems, 2) aggressive maneuvering in a real-world environment including obstacle avoidance and landing at unprepared sites, 3) incorporation of vehicle health into mission planning, and 4) mission planning rapid enough to cope with the highbandwidth dynamic characteristics of small-scale helicopters.

Doron Tal’s task in ARP has been very specific, it included:

• Investigate the ability to use stereo-vision, implement various stereo-vision algorithms and test their usefulness for the goal of obstacle-avoidance by an autonomous helicopter.
• Consult Ann-Patterson Hine’s ISHV/IVHM sub-project, which looks at fault prediction and analysis of a vision-based hardware and software-combined system.
  

Deep space exploration and other future NASA missions require significant advances in artificial intelligence to support the needed capabilities for autonomous systems. RIACS scientists and visitors have been collaborating with NASA researchers in a number of areas as illustrated below.