Steve Hanks

AIJ Journal 2003 Journal Article

On the undecidability of probabilistic planning and related stochastic optimization problems

• Omid Madani
• Steve Hanks
• Anne Condon

Automated planning, the problem of how an agent achieves a goal given a repertoire of actions, is one of the foundational and most widely studied problems in the AI literature. The original formulation of the problem makes strong assumptions regarding the agent's knowledge and control over the world, namely that its information is complete and correct, and that the results of its actions are deterministic and known. Recent research in planning under uncertainty has endeavored to relax these assumptions, providing formal and computation models wherein the agent has incomplete or noisy information about the world and has noisy sensors and effectors. This research has mainly taken one of two approaches: extend the classical planning paradigm to a semantics that admits uncertainty, or adopt another framework for approaching the problem, most commonly the Markov Decision Process (MDP) model. This paper presents a complexity analysis of planning under uncertainty. It begins with the “probabilistic classical planning” problem, showing that problem to be formally undecidable. This fundamental result is then applied to a broad class of stochastic optimization problems, in brief any problem statement where the agent (a) operates over an infinite or indefinite time horizon, and (b) has available only probabilistic information about the system's state. Undecidability is established for policy-existence problems for partially observable infinite-horizon Markov decision processes under discounted and undiscounted total reward models, average-reward models, and state-avoidance models. The results also apply to corresponding approximation problems with undiscounted objective functions. The paper answers a significant open question raised by Papadimitriou and Tsitsiklis [Math. Oper. Res. 12 (3) (1987) 441–450] about the complexity of infinite horizon POMDPs.

FOCS Conference 1996 Conference Paper

Efficient Information Gathering on the Internet (extended abstract)

• Oren Etzioni
• Steve Hanks
• Tao Jiang 0001
• Richard M. Karp
• Omid Madani
• Orli Waarts

The Internet offers unprecedented access to information. At present most of this information is free, but information providers ore likely to start charging for their services in the near future. With that in mind this paper introduces the following information access problem: given a collection of n information sources, each of which has a known time delay, dollar cost and probability of providing the needed information, find an optimal schedule for querying the information sources. We study several variants of the problem which differ in the definition of an optimal schedule. We first consider a cost model in which the problem is to minimize the expected total cost (monetary and time) of the schedule, subject to the requirement that the schedule may terminate only when the query has been answered or all sources have been queried unsuccessfully. We develop an approximation algorithm for this problem and for an extension of the problem in which more than a single item of information is being sought. We then develop approximation algorithms for a reward model in which a constant reward is earned if the information is successfully provided, and we seek the schedule with the maximum expected difference between the reward and a measure of cost. The monetary and time costs may either appear in the cost measure or be constrained not to exceed a fixed upper bound; these options give rise to four different variants of the reward model.

ICAPS Conference 1996 Conference Paper

Flaw Selection Strategies for Value-Directed Planning

• Mike Williamson
• Steve Hanks

The PYRRHUS planning system is a decision-theoretic extension to POCL planners that finds optimal plans for a class of goal-directed value functions. Although PYRRHUS uses a branch-and-bound algorithm instead of best-first satisficing search, it is faced with the same flaw selection decision as other POCL planners. This paper explains why popular domain-independent flaw-selection strategies are ineffective within an optimizing framework, and presents two new strategies that exploit the additional value information available to PYRRHUS.

AIJ Journal 1995 Journal Article

An algorithm for probabilistic planning

• Nicholas Kushmerick
• Steve Hanks
• Daniel S. Weld

We define the probabilistic planning problem in terms of a probability distribution over initial world states, a boolean combination of propositions representing the goal, a probability threshold, and actions whose effects depend on the execution-time state of the world and on random chance. Adopting a probabilistic model complicates the definition of plan success: instead of demanding a plan that provably achieves the goal, we seek plans whose probability of success exceeds the threshold. In this paper, we present buridan, an implemented least-commitment planner that solves problems of this form. We prove that the algorithm is both sound and complete. We then explore buridan's efficiency by contrasting four algorithms for plan evaluation, using a combination of analytic methods and empirical experiments. We also describe the interplay between generating plans and evaluating them, and discuss the role of search control in probabilistic planning.

UAI Conference 1995 Conference Paper

Probabilistic Temporal Reasoning with Endogenous Change

• Steve Hanks
• David Madigan
• Jonathan Gavrin

This paper presents a probabilistic model for reasoning about the state of a system as it changes over time, both due to exogenous and endogenous influences. Our target domain is a class of medical prediction problems that are neither so urgent as to preclude careful diagnosis nor progress so slowly as to allow arbitrary testing and treatment options. In these domains there is typically enough time to gather information about the patient's state and consider alternative diagnoses and treatments, but the temporal interaction between the timing of tests, treatments, and the course of the disease must also be considered. Our approach is to elicit a qualitative structural model of the patient from a human expert---the model identifies important attributes, the way in which exogenous changes affect attribute values, and the way in which the patient's condition changes endogenously. We then elicit probabilistic information to capture the expert's uncertainty about the effects of tests and treatments and the nature and timing of endogenous state changes. This paper describes the model in the context of a problem in treating vehicle accident trauma, and suggests a method for solving the model based on the technique of sequential imputation. A complementary goal of this work is to understand and synthesize a disparate collection of research efforts all using the name �probabilistic temporal reasoning.� This paper analyzes related work and points out essential differences between our proposed model and other approaches in the literature.

UAI Conference 1994 Conference Paper

A Probablistic Model of Action for Least-Commitment Planning with Information Gathering

• Denise Draper
• Steve Hanks
• Daniel S. Weld

UAI Conference 1994 Conference Paper

Localized Partial Evaluation of Belief Networks

• Denise Draper
• Steve Hanks

AIJ Journal 1994 Journal Article

Modeling a dynamic and uncertain world I

• Steve Hanks
• Drew McDermott

Intelligent agency requires some ability to predict the future. An agent must ask itself what is presently its best course of action given what it now knows about what the world will be like when it intends to act. This paper presents a system that uses a probabilistic model to reason about the effects of an agent's proposed actions on a dynamic and uncertain world, computing the probability that relevant propositions will hold at a specified point in time. The model allows for incomplete information about the world, the occurrence of exogenous (unplanned) events, unreliable sensors, and the possibility of an imperfect causal theory. The system provides an application program with answers to questions of the form “is the probability that ϕ will hold in the world at time t greater than τ? ” It is unique among algorithms for probabilistic temporal reasoning in that it tries to limit its inference according to the proposition, time, and probability threshold provided by the application. The system will also notify the application if subsequent evidence invalidates its answer to a query.

ICAPS Conference 1994 Conference Paper

Optimal Planning with a Goal-directed Utility Model

• Mike Williamson
• Steve Hanks

ClassicMAI planning adopts L very narrow notion of plan quality, namelythat a plan is goodjust in case it achieves a specified goal. Despite the fact that planning is intractable in the worst case, goal-satisfying planning algorithms can effectively solve classes of problems by using the goal to focus the search for a solution (by using backward-chaining techniques), and by exploiting domain-specific heuristic knowledge to control search. Our work extends the definition of plan quality to take into account partial satisfaction of the goal and the cost of resources used by the plan, while at the sametime building an effective planning algorithm by exploiting classical plamningtechniques like backward chaining aatd knowledge-based search control rules. This paper presents PYRRHUS, a~ extension to the ucPoe planning system (Barrett et ai. 1993) that finds optimal plans for a class of goal-directed utility models suggested by Hadd~wyand Hanks (Haddawy &Hanks1993). Our empirical results suggest that optimal plans can be generated effectively by a planner using domain-specific heuristic knowledge, and furthermore that the planner can use the sameknowledge as a goal-satisfying planner to solve correspondingoptimization problems.

ICAPS Conference 1994 Conference Paper

Probabilistic Planning with Information Gathering and Contingent Execution

• Denise Draper
• Steve Hanks
• Daniel S. Weld

Most AI representations and algorithms for plan generation have not included the concept of informationproducing actions (also called diagnostics, or tests, in the decision making literature). Wepresent planning representation and algorithm that models information-producing actions and constructs plans that exploit the information produced by those actions. Weextend the BURIDAN (Knshmerick et al. 1994) probabilistic planning algorithm, adapting the action representation to modelthe behavior of imperfect sensors, and combineit with a frameworkfor contingent action that extends the CNLP algorithm (Peot and Smith1992) for conditioned execution. The result, C-BURIDAN, is an implemented planner that builds plans with probabilistic information-producingactions and contingent execution. algorithm (Peot and Smith 1992). C-BURIDAN takes as input a probability distribution over initial world states, a goal expression, a set of action descriptions, and a probability threshold, and produces a contingent plan that makes the goal expression true with a Iprobability no less than the threshold.

IJCAI Conference 1993 Conference Paper

Exploiting Domain Structure to Achieve Efficient Temporal Reasoning

• Mike Williamson
• Steve Hanks

We take temporal reasoning to be the problem of maintaining a set of constraints between time points and/or intervals, and responding to queries about the temporal separation between those individuals. Formal investigations of this constraint-satisfaction problem have demonstrated tradeoffs between the expressive power of the constraint language and the time required to answer queries. A simple constraint language admits an algorithm cubic in the number of individuals; allowing unrestricted disjunctive constraints makes the algorithm exponential. The problem is that applications of temporal reasoning, e. g. plan projection, need both disjunctive constraints and an algorithm much faster than 0 ( n 3 ). It is significant, however, that the nature of the constraints added by and the queries posed by an application tend to be structured and predictable. Our solution to the problem is to exploit the structure of the application domain to provide fast responses to typical queries. We consider the problem of plan projection under uncertainty and build a temporal representation—hierarchical interval constraints ( H I C ) — t h a t allows appropriate disjunctive constraints. We then implement the H I C representation in a temporal-reasoning module, and test it using a plan-projection application. A p p l y i n g the H I C module to a simple temporal projection problem shows orders-of-magnitude improvement over running the same projector using current implementations of domain-independent temporal constraint propagators.

AAAI Conference 1990 Conference Paper

Practical Temporal Projection

• Steve Hanks

Temporal projection-predicting future states of a changing world-has been studied mainly as a formal problem. Researchers have been concerned with getting the concepts of causality and change right, and have ignored the practical issues surrounding projection. In planning, for example, when the effects of a plan’ s actions depend on the prevailing state of the world and that state of the world is not known with certainty, projecting the plan may generate an exponential number of possible outcomes. This problem has traditionally been eliminated by (1) restricting the domain so the world state is always known, and (2) by restricting the action representation so that either the action’ s intended eflect is realized or the action cannot be projected at all. We argue against these restrictions and instead present a system that (1) represents and reasons about an uncertain world, (2) supports a representation that allows context-sensitive action effects, and (3) generates projections that reflect only the significant or reEeuant outcomes of the plans, where relevance is determined by the planner’ s queries about the resulting world state.

AAAI Conference 1988 Conference Paper

Representing and Computing Temporally Scoped Beliefs

• Steve Hanks

Planning effective courses of action requires making predictions about what the world may be like at the time the actions are to be performed. Making these predictions requires a temporal representation, and-assuming a world that is not entirely predictable and an agent that is not omniscient- a representation of the uncertainty that will characterize its incomplete knowledge of the world. We provide in this paper a representation and calculus for computing an agent’s strength of belief in a proposition at a point in time, based on (possibly imperfect) observations about that proposition and information about the tendency of the proposition to persist over time.

AIJ Journal 1987 Journal Article

Nonmonotonic logic and temporal projection

• Steve Hanks
• Drew McDermott

Nonmonotonic formal systems have been proposed as an extension to classical first-order logic that will capture the process of human “default reasoning” or “plausible inference” through their inference mechanisms, just as modus ponens provides a model for deductive reasoning. But although the technical properties of these logics have been studied in detail and many examples of human default reasoning have been identified, for the most part these logics have not actually been applied to practical problems to see whether they produce the expected results. We provide axioms for a simple problem in temporal reasoning which has long been identified as a case of default reasoning, thus presumably amenable to representation in nonmonotonic logic. Upon examining the resulting nonmonotonic theories, however, we find that the inferences permitted by the logics are not those we had intended when we wrote the axioms, and in fact are much weaker. This problem is shown to be independent of the logic used; nor does it depend on any particular temporal representation. Upon analyzing the failure we find that the nonmonotonic logics we considered are inherently incapable of representing this kind of default reasoning. The first part of the paper is an expanded version of one that appeared in the 1986 AAAI proceedings. The second part reports on several responses to our result that have appeared since the original paper was published.

AAAI Conference 1986 Conference Paper

Default Reasoning, Nonmonotonic Logics, and the Frame Problem

• Steve Hanks

Nonmonotonic formal systems have been proposed as an extension to classical first-order logic that will capture the process of human “default reasoning” or “plausible inference” through their inference mechanisms just as modus ponena provides a model for deductive reasoning. But although the technical properties of these logics have been studied in detail and many examples of human default reasoning have been identified, for the most part these logics have not actually been applied to practical problems to see whether they produce the expected results. We provide axioms for a simple problem in temporal reasoning which has long been identified as a case of default reasoning, thus presumably amenable to representation in nonmonotonic logic. Upon examining the resulting nonmonotonic theories, however, we find that the inferences permitted by the logics are not those we had intended when we wrote the axioms, and in fact are much weaker. This problem is shown to be independent of the logic used; nor does it depend on any particular temporal representation. Upon analyzing the failure we find that the nonmonotonic logics we considered are inherently incapable of representing this kind of default reasoning. Finally we discuss two recent proposals for solving this problem.