robabilistic Propositional Planning: Representations and Complexity

AAAI Conferences

This paper reviews several such representations and shows that, in spite of superficial differences between the represent at ions, they are "expressively equivalent," meaning that planning problems specified in one representation can be converted to equivalent planning problems in any of the other representations with at most a polynomial factor increase in the size of the resulting representation and the number of steps needed to reach the goal with sufficient probability. The paper proves that the computational complexity of determining whether a successful plan exists for planning problems expressed in any of these representations is EXPTIME-complete and PSPACE-complete when plans are restricted to take a polynomial number of steps.


Learning Heuristic Functions from Relaxed Plans

AAAI Conferences

We present a novel approach to learning heuristic functions for AI planning domains. Given a state, we view a relaxed plan (RP) found from that state as a relational database, which includes the current state and goal facts, the actions in the RP, and the actions' add and delete lists. We represent heuristic functions as linear combinations of generic features of the database, selecting features and weights using training data from solved problems in the target planning domain. Many recent competitive planners use RP-based heuristics, but focus exclusively on the length of the RP, ignoring other RP features. Since RP construction ignores delete lists, for many domains, RP length dramatically underestimates the distance to a goal, providing poor guidance. By using features that depend on deleted facts and other RP properties, our learned heuristics can potentially capture patterns that describe where such underestimation occurs. Experiments in the STRIPS domains of IPC 3 and 4 show that best-first search using the learned heuristic can outperform FF (Hoffmann & Nebel 2001), which provided our training data, and frequently outperforms the top performances in IPC 4.


Hybrid Propositional Encodings of Planning

AAAI Conferences

Casting planning as propositional satisfiability has been recently shown to be a very promising technique of plan synthesis. Some challenges, one of which is the development of hybrid propositional encodings (that combine the important notions from the existing encodings) have also been posed to the community [1]. The existing encodings [3] are either entirely based only on the plan space planning (also known as "causal" or "least commitment" or "partial order" planning) or only on the state space planning. To answer this challenge, we have developed several hybrid encodings. A key difference between state space planning and plan space planning is that state of the world is represented at each time step during the state space planning process and it is never available during the partial order planning process.


A Linear Programming Heuristic for 0 g'om

AAAI Conferences

Planning is the problem of finding a combination of actions that achieves a goal (Allen, Hendler, & Tate 1990; Hendler, Tate, & Drummond 1990). So far, there is limited success in general-purpose planning, in large part due to two factors. One factor is the computational complexity of planning, e.g., propositional STRIPS planning is PSPACEcomplete except for very severe restrictions (Btickstrijm & Nebel 1995; Bylander 1994; Erol, Nau, & Subrahmanian 1995). The other factor is that planning formalisms make very strong representational assumptions, e.g., the STRIPS formalism assumes that actions are deterministic, and that an agent knows all relevant aspects of the environment (Dean & Wellman 1991). Work within planning research can be viewed as attempting to find a suitable compromise or deviation from the known formalisms and algorithms. This paper introduces a new heuristic for propositional STRIPS planning based on converting planning instances to linear programming instances. More precisely, an incomplete partial-order plan with a constraint on the length (number of operators) of the plan is translated to a 0-1 integer programming instance, and linear programming is used to determine if the relaxed instance has a solution. The relaxed instance does not require an integer Copyright @ 1997, American Association for Artificial Intelligence (www.aaai.org).


Magic Inference Rules for Probabilistic Deduction under Taxonomic Knowledge

arXiv.org Artificial Intelligence

We present locally complete inference rules for probabilistic deduction from taxonomic and probabilistic knowledge-bases over conjunctive events. Crucially, in contrast to similar inference rules in the literature, our inference rules are locally complete for conjunctive events and under additional taxonomic knowledge. We discover that our inference rules are extremely complex and that it is at first glance not clear at all where the deduced tightest bounds come from. Moreover, analyzing the global completeness of our inference rules, we find examples of globally very incomplete probabilistic deductions. More generally, we even show that all systems of inference rules for taxonomic and probabilistic knowledge-bases over conjunctive events are globally incomplete. We conclude that probabilistic deduction by the iterative application of inference rules on interval restrictions for conditional probabilities, even though considered very promising in the literature so far, seems very limited in its field of application.