Brian C. Williams

JAAMAS Journal 2026 Journal Article

A Hybrid Procedural/Deductive Executive for Autonomous Spacecraft

• Barney Pell
• Edward B. Gamble
• Brian C. Williams

Abstract The New Millennium Remote Agent (NMRA) will be the first AI system to control an actual spacecraft. The spacecraft domain places a strong premium on autonomy and requires dynamic recoveries and robust concurrent execution, all in the presence of tight real-time deadlines, changing goals, scarce resource constraints, and a wide variety of possible failures. To achieve this level of execution robustness, we have integrated a procedural executive based on generic procedures with a deductive model-based executive. A procedural executive provides sophisticated control constructs such as loops, parallel activity, locks, and synchronization which are used for robust schedule execution, hierarchical task decomposition, and routine configuration management. A deductive executive provides algorithms for sophisticated state inference and optimal failure recovery planning. The integrated executive enables designers to code knowledge via a combination of procedures and declarative models, yielding a rich modeling capability suitable to the challenges of real spacecraft control. The interface between the two executives ensures both that recovery sequences are smoothly merged into high-level schedule execution and that a high degree of reactivity is retained to effectively handle additional failures during recovery.

PRL Workshop 2025 Workshop Paper

Risk-Bounded Multi-Agent Visual Navigation via Dynamic Budget Allocation

• Viraj Parimi
• Brian C. Williams

Safe navigation is essential for autonomous systems operating in hazardous environments, especially when multiple agents must coordinate using just visual inputs over extended time horizons. Traditional planning methods excel at solving long-horizon tasks but rely on predefined distance metrics, while safe Reinforcement Learning (RL) can learn complex behaviors using high-dimensional inputs yet struggles with multi-agent, goal-conditioned scenarios. Recent work combined these paradigms by leveraging goal-conditioned RL (GCRL) to build an intermediate graph from replay buffer states, pruning unsafe edges, and using Conflict-Based Search (CBS) for multi-agent path planning. Although effective, this graph-pruning approach can be overly conservative, limiting mission efficiency by precluding missions that must traverse high-risk regions. To address this limitation, we propose RB-CBS, a novel extension to CBS that dynamically allocates and adjusts user-specified risk bound (Delta) across agents to flexibly trade off safety and speed. Our improved planner ensures that each agent receives a local risk budget (delta) enabling more efficient navigation while still respecting overall safety constraints. Experimental results demonstrate that this iterative risk-allocation framework yields superior performance in complex environments, allowing multiple agents to find collision-free paths within the user-specified Delta.

AIJ Journal 2023 Journal Article

A conflict-directed approach to chance-constrained mixed logical linear programming

• Cheng Fang
• Brian C. Williams

Resistance to the adoption of autonomous systems comes in part from the perceived unreliability of the systems. The concerns can be addressed by deploying decision making algorithms that defines what it means to fail, and look for plans with the highest reward while limiting the probability of failure. This chance-constrained approach thus explicitly imposes a set of constraints that must be satisfied for success, and provides upper-bounds on the probability of violating such constraints. A chance-constrained mixed logical-linear program (CC-MLLP) is a natural formulation, allowing for the specification of linear and logical constraints, with probabilistic continuous variables. The formalism can be used to describe problems ranging from autonomous underwater vehicle path planning, to network routing under uncertainty. While naive encodings of CC-MLLPs can be solved with generalised solvers, the solution time may be unreasonable. In this work, we study architectures to speed up solutions by partitioning CC-MLLPs into the discrete and continuous portions. In order to provide faster solutions, we investigate methods for speeding up the solutions to the continuous chance-constrained linear programs. Further, by exploiting the new solution methods, we develop techniques for guiding the discrete decision making portion of the problem. The resulting algorithm achieves 10 times speed up over prior approaches on autonomous path planning benchmarks.

AIJ Journal 2023 Journal Article

An anytime algorithm for constrained stochastic shortest path problems with deterministic policies

• Sungkweon Hong
• Brian C. Williams

Sequential decision-making problems arise in every arena of daily life and pose unique challenges for research in decision-theoretic planning. Although there has been a wide variety of research in this field, most of the studies have largely focused on single objective problem without constraints. In many real-world applications, however, it is often desirable to bound certain costs or resources under some predefined level. Constrained stochastic shortest path problem (C-SSP), one of the most well-known mathematical frameworks for stochastic decision-making problems with constraints, can formally model such problems, by incorporating constraints in the model formulation. However, it remains an open challenge to produce a deterministic optimal policy with desirable computation time due to its intrinsic complexity. In this paper, we propose a method that produces an optimal and deterministic policy for a C-SSP based on the Lagrangian duality theory and the heuristic forward search method. To address the intrinsic complexity of C-SSP, the proposed method is designed to have an anytime property. In other words, the proposed algorithm tries to find a feasible but decent solution quickly, then improves the solution incrementally until it converges to a true optimal solution. An extensive experimental evaluation on three problem domains shows that the proposed method outperforms the state-of-the-art methods in terms of the near-optimal solution with an optimality gap of less than 0. 1%.

JAIR Journal 2022 Journal Article

Chance-constrained Static Schedules for Temporally Probabilistic Plans

• Cheng Fang
• Andrew J. Wang
• Brian C. Williams

Time management under uncertainty is essential to large scale projects. From space exploration to industrial production, there is a need to schedule and perform activities. given complex specifications on timing. In order to generate schedules that are robust to uncertainty in the duration of activities, prior work has focused on a problem framing that uses an interval-bounded uncertainty representation. However, such approaches are unable to take advantage of known probability distributions over duration. In this paper we concentrate on a probabilistic formulation of temporal problems with uncertain duration, called the probabilistic simple temporal problem. As distributions often have an unbounded range of outcomes, we consider chance-constrained solutions, with guarantees on the probability of meeting temporal constraints. By considering distributions over uncertain duration, we are able to use risk as a resource, reason over the relative likelihood of outcomes, and derive higher utility solutions. We first demonstrate our approach by encoding the problem as a convex program. We then develop a more efficient hybrid algorithm whose parent solver generates risk allocations and whose child solver generates schedules for a particular risk allocation. The child is made efficient by leveraging existing interval-bounded scheduling algorithms, while the parent is made efficient by extracting conflicts over risk allocations. We perform numerical experiments to show the advantages of reasoning over probabilistic uncertainty, by comparing the utility of schedules generated with risk allocation against those generated from reasoning over bounded uncertainty. We also empirically show that solution time is greatly reduced by incorporating conflict-directed risk allocation.

AAMAS Conference 2022 Conference Paper

Multi-Agent Path Finding for Precedence-Constrained Goal Sequences

• Han Zhang
• Jingkai Chen
• Jiaoyang Li
• Brian C. Williams
• Sven Koenig

With the rising demand for deploying robot teams in autonomous warehouses and factories, the Multi-Agent Path Finding (MAPF) problem has drawn more and more attention. The classical MAPF problem and most of its variants focus on navigating agent teams to goal locations while avoiding collisions. However, they do not take into account any precedence constraints that agents should respect when reaching their goal locations. Planning with precedence constraints is important for real-world multi-agent systems. For example, a mobile robot can only pick up a package at a station after it has been delivered by another robot. In this paper, we study the Multi-Agent Path Finding with Precedence Constraints (MAPF-PC) problem, in which agents need to visit sequences of goal locations while satisfying precedence constraints between the goal locations. We propose two algorithms for solving this problem systematically: Conflict-Based Search with Precedence Constraints (CBS-PC) is complete and optimal, and Priority-Based Search with Precedence Constraints (PBS-PC) is incomplete but more efficient in finding near-optimal solutions in practice. Our experimental results show that CBS-PC scales to dozens of agents and hundreds of goal locations and precedence constraints, and PBS-PC scales to hundreds of agents, around one thousand goal locations, and hundreds of precedence constraints.

AAAI Conference 2021 Conference Paper

Scalable and Safe Multi-Agent Motion Planning with Nonlinear Dynamics and Bounded Disturbances

• Jingkai Chen
• Jiaoyang Li
• Chuchu Fan
• Brian C. Williams

We present a scalable and effective multi-agent safe motion planner that enables a group of agents to move to their desired locations while avoiding collisions with obstacles and other agents, with the presence of rich obstacles, high-dimensional, nonlinear, nonholonomic dynamics, actuation limits, and disturbances. We address this problem by finding a piecewise linear path for each agent such that the actual trajectories following these paths are guaranteed to satisfy the reach-andavoid requirement. We show that the spatial tracking error of the actual trajectories of the controlled agents can be precomputed for any qualified path that considers the minimum duration of each path segment due to actuation limits. Using these bounds, we find a collision-free path for each agent by solving Mixed Integer-Linear Programs and coordinate agents by using the priority-based search. We demonstrate our method by benchmarking in 2D and 3D scenarios with ground vehicles and quadrotors, respectively, and show improvements over the solving time and the solution quality compared to two state-of-the-art multi-agent motion planners.

IJCAI Conference 2020 Conference Paper

Best-first Enumeration Based on Bounding Conflicts, and its Application to Large-scale Hybrid Estimation (Extended Abstract)

• Eric Timmons
• Brian C. Williams

State estimation methods based on hybrid discrete and continuous state models have emerged as a method of precisely computing belief states for real world systems, however they have difficulty scaling to systems with more than a handful of components. Classical, consistency based diagnosis methods scale to this level by combining best-first enumeration and conflict-directed search. While best-first methods have been developed for hybrid estimation, conflict-directed methods have thus far been elusive as conflicts summarize constraint violations, but probabilistic hybrid estimation is relatively unconstrained. In this paper we present an approach (A*BC) that unifies best-first enumeration and conflict-directed search in relatively unconstrained problems through the concept of "bounding" conflicts, an extension of conflicts that represent tighter bounds on the cost of regions of the search space. Experiments show that an A*BC powered state estimator produces estimates up to an order of magnitude faster than the current state of the art, particularly on large systems.

AIJ Journal 2019 Journal Article

Complexity bounds for the controllability of temporal networks with conditions, disjunctions, and uncertainty

• Nikhil Bhargava
• Brian C. Williams

In temporal planning, many different temporal network formalisms are used to model real world situations. Each of these formalisms has different features which affect how easy it is to determine whether the underlying network of temporal constraints is consistent. While many of the simpler models have been well-studied from a computational complexity perspective, the algorithms developed for advanced models which combine features have very loose complexity bounds. In this paper, we provide tight completeness bounds for strong, weak, and dynamic controllability checking of temporal networks that have conditions, disjunctions, and temporal uncertainty. Our work exposes some of the subtle differences between these different structures and, remarkably, establishes a guarantee that all of these problems are computable in PSPACE.

IJCAI Conference 2019 Conference Paper

Complexity Bounds for the Controllability of Temporal Networks with Conditions, Disjunctions, and Uncertainty (Extended Abstract)

• Nikhil Bhargava
• Brian C. Williams

In temporal planning, many different temporal network formalisms are used to model real world situations. Each of these formalisms has different features which affect how easy it is to determine whether the underlying network of temporal constraints is consistent. While many of the simpler models have been well-studied from a computational complexity perspective, the algorithms developed for advanced models which combine features have very loose complexity bounds. In this work, we provide tight completeness bounds for strong, weak, and dynamic controllability checking of temporal networks that have conditions, disjunctions, and temporal uncertainty. Our work exposes some of the subtle differences between these different structures and, remarkably, establishes a guarantee that all of these problems are computable in PSPACE.

IJCAI Conference 2019 Conference Paper

Faster Dynamic Controllability Checking in Temporal Networks with Integer Bounds

• Nikhil Bhargava
• Brian C. Williams

Simple Temporal Networks with Uncertainty (STNUs) provide a useful formalism with which to reason about events and the temporal constraints that apply to them. STNUs are in particular notable because they facilitate reasoning over stochastic, or uncontrollable, actions and their corresponding durations. To evaluate the feasibility of a set of constraints associated with an STNU, one checks the network's \textit{dynamic controllability}, which determines whether an adaptive schedule can be constructed on-the-fly. Our work improves the runtime of checking the dynamic controllability of STNUs with integer bounds to O(min(mn, m sqrt(n) log N) + km + k^2n + kn log n). Our approach pre-processes the STNU using an existing O(n^3) dynamic controllability checking algorithm and provides tighter bounds on its runtime. This makes our work easily adaptable to other algorithms that rely on checking variants of dynamic controllability.

AIJ Journal 2017 Journal Article

Temporally and spatially flexible plan execution for dynamic hybrid systems

• Andreas G. Hofmann
• Brian C. Williams

Planners developed in the Artificial Intelligence community assume that tasks in the task plans they generate will be executed predictably and reliably. This assumption provides a useful abstraction in that it lets the task planners focus on what tasks should be done, while lower-level motion planners and controllers take care of the details of how the task should be performed. While this assumption is useful in many domains, it becomes problematic when controlling physically embedded systems, where there are often delays, disturbances, and failures. The task plans do not provide enough information about allowed flexibility in task duration and hybrid state evolution. Such flexibility could be useful when deciding how to react to disturbances. An important domain where this gap has caused problems is robotics, particularly, the operation of robots in unstructured, uncertain environments. Due to the complexity of this domain, the demands of tasks to be performed, and the actuation limits of robots, knowledge about permitted flexibility in execution of a task is crucial. We address this gap through two key innovations. First, we specify a Qualitative State Plan (QSP), which supports representation of spatial and temporal flexibility with respect to tasks. Second, we extend compilation approaches developed for temporally flexible execution of discrete activity plans to work with hybrid discrete/continuous systems using a recently developed Linear Quadratic Regulator synthesis algorithm, which performs a state reachability analysis to prune infeasible trajectories, and which determines optimal control policies for feasible state regions. The resulting Model-based Executive is able to take advantage of spatial and temporal flexibility in a QSP to improve handling of disturbances. Note that in this work, we focus on execution of QSPs, and defer the problem of how they are generated. We believe the latter could be accomplished through extensions to existing task planners.

IJCAI Conference 2015 Conference Paper

Dynamic Execution of Temporal Plans with Sensing Actions and Bounded Risk

• Pedro Henrique Santana
• Brian C. Williams

This thesis focuses on the problem of temporal planning under uncertainty with explicit safety guarantees, which are enforced by means of chance constraints. We aim at elevating the level in which operators interact with autonomous agents and specify their desired behavior, while retaining a keen sensitivity to risk. Instead of relying on unconditional sequences, our goal is to allow contingent plans to be dynamically scheduled and conditioned on observations of the world while remaining safe. Contingencies add flexibility by allowing goals to be achieved through different methods, while observations allow the agent to adapt to the environment. We demonstrate the usefulness of our chance-constrained temporal planning approaches in real-world applications, such as partially observable power supply restoration and collaborative human-robot manufacturing.

IJCAI Conference 2015 Conference Paper

Mixed Discrete-Continuous Heuristic Generative Planning Based on Flow Tubes

• Enrique Fernandez-Gonzalez
• Erez Karpas
• Brian C. Williams

Nowadays, robots are programmed with a mix of discrete and continuous low level behaviors by experts in a very time consuming and expensive process. Existing automated planning approaches are either based on hybrid model predictive control techniques, which do not scale well due to time discretization, or temporal planners, which sacrifice plan expressivity by only supporting discretized fixed rates of change in continuous effects. We introduce Scotty, a mixed discrete-continuous generative planner that finds the middle ground between these two. Scotty can reason with linear time evolving effects whose behaviors can be modified by bounded control variables, with no discretization involved. Our planner exploits the expressivity of flow tubes, which compactly encapsulate continuous effects, and the performance of heuristic forward search. The generated solution plans are better suited for robust execution, as executives can use the flexibility in both time and continuous control variables to react to disturbances.

IJCAI Conference 2015 Conference Paper

Reactive Integrated Motion Planning and Execution

• Andreas G. Hofmann
• Enrique Fernandez
• Justin Helbert
• Scott D. Smith
• Brian C. Williams

Current motion planners, such as the ones available in ROS MoveIt, can solve difficult motion planning problems. However, these planners are not practical in unstructured, rapidly-changing environments. First, they assume that the environment is well-known, and static during planning and execution. Second, they do not support temporal constraints, which are often important for synchronization between a robot and other actors. Third, because many popular planners generate completely new trajectories for each planning problem, they do not allow for representing persistent control policy information associated with a trajectory across planning problems. We present Chekhov, a reactive, integrated motion planning and execution system that addresses these problems. Chekhov uses a Tube-based Roadmap in which the edges of the roadmap graph are families of trajectories called flow tubes, rather than the single trajectories commonly used in roadmap systems. Flow tubes contain control policy information about how to move through the tube, and also represent the dynamic limits of the system, which imply temporal constraints. This, combined with an incremental APSP algorithm for quickly finding paths in the roadmap graph, allows Chekhov to operate in rapidly changing environments. Testing in simulation, and with a robot testbed has shown improvement in planning speed and motion predictability over current motion planners.

AAAI Conference 1998 Conference Paper

Decompositional, Model-Based Learning and its Analogy to Diagnosis

• Brian C. Williams

AIJ Journal 1998 Journal Article

Remote Agent: to boldly go where no AI system has gone before

• Nicola Muscettola
• P.Pandurang Nayak
• Barney Pell
• Brian C. Williams

Renewed motives for space exploration have inspired NASA to work toward the goal of establishing a virtual presence in space, through heterogeneous fleets of robotic explorers. Information technology, and Artificial Intelligence in particular, will play a central role in this endeavor by endowing these explorers with a form of computational intelligence that we call remote agents. In this paper we describe the Remote Agent, a specific autonomous agent architecture based on the principles of model-based programming, on-board deduction and search, and goal-directed closed-loop commanding, that takes a significant step toward enabling this future. This architecture addresses the unique characteristics of the spacecraft domain that require highly reliable autonomous operations over long periods of time with tight deadlines, resource constraints, and concurrent activity among tightly coupled subsystems. The Remote Agent integrates constraintbased temporal planning and scheduling, robust multi-threaded execution, and model-based mode identification and reconfiguration. The demonstration of the integrated system as an on-board controller for Deep Space One, NASA's first New Millennium mission, is scheduled for a period of a week in mid 1999. The development of the Remote Agent also provided the opportunity to reassess some of AI's conventional wisdom about the challenges of implementing embedded systems, tractable reasoning, and knowledge representation. We discuss these issues, and our often contrary experiences, throughout the paper.

IJCAI Conference 1997 Conference Paper

A Reactive Planner for a Model-based Executive

• Brian C. Williams
• P. Pandurang Nayak

AAAI Conference 1996 Conference Paper

A Model-Based Approach to Reactive Self-Configuring Systems

• Brian C. Williams

This paper describes Livingstone, an implemented kernel for a model-based reactive self-configuring autonomous system. It presents a formal characterization of Livingstone’ s representation formalism, and reports on our experience with the implementation in a variety of domains. Livingstone provides a reactive system that performs significant deduction in the sense/response loop by drawing on our past experience at building fast propositional conflict-based algorithms for model-based diagnosis, and by framing a model-based configuration manager as a propositional feedback controller that generates focused, optimal responses. Livingstone’ s representation formalism achieves broad coverage of hybrid hardware/software systems by coupling the transition system models underlying concurrent reactive languages with the qualitative representations developed in model-based reasoning. Livingstone automates a wide variety of tasks using a single model and a single core algorithm, thus making significant progress towards achieving a central goal of model-based reasoning. Livingstone, together with the HSTS planning and scheduling engine and the RAPS executive, has been selected as part of the core autonomy architecture for NASA’ s first New Millennium spacecraft.

AAAI Conference 1994 Conference Paper

Activity Analysis: The Qualitative Analysis of Stationary Points for Optimal Reasoning

• Brian C. Williams

We present a. theory of a modeler’ s problem decomposition skills in the context of opthal Teasowing - the use of qualitative modeling to strategically guide numerical explorations of objective space. Our technique, called activity annlysl: s, applies to the pervasive family of linear and non-linear, constrained optimization problems, and easily integrates with any existing numerical approach. Activity analysis draws from the power of two seemingly divergent perspectives the global conflict-based approaches of combinatorial satisficing search, and the local gradientbased approaches of continuous optimization combined with the underlying insights of engineering monotonicity analysis. The result is an approach that strategically cuts away subspaces that it can quickly rule out as suboptimal, and then guides the numerical methods to the remaining subspaces.

AAAI Conference 1994 Conference Paper

Decompositional Modeling through Caricatural Reasoning

• Brian C. Williams

Many physical phenomena are sufficiently complex that the corresponding equations afford little insight, or no analytical method provides an exact solution. Decompositional modeling (DM) captures a modeler’ s tacit skill at solving nonlinear algebraic systems. DM divides statespace into a patchwork of simpler subregimes, called caricatures, each of which preserves only the dominant characteristics of that regime. It then solves the simpler nonlinear system and identifies its domndn of validity. The varying patchwork reflects how variations in the parameters change the dominant characteristics. The patchwork is built by extracting equational features consisting of the relative strength of terms, and then exagerating and merging these features in different combinations, resulting in the different caricatural regimes. DM operates by providing strategic guidance to a pair of symbolic manipulation systems for qualitative sign and order of magnitude algebra. The approach is sufficient to replicate a broad set of examples from acid-base chemistry.

AIJ Journal 1991 Journal Article

A theory of interactions: unifying qualitative and quantitative algebraic reasoning

• Brian C. Williams

The apparently weak properties of a purely qualitative algebra have led some to conclude that researchers must turn instead to extra-mathematical properties of physical systems. We propose instead that a more powerful qualitative algebra is needed, one that merges the algebras on signs and reals, along with symbolic techniques for manipulating this algebra. We have constructed a hybrid algebra, called SR1 which allows intermediate abstractions to be selected between traditional qualitative and quantitative algebras. SR1 and the symbolic algebra system Minima demonstrate substantial progress towards a theory of continuous interactions between quantities—one that allows just the interesting features of interactions to be represented, and that captures skills for composing and comparing interactions. This theory is sufficiently expressive to determine the behaviors that a variety of fluid regulation devices will achieve—not just what is impossible. It embodies in a simple manner many existing algebraic formalisms for describing and individually manipulating interactions, including confluences, inequalities, and monotonicity operators, as well as many of the individual inferences of qualitative arithmetic, composition of monotonicity, inequality algebra, transition analysis, qualitative resolution and traditional algebra.

AIJ Journal 1991 Journal Article

Qualitative reasoning about physical systems: A return to roots

• Brian C. Williams
• Johan de Kleer

AAAI Conference 1990 Conference Paper

Interaction-Based Invention: Designing Novel Devices from First Principles

• Brian C. Williams

An inventor who is skilled at constructing innovative designs is distinguished, not just by the first principles he knows, but by the way he uses these principles and how he focusses the search for novel devices among an overwhelming space of possibilities. We propose that an appropriate focus for design is the network of qualitative interactions between quantities, (called an interaction topology), used by a device to achieve its desired behavior. We present an approach, called interaction-based invention, which views design as a process of building interaction topologies - in this paper directly from first principles. The program fiis, which embodies this approach, designs simple hydro-mechanical regulators, analogous to devices that were fundamental to the development of feedback control theory.

IJCAI Conference 1989 Conference Paper

Diagnosis with Behavioral Modes

• Johan de Kleer
• Brian C. Williams

Diagnostic tasks involve identifying faulty components from observations of symptomatic device behavior. This paper presents a general diagnostic theory that uses the perspective of diagnosis as identifying consistent modes of behavior, correct or faulty. Our theory draws on the intuitions behind recent diagnostic theories to identify faulty components without necessarily knowing how they fail. To derive additional diagnostic discrimination we use the models for behavioral modes together with probabilistic information about the likelihood of each mode of behavior.

AAAI Conference 1988 Conference Paper

MINIMA: A Symbolic Approach to Qualitative Algebraic Reasoning

• Brian C. Williams

The apparently weak properties of a qualitative algebra have lead some to conclude that we must turn instead to extra-mathematical properties of physical systems. We propose instead that a more powerful qualitative algebra is needed, one that merges the algebras on signs and reals. We have invented a hybrid algebra, called Ql, allows us to select abstractions intermediate between traditional qualitative and quantitative algebras. The power of our algebra is demonstrated in three ways: First, analysis of Ql shows that the algebra is robust, sharing many properties of reals, but including several that are unique. Second, these properties enable symbolic manipulation techniques for canonicalization and factorization distinct from those applied to the reals. Finally, these manipulation techniques hold much promise for tasks like design and verification, as suggested by a simple design example.

AIJ Journal 1987 Journal Article

Diagnosing multiple faults

• Johan de Kleer
• Brian C. Williams

Diagnostic tasks require determining the differences between a model of an artifact and the artifact itself. The differences between the manifested behavior of the artifact and the predicted behavior of the model guide the search for the differences between the artifact and its model. The diagnostic procedure presented in this paper is model-based, inferring the behavior of the composite device from knowledge of the structure and function of the individual components comprising the device. The system (GDE—general diagnostic engine) has been implemented and tested on many examples in the domain of troubleshooting digital circuits. This research makes several novel contributions: First, the system diagnoses failures due to multiple faults. Second, failure candidates are represented and manipulated in terms of minimal sets of violated assumptions, resulting in an efficient diagnostic procedure. Third, the diagnostic procedure is incremental, exploiting the iterative nature of diagnosis. Fourth, a clear separation is drawn between diagnosis and behavior prediction, resulting in a domain (and inference procedure) independent diagnostic procedure. Fifth, GDE combines model-based prediction with sequential diagnosis to propose measurements to localize the faults. The normally required conditional probabilities are computed from the structure of the device and models of its components. This capability results from a novel way of incorporating probabilities and information theory into the context mechanism provided by assumption-based truth maintenance.

AAAI Conference 1986 Conference Paper

Doing Time: Putting Qualitative Reasoning on Firmer Ground

• Brian C. Williams

Recent work in qualitative reasoning has focused on predicting the dynamic behavior of continuous physical systems. Significant headway has been made in identifying the principles necessary to predict this class of behavior. However, the predictive inference engines based on these principles are limited in their ability to reason about time. This paper presents a general approach to behavioral prediction which overcomes many of these limitations. Generality results from a clean separation between principles relating to time, continuity, and qualitative representations. The resulting inference mechanism, based on propagation of constraints, is applicable to a wide class of physical systems exhibiting discrete or continuous behavior, and can be used with a variety of representations (e.g., digital, quantitative, qualitative or symbolic abstractions). In addition, it provides a framework in which to explore a broad range of tasks including prediction, explanation, diagnosis, and design.

AIJ Journal 1984 Journal Article

Qualitative analysis of MOS circuits

• Brian C. Williams

With the push towards submicron technology, transistor models have become increasingly complex. The number of components in integrated circuits has forced designers' efforts and skills towards higher levels of design. This has created a gap between design expertise and the performance demands increasingly imposed by the technology. To alleviate this problem, software tools must be developed that provide the designer with expert advice on circuit performance and design. This requires a theory that links the intuitions of an expert circuit analyst with the corresponding principles of formal theory (i. e. , algebra, calculus, feedback analysis, network theory, and electrodynamics), and that makes each underlying assumption explicit. Temporal qualitative analysis is a technique for analyzing the qualitative large signal behavior of MOS circuits that straddle the line between the digital and analog domains. Temporal qualitative analysis is based on the following four components: First, a qualitative representation is composed of a set of open regions separated by boundaries. These boundaries are chosen at the appropriate level of detail for the analysis. This concept is used in modeling time, space, circuit state variables, and device operating regions. Second, constraints between circuit state variables are established by circuit theory. At a finer time scale, the designer's intuition of electrodynamics is used to impose a causal relationship among these constraints. Third, large signal behavior is modeled by transition analysis, using continuity and theorems of calculus to determine how quantities pass between regions over time. Finally, feedback analysis uses knowledge about the structure of equations and the properties of structure classes to resolve ambiguities.

AAAI Conference 1984 Conference Paper

The Use of Continuity in a Qualitative Physics

• Brian C. Williams

The ability to reason about a series of complex events over time is essential in analyzing physical systems. This paper discusses the role of continuity in qualitative physics and its application in a system for analyzing the behavior of Digital MOS circuits that exhibit analog behavior. The discussion begins with a brief overview of the reasoning steps necessary to perform a qualitative simulation using Temporal Qualitative (TQ) Analysis. The discussion then focuses in on the use of continuity and the relationship between quantities and their higher order derivatives in describing how physical quantities change over time.