Henry A. Kautz

TARK Conference 2013 Conference Paper

Reasoning Under the Principle of Maximum Entropy for Modal Logics K45, KD45, and S5

• Tivadar Papai
• Henry A. Kautz
• Daniel Stefankovic

We propose modal Markov logic as an extension of propositional Markov logic to reason under the principle of maximum entropy for modal logics K45, KD45, and S5. Analogous to propositional Markov logic, the knowledge base consists of weighted formulas, whose weights are learned from data. However, in contrast to Markov logic, in our framework we use the knowledge base to define a probability distribution over non-equivalent epistemic situations (pointed Kripke structures) rather than over atoms, and use this distribution to assign probabilities to modal formulas. As in all probabilistic representations, the central task in our framework is inference. Although the size of the state space grows doubly exponentially in the number of propositions in the domain, we provide an algorithm that scales only exponentially in the size of the knowledge base. Finally, we briefly discuss the case of languages with an infinite number of propositions. 1.

SAT Conference 2005 Conference Paper

Heuristics for Fast Exact Model Counting

• Tian Sang
• Paul Beame
• Henry A. Kautz

Abstract An important extension of satisfiability testing is model-counting, a task that corresponds to problems such as probabilistic reasoning and computing the permanent of a Boolean matrix. We recently introduced Cachet, an exact model-counting algorithm that combines formula caching, clause learning, and component analysis. This paper reports on experiments with various techniques for improving the performance of Cachet, including component-selection strategies, variable-selection branching heuristics, randomization, backtracking schemes, and cross-component implications. The result of this work is a highly-tuned version of Cachet, the first (and currently, only) system able to exactly determine the marginal probabilities of variables in random 3-SAT formulas with 150+ variables. We use this to discover an interesting property of random formulas that does not seem to have been previously observed.

SAT Conference 2004 Conference Paper

Combining Component Caching and Clause Learning for Effective Model Counting

• Tian Sang
• Fahiem Bacchus
• Paul Beame
• Henry A. Kautz
• Toniann Pitassi

SAT Conference 2003 Conference Paper

Using Problem Structure for Efficient Clause Learning

• Ashish Sabharwal
• Paul Beame
• Henry A. Kautz

Abstract DPLL based clause learning algorithms for satisfiability testing are known to work very well in practice. However, like most branch-and-bound techniques, their performance depends heavily on the variable order used in making branching decisions. We propose a novel way of exploiting the underlying problem structure to guide clause learning algorithms toward faster solutions. The key idea is to use a higher level problem description, such as a graph or a PDDL specification, to generate a good branching sequence as an aid to SAT solvers. The sequence captures hierarchical structure that is lost in the CNF translation. We show that this leads to exponential speedups on grid and randomized pebbling problems. The ideas we use originate from the analysis of problem structure recently used in [1] to study clause learning from a theoretical perspective.

IROS Conference 2003 Conference Paper

Voronoi tracking: location estimation using sparse and noisy sensor data

• Lin Liao
• Dieter Fox
• Jeffrey Hightower
• Henry A. Kautz
• Dirk Schulz 0001

Tracking the activity of people in indoor environments has gained considerable attention in the robotics community over the last years. Most of the existing approaches are based on sensors, which allow to accurately determining the locations of people but do not provide means to distinguish between different persons. In this paper we propose a novel approach to tracking moving objects and their identity using noisy, sparse information collected by id-sensors such as infrared and ultrasound badge systems. The key idea of our approach is to use particle filters to estimate the locations of people on the Voronoi graph of the environment. By restricting particles to a graph, we make use of the inherent structure of indoor environments. The approach has two key advantages. First, it is by far more efficient and robust than unconstrained particle filters. Second, the Voronoi graph provides a natural discretization of human motion, which allows us to apply unsupervised learning techniques to derive typical motion patterns of the people in the environment. Experiments using a robot to collect ground-truth data indicate the superior performance of Voronoi tracking. Furthermore, we demonstrate that EM-based learning of behavior patterns increases the tracking performance and provides valuable information for high-level behavior recognition.

UAI Conference 2001 Conference Paper

A Bayesian Approach to Tackling Hard Computational Problems

• Eric Horvitz
• Yongshao Ruan
• Carla P. Gomes
• Henry A. Kautz
• Bart Selman
• Max Chickering

We are developing a general framework for using learned Bayesian models for decision-theoretic control of search and reasoningalgorithms. We illustrate the approach on the specific task of controlling both general and domain-specific solvers on a hard class of structured constraint satisfaction problems. A successful strategyfor reducing the high (and even infinite) variance in running time typically exhibited by backtracking search algorithms is to cut off and restart the search if a solution is not found within a certainamount of time. Previous work on restart strategies have employed fixed cut off values. We show how to create a dynamic cut off strategy by learning a Bayesian model that predicts the ultimate length of a trial based on observing the early behavior of the search algorithm. Furthermore, we describe the general conditions under which a dynamic restart strategy can outperform the theoretically optimal fixed strategy.

ICML Conference 2000 Conference Paper

Learning Declarative Control Rules for Constraint-BAsed Planning

• Yi-Cheng Huang
• Bart Selman
• Henry A. Kautz

ICAPS Conference 1998 Conference Paper

The Role of Domain-Specific Knowledge in the Planning as Satisfiability Framework

• Henry A. Kautz
• Bart Selman

SATPLAN is currently one of the fastest planning systems for domain-independentplanning. In nearly all practical applications, however, there exists an abundance of domain-specific knowledgethat can be used to improve the performanceof a planning system. This knowledgeis traditionally encoded as procedures or rules that are tied to the details of the planning engine. Wepresent a way to encode domain knowledge in a purely declarative, algorithm independentmanner. Wedemonstrate that the same heuristic knowledgecan be used by completelydifferent search engines, one systematic, the other using greedy local search. This approach greatly enhances the power of SATPLAN: solution times for someproblems are reduced fxomdays to seconds. problem log. a log. b log. c log. d bw. a bw. b bw. c bw. d sob length 11 13 13 14 6 9 14 18 soln size 54 47 63 74 12 18 28 36 as configurations TM 10 sl0 l° 10 1016 110--0-~ 1091 1013[ I019 J Table 1: Planning benchmark testbed. For logistics problems, the solution length is optimal, and the number of actions per solution is the smallest that has been found using any search procedure so far. For the blocks world (one arm), the solution length and sizes are optimal (each time step includes a pickup/putdown pair).

AAAI Conference 1993 Conference Paper

Reasoning with Characteristic Models

• Henry A. Kautz

Formal AI systems traditionally represent knowledge using logical formulas. We will show, however, that for certain kinds of information, 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. In addition, we will show that deduction based on a set of characteristic models takes only linear time, thus matching the performance 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.

ECAI Conference 1992 Conference Paper

Planning as Satisfiability

• Henry A. Kautz
• Bart Selman

AIJ Journal 1991 Journal Article

Hard problems for simple default logics

• Henry A. Kautz
• Bart Selman

AAAI Conference 1991 Conference Paper

Integrating Metric and Qualitative Temporal Reasoning

• Henry A. Kautz

Research in Artificial Intelligence on constraint-based representations for temporal reasoning has largely concentrated on two kinds of formalisms: systems of simple linear inequalities to encode metric relations between time points, and systems of binary constraints in Allen’ s temporal calculus to encode qualitative relations between time intervals. Each formalism has certain advantages. Linear inequalities can represent dates, durations, and other quantitive information; Allen’ s qualitative calculus can express relations between time intervals, such as disjointedness, that are useful for constraint-based approaches to planning. In this paper we demonstrate how metric and Allenstyle constraint networks can be integrated in a constraint-based reasoning system. The highlights of the work include a simple but powerful logical language for expressing both quantitative and qualitative information; translation algorithms between the metric and Allen sublanguages that entail minimal loss of information; and a constraint-propagation procedure for problems expressed in a combination of metric and Allen constraints.

AIJ Journal 1990 Journal Article

Model-preference default theories

• Bart Selman
• Henry A. Kautz

NMR Workshop 1989 Conference Paper

The Complexity of Model-Preference Default Theories

• Bart Selman
• Henry A. Kautz

Abstract Most formal theories of default inference have very poor computational properties, and are easily shown to be intractable, or worse, undecidable. We are therefore investigating limited but efficiently computable theories of default reasoning. This paper defines systems of Propositional Model Preference Defaults, which provide a true model-theoretic account of default inference with exceptions. Some of our results extend to other nonmonotonic formalisms, such as Default Logic. The most general system of Model Preference Defaults is decidable but still intractable. Inspired by the very good (linear) complexity of propositional Horn theories, we consider systems of Horn Defaults. Surprisingly, finding a most-preferred model in even this very limited system is shown to be NP-Hard. Tractability can be achieved in two ways: by eliminating the “specificity ordering” among default rules, thus limiting the system's expressive power; and by restricting our attention to systems of Acyclic Horn Defaults. These acyclic theories can encode inheritance hierarchies of the form examined by Touretzky, but are strictly more general. This analysis suggests several directions for future research: finding other syntactic restrictions which permit efficient computation; or more daringly, investigation of default systems whose implementations do not require checking global consistency — that is, fast “approximate” inference.

AAAI Conference 1986 Conference Paper

Generalized Plan Recognition

• Henry A. Kautz

This paper outlines a new theory of plan recognition that is significantly more powerful than previous approaches. Concurrent actions, shared steps between actions, and disjunctive information are all handled. The theory allows one to draw conclusions based on the class of possible plans being performed, rather than having to prematurely commit to a single interpretation. The theory employs circumscription to transform a first-order theory of action into an action taxonomy, which can be used to logically deduce the complex action(s) an agent is performing.

AAAI Conference 1986 Conference Paper

The Logic of Persistence

• Henry A. Kautz

A recent paper [Hanks1985] examines temporal reasoning as an example of default reasoning. They conclude that all current systems of default reasoning, including non-monotonic logic, default logic, and circumscription, are inadequate for reasoning about persistence. I present a way of representing persistence in a framework based on a generalization of circumscription, which captures Hanks and McDermott’s procedural representation.