Matthew L. Ginsberg

ICAPS Conference 2008 Conference Paper

The Complexity of Optimal Planning and a More Efficient Method for Finding Solutions

• Katrina Ray
• Matthew L. Ginsberg

We present a faster method of solving optimal planning problems and show that our solution performs up to an order of magnitude faster than Satplan on a variety of problems from the IPC-5 benchmarks. Satplan makes several calls to a SAT solver, discarding learned information with each call. Our planner uses a single call to a SAT solver, eliminating this problem.. We explain our technique by describing a new theoretical framework which allows us to prove that a single call to a SAT solver is sufficient to solve every problem in Δ2. (This does not imply that NP is equal to Δ2; only that SAT solvers' capabilities are greater than previously realized.) We also prove that optimal planning is FΘ2 Complete when the plan length is bounded by a polynomial; optimal planning is thus harder than SAT even in the presence of such a bound. Despite the relative complexities, the Δ2 capability of DPLL and the fact that Θ2 ⊆ Δ2 show that a single satisfiability call can solve optimal planning problems in the presence of a polynomial bound on plan length.

KER Journal 2000 Journal Article

Combining satisfiability techniques from AI and OR

• Heidi E. Dixon
• Matthew L. Ginsberg

The recent effort to integrate techniques from the fields of artificial intelligence and operations research has been motivated in part by the fact that scientists in each group are often unacquainted with recent (and not so recent) progress in the other field. Our goal in this paper is to introduce the artificial intelligence community to pseudo-Boolean representation and cutting plane proofs, and to introduce the operations research community to restricted learning methods such as relevance-bounded learning. Complete methods for solving satisfiability problems are necessarily bounded from below by the length of the shortest proof of unsatisfiability; the fact that cutting plane proofs of unsatisfiability can be exponentially shorter than the shortest resolution proof can thus in theory lead to substantial improvements in the performance of complete satisfiability engines. Relevance-bounded learning is a method for bounding the size of a learned constraint set. It is currently the best artificial intelligence strategy for deciding which learned constraints to retain and which to discard. We believe these two elements or some analogous form of them are necessary ingredients to improving the performance of satisfiability algorithms generally. We also present a new cutting plane proof of the pigeonhole principle that is of size n 2, and show how to implement some intelligent backtracking techniques using pseudo-Boolean representation.

AAAI Conference 1998 Conference Paper

Supermodels and Robustness

• Matthew L. Ginsberg

When search techniques are used to solve a practical problem, the solution produced is often brittle in the sense that small execution difficulties can have an arbitrarily large effect on the viability of the solution. The AI community has responded to this difficulty by investigating the development of “robust problem solvers” that are intended to be proof against this difficulty. We argue that robustness is best cast not as a property of the problem solver, but as a property of the solution. We introduce a new class of models for a logical theory, called supermodels, that captures this idea. Supermodels guarantee that the model in question is robust, and allow us to quantify the degree to which it is so. We investigate the theoretical properties of supermodels, showing that finding supermodels is typically of the same theoretical complexity as finding models. We provide a general way to modify a logical theory so that a model of the modified theory is a supermodel of the original. Experimentally, we show that the supermodel problem exhibits phase transition behavior similar to that found in other satisfiability work.

AAAI Conference 1996 Conference Paper

Partition Search

• Matthew L. Ginsberg

We introduce a new form of game search called partition search that incorporates dependency analysis, allowing substantial reductions in the portion of the tree that needs to be expanded. Both theoretical results and experimental data are presented. For the game of bridge, partition search provides approximately as much of an improvement over existing methods as a-0 pruning provides over minimax.

AIJ Journal 1995 Journal Article

Approximate planning

• Matthew L. Ginsberg

This paper makes two linked contributions. First, we argue that planning systems, instead of being correct (every plan returned achieves the goal) and complete (all such plans are returned), should be approximately correct and complete, in that most plans returned achieve the goal and that most such plans are returned. The first contribution we make is to formalize this notion. Our second aim is to demonstrate the practical importance of these ideas. We argue that the cached plans used by case-based planners are best thought of as approximate as opposed to exact, and also show that we can use our approach to plan for subgoals g 1 and g 2 separately and to combine the plans generated to produce a plan for the conjoined goal g 1 Λ g 2. The computational benefits of working with subgoals separately have long been recognized, but attempts to do so using correct and complete planners have failed.

IJCAI Conference 1995 Conference Paper

Limited Discrepancy Search

• William D. Harvey
• Matthew L. Ginsberg

Many problems of practical interest can be solved using tree search methods because carefully tuned successor ordering heuristics guide the search toward regions of the space that are likely to contain solutions. For some problems, the heuristics often lead directly to a solution— but not always. Limited discrepancy search addresses the problem of what to do when the heuristics fail. Our intuition is that a failing heuristic might well have succeeded if it were not for a small number of "wrong turns" along the way. For a binary tree of height d, there are only d ways the heuristic could make a single wrong turn, and only d(d-i)/2 ways it could make two. A small number of wrong turns can be overcome by systematically searching all paths that differ from the heuristic path in at most a small number of decision points, or "discrepancies. " Limited discrepancy search is a backtracking algorithm that searches the nodes of the tree in increasing order of such discrepancies. We show formally and experimentally that limited discrepancy search can be expected to outperform existing approaches.

ICAPS Conference 1994 Conference Paper

Approximate Planning (Extended Abstract)

• Matthew L. Ginsberg

This paper makestwo linked contributions. First, we argue that p]ann; ng systems, instead of being correct (every plan returned achieves the goal) and complete (all such plans are returned), should be app~zimately correct and complete, in that most plans returned achieve the goal and that most such plans are returned. Our first contribution is to formalize this notion. Our second aim is to demonstrate the practical iraportance of these ideas. Weargue that the cached plans used by case-based p]AnneXS are best thought of as approximate as opposed to exact, and also show that we can use our approach to plan for subgoals gl and g~ separately and to combinethe plans generated to produce a plan for the conjoined goal gl A g2. The computational benefits of working with subgoals separately have long been recognized, but attempts to do so using correct and complete planners have failed.

AIJ Journal 1992 Journal Article

Iterative broadening

• Matthew L. Ginsberg
• William D. Harvey

Conventional blind search techniques generally assume that the goal nodes for a given problem are distributed randomly along the fringe of the search tree. We argue that this is often invalid in practice and suggest that a more reasonable assumption is that decisions made at each point in the search carry equal weight. We go on to show that a new search technique called iterative broadening leads to orders-of-magnitude savings in the time needed to search a space satisfying this assumption; the basic idea is to search the space using artificial breadth cutoffs that are gradually increased until a goal is found. Both theoretical and experimental results are presented.

AAAI Conference 1991 Conference Paper

Is There any Need for Domain-Dependent Control Information?

• Matthew L. Ginsberg

TARK Conference 1990 Conference Paper

Bilattices and Modal Operators

• Matthew L. Ginsberg

A bilattice is a set equipped with two partial orders and a negation operation that inverts one of them while leaving the other unchanged; it has been suggested that the truth values used by inference systems should be chosen from such a structure instead of the two-point set {t, f}. Given such a choice, we redefine a modal operator to be a function on the bilattice selected, and show that this definition generalizes both Kripke's possible worlds approach and Moore's autoepistemic logic. Extensions to causal and temporal reasoning are also discussed.

AAAI Conference 1990 Conference Paper

Iterative Broadening

• Matthew L. Ginsberg

Conventional blind search techniques generally assume that the goal nodes for a given problem are distributed randomly along the fringe of the search tree. We argue that this is often invalid in practice, suggest that a more reasonable assumption is that decisions made at each point in the search carry equal weight, and show that a new search technique that we call iterative broadening leads to orders-of-magnitude savings in the time needed to search a space satisfying this assumption. Both theoretical and experimental results are presented.

AAAI Conference 1990 Conference Paper

Search Lessons Learned from Crossword Puzzles

• Matthew L. Ginsberg
• Michael P. Halpin

The construction of a program that generates crossword puzzles is discussed. As in a recent paper by Dechter and Meiri, we make an experimental comparison of various search techniques. The conclusions to which we come differ from theirs in some areas - although we agree that directional arc consistency is better than path-consistency or other forms of lookahead, and that backjumping is to be preferred to backtracking, we disagree in that we believe dynamic ordering of the constraints to be necessary in the solution of more difficult problems.

NMR Workshop 1989 Conference Paper

A Circumscriptive Theorem Prover

• Matthew L. Ginsberg

Abstract In [6], a generalization of first-order logic was introduced that led to the development of an effective theorem prover for some simple sorts of default reasoning. In this paper, we show that these ideas can also be used to construct a theorem prover for a wide class of circumscriptive theories. The ideas to be discussed have been implemented, and the resulting system has been applied to the canonical birds flying example, to a non-separable circumscription [9], and to the Yale shooting problem. In all of these cases, the implementation returns the circumscriptively correct answer.

AIJ Journal 1989 Journal Article

A circumscriptive theorem prover

• Matthew L. Ginsberg

In [6], a generalization of first-order logic was introduced that led to the development of an effective theorem prover for some simple sorts of default reasoning. In this paper, we show that these ideas can also be used to construct a theorem prover for a wide class of circumscriptive theories. The ideas to be discussed have been implemented, and the resulting system has been applied to the canonical birds flying example, to a nonseparable circumscription [9], and to the Yale shooting problem. In all of these cases, the implementation returns the circumscriptively correct answer.

IJCAI Conference 1989 Conference Paper

A Theorem Prover for Prioritized Circumscription

• Andrew B. Baker
• Matthew L. Ginsberg

IJCAI Conference 1989 Conference Paper

Temporal Projection and Explanation

• Andrew B. Baker
• Matthew L. Ginsberg

AAAI Conference 1988 Conference Paper

A Circumscriptive Theorem Prover: Preliminary Report

• Matthew L. Ginsberg

We discuss the application of an assumptionbased truth maintenance system to the construction of a circumscriptive theorem prover, showing that the connection discovered by Reiter and de Kleer between assumption-based truth maintenance and prime implicants relates to the notions of minimality appearing in nonmonotonic reasoning. The ideas we present have been implemented, and the resulting system is applied to the canonical birds flying example and to the Yale shooting problem. In both cases, the implementation returns the circumscriptively correct answer.

AIJ Journal 1988 Journal Article

Reasoning about action I

• Matthew L. Ginsberg
• David E. Smith

Reasoning about change is an important aspect of commonsense reasoning and planning. In this paper we describe an approach to reasoning about change for rich domains where it is not possible to anticipate all situations that might occur. The approach provides a solution to the frame problem, and to the related problem that it is not always reasonable to explicitly specify all of the consequences of actions. The approach involves keeping a single model of the world that is updated when actions are performed. The update procedure involves constructing the nearest world to the current one in which the consequences of the actions under consideration hold. The way we find the nearest world is to construct proofs of the negation of the explicit consequences of the expected action, and to remove a premise in each proof from the current world. Computationally, this construction procedure appears to be tractable for worlds like our own where few things tend to change with each action, or where change is regular.

AIJ Journal 1988 Journal Article

Reasoning about action II

• Matthew L. Ginsberg
• David E. Smith

We present a computationally effective approach to representing and reasoning about actions with many qualifications. The approach involves treating actions as qualified not by specific facts that may or may not hold when the action is executed, but instead as potentially qualified by general constraints describing the domain being investigated. Specifically, we suggest that the result of the action be computed without considering these qualifying domain constraints, and take the action to be qualified if and only if any of the constraints is violated after the computation is complete. Our approach is presented using the framework developed in [6], where we discussed a solution to the frame and ramification problems based on the notion of possible worlds, and compared the computational requirements of that solution to the needs of more conventional ones. In the present paper, we show that the domain constraint approach to qualification, coupled with the possible worlds approach described earlier, has the remarkable property that essentially no computational resources are required to confirm that an action is unqualified. As before, we also make a quantitative comparison between the resources needed by our approach and those required by other formulations.

AAAI Conference 1987 Conference Paper

Possible Worlds and the Qualification Problem

• Matthew L. Ginsberg

In this paper, we propose a solution to McCarthy’s qualification problem [10] based on the notion of possible worlds [3,6]. We begin by noting that existing formal solutions to qualification seem to us to suffer from serious epistemological and computational difficulties. We present a formalization of action based on the notion of possible worlds, and show that our solution to the qualification problem avoids the difficulties encountered by earlier ones by associating to each action a set of domain constraints that can potentially block it. We also compare the computational resources needed by our approach with those required by other formulations.

AIJ Journal 1986 Journal Article

Controlling recursive inference

• David E. Smith
• Michael R. Genesereth
• Matthew L. Ginsberg

Loosely speaking, recursive inference occurs when an inference procedure generates an infinite sequence of similar subgoals. In general, the control of recursive inference involves demonstrating that recursive portions of a search space will not contribute any new answers to the problem beyond a certain level. We first review a well-known syntactic method for controlling repeating inference (inference where the conjuncts processed are instances of their ancestors), provide a proof that it is correct, and discuss the conditions under which the strategy is optimal. We also derive more powerful pruning theorems for cases involving transitivity axioms and cases involving subsumed subgoals. The treatment of repeating inference is followed by consideration of the more difficult problem of recursive inference that does not repeat. Here we show how knowledge of the properties of the relations involved and knowledge about the contents of the system's database can be used to prove that portions of a search space will not contribute any new answers.

AIJ Journal 1986 Journal Article

Counterfactuals

• Matthew L. Ginsberg

Counterfactuals are a form of common-sense nonmonotonic inference that has been of long-term interest to philosophers. In this paper, we begin by describing some of the impact counterfactuals can be expected to have in artificial intelligence, and by reviewing briefly some of the philosophical conclusions which have been drawn about them. We continue by presenting a formal description of counterfactual implication and discussing the issues involved in implementing it. Specific applications in the domains of planning and the automated diagnosis of hardware faults are considered, and we conclude by describing possible extensions to this work involving multi-valued logics and situation semantics.

AAAI Conference 1986 Conference Paper

Multi-Valued Logics

• Matthew L. Ginsberg

A great deal of recent theoretical work in inference has involved extending classical logic in some way. I argue that these extensions share two properties: firstly, the formal addition of truth values encoding intermediate levels of validity between true (i. e. , valid) and false (i. e. , invalid) and, secondly, the addition of truth values encoding intermediate levels of certainty between true or false on the one hand (complete information) and unknown (no information) on the other. Each of these properties can be described by associating lattice structures to the collection of truth values involved; this observation lead us to describe a general framework of which both truth maintenance systems are special cases. default logics and

UAI Conference 1985 Conference Paper

Implementing Probabilistic Reasoning

• Matthew L. Ginsberg

General problems in analyzing information in a probabilistic database are considered. The practical difficulties (and occasional advantages) of storing uncertain data, of using it conventional forward- or backward-chaining inference engines, and of working with a probabilistic version of resolution are discussed. The background for this paper is the incorporation of uncertain reasoning facilities in MRS, a general-purpose expert system building tool.

AAAI Conference 1984 Conference Paper

Non-Monotonic Reasoning Using Dempster’s Rule

• Matthew L. Ginsberg

Rich’s suggestion that the arcs of semantic nets be labelled so as to reflect confidence in the properties they represent is investigated in greater detail. If these confidences are thought of as ranges of acceptable probabilities, existing statistical methods can be used effectively to combine them. The framework developed also seems to be a natural one in which to describe higher levels of deduction, such as "reasoning about reasoning."