Arrow Research search

Author name cluster

Héctor Geffner

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.

8 papers
1 author row

Possible papers

8

IJCAI Conference 2009 Conference Paper

  • Blai Bonet
  • Héctor Geffner

Point-based algorithms and RTDP-Bel are approximate methods for solving POMDPs that replace the full updates of parallel value iteration by faster and more effective updates at selected beliefs. An important difference between the two methods is that the former adopt Sondik’s representation of the value function, while the latter uses a tabular representation and a discretization function. The algorithms, however, have not been compared up to now, because they target different POMDPs: discounted POMDPs on the one hand, and Goal POMDPs on the other. In this paper, we bridge this representational gap, showing how to transform discounted POMDPs into Goal POMDPs, and use the transformation to compare RTDP-Bel with point-based algorithms over the existing discounted benchmarks. The results appear to contradict the conventional wisdom in the area showing that RTDP-Bel is competitive, and sometimes superior to point-based algorithms in both quality and time.

PDF Details

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.

PDF Details

IJCAI Conference 2009 Conference Paper

  • Miquel Ramírez
  • Héctor Geffner

In this work we aim to narrow the gap between plan recognition and planning by exploiting the power and generality of recent planning algorithms for recognizing the set G∗ of goals G that explain a sequence of observations given a domain theory. After providing a crisp definition of this set, we show by means of a suitable problem transformation that a goal G belongs to G∗ if there is an action sequence π that is an optimal plan for both the goal G and the goal G extended with extra goals representing the observations. Exploiting this result, we show how the set G∗ can be computed exactly and approximately by minor modifications of existing optimal and suboptimal planning algorithms, and existing polynomial heuristics. Experiments over several domains show that the suboptimal planning algorithms and the polynomial heuristics provide good approximations of the optimal goal set G∗ while scaling up as well as state-of-the-art planning algorithms and heuristics.

PDF Details

IJCAI Conference 2009 Conference Paper

  • Alexandre Albore
  • Héctor Palacios
  • Héctor Geffner

The problem of planning in the presence of sensing has been addressed in recent years as a nondeterministic search problem in belief space. In this work, we use ideas advanced recently for compiling conformant problems into classical ones for introducing a different approach where contingent problems P are mapped into non-deterministic problems X(P) in state space. We also identify a contingent width parameter, and show that for problems P with bounded contingent width, the translation is sound, polynomial, and complete. We then solve X(P) by using a relaxation X+ (P) that is a classical planning problem. The formulation is tested experimentally over contingent benchmarks where it is shown to yield a planner that scales up better than existing contingent planners.

PDF Details

AAAI Conference 2004 Conference Paper

Branching and Pruning: An Optimal Temporal POCL Planner Based on Constraint Programming

  • Vincent Vidal
  • Héctor Geffner

A key feature of modern optimal planners such as Graphplan and Blackbox is their ability to prune large parts of the search space. Previous Partial Order Causal Link (POCL) planners provide an alternative branching scheme but lacking comparable pruning mechanisms do not perform as well. In this paper, a domain-independent formulation of temporal planning based on Constraint Programming is introduced that successfully combines a POCL branching scheme with powerful and sound pruning rules. The key novelty in the formulation is the ability to reason about supports, precedences, and causal links involving actions that are not in the plan. Experiments over a wide range of benchmarks show that the resulting optimal temporal planner is much faster than current ones and is competitive with the best parallel planners in the special case in which actions have all the same duration.

PDF Details