Author name cluster

Arizona State University

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

AAAI Conference 1999 Conference Paper

Exploiting Symmetry in the Planning-Graph via Explanation-Guided Search

Terry Zimmerman
Subbarao Kambhampati
Arizona State University

We present a method for exploiting the symmetry in the planning graph structure and certain redundancies inherent in the Graphplan algorithm, so as to improve its backward search. The main insight underlying our method is that due to these features the backward search conducted at level k + 1 of the graph is essentially a replay of the search conducted at the previous level k with certain welldefined extensions. Our method consists of maintaining a pilot explanation structure capturing the failures encountered at previous levels of the search, and using it in an intelligent way to guide the search at the newer levels. The standard EBL and DDB techniques can be employed to control the size of the pilot explanation. The technique has been implemented in the EGBG system, and we present a preliminary empirical study.

PDF Details

AAAI Conference 1999 Short Paper

Externalizing Internal State

Amol D. Mali
Arizona State University

Current autonomous robots that are highly reactive are not significantly intelligent and the robots that are significantly intelligent are not highly reactive. The previous research has concentrated on modifications to internal computational structures of robots, ignoring the modifications to external environments (which can preserve both intelligence and reactivity). This work is the first to formalize the modification of an environment that externalizes the internal states.

PDF Details

AAAI Conference 1999 Short Paper

Hybrid Propositional Encodings of Planning

Amol D. Mali
Arizona State University

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 de- velopment of hybrid propositional encodings (that com- bine the important notions from the existing encodings) have also been posed to the community. The existing encodings are either entirely based only on the plan space planning (also known as "causal" or "least com- mitment" or "partial order" planning) or only on the state space planning. To answer this challenge, we have developed several hybrid encodings.

PDF Details

AAAI Conference 1999 Short Paper

Investigating the Effect of Relevance and Reachability Constraints on SAT Encodings of Planning

Biplav Srivastava
Arizona State University

Recently, satisfiability (SAT) techniques have been shown to be more efficient at extracting solutions from a planning graph in Graphplan than the standard backward search. Graphplan gains efficiency from forward propagation and backward use of mutual exclusion constraints. The utility of SAT techniques for solution extraction raises two important questions: (a) Are the mutual exclusion constraints equally useful for so-lution extraction with SAT encodings? (b) If so, are there additional types of propagated constraints that can benefit them even more? Our ongoing research investigates these two questions.

PDF Details

AAAI Conference 1999 Conference Paper

On the Utility of Plan-Space (Causal) Encodings

Amol D. Mali
Subbarao Kambhampati
Arizona State University

Recently, casting planning as propositional satisfiability has been shown to be a very promising technique for plan synthesis. Although encodings based both on statespace planning and on plan-space (causal) planning have been proposed, most implementations and trade-off evaluations primarily use state-based encodings. This is surprising given both the prominence of plan-space planners in traditional planning, as well as the recent claim that lifted versions of causal encodings provide the smallest encodings. In this paper we attempt a systematic analytical and empirical comparison of plan-space (causal) encodings and state-space encodings. We start by pointing out the connection between the different ways of proving the correctness of a plan, and the spectrum of possible SAT encodings. We then characterize the dimensions along which causal proofs, and consequently, plan-space encodings, can vary. We provide two encodings that are much smaller than those previously proposed. We then show that the smallest causal encodings cannot be smaller in size than the smallest state-based encodings. We shall show that the “lifting” transformation does not affect this relation. Finally, we will present some empirical results that demonstrate that the relative encoding sizes are indeed correlated with the hardness of solving them. We end with a discussion on when the primacy of traditional plan-space planners over state-space planners might carry over to their respective SAT encodings.

PDF Details