The World Wide Web provides access to vast amounts of information, but content providers are considering charging for the information and services they supply. Thus the consumer may face the problem of balancing the benefit of asking for information against the cost (in terms of both money and time) of acquiring it. We study information-gathering strategies that maximize the expected value to the consumer. In our model there is a single information request, which has a known benefit to the consumer. To satisfy the request, queries can be sent simultaneously or in sequence to any of a finite set of independent information sources. For each source we know the monetary cost of making the query, the amount of time it will take, and the probability that the source will be able to provide the requested information. A policy specifies which sources to contact at which times, and the expected value of the policy can be defined as some function of the likelihood that the policy will yield an answer, the expected benefit, and the monetary cost and time delay associated with executing the policy. The problem is to find an expected-value-maximizing policy. We explore four variants of the objective function V: (i) V consists only of the benefit term subject to threshold constraints on both total cost and total elapsed time, (ii) V is linear in the expected total cost of the policy subject to the constraint that the total elapsed time never exceeds somedeadline, (iii) V is linear in the expected total elapsed time subject to the constraint that the total cost never exceeds some threshold, and (iv) V is linear in the expected total monetary cost and the expected time delay of the policy. The problems of devising an optimal querying policy for all four variants and approximating an optimal querying policy for variants (iii) and (iv) are shown to be NP-hard. For (i), and with a mild simplifying assumption for (iii), we give a fully polynomial time approximation scheme. For (ii), we consider batched querying policies, and design an O(n 2 ) time approximation algorithm with ratio $\frac{1}{2}$ and a polynomial time approximation scheme for optimal single-batch policies, and an O(kn 2 ) time approximation algorithm with ratio $\frac{1}{5}$ for optimal k-batch policies.

Planning under uncertainty is a central problem in the study of automated sequential decision making, and has been addressed by researchers in many different fields, including AI planning, decision analysis, operations research, control theory and economics. While the assumptions and perspectives adopted in these areas often differ in substantial ways, many planning problems of interest to researchers in these fields can be modeled as Markov decision processes (MDPs) and analyzed using the techniques of decision theory. This paper presents an overview and synthesis of MDP-related methods, showing how they provide a unifying framework for modeling many classes of planning problems studied in AI. It also describes structural properties of MDPs that, when exhibited by particular classes of problems, can be exploited in the construction of optimal or approximately optimal policies or plans. Planning problems commonly possess structure in the reward and value functions used to describe performance criteria, in the functions used to describe state transitions and observations, and in the relationships among features used to describe states, actions, rewards, and observations. Specialized representations, and algorithms employing these representations, can achieve computational leverage by exploiting these various forms of structure. Certain AI techniques -- in particular those based on the use of structured, intensional representations -- can be viewed in this way. This paper surveys several types of representations for both classical and decision-theoretic planning problems, and planning algorithms that exploit these representations in a number of different ways to ease the computational burden of constructing policies or plans. It focuses primarily on abstraction, aggregation and decomposition techniques based on AI-style representations.

AI planning agents are goal‐directed: success is measured in terms of whether an input goal is satisfied. The goal gives structure to the planning problem, and planning representations and algorithms have been designed to exploit that structure. Strict goal satisfaction may be an unacceptably restrictive measure of good behavior, however. A general decision‐theoretic agent, on the other hand, has no explicit goals: success is measured in terms of an arbitrary preference model or utility function defined over plan outcomes. Although it is a very general and powerful model of problem solving, decision‐theoretic choice lacks structure, which can make it difficult to develop effective plan‐generation algorithms. This paper establishes a middle ground between the two models. We extend the traditional AI goal model in several directions: allowing goals with temporal extent, expressing preferences over partial satisfaction of goals, and balancing goal satisfaction against the cost of the resources consumed in service of the goals. In doing so we provide a utility model for a goal‐directed agent. An important quality of the proposed model is its tractability. We claim that our model, like classical goal models, makes problem structure explicit. This structure can then be exploited by a problem‐solving algorithm. We support this claim by reporting on two implemented planning systems that adopt and exploit our model.

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.

The paradigms of transformational planning, case-based planning, and plan debugging all involve a process known as plan adaptation - modifying or repairing an old plan so it solves a new problem. In this paper we provide a domain-independent algorithm for plan adaptation, demonstrate that it is sound, complete, and systematic, and compare it to other adaptation algorithms in the literature. Our approach is based on a view of planning as searching a graph of partial plans. Generative planning starts at the graph's root and moves from node to node using plan-refinement operators. In planning by adaptation, a library plan - an arbitrary node in the plan graph - is the starting point for the search, and the plan-adaptation algorithm can apply both the same refinement operators available to a generative planner and can also retract constraints and steps from the plan. Our algorithm's completeness ensures that the adaptation algorithm will eventually search the entire graph and its systematicity ensures that it will do so without redundantly searching any parts of the graph.

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.

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.