Henry Kautz

TMLR Journal 2026 Journal Article

The Clever Hans Mirage: A Comprehensive Survey on Spurious Correlations in Machine Learning

• Wenqian Ye
• Luyang Jiang
• Eric Xie
• Guangtao Zheng
• Yunsheng Ma
• Xu Cao
• Dongliang Guo
• Daiqing Qi

Back in the early 20th century, a horse named Hans appeared to perform arithmetic and other intellectual tasks during exhibitions in Germany, while it actually relied solely on involuntary cues in the body language from the human trainer. Modern machine learning models are no different. These models are known to be sensitive to spurious correlations between non-essential features of the inputs (e.g., background, texture, and secondary objects) and the corresponding labels. Such features and their correlations with the labels are known as spurious because they tend to change with shifts in real-world data distributions, which can negatively impact the model's generalization and robustness. In this paper, we provide a comprehensive survey of this emerging issue, along with a fine-grained taxonomy of existing state-of-the-art methods for addressing spurious correlations in machine learning models. Additionally, we summarize existing datasets, benchmarks, and metrics to facilitate future research. The paper concludes with a discussion of the broader impacts, the recent advancements, and future challenges in the era of generative AI, aiming to provide valuable insights for researchers in the related domains of the machine learning community.

AAAI Conference 2020 Conference Paper

Inferring Nighttime Satellite Imagery from Human Mobility

• Brian Dickinson
• Gourab Ghoshal
• Xerxes Dotiwalla
• Adam Sadilek
• Henry Kautz

Nighttime lights satellite imagery has been used for decades as a uniform, global source of data for studying a wide range of socioeconomic factors. Recently, another more terrestrial source is producing data with similarly uniform global coverage: anonymous and aggregated smart phone location. This data, which measures the movement patterns of people and populations rather than the light they produce, could prove just as valuable in decades to come. In fact, since human mobility is far more directly related to the socioeconomic variables being predicted, it has an even greater potential. Additionally, since cell phone locations can be aggregated in real time while preserving individual user privacy, it will be possible to conduct studies that would previously have been impossible because they require data from the present. Of course, it will take quite some time to establish the new techniques necessary to apply human mobility data to problems traditionally studied with satellite imagery and to conceptualize and develop new real time applications. In this study we demonstrate that it is possible to accelerate this process by inferring artificial nighttime satellite imagery from human mobility data, while maintaining a strong differential privacy guarantee. We also show that these artificial maps can be used to infer socioeconomic variables, often with greater accuracy than using actual satellite imagery. Along the way, we find that the relationship between mobility and light emissions is both nonlinear and varies considerably around the globe. Finally, we show that models based on human mobility can significantly improve our understanding of society at a global scale.

IJCAI Conference 2016 Conference Paper

Unsupervised Alignment of Actions in Video with Text Descriptions

• Young Chol Song
• Iftekhar Naim
• Abdullah Al Mamun
• Kaustubh Kulkarni
• Parag Singla
• Jiebo Luo
• Daniel Gildea
• Henry Kautz

Advances in video technology and data storage have made large scale video data collections of complex activities readily accessible. An increasingly popular approach for automatically inferring the details of a video is to associate the spatio-temporal segments in a video with its natural language descriptions. Most algorithms for connecting natural language with video rely on pre-aligned supervised training data. Recently, several models have been shown to be effective for unsupervised alignment of objects in video with language. However, it remains difficult to generate good spatio-temporal video segments for actions that align well with language. This paper presents a framework that extracts higher level representations of low-level action features through hyperfeature coding from video and aligns them with language. We propose a two-step process that creates a high-level action feature codebook with temporally consistent motions, and then applies an unsupervised alignment algorithm over the action codewords and verbs in the language to identify individual activities. We show an improvement over previous alignment models of objects and nouns on videos of biological experiments, and also evaluate our system on a larger scale collection of videos involving kitchen activities.

NeurIPS Conference 2015 Conference Paper

Lifted Symmetry Detection and Breaking for MAP Inference

• Timothy Kopp
• Parag Singla
• Henry Kautz

Symmetry breaking is a technique for speeding up propositional satisfiability testing by adding constraints to the theory that restrict the search space while preserving satisfiability. In this work, we extend symmetry breaking to the problem of model finding in weighted and unweighted relational theories, a class of problems that includes MAP inference in Markov Logic and similar statistical-relational languages. We introduce term symmetries, which are induced by an evidence set and extend to symmetries over a relational theory. We provide the important special case of term equivalent symmetries, showing that such symmetries can be found in low-degree polynomial time. We show how to break an exponential number of these symmetries with added constraints whose number is linear in the size of the domain. We demonstrate the effectiveness of these techniques through experiments in two relational domains. We also discuss the connections between relational symmetry breaking and work on lifted inference in statistical-relational reasoning.

AAAI Conference 2015 Conference Paper

Tackling Mental Health by Integrating Unobtrusive Multimodal Sensing

• Dawei Zhou
• Jiebo Luo
• Vincent Silenzio
• Yun Zhou
• Jile Hu
• Glenn Currier
• Henry Kautz

Mental illness is becoming a major plague in modern societies and poses challenges to the capacity of current public health systems worldwide. With the widespread adoption of social media and mobile devices, and rapid advances in artificial intelligence, a unique opportunity arises for tackling mental health problems. In this study, we investigate how users’ online social activities and physiological signals detected through ubiquitous sensors can be utilized in realistic scenarios for monitoring their mental health states. First, we extract a suite of multimodal time-series signals using modern computer vision and signal processing techniques, from recruited participants while they are immersed in online social media that elicit emotions and emotion transitions. Next, we use machine learning techniques to build a model that establishes the connection between mental states and the extracted multimodal signals. Finally, we validate the effectiveness of our approach using two groups of recruited subjects.

AAAI Conference 2014 Conference Paper

Unsupervised Alignment of Natural Language Instructions with Video Segments

• Iftekhar Naim
• Young Song
• Qiguang Liu
• Henry Kautz
• Jiebo Luo
• Daniel Gildea

We propose an unsupervised learning algorithm for automatically inferring the mappings between English nouns and corresponding video objects. Given a sequence of natural language instructions and an unaligned video recording, we simultaneously align each instruction to its corresponding video segment, and also align nouns in each instruction to their corresponding objects in video. While existing grounded language acquisition algorithms rely on pre-aligned supervised data (each sentence paired with corresponding image frame or video segment), our algorithm aims to automatically infer the alignment from the temporal structure of the video and parallel text instructions. We propose two generative models that are closely related to the HMM and IBM 1 word alignment models used in statistical machine translation. We evaluate our algorithm on videos of biological experiments performed in wetlabs, and demonstrate its capability of aligning video segments to text instructions and matching video objects to nouns in the absence of any direct supervision.

IJCAI Conference 2013 Conference Paper

Modeling the Interplay of People's Location, Interactions, and Social Ties

• Adam Sadilek
• Henry Kautz
• Jeffrey P. Bigham

Location plays an essential role in our lives, bridging our online and offline worlds. This paper explores the interplay of people’s location, interactions, and social ties within a large real-world dataset. We present and evaluate Flap, a system that solves two intimately related tasks: link and location prediction in online social networks. For link prediction, Flap infers social ties by considering patterns in friendship formation, the content of people’s messages, and user location. We show that while each component is a weak predictor of friendship alone, combining them results in a strong model—accurately identifying the majority of friendships. For location prediction, Flap implements a scalable probabilistic model of human mobility, where we treat users with known GPS positions as noisy sensors of the location of their friends. We explore supervised and unsupervised learning scenarios, and focus on the efficiency of both learning and inference. We evaluate Flap on a large sample of highly active users from two distinct geographical areas and show that it (1) reconstructs the entire friendship graph with high accuracy even when no edges are given; and (2) infers people’s fine-grained location, even when they keep their data private and we can only access the location of their friends. Our models significantly outperform current approaches to either task.

IJCAI Conference 2013 Conference Paper

Towards Understanding Global Spread of Disease from Everyday Interpersonal Interactions

• Sean Brennan
• Adam Sadilek
• Henry Kautz

Monitoring and forecast of global spread of infectious diseases is difficult, mainly due to lack of finegrained and timely data. Previous work in computational epidemiology has shown that mining data from the web can improve the predictability of high-level aggregate patterns of epidemics. By contrast, this paper explores how individuals contribute to the global spread of disease. We consider the important task of predicting the prevalence of flulike illness in a given city based on interpersonal interactions of the city’s residents with the outside world. We use the geo-tagged status updates of traveling Twitter users to infer properties of the flow of individuals between cities. While previous research considered only the raw volume of passengers, we estimate a number of latent variables, including the number of sick (symptomatic) travelers and the number of sick individuals to whom each traveler was exposed. We show that AI techniques provide insights into the mechanisms of disease spread and significantly improve predictability of future flu outbreaks. Our experiments involve over 51, 000 individuals traveling between 75 cities prior and during a severe ongoing flu epidemic (October 2012 - January 2013). Our model leverages the text and interpersonal interactions recorded in over 6. 5 million online status updates without any active user participation, enabling scalable public health applications.

IJCAI Conference 2013 Conference Paper

Towards Understanding Global Spread of Disease from Everyday Interpersonal Interactions

• Sean Brennan
• Adam Sadilek
• Henry Kautz

This paper proposes a new algorithm to compute the resilience of a social system or an ecosystem when it is defined in the framework of the mathematical viability theory. It is applied to the problem of language coexistence: Although bilingual societies do exist, many languages have disappeared and some seem endangered presently. Mathematical models of language competition generally conclude that one language will disappear, except when the relative prestige of the languages can be modified. The viability theory provides concepts and tools that are suitable to study the resilience, but with severe computational limits since it uses extensive search on regular grids. The method we propose considers the computation of the viability output sets as an active learning problem with the objective of restraining the number of calls to the model and information storage. We adapt a kd-tree algorithm to approximate the level sets of the resilience value. We prove that this algorithm converges to the output sets defined by the viability theory (viability kernel and capture basin). The resilience value we compute can then be used to propose a policy of action in risky situations such as migration flows.

AAAI Conference 2012 Conference Paper

A Testbed for Learning by Demonstration from Natural Language and RGB-Depth Video

• Young Chol Song
• Henry Kautz

AAAI Conference 2012 Conference Paper

Predicting Disease Transmission from Geo-Tagged Micro-Blog Data

• Adam Sadilek
• Henry Kautz
• Vincent Silenzio

Researchers have begun to mine social network data in order to predict a variety of social, economic, and health related phenomena. While previous work has focused on predicting aggregate properties, such as the prevalence of seasonal influenza in a given country, we consider the task of finegrained prediction of the health of specific people from noisy and incomplete data. We construct a probabilistic model that can predict if and when an individual will fall ill with high precision and good recall on the basis of his social ties and co-locations with other people, as revealed by their Twitter posts. Our model is highly scalable and can be used to predict general dynamic properties of individuals in large realworld social networks. These results provide a foundation for research on fundamental questions of public health, including the identification of non-cooperative disease carriers (“Typhoid Marys”), adaptive vaccination policies, and our understanding of the emergence of global epidemics from day-today interpersonal interactions.

NeurIPS Conference 2012 Conference Paper

Slice Normalized Dynamic Markov Logic Networks

• Tivadar Papai
• Henry Kautz
• Daniel Stefankovic

Markov logic is a widely used tool in statistical relational learning, which uses a weighted first-order logic knowledge base to specify a Markov random field (MRF) or a conditional random field (CRF). In many applications, a Markov logic network (MLN) is trained in one domain, but used in a different one. This paper focuses on dynamic Markov logic networks, where the domain of time points typically varies between training and testing. It has been previously pointed out that the marginal probabilities of truth assignments to ground atoms can change if one extends or reduces the domains of predicates in an MLN. We show that in addition to this problem, the standard way of unrolling a Markov logic theory into a MRF may result in time-inhomogeneity of the underlying Markov chain. Furthermore, even if these representational problems are not significant for a given domain, we show that the more practical problem of generating samples in a sequential conditional random field for the next slice relying on the samples from the previous slice has high computational cost in the general case, due to the need to estimate a normalization factor for each sample. We propose a new discriminative model, slice normalized dynamic Markov logic networks (SN-DMLN), that suffers from none of these issues. It supports efficient online inference, and can directly model influences between variables within a time slice that do not have a causal direction, in contrast with fully directed models (e. g. , DBNs). Experimental results show an improvement in accuracy over previous approaches to online inference in dynamic Markov logic networks.

AAAI Conference 2010 Conference Paper

Recognizing Multi-Agent Activities from GPS Data

• Adam Sadilek
• Henry Kautz

Recent research has shown that surprisingly rich models of human behavior can be learned from GPS (positional) data. However, most research to date has concentrated on modeling single individuals or aggregate statistical properties of groups of people. Given noisy real-world GPS data, we—in contrast—consider the problem of modeling and recognizing activities that involve multiple related individuals playing a variety of roles. Our test domain is the game of capture the flag—an outdoor game that involves many distinct cooperative and competitive joint activities. We model the domain using Markov logic, a statistical relational language, and learn a theory that jointly denoises the data and infers occurrences of high-level activities, such as capturing a player. Our model combines constraints imposed by the geometry of the game area, the motion model of the players, and by the rules and dynamics of the game in a probabilistically and logically sound fashion. We show that while it may be impossible to directly detect a multi-agent activity due to sensor noise or malfunction, the occurrence of the activity can still be inferred by considering both its impact on the future behaviors of the people involved as well as the events that could have preceded it. We compare our unified approach with three alternatives (both probabilistic and nonprobabilistic) where either the denoising of the GPS data and the detection of the high-level activities are strictly separated, or the states of the players are not considered, or both. We show that the unified approach with the time window spanning the entire game, although more computationally costly, is significantly more accurate.

IJCAI Conference 2007 Conference Paper

• Tian Sang
• Paul Beame
• Henry Kautz

The problem of Most Probable Explanation (MPE) arises in the scenario of probabilistic inference: finding an assignment to all variables that has the maximum likelihood given some evidence. We consider the more general CNF-based MPE problem, where each literal in a CNF-formula is associated with a weight. We describe reductions between MPE and weighted MAX-SAT, and show that both can be solved by a variant of weighted model counting. The MPE-SAT algorithm is quite competitive with the state-of-the-art MAX-SAT, WCSP, and MPE solvers on a variety of problems.

IJCAI Conference 2007 Conference Paper

• J
• ouml; rg Hoffmann
• Carla Gomes
• Bart Selman
• Henry Kautz

Translation to Boolean satisfiability is an important approach for solving state-space reachability problems that arise in planning and verification. Many important problems, however, involve numeric variables; for example, C programs or planning with resources. Focussing on planning, we propose a method for translating such problems into propositional SAT, based on an approximation of reachable variable domains. We compare to a more direct translation into "SAT modulo theory" (SMT), that is, SAT extended with numeric variables and arithmetic constraints. Though translation to SAT generates much larger formulas, we show that it typically outperforms translation to SMT almost up to the point where the formulas don't fit into memory any longer. We also show that, even though our planner is optimal, it tends to outperform state-of-the-art sub-optimal heuristic planners in domains with tightly constrained resources. Finally we present encouraging initial results on applying the approach to model checking.

IJCAI Conference 2007 Conference Paper

• Lin Liao
• Tanzeem Choudhury
• Dieter Fox
• Henry Kautz

While conditional random fields (CRFs) have been applied successfully in a variety of domains, their training remains a challenging task. In this paper, we introduce a novel training method for CRFs, called virtual evidence boosting, which simultaneously performs feature selection and parameter estimation. To achieve this, we extend standard boosting to handle virtual evidence, where an observation can be specified as a distribution rather than a single number. This extension allows us to develop a unified framework for learning both local and compatibility features in CRFs. In experiments on synthetic data as well as real activity classification problems, our new training algorithm outperforms other training approaches including maximum likelihood, maximum pseudo-likelihood, and the most recent boosted random fields.

IJCAI Conference 2007 Conference Paper

• Danny Wyatt
• Tanzeem Choudhury
• Jeff Bilmes
• Henry Kautz

In this paper we introduce a new dynamic Bayesian network that separates the speakers and their speaking turns in a multi-person conversation. We protect the speakers' privacy by using only features from which intelligible speech cannot be reconstructed. The model we present combines data from multiple audio streams, segments the streams into speech and silence, separates the different speakers, and detects when other nearby individuals who are not wearing microphones are speaking. No pre-trained speaker specific models are used, so the system can be easily applied in new and different environments. We show promising results in two very different datasets that vary in background noise, microphone placement and quality, and conversational dynamics.

AIJ Journal 2007 Journal Article

Learning and inferring transportation routines

• Lin Liao
• Donald J. Patterson
• Dieter Fox
• Henry Kautz

This paper introduces a hierarchical Markov model that can learn and infer a user's daily movements through an urban community. The model uses multiple levels of abstraction in order to bridge the gap between raw GPS sensor measurements and high level information such as a user's destination and mode of transportation. To achieve efficient inference, we apply Rao–Blackwellized particle filters at multiple levels of the model hierarchy. Locations such as bus stops and parking lots, where the user frequently changes mode of transportation, are learned from GPS data logs without manual labeling of training data. We experimentally demonstrate how to accurately detect novel behavior or user errors (e. g. taking a wrong bus) by explicitly modeling activities in the context of the user's historical data. Finally, we discuss an application called “Opportunity Knocks” that employs our techniques to help cognitively-impaired people use public transportation safely.

NeurIPS Conference 2005 Conference Paper

Location-based activity recognition

• Lin Liao
• Dieter Fox
• Henry Kautz

Learning patterns of human behavior from sensor data is extremely important for high-level activity inference. We show how to extract and label a person's activities and significant places from traces of GPS data. In contrast to existing techniques, our approach simultaneously detects and classifies the significant locations of a person and takes the highlevel context into account. Our system uses relational Markov networks to represent the hierarchical activity model that encodes the complex relations among GPS readings, activities and significant places. We apply FFT-based message passing to perform efficient summation over large numbers of nodes in the networks. We present experiments that show significant improvements over existing techniques.

IJCAI Conference 2003 Conference Paper

Understanding the Power of Clause Learning

• Paul Beame
• Henry Kautz
• Ashish Sabharwal

Efficient implementations of DPLL with the addition of clause learning are the fastest complete satisfiability solvers and can handle many significant real-world problems, such as verification, planning, and design. Despite its importance, little is known of the ultimate strengths and limitations of the technique. This paper presents the first precise characterization of clause learning as a proof system, and begins the task of understanding its power. In particular, we show that clause learning using any nonredundant scheme and unlimited restarts is equivalent to general resolution. We also show that without restarts but with a new learning scheme, clause learning can provide exponentially smaller proofs than regular resolution, which itself is known to be much stronger than ordinary DPLL.

AAAI Conference 2002 Conference Paper

Dynamic Restart Policies

• Henry Kautz
• Microsoft Research; Yongshao Ruan

We describe theoretical results and empirical study of context-sensitive restart policies for randomized search procedures. The methods generalize previous results on optimal restart policies by exploiting dynamically updated beliefs about the probability distribution for run time. Rather than assuming complete knowledge or zero knowledge about the run-time distribution, we formulate restart policies that consider real-time observations about properties of instances and the solver’s activity. We describe background work on the application of Bayesian methods to build predictive models for run time, introduce an optimal policy for dynamic restarts that considers predictions about run time, and perform a comparative study of traditional fixed versus dynamic restart policies.

KER Journal 2000 Journal Article

Integer optimization models of AI planning problems

• Henry Kautz
• Joachim P. Walser

This paper describes ILP-PLAN, a framework for solving AI planning problems represented as integer linear programs. ILP-PLAN extends the planning as satisfiability framework to handle plans with resources, action costs, and complex objective functions. We show that challenging planning problems can be effectively solved using both traditional branch-and-bound integer programming solvers and efficient new integer local search algorithms. ILP-PLAN can find better quality solutions for a set of hard benchmark logistics planning problems than had been found by any earlier system.

AAAI Conference 1999 Conference Paper

State-Space Planning by Integer Optimization

• Henry Kautz
• T Shannon Labs; Joachim P. Walser
• AT
• T Shannon Labs
• i2 Technologies

This paper describes ILP-PLAN, a framework for solving AI planning problems represented as integer linear programs. ILP-PLAN extends the planning as satisfiability framework to handle plans with resources, action costs, and complex objective functions. We show that challenging planning problems can be effectively solved using both traditional branchand-bound IP solvers and efficient new integer local search algorithms. ILP-PLAN can find better quality solutions for a set of hard benchmark logistics planning problems than had been found by any earlier system.

IJCAI Conference 1999 Conference Paper

Unifying SAT-based and Graph-based Planning

• Henry Kautz
• Bart Selman

The B l a c k b o x planning system unifies the planning as satisfiability framework (Kautz and Selman 1992, 1996) with the plan graph approach to STRIPS planning (Blum and Furst 1995). We show that STRIPS problems can be directly translated into SAT and efficiently solved using new randomized systematic solvers. For certain computationally challenging benchmark problems this unified approach outperforms both SATPLAN and Graphplan alone. We also demonstrate that polynomialtime SAT simplification algorithms applied to the encoded problem instances are a powerful complement to the "mutex" propagation algorithm that works directly on the plan graph.

IJCAI Conference 1997 Conference Paper

Ten Challenges in Propositional Reasoning and Search

• Bart Selman
• Henry Kautz
• David McAllester

AAAI Conference 1996 Conference Paper

Agent Amplified Communication

• Henry Kautz

We propose an agent-based framework for assisting and simplifying person-to-person communication for information gathering tasks. As an example, we focus on locating experts for any specified topic. In our approach, the informal person-to-person networks that exist within an organization are used to “referral chain” requests for expertise. User-agents help automate this process. The agents generate referrals by analyzing records of email communication patterns. Simulation results show that the higher responsiveness of an agent-based system can be effectively traded for the higher accuracy of a completely manual approach. E’ urthermore, preliminary experience with a group of users on a prototype system has shown that useful automatic referrals can be found in practice. Our experience with actual users has also shown that privacy concerns are central to the successful deployment of personal agents: an advanced agent-based system will therefore need to reason about issues involving trust and authority.

AAAI Conference 1996 Conference Paper

Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search

• Henry Kautz

Planning is a notoriously hard combinatorial search problem. In many interesting domains, current planning algorithms fail to scale up gracefully. By combining a general, stochastic search algorithm and appropriate problem encodings based on propositional logic, we are able to solve hard planning problems many times faster than the best current planning systems. Although stochastic methods have been shown to be very effective on a wide range of scheduling problems, this is the first demonstration of its power on truly challenging classical planning instances. This work also provides a new perspective on representational issues in planning.

AIJ Journal 1995 Journal Article

Horn approximations of empirical data

• Henry Kautz
• Michael Kearns
• Bart Selman

Formal AI systems traditionally represent knowledge using logical formulas. Sometimes, however, a model-based representation is more compact and enables faster reasoning than the corresponding formula-based representation. The central idea behind our work is to represent a large set of models by a subset of characteristic models. More specifically, we examine model-based representations of Horn theories, and show that there are large Horn theories that can be exactly represented by an exponentially smaller set of characteristic models. We show that deduction based on a set of characteristic models requires only polynomial time, as it does using Horn theories. More surprisingly, abduction can be performed in polynomial time using a set of characteristic models, whereas abduction using Horn theories is NP-complete. Finally, we discuss algorithms for generating efficient representations of the Horn theory that best approximates a general set of models.

IJCAI Conference 1995 Conference Paper

The Comparative Linguistics of Knowledge Representation

• Goran Gogic
• Henry Kautz
• Christos Papadimitriou
• Bart Selrnan

We develop a methodology for comparing knowledge representation formalisms in terms of their "representational succinctness, " that is, their ability to express knowledge situations relatively efficiently. We use this framework for comparing many important formalisms for knowledge base representation: propositional logic, default logic, circumscription, and model preference defaults; and, at a lower level, Horn formulas, characteristic models, decision trees, disjunctive normal form, and conjunctive nor­ mal form. We also show that adding new vari­ ables improves the effective expressibility of certain knowledge representation formalisms.

AAAI Conference 1994 Conference Paper

An Empirical Evaluation of Knowledge Compilation by Theory Approximation

• Henry Kautz

Computational efficiency is a central concern in the design of knowledge representation systems. Compiling a knowledgebase into a more tractable form has been suggested as a way around the inherent intractability of many representation formalisms. Because not all theories can be put into an equivalent tractable form, Selrnan and Kautz (199 1)have suggested compiling a theory into upper and lower bounds (one logically weaker, the other logical stronger) that approximate the original information. A central question in this approach is how well the bounds capture the original knowledge. This question is inherently empirical. We present a detailed empirical evaluation of the compilation of two kinds of theories: computationally challenging randomly generated theories, and propositional encodings of planning problems. Our results show that one can answer a very high percentage of queries even using unit clause bounds, which are much easier to compute than more general tractable approximations. Furthermore, we demonstrate that many of the queries that can be answered by the bounds are expensive to answer using only the original theory: in other words, knowledge compilation does not just “skim off” easy queries. In fact, we show substantial total computational savings in using the bounds together with the original theory to answer all queries (with no errors) from a large benchmark set, over using the original theory alone. This study suggests that knowledge compilation may indeed be a practical approach for dealing with intractability in knowledge representation systems.

AAAI Conference 1994 Conference Paper

An Experiment in the Design of Software Agents

• Henry Kautz
• Michael Coen

We describe a bottom-up approach to the design of software agents. We built and tested an agent system that addresses the real-world problem of handling the activities involved in scheduling a visitor to our laboratory. The system employs both task-specific and user-centered agents, and communicates with users using both email and a graphical interface. This experiment has helped us to identify crucial requirements in the successful deployment of software agents, including issues of reliability, security, and ease of use. The architecture we developed to meet these requirements is flexible and extensible, and is guiding our current research on principles of agent design.

IJCAI Conference 1993 Conference Paper

Domain-Independent Extensions to GSAT: Solving Large Structured Satisfiability Problems

• Bart Selman
• Henry Kautz

GSAT is a randomized local search procedure for solving propositional satisfiability problems (Selman et al. 1992). GSAT can solve hard, randomly generated problems that are an order of magnitude larger than those that can be handled by more traditional approaches such as the Davis-Putnam procedure. GSAT also efficiently solves encodings of graph coloring problems, N-queens, and Boolean induction. However, GSAT does not perform as well on handcrafted encodings of blocks-world planning problems and formulas with a high degree of asymmetry. We present three strategies that dramatically improve GSAT's performance on such formulas. These strategies, in effect, manage to uncover hidden structure in the formula under considerations, thereby significantly extending the applicability of the GSAT algorithm.

AAAI Conference 1992 Conference Paper

Forming Concepts for Fast Inference

• Henry Kautz

Knowledge compilation speeds inference by creating tractable approximations of a knowledge base, but this advantage is lost if the approximations are too large. We show how learning concept generalizations can allow for a more compact representation of the tractable theory. We also give a general induction rule for generating such concept generalizations. Finally, we prove that unless NP E non-uniform P, not all theories have small Horn least upper-bound approximations.

IJCAI Conference 1989 Conference Paper

Vivid Knowledge and Tractable Reasoning:

• David W. Etherington
• Alex Borgida
• Ronald). Brachman
• Henry Kautz