Daniel Bryce

AAAI Conference 2015 Conference Paper

SMT-Based Nonlinear PDDL+ Planning

• Daniel Bryce
• Sicun Gao
• David Musliner
• Robert Goldman

PDDL+ planning involves reasoning about mixed discretecontinuous change over time. Nearly all PDDL+ planners assume that continuous change is linear. We present a new technique that accommodates nonlinear change by encoding problems as nonlinear hybrid systems. Using this encoding, we apply a Satisfiability Modulo Theories (SMT) solver to find plans. We show that it is important to use novel planningspecific heuristics for variable and value selection for SMT solving, which is inspired by recent advances in planning as SAT. We show the promising performance of the resulting solver on challenging nonlinear problems.

ICAPS Conference 2014 Conference Paper

Landmark-Based Plan Distance Measures for Diverse Planning

• Daniel Bryce

Prior approaches to generating diverse plans in domain-independent planning seek out variations on plan structure such as actions or causal links used, or states entered. Measuring such syntactic differences between plans can be misleading because syntactically different plans can be semantically identical. We develop a landmark-based plan distance measure that captures semantic differences between plans. The landmark-based distance measure focuses on the disjunctive landmarks satisfied by each plan. We develop a simple algorithm for finding diverse plans that is based upon the LAMA planner. We illustrate that, in comparison with plan distance measures, landmark-based plan distance is not as susceptible to including irrelevant or redundant actions in plans to increase plan distance. Through extensive empirical evaluation, we find that high landmark distance between plans implies high action set distance, but not vice versa. Landmark-based plan distance overcomes some of the weaknesses of syntactic plan distance measures and can be used to find plan sets that are both landmark diverse and action set diverse.

AAAI Conference 2012 Conference Paper

Evaluating Temporal Plans in Incomplete Domains

• Daniel Morwood
• Daniel Bryce

Recent work on planning in incomplete domains focuses on constructing plans that succeed despite incomplete knowledge of action preconditions and effects. As planning models become more expressive, such as in temporal planning, the types of incompleteness may not only change, but plans become more challenging to evaluate. The primary difficulty to temporal plan evaluation is accounting for temporal constraints that may not be satisfied under all interpretations of the incomplete domain. In this work, we formulate incomplete temporal plan evaluation as a generalization of the temporal consistency problem, called partial temporal consistency. We present a knowledge compilation approach that is combined with symbolic constraint propagation and model counting algorithms for counting the number of incomplete domain model interpretations under which a plan is consistent. We present an evaluation that identifies the aspects of incomplete temporal plans most impact performance.

ICAPS Conference 2011 Conference Paper

Planning and Acting in Incomplete Domains

• Christopher Weber
• Daniel Bryce

Engineering complete planning domain descriptions is often very costly because of human error or lack of domain knowl- edge. Learning complete domain descriptions is also very challenging because many features are irrelevant to achieving the goals and data may be scarce. We present a planner and agent that respectively plan and act in incomplete domains by i) synthesizing plans to avoid execution failure due to ignorance of the domain model, and ii) passively learning about the domain model during execution to improve later re-planning attempts. Our planner DeFault is the first to reason about a domain's incompleteness to avoid potential plan failure. DeFault computes failure explanations for each action and state in the plan and counts the number of interpretations of the incomplete domain where failure will occur. We show that DeFault performs best by counting prime implicants (failure diagnoses) rather than propositional models. Our agent Goalie learns about the preconditions and effects of incompletely-specified actions while monitoring its state and, in conjunction with DeFault plan failure explanations, can diagnose past and future action failures. We show that by reasoning about incompleteness (as opposed to ignoring it) Goalie fails and re-plans less and executes fewer actions.

AIJ Journal 2011 Journal Article

State agnostic planning graphs: deterministic, non-deterministic, and probabilistic planning

• Daniel Bryce
• William Cushing
• Subbarao Kambhampati

Planning graphs have been shown to be a rich source of heuristic information for many kinds of planners. In many cases, planners must compute a planning graph for each element of a set of states, and the naive technique enumerates the graphs individually. This is equivalent to solving a multiple-source shortest path problem by iterating a single-source algorithm over each source. We introduce a data-structure, the state agnostic planning graph, that directly solves the multiple-source problem for the relaxation introduced by planning graphs. The technique can also be characterized as exploiting the overlap present in sets of planning graphs. For the purpose of exposition, we first present the technique in deterministic (classical) planning to capture a set of planning graphs used in forward chaining search. A more prominent application of this technique is in conformant and conditional planning (i. e. , search in belief state space), where each search node utilizes a set of planning graphs; an optimization to exploit state overlap between belief states collapses the set of sets of planning graphs to a single set. We describe another extension in conformant probabilistic planning that reuses planning graph samples of probabilistic action outcomes across search nodes to otherwise curb the inherent prediction cost associated with handling probabilistic actions. Finally, we show how to extract a state agnostic relaxed plan that implicitly solves the relaxed planning problem in each of the planning graphs represented by the state agnostic planning graph and reduces each heuristic evaluation to counting the relevant actions in the state agnostic relaxed plan. Our experimental evaluation (using many existing International Planning Competition problems from classical and non-deterministic conformant tracks) quantifies each of these performance boosts, and demonstrates that heuristic belief state space progression planning using our technique is competitive with the state of the art.

TIST Journal 2010 Journal Article

Planning interventions in biological networks

• Daniel Bryce
• Michael Verdicchio
• Seungchan Kim

Modeling the dynamics of biological processes has recently become an important research topic in computational biology and systems engineering. One of the most important reasons to model a biological process is to enable high-throughput in-silico experiments that attempt to predict or intervene in the process. These experiments can help accelerate the design of therapies through their rapid and inexpensive replication and alteration. While some techniques exist for reasoning with biological processes, few take advantage of the flexible and scalable algorithms popular in AI research. In reasoning about interventions in biological processes, where scalability is crucial for feasible application, we apply AI planning-based search techniques and demonstrate their advantage over existing enumerative methods. We also present a novel formulation of intervention planning that relies on models that characterize and attempt to change the phenotype of a system. We study three biological systems: the yeast cell cycle, a model of the human aging process, and the Wnt5a network governing the metastasis of melanoma in humans. The contribution of our investigation is in demonstrating that: (i) prior approaches, based on dynamic programming, cannot scale as well as heuristic search, and (ii) the newly found scalability enables us to plan previously unknown sequences of interventions that reveal novel and biologically significant responses in the systems which are consistent with biological knowledge in the literature.

AAMAS Conference 2009 Conference Paper

MABLE: A Framework for Learning from Natural Instruction

• Roger Mailler
• Daniel Bryce
• Jiaying Shen
• Ciaran O'Reilly

AIJ Journal 2008 Journal Article

Sequential Monte Carlo in reachability heuristics for probabilistic planning

• Daniel Bryce
• Subbarao Kambhampati
• David E. Smith

Some of the current best conformant probabilistic planners focus on finding a fixed length plan with maximal probability. While these approaches can find optimal solutions, they often do not scale for large problems or plan lengths. As has been shown in classical planning, heuristic search outperforms bounded length search (especially when an appropriate plan length is not given a priori). The problem with applying heuristic search in probabilistic planning is that effective heuristics are as yet lacking. In this work, we apply heuristic search to conformant probabilistic planning by adapting planning graph heuristics developed for non-deterministic planning. We evaluate a straight-forward application of these planning graph techniques, which amounts to exactly computing a distribution over many relaxed planning graphs (one planning graph for each joint outcome of uncertain actions at each time step). Computing this distribution is costly, so we apply Sequential Monte Carlo (SMC) to approximate it. One important issue that we explore in this work is how to automatically determine the number of samples required for effective heuristic computation. We empirically demonstrate on several domains how our efficient, but sometimes suboptimal, approach enables our planner to solve much larger problems than an existing optimal bounded length probabilistic planner and still find reasonable quality solutions.

IJCAI Conference 2007 Conference Paper

• Daniel Bryce
• Seungchan Kim

Modeling the dynamics of cellular processes has recently become a important research area of many disciplines. One of the most important reasons to model a cellular process is to enable high-throughput in-silico experiments that attempt to predict or intervene in the process. These experiments can help accelerate the design of therapies through their cheap replication and alteration. While some techniques exist for reasoning with cellular processes, few take advantage of the flexible and scalable algorithms popularized in AI research. In this domain, where scalability is crucial for feasible application, we apply AI planning based search techniques and demonstrate their advantage over existing enumerative methods.

ICAPS Conference 2006 Conference Paper

Sequential Monte Carlo in Probabilistic Planning Reachability Heuristics

• Daniel Bryce
• Subbarao Kambhampati
• David E. Smith 0001

The current best conformant probabilistic planners encode the problem as a bounded length CSP or SAT problem. While these approaches can find optimal solutions for given plan lengths, they often do not scale for large problems or plan lengths. As has been shown in classical planning, heuristic search outperforms CSP/SAT techniques (especially when a plan length is not given a priori). The problem with applying heuristic search in probabilistic planning is that effective heuristics are as yet lacking. In this work, we apply heuristic search to conformant probabilistic planning by adapting planning graph heuristics developed for non-deterministic planning. We evaluate a straight-forward application of these planning graph techniques, which amounts to exactly computing the distribution over reachable relaxed planning graph layers. Computing these distributions is costly, so we apply Sequential Monte Carlo to approximate them. We demonstrate on several domains how our approach enables our planner to far out-scale existing (optimal) probabilistic planners and still find reasonable quality solutions.

UAI Conference 2005 Conference Paper

Cost Sensitive Reachability Heuristics for Handling State Uncertainty

• Daniel Bryce
• Subbarao Kambhampati

ICAPS Conference 2004 Conference Paper

Heuristic Guidance Measures for Conformant Planning

• Daniel Bryce
• Subbarao Kambhampati

Scaling conformant planning is a problem that has received much attention of late. Many planners solve the problem as a search in the space of belief states, and some heuristic guidance techniques have been developed to estimate the distance between belief states. We claim that heuristic techniques in the past involved an ad hoc combination of classical planning heuristics and cardinality measures. We discuss how to derive heuristics systematically, with the help of planning graphs, such that the measures reflect the reachability of relevant states within belief states. To demonstrate these ideas we show how distances between belief states can be estimated by a set of reachability heuristics. We empirically evaluate their effectiveness within a conformant regression planner named CAltAlt.