UAI 2005

Concomitantly, a wealth of interesting computational problems arise in proposed methods for discovering new pharmaceuticals. In this talk, I'll discuss some recent results from my lab, including new algorithms for interpreting X-ray crystallography and NMR (nuclear magnetic resonance) data, disease classification using mass spectrometry of human serum, and protein redesign. Our algorithms have recently been used, respectively, to reveal the enzymatic architecture of organisms high on the CDC bioterrorism watch-list, for probabilistic cancer classification from human peripheral blood, and to redesign an antibiotic-producing enzyme to bind a novel substrate. I'll overview these projects, highlighting instances of the general problem of recovering structure from uncertain data. For example, in our work on computational methods for NMR structural biology, automated resonance assignment is formulated as an expectation/maximization geometric matching problem under noise, and high-throughput detection of protein structural homology by NMR can be viewed as a combinatorial optimization to minimize KL-distance on a Lie group.

The vision of Mars rovers, pursued for the last two decades, has seemingly become all but routine, through the success of Spirit and Opportunity.  As a new vision, in another two decades we could see Mars airplanes scouting Valle Marineris for sites of ancient water springs, followed by quadruped or biped robots, which deftly traverse this “grand canyon” to the sites of scientific interest.  Yet the loss or close calls experienced by virtually every Mars mission, underscore the daunting challenge of this new, bi-decadal challenge.  Achieving this and similar robotic challenges on Earth, requires a new paradigm for programming robotic systems, one that elevates the programmer above the level of micro-managing responses to uncertain outcomes. 

This talk introduces a new approach, called Model-based Programming, in which a human programs individual or robot teams at a qualitative level, in terms of the robots’ intended state evolutions.  This program is then executed robustly, while adapting to uncertainty and failure, by continuously reasoning from models of the robots and their environment.  The models used by the executive, called probabilistic constraint automata, combine Markov processes, mixed discrete/continuous constraints and hierarchical, timed automata, in order to represent complex, concurrent, stochastic processes, while the reasoning algorithms underlying the executive efficiently solve hybrid logic/optimization problems, through forward, conflict-directed search.  In this talk, we develop the concepts underlying model-based programming, using three examples related to the Mars exploration challenge, a self diagnosing explorer that reasons about its mixed software/hardware subsystems, a team of cooperating airplanes, and a biped robot that is adept at navigating rough terrain.

Brian Williams received his SB, SM and PhD from MIT in Computer Science and Electrical Engineering in 1989.  Starting in the 80’s, he pioneered multiple fault, model-based diagnosis and repair at Xerox PARC and NASA through the GDE, Sherlock, Livingstone and Burton systems.  At the NASA Ames Research Center he formed the Autonomous Systems and Robotics Branch, co-invented the Remote Agent, model-based autonomous system, and was a member of the NASA Deep Space One Probe flight team, which took Remote Agent to flight in 1999.

He has received three best paper and one distinguished paper prize, for research on qualitative algebras, propositional inference, model-based monitoring and soft constraints.  He has served on the editorial boards of JAIR, the journal of field robotics and AAAI Press, in addition to acting as a guest editor of AIJ.  He has received several NASA Space Act Awards; was a member of the Tom Young’s Blue Ribbon Team n 2000, assessing future Mars missions in light of the Mars Climate Orbiter and Polar Lander, and is a Member of the Advisory Council of the NASA Jet Propulsion Laboratory.