Benjamin D. Smith

ICAPS Conference 2000 Conference Paper

Challenges and Methods in Testing the Remote Agent Planner

• Benjamin D. Smith
• Martin S. Feather
• Nicola Muscettola

The Remote Agent Experiment (RAX) on the Deep Space 1 (DS1) mission was the first time that an artificially intelligent agent controlled a NASA spacecraft. One of the key components of the remote agent is an on-board planner. Since there was no opportunity for human intervention between plan generation and execution, extensive testing was required to ensure that the planner would not endanger the spacecraft by producing an incorrect plan, or by not producing a plan at all. The testing process raised many challenging issues, several of which remain open. The planner and domain model are complex, with billions of possible inputs and outputs. How does one obtain adequate coverage with a reasonable number of test cases? How does one even measure coverage for a planner? How does one determine plan correctness? Other issues arise from developing a planner in the context of a larger operationsoriented project, such as limited workforce and changing domain models, interfaces and requirements. As planning systems are fielded in mission-critical applications, it becomes increasingly important to address these issues. This paper describes the major issues that we encountered while testing the Remote Agent planner, how we addressed them, and what issues remain open.

ICAPS Conference 2000 Conference Paper

Planning in Interplanetary Space: Theory and Practice

• Ari K. Jónsson
• Paul H. Morris
• Nicola Muscettola
• Kanna Rajan
• Benjamin D. Smith

On May 17th 1999, NASA activated for the first time an AI-based planner/scheduler running on the flight processor of a spacecraft. This was part of the Remote Agent Experiment (RAX), a demonstration of closedloop planning and execution, and model-based state inference and failure recovery. This paper describes the RAX Planner/Scheduler (RAX-PS), both in terms of the underlying planning framework and in terms of the fielded planner. RAX-PS plans are networks of constraints, built incrementally by consulting a model of the dynamics of the spacecraft. The RAX-PS planning procedure is formally well defined and can be proved to be complete. RAX-PS generates plans that are temporally flexible, allowing the execution system to adjust to actual plan execution conditions without breaking the plan. The practical aspect, developing a mission critical application, required paying attention to important engineering issues such as the design of methods for programmable search control, knowledge acquisition and planner validation. The result was a system capable of building concurrent plans with over a hundred tasks within the performance requirements of operational, mission-critical software.

ECAI Conference 2000 Conference Paper

Remote Agent: An Autonomous Control System for the New Millennium

• Kanna Rajan
• Douglas E. Bernard
• Gregory Dorais
• Edward B. Gamble
• Bob Kanefsky
• James Kurien
• William Millar
• Nicola Muscettola

AAAI Conference 1990 Conference Paper

Incremental Non-Backtracking Focusing: A Polynomially Bounded Generalization Algorithm for Version Spaces

• Benjamin D. Smith

The candidate elimination algorithm for inductive learning with version spaces can require both exponential time and space. This article describes the Incremental Non-Backtracking Focusing (INBF) algorithm which learns strictly tree-structured concepts in polynomial space and time. Specifically, it learns in time O(pnrC) and space 0( nk) where p is the number of positives, n the number of negatives, and k the number of features. INBF is an extension of an existing batch algorithm, Avoidance Focusing (AF). Although AF also learns in polynomial time, it assumes a convergent set of positive examples, and handles additional examples inefficiently; INBF has neither of these restrictions. Both the AF and INBF algorithms assume that the positive examples plus the near misses will be sufficient for convergence if the initial set of examples is convergent. This article formally proves that for treestructured concepts this assumption does in fact hold.