Robert Givan

JMLR Journal 2008 Journal Article

Learning Control Knowledge for Forward Search Planning

• Sungwook Yoon
• Alan Fern
• Robert Givan

A number of today's state-of-the-art planners are based on forward state-space search. The impressive performance can be attributed to progress in computing domain independent heuristics that perform well across many domains. However, it is easy to find domains where such heuristics provide poor guidance, leading to planning failure. Motivated by such failures, the focus of this paper is to investigate mechanisms for learning domain-specific knowledge to better control forward search in a given domain. While there has been a large body of work on inductive learning of control knowledge for AI planning, there is a void of work aimed at forward-state-space search. One reason for this may be that it is challenging to specify a knowledge representation for compactly representing important concepts across a wide range of domains. One of the main contributions of this work is to introduce a novel feature space for representing such control knowledge. The key idea is to define features in terms of information computed via relaxed plan extraction, which has been a major source of success for non-learning planners. This gives a new way of leveraging relaxed planning techniques in the context of learning. Using this feature space, we describe three forms of control knowledge---reactive policies (decision list rules and measures of progress) and linear heuristics---and show how to learn them and incorporate them into forward state-space search. Our empirical results show that our approaches are able to surpass state-of-the-art non-learning planners across a wide range of planning competition domains. [abs] [ pdf ][ bib ] &copy JMLR 2008. ( edit, beta )

AAAI Conference 2008 Conference Paper

Probabilistic Planning via Determinization in Hindsight

• Sungwook Yoon
• Robert Givan

This paper investigates hindsight optimization as an approach for leveraging the significant advances in deterministic planning for action selection in probabilistic domains. Hindsight optimization is an online technique that evaluates the onestep-reachable states by sampling future outcomes to generate multiple non-stationary deterministic planning problems which can then be solved using search. Hindsight optimization has been successfully used in a number of online scheduling applications; however, it has not yet been considered in the substantially different context of goal-based probabilistic planning. We describe an implementation of hindsight optimization for probabilistic planning based on deterministic forward heuristic search and evaluate its performance on planning-competition benchmarks and other probabilistically interesting problems. The planner is able to outperform a number of probabilistic planners including FF- Replan on many problems. Finally, we investigate conditions under which hindsight optimization is guaranteed to be effective with respect to goal achievement, and also illustrate examples where the approach can go wrong.

ICAPS Conference 2008 Conference Paper

Stochastic Enforced Hill-Climbing

• Jia-Hong Wu
• Rajesh Kalyanam
• Robert Givan

Enforced hill-climbing is an effective deterministic hill-climbing technique that deals with local optima using breadth-first search (a process called ``basin flooding''). We propose and evaluate a stochastic generalization of enforced hill-climbing for online use in goal-oriented probabilistic planning problems. We assume a provided heuristic function estimating expected cost to the goal with flaws such as local optima and plateaus that thwart straightforward greedy action choice. While breadth-first search is effective in exploring basins around local optima in deterministic problems, for stochastic problems we dynamically build and solve a local Markov-decision process model of the basin in order to find a good escape policy exiting the local optimum. We evaluate our proposal in a wide range of recent probabilistic planning-competition benchmark domains. For evaluation, we show that stochastic enforced hill-climbing produces better policies than greedy action choice for value functions derived in two very different ways. First, we propose a novel heuristic function derived from the ideas in the effective re-planner FF-Replan. This new ``controlled-randomness FF heuristic'' is the deterministic FF heuristic computed on the simple determinization of the probabilistic problem that makes available a deterministic transition wherever a probabilistic transition was possible. Our results show that stochastic enforced hill-climbing with this heuristic significantly outperforms simply greedily following the heuristic, and also substantially outperforms FF-Replan. We additionally evaluate our technique on automatically learned value functions that on their own perform at the state-of-the-art when used to construct a greedy policy, and again show significant improvement over greedy action selection.

IJCAI Conference 2007 Conference Paper

• Sungwook Yoon
• Alan Fern
• Robert Givan

Many current state-of-the-art planners rely on forward heuristic search. The success of such search typically depends on heuristic distance-to-the-goal estimates derived from the plangraph. Such estimates are effective in guiding search for many domains, but there remain many other domains where current heuristics are inadequate to guide forward search effectively. In some of these domains, it is possible to learn reactive policies from example plans that solve many problems. However, due to the inductive nature of these learning techniques, the policies are often faulty, and fail to achieve high success rates. In this work, we consider how to effectively integrate imperfect learned policies with imperfect heuristics in order to improve over each alone. We propose a simple approach that uses the policy to augment the states expanded during each search step. In particular, during each search node expansion, we add not only its neighbors, but all the nodes along the trajectory followed by the policy from the node until some horizon. Empirical results show that our proposed approach benefits both of the leveraged automated techniques, learning and heuristic search, outperforming the state-of-the-art in most benchmark planning domains.

ICAPS Conference 2007 Conference Paper

Discovering Relational Domain Features for Probabilistic Planning

• Jia-Hong Wu
• Robert Givan

In sequential decision-making problems formulated as Markov decision processes, state-value function approximation using domain features is a critical technique for scaling up the feasible problem size. We consider the problem of automatically finding useful domain features in problem domains that exhibit relational structure. Specifically we consider learning compact relational features without input from human expertise; we use neither expert decisions nor human domain knowledge beyond the basic domain definition. We propose a method to learn relational features for a linear value-function representation---numerically valued features are selected by their fit to the Bellman residual of the current value function and are automatically learned and added to the representation when needed. Starting with only a trivial feature in the value-function representation, our method finds useful value functions by combining feature learning with approximate value iteration. Empirical work presented here for Tetris and for probabilistic planning competition domains shows that our technique represents the state-of-the-art for both domain-independent feature learning and for stochastic planning in relational domains.

ICAPS Conference 2007 Conference Paper

FF-Replan: A Baseline for Probabilistic Planning

• Sung Wook Yoon
• Alan Fern
• Robert Givan

FF-Replan was the winner of the 2004 International Probabilistic Planning Competition (IPPC-04) and was also the top performer on IPPC-06 domains, though it was not an official entry. This success was quite surprising, due to the simplicity of the approach. In particular, FF-Replan calls FF on a carefully constructed deterministic variant of the planning problem and selects actions according to the plan until observing an unexpected effect, upon which it replans. Despite the obvious shortcomings of the approach and its strawman nature, it is the state-of-the-art in probabilistic planning as measured on recent competition benchmarks. This paper gives the first technical description of FF-Replan and provides an analysis of its results on all of the recent IPPC-04 and IPPC-06 domains. We hope that this will inspire extensions and insight into the approach and planning domains themselves that will soon lead to the dethroning of FF-Replan.

ICAPS Conference 2006 Conference Paper

Learning Heuristic Functions from Relaxed Plans

• Sung Wook Yoon
• Alan Fern
• Robert Givan

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 under-estimates 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 under-estimation 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.

AIJ Journal 2006 Journal Article

Sequential inference with reliable observations: Learning to construct force-dynamic models

• Alan Fern
• Robert Givan

We present a trainable sequential-inference technique for processes with large state and observation spaces and relational structure. We apply our technique to the problem of force-dynamic state inference from video, which is a critical component of the LEONARD [J. M. Siskind, Grounding lexical semantics of verbs in visual perception using force dynamics and event logic, Journal of Artificial Intelligence Research 15 (2001) 31–90] visual-event recognition system. LEONARD uses event definitions that are grounded in force-dynamic primitives—making robust and efficient force-dynamic inference critical to good performance. Our sequential-inference method assumes “reliable observations”, i. e. , that each process state (e. g. , force-dynamic state) persists long enough to be reliably inferred from the observations (e. g. , video frames) it generates. We introduce the idea of a “state-inference function” (from observation sequences to underlying hidden states) for representing knowledge about a process and develop an efficient sequential-inference algorithm, utilizing this function, that is correct for processes that generate reliable observations consistent with the state-inference function. We describe a representation for state-inference functions in relational domains and give a corresponding supervised learning algorithm. Our experiments in force-dynamic state inference show that our technique provides significantly improved accuracy and speed relative to a variety of recent, hand-coded, non-trainable systems, and a trainable system based on probabilistic modeling.

ICAPS Conference 2004 Conference Paper

Learning Domain-Specific Control Knowledge from Random Walks

• Alan Fern
• Sung Wook Yoon
• Robert Givan

Wedescribe and evaluate a system for learning domainspecific control knowledge. In particular, given a planning domain, the goal is to output a control policy that performs well on "long random walk" problem distributions. The system is based on viewing planning domains as very large Markov decision processes and then applying a recent variant of approximate policy iteration that is bootstrapped with a new technique based on random walks. We evaluate the system on the AIPS-2000 planning domains (among others) and show that often the learned policies perform well on problems drawn from the long-random-walk distribution. In addition, we show that these policies often perform well on the original problem distributions from the domains involved. Our evaluation also uncovers limitations of our current system that point to future challenges.

ICML Conference 2004 Conference Paper

Relational sequential inference with reliable observations

• Alan Fern
• Robert Givan

NeurIPS Conference 2003 Conference Paper

Approximate Policy Iteration with a Policy Language Bias

• Alan Fern
• Sungwook Yoon
• Robert Givan

We explore approximate policy iteration, replacing the usual cost- function learning step with a learning step in policy space. We give policy-language biases that enable solution of very large relational Markov decision processes (MDPs) that no previous technique can solve. In particular, we induce high-quality domain-specific planners for clas- sical planning domains (both deterministic and stochastic variants) by solving such domains as extremely large MDPs.

AIJ Journal 2003 Journal Article

Equivalence notions and model minimization in Markov decision processes

• Robert Givan
• Thomas Dean
• Matthew Greig

Many stochastic planning problems can be represented using Markov Decision Processes (MDPs). A difficulty with using these MDP representations is that the common algorithms for solving them run in time polynomial in the size of the state space, where this size is extremely large for most real-world planning problems of interest. Recent AI research has addressed this problem by representing the MDP in a factored form. Factored MDPs, however, are not amenable to traditional solution methods that call for an explicit enumeration of the state space. One familiar way to solve MDP problems with very large state spaces is to form a reduced (or aggregated) MDP with the same properties as the original MDP by combining “equivalent” states. In this paper, we discuss applying this approach to solving factored MDP problems—we avoid enumerating the state space by describing large blocks of “equivalent” states in factored form, with the block descriptions being inferred directly from the original factored representation. The resulting reduced MDP may have exponentially fewer states than the original factored MDP, and can then be solved using traditional methods. The reduced MDP found depends on the notion of equivalence between states used in the aggregation. The notion of equivalence chosen will be fundamental in designing and analyzing algorithms for reducing MDPs. Optimally, these algorithms will be able to find the smallest possible reduced MDP for any given input MDP and notion of equivalence (i. e. , find the “minimal model” for the input MDP). Unfortunately, the classic notion of state equivalence from non-deterministic finite state machines generalized to MDPs does not prove useful. We present here a notion of equivalence that is based upon the notion of bisimulation from the literature on concurrent processes. Our generalization of bisimulation to stochastic processes yields a non-trivial notion of state equivalence that guarantees the optimal policy for the reduced model immediately induces a corresponding optimal policy for the original model. With this notion of state equivalence, we design and analyze an algorithm that minimizes arbitrary factored MDPs and compare this method analytically to previous algorithms for solving factored MDPs. We show that previous approaches implicitly derive equivalence relations that we define here.

UAI Conference 2002 Conference Paper

Inductive Policy Selection for First-Order MDPs

• Sung Wook Yoon
• Alan Fern
• Robert Givan

I&C Journal 2002 Journal Article

Tarskian Set Constraints

• Robert Givan
• David McAllester
• Carl Witty
• Dexter Kozen

We investigate set constraints over set expressions with Tarskian functional and relational operations. Unlike the Herbrand constructor symbols used in recent set constraint formalisms, the meaning of a Tarskian function symbol is interpreted in an arbitrary first order structure. We show that satisfiability of Tarskian set constraints is decidable in nondeterministic doubly exponential time. We also give complexity results and open problems for various extensions and restrictions of the language.

AIJ Journal 2000 Journal Article

Bounded-parameter Markov decision processes

• Robert Givan
• Sonia Leach
• Thomas Dean

In this paper, we introduce the notion of a bounded-parameter Markov decision process (BMDP) as a generalization of the familiar exact MDP. A bounded-parameter MDP is a set of exact MDPs specified by giving upper and lower bounds on transition probabilities and rewards (all the MDPs in the set share the same state and action space). BMDPs form an efficiently solvable special case of the already known class of MDPs with imprecise parameters (MDPIPs). Bounded-parameter MDPs can be used to represent variation or uncertainty concerning the parameters of sequential decision problems in cases where no prior probabilities on the parameter values are available. Bounded-parameter MDPs can also be used in aggregation schemes to represent the variation in the transition probabilities for different base states aggregated together in the same aggregate state. We introduce interval value functions as a natural extension of traditional value functions. An interval value function assigns a closed real interval to each state, representing the assertion that the value of that state falls within that interval. An interval value function can be used to bound the performance of a policy over the set of exact MDPs associated with a given bounded-parameter MDP. We describe an iterative dynamic programming algorithm called interval policy evaluation that computes an interval value function for a given BMDP and specified policy. Interval policy evaluation on a policy π computes the most restrictive interval value function that is sound, i. e. , that bounds the value function for π in every exact MDP in the set defined by the bounded-parameter MDP. We define optimistic and pessimistic criteria for optimality, and provide a variant of value iteration (Bellman, 1957) that we call interval value iteration that computes policies for a BMDP that are optimal with respect to these criteria. We show that each algorithm we present converges to the desired values in a polynomial number of iterations given a fixed discount factor.

ICAPS Conference 2000 Conference Paper

On-line Scheduling via Sampling

• Hyeong Soo Chang
• Robert Givan
• Edwin K. P. Chong

We consider the problem of scheduling an unknown sequence of tasks for a single server as the tasks arrive with the goal of maximizing the total weighted value of the tasks served before their deadline is reached. This problem is faced for example by schedulers in packet communication networks when packets have deadlines and rewards associated with them. We make the simplifying assumptions that every task takes the same fixed amount of time to serve, that every task arrives with the same initial latency to its deadline. We also assume that future task arrivals are stochastically described by a Hidden Markov Model (HMM). The resulting decision problem can be formally modelled as a Partially Observable Markov Decision Process (POMDP). We first present and analyze a new optimal off-line scheduling algorithm called Prescient Minloss scheduling for the problem just described, but with “prescient” foreknowledge of the future task arrivals. We then discuss heuristically adapting this off-line algorithm into an on-line algorithm by sampling possible future task sequences from the HMM. We discuss and empirically compare scheduling methods for this on-line problem, including previously proposed sampling-based POMDP solution methods. Our heuristic approach can be used to adapt any off-line scheduler into an on-line scheduler.

ICML Conference 2000 Conference Paper

Online Ensemble Learning: An Empirical Study

• Alan Fern
• Robert Givan

ICAPS Conference 1998 Conference Paper

Solving Stochastic Planning Problems with Large State and Action Spaces

• Thomas L. Dean
• Robert Givan
• Kee-Eung Kim

nated from consideration. In other problems, such identifiPlanning methods for deterministic planning problems traditionally exploit factored representations to encode the dynamics of problems in terms of a set of parameters, e. g., the location of a robot or the status of a piece of equipment. Factored representations achieve economy of representation by taking advantage of structure in the form of dependency relationships among these parameters. In recent work, we have addressed the problem of achieving the same economy of representation and exploiting the resulting encoding of structure for stochastic planning problems represented as Markov decision processes. In this paper, we extend our earlier work on reasoning about such factored representations to handle problems with large action spaces that are also represented in factored form, where the parameters in this case might correspond to the control parameters for different effectors on a robot or the allocations for a set of resources. The techniques described in this paper employ factored representations for Markov decision processes to identify and exploit regularities in the dynamics to expedite inference. These regularities are in the form of sets of states (described for example by boolean formulas) that behave the same with respect to sets of actions where these sets are thought of as aggregate states and aggregate actions respectively. We present theoretical foundations, describe algorithms, provide examples in which our techniques provide leverage and examples in which they fail to do so, and summarize the results of experiments with a preliminary implementation.

IJCAI Conference 1997 Conference Paper

Model Minimization, Regression, and Propositional STRIPS Planning

• Robert Givan
• Tltomas Dean

Propositional STRIPS planning problems can be viewed as finite state automata (FSAs) represented in a factored form. Automaton minimization is a well-known technique for reducing the size of an explicit FSA. Recent work in computer-aided verification on model checking has extended this technique to provide automaton minimization algorithms for factored FSAs. In this paper, we consider the relationship between STRIPS problem-solving techniques such as regression and the recently developed automaton minimization techniques for factored FSAs. We show that regression computes a partial and approximate minimized form of the FSA corresponding to the STRIPS problem. We then define a systematic form of regression which computes a partial but exact minimized form of the associated FSA. We also relate minimization to methods for performing reachability analysis to detect irrelevant fluents. Finally, we show that exact computation of the minimized automaton is NP-complete under the assumption that this automaton is polynomial in size.

UAI Conference 1997 Conference Paper

Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes

• Thomas L. Dean
• Robert Givan
• Sonia M. Leach

We present a method for solving implicit (factored) Markov decision processes (MDPs) with very large state spaces. We introduce a property of state space partitions which we call epsilon-homogeneity. Intuitively, an epsilon-homogeneous partition groups together states that behave approximately the same under all or some subset of policies. Borrowing from recent work on model minimization in computer-aided software verification, we present an algorithm that takes a factored representation of an MDP and an 0<=epsilon<=1 and computes a factored epsilon-homogeneous partition of the state space. This partition defines a family of related MDPs---those MDPs with state space equal to the blocks of the partition, and transition probabilities "approximately" like those of any (original MDP) state in the source block. To formally study such families of MDPs, we introduce the new notion of a "bounded parameter MDP" (BMDP), which is a family of (traditional) MDPs defined by specifying upper and lower bounds on the transition probabilities and rewards. We describe algorithms that operate on BMDPs to find policies that are approximately optimal with respect to the original MDP. In combination, our method for reducing a large implicit MDP to a possibly much smaller BMDP using an epsilon-homogeneous partition, and our methods for selecting actions in BMDPs constitute a new approach for analyzing large implicit MDPs. Among its advantages, this new approach provides insight into existing algorithms to solving implicit MDPs, provides useful connections to work in automata theory and model minimization, and suggests methods, which involve varying epsilon, to trade time and space (specifically in terms of the size of the corresponding state space) for solution quality

AAAI Conference 1997 Conference Paper

Obvious Properties of Computer Programs

• Robert Givan

We explore the question of what properties of LISP programs can be made “obvious” to a computer system. We present a polynomial-time algorithm for inferring interesting properties of pure LISP programs. Building on previous work in knowledge representation for rapid inference, we present a language for representing properties of programs. We treat properties as generalized types, i. e. , sets of program values. The property language is expressive enough to represent any RE set of LISP values as a property, and can naturally represent, a wide variety of useful properties. We then use a general technique to construct a polynomial-time property inference relation and use type-inference style program analysis to integrate this relation into an algorithm for inferring properties of programs. This algorithm is intended to work in the context of a library of background information, most of which is typically derived from previous runs of the algorithm. Due to the expressive representation system, no algorithm can infer every valid propertyso instead of proving completeness we show our algorithm’s usefulness by giving examples of properties inferred. These examples include that insertion sort returns a sorted permutation of its input, and that a clique finding program correctly returns a clique.

AIJ Journal 1992 Journal Article

Natural language syntax and first-order inference

• David A. McAllester
• Robert Givan

We have argued elsewhere that first-order inference can be made more efficient by using nonstandard syntax for first-order logic. In this paper we define a syntax for first-order logic based on the structure of natural language under Montague semantics. We show that, for a certain fairly expressive fragment of this language, satisfiability is polynomial time decidable. The polynomial time decision procedure can be used as a subroutine in general purpose inference systems and seems to be more powerful than analogous procedures based on either classical or taxonomic syntax.

AAAI Conference 1991 Conference Paper

Natural Language Based Inference Procedures Applied to Schubert’s Steamroller

• Robert Givan

We have previously argued that the syntactic structure of natural language can be exploited to construct powerful polynomial time inference procedures. This paper supports the earlier arguments by demonstrating that a natural language based polynomial time procedure can solve Schubert’ s steamroller in a single step.