Emil Keyder

AAAI Conference 2022 Conference Paper

A* Search and Bound-Sensitive Heuristics for Oversubscription Planning

• Michael Katz
• Emil Keyder

Oversubscription planning (OSP) is the problem of finding plans that maximize the utility value of their end state while staying within a specified cost bound. Recently, it has been shown that OSP problems can be reformulated as classical planning problems with multiple cost functions but no utilities. Here we take advantage of this reformulation to show that OSP problems can be solved optimally using the A∗ search algorithm, in contrast to previous approaches that have used variations on branch-and-bound search. This allows many powerful techniques developed for classical planning to be applied to OSP problems. We also introduce novel bound-sensitive heuristics, which are able to reason about the primary cost of a solution while taking into account secondary cost functions and bounds, to provide superior guidance compared to heuristics that do not take these bounds into account. We propose two such bound-sensitive variants of existing classical planning heuristics, and show experimentally that the resulting search is significantly more informed than with comparable heuristics that do not consider bounds.

SoCS Conference 2022 Conference Paper

Trajectory Constraint Heuristics for Optimal Probabilistic Planning

• John R. Peterson
• Anagha Kulkarni 0005
• Emil Keyder
• Joseph Kim
• Shlomo Zilberstein

Search algorithms such as LAO* and LRTDP coupled with admissible heuristics are widely used methods for optimal probabilistic planning. Their effectiveness depends on the degree to which heuristics are able to approximate the optimal cost of a state. Most common domain-independent heuristics, however, rely on determinization, and ignore the probabilities associated with different effects of actions. Here, we present a method for decomposing a probabilistic planning problem into subproblems by constraining possible action outcomes. Admissible heuristics evaluated for each subproblem can then be combined via a weighted sum to obtain an admissible heuristic for the original problem that takes into account a limited amount of probabilistic information. We use this approach to derive new admissible heuristics for probabilistic planning, and show that for some problems they are significantly more informative than existing heuristics, leading to up to an order of magnitude speedups in the time to converge to an optimal policy.

ICAPS Conference 2019 Conference Paper

Oversubscription Planning as Classical Planning with Multiple Cost Functions

• Michael Katz 0001
• Emil Keyder
• Dominik Winterer
• Florian Pommerening

The aim of classical planning is to minimize the summed cost of operators among those plans that achieve a fixed set of goals. Oversubscription planning (OSP), on the other hand, seeks to maximize the utility of the set of facts achieved by a plan, while keeping the cost of the plan at or below some specified bound. Here, we investigate the use of reformulations that yield planning problems with two separate cost functions, but no utilities, for solving OSP tasks. Such reformulations have also been proposed in the context of netbenefit planning, where the planner tries to maximize the difference between the utility achieved and the cost of the plan. One of our reformulations is adapted directly from that setting, while the other is novel. In both cases, they allow for easy adaptation of existing classical planning heuristics to the OSP problem within a simple branch and bound search. We validate our approach using state of the art admissible heuristics in this framework, and report our results.

AAAI Conference 2012 Conference Paper

Semi-Relaxed Plan Heuristics

• Emil Keyder
• Joerg Hoffmann
• Patrik Haslum

The currently dominant approach to domain-independent planning is planning as heuristic search, with most successful planning heuristics being based on solutions to delete-relaxed versions of planning problems, in which the negative effects of actions are ignored. We introduce a principled, flexible, and practical technique for augmenting delete-relaxed tasks with a limited amount of delete information, by introducing special fluents that explicitly represent conjunctions of fluents in the original planning task. Differently from previous work, conditional effects are used to limit the growth of the task to be linear in the number of such conjunctions, making its use for obtaining heuristic functions feasible. The resulting heuristics are empirically evaluated, and shown to be sometimes much more informative than standard delete-relaxation heuristics. 1

AAAI Conference 2012 Conference Paper

Structural Patterns Beyond Forks: Extending the Complexity Boundaries of Classical Planning

• Michael Katz
• Emil Keyder

Tractability analysis in terms of the causal graphs of planning problems has emerged as an important area of research in recent years, leading to new methods for the derivation of domain-independent heuristics (Katz and Domshlak 2010). Here we continue this work, extending our knowledge of the frontier between tractable and NP-complete fragments. We close some gaps left in previous work, and introduce novel causal graph fragments that we call the hourglass and semifork, for which under certain additional assumptions optimal planning is in P. We show that relaxing any one of the restrictions required for this tractability leads to NP-complete problems. Our results are of both theoretical and practical interest, as these fragments can be used in existing frameworks to derive new abstraction heuristics. Before they can be used, however, a number of practical issues must be addressed. We discuss these issues and propose some solutions.

ECAI Conference 2010 Conference Paper

Sound and Complete Landmarks for And/Or Graphs

• Emil Keyder
• Silvia Richter
• Malte Helmert

Landmarks for a planning problem are subgoals that are necessarily made true at some point in the execution of any plan. Since verifying that a fact is a landmark is PSPACE-complete, earlier approaches have focused on finding landmarks for the delete relaxation Π +. Furthermore, some of these approaches have approximated this set of landmarks, although it has been shown that the complete set of causal delete-relaxation landmarks can be identified in polynomial time by a simple procedure over the relaxed planning graph. Here, we give a declarative characterisation of this set of landmarks and show that the procedure computes the landmarks described by our characterisation. Building on this, we observe that the procedure can be applied to any delete-relaxation problem and take advantage of a recent compilation of the m-relaxation of a problem into a problem with no delete effects to extract landmarks that take into account delete effects in the original problem. We demonstrate that this approach finds strictly more causal landmarks than previous approaches and discuss the relationship between increased computational effort and experimental performance, using these landmarks in a recently proposed admissible landmark-counting heuristic.

IJCAI Conference 2009 Conference Paper

• Emil Keyder
• Héctor Geffner

Heuristic search using heuristics extracted from the delete relaxation is one of the most effective methods in planning. Since finding the optimal solution of the delete relaxation is intractable, various heuristics introduce independence assumptions, the implications of which are not yet fully understood. Here we use concepts from graph theory to show that in problems with unary action preconditions, the delete relaxation is closely related to the Steiner Tree problem, and that the independence assumption for the set of goals results in a tree-of-shortestpaths approximation. We analyze the limitations of this approximation and develop an alternative method for computing relaxed plans that addresses them. The method is used to guide a greedy best- first search, where it is shown to improve plan quality and coverage over several benchmark domains.

ECAI Conference 2008 Conference Paper

Heuristics for Planning with Action Costs Revisited

• Emil Keyder
• Hector Geffner

We introduce a simple variation of the additive heuristic used in the HSP planner that combines the benefits of the original additive heuristic, namely its mathematical formulation and its ability to handle non-uniform action costs, with the benefits of the relaxed planning graph heuristic used in FF, namely its compatibility with the highly effective enforced hill climbing search along with its ability to identify helpful actions. We implement a planner similar to FF except that it uses relaxed plans obtained from the additive heuristic rather than those obtained from the relaxed planning graph. We then evaluate the resulting planner in problems where action costs are not uniform and plans with smaller overall cost (as opposed to length) are preferred, where it is shown to compare well with cost-sensitive planners such as SGPlan, Sapa, and LPG. We also consider a further variation of the additive heuristic, where symbolic labels representing action sets are propagated rather than numbers, and show that this scheme can be further developed to construct heuristics that can take delete-information into account.