Omer Giménez

AIJ Journal 2012 Journal Article

The influence of k-dependence on the complexity of planning

• Omer Giménez
• Anders Jonsson

A planning problem is k-dependent if each action has at most k pre-conditions on variables unaffected by the action. This concept is of interest because k is a constant for all but a few of the current benchmark domains in planning, and is known to have implications for tractability. In this paper, we present an algorithm for solving planning problems in P ( k ), the class of k-dependent planning problems with binary variables and polytree causal graphs. We prove that our algorithm runs in polynomial time when k is a fixed constant. If, in addition, the causal graph has bounded depth, we show that plan generation is linear in the size of the input. Although these contributions are theoretical due to the limited scope of the class P ( k ), suitable reductions from more complex planning problems to P ( k ) could potentially give rise to fast domain-independent heuristics.

SODA Conference 2012 Conference Paper

The maximum degree of random planar graphs

• Michael Drmota
• Omer Giménez
• Marc Noy
• Konstantinos Panagiotou
• Angelika Steger

STOC Conference 2010 Conference Paper

The HOM problem is decidable

• Guillem Godoy
• Omer Giménez
• Lander Ramos
• Carme Àlvarez

ICAPS Conference 2009 Conference Paper

The Influence of k- Dependence on the Complexity of Planning

• Omer Giménez
• Anders Jonsson 0001

A planning problem is k-dependent if each action has at most k pre-conditions on variables unaffected by the action. This concept is well-founded since k is a constant for all but a few of the standard planning domains, and is known to have implications for tractability. In this paper, we present several new complexity results for P(k), the class of k-dependent planning problems with binary variables and polytree causal graphs. The problem of plan generation for P(k) is equivalent to determining how many times each variable can change. Using this fact, we present a polytime plan generation algorithm for P(2) and P(3). For constant k > 3, we introduce and use the notion of a cover to find conditions under which plan generation for P(k) is polynomial.

ICAPS Conference 2008 Conference Paper

Causal Graphs and Structurally Restricted Planning

• Hubie Chen
• Omer Giménez

The causal graph is a directed graph that describes the variable dependencies present in a planning instance. A number of papers have studied the causal graph in both practical and theoretical settings. In this work, we systematically study the complexity of planning restricted by the causal graph. In particular, any set of causal graphs gives rise to a subcase of the planning problem. We give a complete classification theorem on causal graphs, showing that a set of graphs is either polynomial-time tractable, or is not polynomial-time tractable unless an established complexity-theoretic assumption fails; our theorem describes which graph sets correspond to each of the two cases. We also give a classification theorem for the case of reversible planning, and discuss the general direction of structurally restricted planning.

ICAPS Conference 2008 Conference Paper

In Search of the Tractability Boundary of Planning Problems

• Omer Giménez
• Anders Jonsson 0001

Recently, considerable focus has been given to the problem of determining the boundary between tractable and intractable planning problems. To this end, we present complexity results for two classes of planning problems from the literature. First, we show that approximating a solution to a planning problem in the class 3S to within polynomial factors is NP-hard. We also show that plan existence is NP-hard for planning problems with chain causal graphs and variables with domain size at most 7. In addition to the immediate implications, our results provide some insight into what makes some planning problems intractable.

ICAPS Conference 2007 Conference Paper

Act Local, Think Global: Width Notions for Tractable Planning

• Hubie Chen
• Omer Giménez

Many of the benchmark domains in AI planning are tractable on an individual basis. In this paper, we seek a theoretical, domain-independent explanation for their tractability. We present a family of structural conditions that both imply tractability and capture some of the established benchmark domains. These structural conditions are, roughly speaking, based on measures of how many variables need to be changed in order to move a state closer to a goal state.

ICAPS Conference 2007 Conference Paper

On the Hardness of Planning Problems with Simple Causal Graphs

• Omer Giménez
• Anders Jonsson 0001

We present three new complexity results for classes of planning problems with simple causal graphs. First, we describe a polynomial time algorithm that uses macros to generate plans for a class of planning problems with binary state variables and acyclic causal graphs. This implies that plan generation may not be intractable just because a planning problem has exponential length solution. We also prove that the problem of plan existence for planning problems with multi-valued variables and chain causal graphs is NP-hard. Finally, we show that plan existence for planning problems with binary state variables and polytree causal graphs is NP-complete.