Carmel Domshlak

IJCAI Conference 2016 Conference Paper

Blind Search for Atari-Like Online Planning Revisited

• Alexander Shleyfman
• Alexander Tuisov
• Carmel Domshlak

Similarly to the classical AI planning, the Atari 2600 games supported in the Arcade Learning Environment all feature a fully observable (RAM) state and actions that have deterministic effect. At the same time, the problems in ALE are given only implicitly, via a simulator, a priori precluding exploiting most of the modern classical planning techniques. Despite that, Lipovetzky et al. [2015] recently showed how online planning for Atari-like problems can be effectively addressed using IW(i), a blind state-space search algorithm that employs a certain form of structural similarity-based pruning. We show that the effectiveness of the blind state-space search for Atari-like online planning can be pushed even further by focusing the search using both structural state similarity and the relative myopic value of the states. We also show that the planning effectiveness can be further improved by considering online planning for the Atari games as a multiarmed bandit style competition between the various actions available at the state planned for, and not purely as a classical planning style action sequence optimization problem.

JAIR Journal 2015 Journal Article

Deterministic Oversubscription Planning as Heuristic Search: Abstractions and Reformulations

• Carmel Domshlak
• Vitaly Mirkis

While in classical planning the objective is to achieve one of the equally attractive goal states at as low total action cost as possible, the objective in deterministic oversubscription planning (OSP) is to achieve an as valuable as possible subset of goals within a fixed allowance of the total action cost. Although numerous applications in various fields share the latter objective, no substantial algorithmic advances have been made in deterministic OSP. Tracing the key sources of progress in classical planning, we identify a severe lack of effective domain-independent approximations for OSP. With our focus here on optimal planning, our goal is to bridge this gap. Two classes of approximation techniques have been found especially useful in the context of optimal classical planning: those based on state-space abstractions and those based on logical landmarks for goal reachability. The question we study here is whether some similar-in-spirit, yet possibly mathematically different, approximation techniques can be developed for OSP. In the context of abstractions, we define the notion of additive abstractions for OSP, study the complexity of deriving effective abstractions from a rich space of hypotheses, and reveal some substantial, empirically relevant islands of tractability. In the context of landmarks, we show how standard goal-reachability landmarks of certain classical planning tasks can be compiled into the OSP task of interest, resulting in an equivalent OSP task with a lower cost allowance, and thus with a smaller search space. Our empirical evaluation confirms the effectiveness of the proposed techniques, and opens a wide gate for further developments in oversubscription planning.

SoCS Conference 2015 Conference Paper

From Fork Decoupling to Star-Topology Decoupling

• Daniel Gnad 0001
• Jörg Hoffmann 0001
• Carmel Domshlak

Fork decoupling is a recent approach to exploiting problem structure in state space search. The problem is assumed to take the form of a fork, where a single (large) center component provides preconditions for several (small) leaf components. The leaves are then conditionally independent in the sense that, given a fixed center path p, the compliant leaf moves - those leaf moves enabled by the preconditions supplied along p - can be scheduled independently for each leaf. Fork-decoupled state space search exploits this through conducting a regular search over center paths, augmented with maintenance of the compliant paths for each leaf individually. We herein show that the same ideas apply to much more general star-topology structures, where leaves may supply preconditions for the center, and actions may affect several leaves simultaneously as long as they also affect the center. Our empirical evaluation in planning, super-imposing star topologies by automatically grouping the state variables into suitable components, shows the merits of the approach.

AAAI Conference 2015 Conference Paper

On Interruptible Pure Exploration in Multi-Armed Bandits

• Alexander Shleyfman
• Antonín Komenda
• Carmel Domshlak

Interruptible pure exploration in multi-armed bandits (MABs) is a key component of Monte-Carlo tree search algorithms for sequential decision problems. We introduce Discriminative Bucketing (DB), a novel family of strategies for pure exploration in MABs, which allows for adapting recent advances in non-interruptible strategies to the interruptible setting, while guaranteeing exponential-rate performance improvement over time. Our experimental evaluation demonstrates that the corresponding instances of DB favorably compete both with the currently popular strategies UCB1 and ε-Greedy, as well as with the conservative uniform sampling.

AIJ Journal 2015 Journal Article

Red–black planning: A new systematic approach to partial delete relaxation

• Carmel Domshlak
• Jörg Hoffmann
• Michael Katz

To date, delete relaxation underlies some of the most effective heuristics for deterministic planning. Despite its success, however, delete relaxation has significant pitfalls in many important classes of planning domains, and it has been a challenge from the outset to devise heuristics that take some deletes into account. We herein devise an elegant and simple method for doing just that. In the context of finite-domain state variables, we define red variables to take the relaxed semantics, in which they accumulate their values rather than switching between them, as opposed to black variables that take the regular semantics. Red–black planning then interpolates between relaxed planning and regular planning simply by allowing a subset of variables to be painted red. We investigate the tractability region of red–black planning, extending Chen and Giménez' characterization theorems for regular planning to the more general red–black setting. In particular, we identify significant islands of tractable red–black planning, use them to design practical heuristic functions, and experiment with a range of “painting strategies” for automatically choosing the red variables. Our experiments show that these new heuristic functions can improve significantly on the state of the art in satisficing planning. 1

ECAI Conference 2014 Conference Paper

Landmarks in Oversubscription Planning

• Vitaly Mirkis
• Carmel Domshlak

In the basic setup of oversubscription planning (OSP), the objective is to achieve an as valuable as possible subset of goals within a fixed allowance of the total action cost [32]. Continuing from the recent successes in exploiting logical goal-reachability landmarks in classical planning, we develop a framework for exploiting such landmarks in heuristic-search OSP. We show how standard landmarks of certain classical planning tasks can be compiled into the OSP task of interest, resulting in an equivalent OSP task with a lower budget, and thus with a smaller search space. We then show how such landmark-based task enrichment can be combined in a mutually stratifying way with the BFBB search used for OSP planning. Our empirical evaluation confirms the effectiveness of the proposed landmark-based budget reduction scheme.

ECAI Conference 2014 Conference Paper

Monte-Carlo Tree Search: To MC or to DP?

• Zohar Feldman
• Carmel Domshlak

State-of-the-art Monte-Carlo tree search algorithms can be parametrized with any of the two information updating procedures: MC-backup and DP-backup. The dynamics of these two procedures is very different, and so far, their relative pros and cons have been poorly understood. Formally analyzing the dependency of MC- and DP-backups on various MDP parameters, we reveal numerous important issues that get hidden by the worst-case bounds on the algorithm performance, and reconfirm these findings by a systematic experimental test.

ECAI Conference 2014 Conference Paper

On Combinatorial Actions and CMABs with Linear Side Information

• Alexander Shleyfman
• Antonín Komenda
• Carmel Domshlak

Online planning algorithms are typically a tool of choice for dealing with sequential decision problems in combinatorial search spaces. Many such problems, however, also exhibit combinatorial actions, yet standard planning algorithms do not cope well with this type of "the curse of dimensionality". Following a recently opened line of related work on combinatorial multi-armed bandit (CMAB) problems, we propose a novel CMAB planning scheme, as well as two specific instances of this scheme, dedicated to exploiting what is called linear side information. Using a representative strategy game as a benchmark, we show that the resulting algorithms very favorably compete with the state-of-the-art.

ICAPS Conference 2014 Conference Paper

On MABs and Separation of Concerns in Monte-Carlo Planning for MDPs

• Zohar Feldman
• Carmel Domshlak

Linking online planning for MDPs with their special case of stochastic multi-armed bandit problems, we analyze three state-of-the-art Monte-Carlo tree search al-gorithms: UCT, BRUE, and MaxUCT. Using the outcome, we (i) introduce two new MCTS algorithms, MaxBRUE, which combines uniform sampling with Bellman backups, and MpaUCT, which combines UCB1with a novel backup procedure, (ii) analyze them formally and empirically, and (iii) show how MCTS algorithms can be further stratified by an exploration control mechanism that improves their empirical performance without harming the formal guarantees.

ICAPS Conference 2014 Conference Paper

The Complexity of Optimal Monotonic Planning: The Bad, The Good, and The Causal Graph

• Carmel Domshlak
• Anton Nazarenko

For almost two decades, monotonic, or ``delete free, '' relaxation has been one of the key auxiliary tools in the practice of domain-independent deterministic planning. In the particular contexts of both satisficing and optimal planning, it underlies most state-of-the-art heuristic functions. While satisficing planning for monotonic tasks is polynomial-time, optimal planning for monotonic tasks is NP-equivalent. We took a step towards a fine-grained classification of worst-case time complexity of optimal monotonic planning, with a focus on ``what gets harder" and ``what gets easier" when switching from optimal planning to optimal relaxed planning, in the context of finite-domain planning task representations.

ICAPS Conference 2013 Conference Paper

Abstractions for Oversubscription Planning

• Vitaly Mirkis
• Carmel Domshlak

In deterministic OSP, the objective is to achieve an as valuable as possible subset of goals within a fixed allowance of the total action cost. Although numerous applications in various fields share this objective, no substantial algorithmic advances have been made beyond the very special settings of net-benefit optimization. Tracing the key sources of progress in classical planning, we identify a severe lack of domain-independent approximations for OSP, and start with investigating the prospects of abstraction approximations for this problem. In particular, we define the notion of additive abstractions for OSP, study the complexity of deriving effective abstractions from a rich space of hypotheses, and reveal some substantial, empirically relevant islands of tractability.

AAAI Conference 2013 Conference Paper

Data-Parallel Computing Meets STRIPS

• Erez Karpas
• Tomer Sagi
• Carmel Domshlak
• Avigdor Gal
• Avi Mendelson
• Moshe Tennenholtz

ICAPS Conference 2013 Conference Paper

Fault Tolerant Planning: Complexity and Compilation

• Carmel Domshlak

In the context of modeling and reasoning about agent actions, contingent and classical planning can often be respectively seen as adopting ``extreme pessimism'' and ``extreme optimism'' about the action outcomes. For many everyday scenarios of human reasoning (and thus for many types of autonomous systems), both these approaches are just too extreme. Following Jensen, Veloso, and Bryant (2004), we examine a planning model that interpolates between classical and contingent planning via tolerance to arbitrary k faults occurring during plan execution. We show that an important fragment of this fault tolerant planning (FT-planning) exhibits both an appealing solution structure, as well as appealing worst-case time-complexity properties. We also show that such FT-planning tasks can be efficiently compiled into classical planning as long as the number of possible faults per operator is bounded by a constant, and we show that this compilation can be attractive in practice.

UAI Conference 2013 Conference Paper

Monte-Carlo Planning: Theoretically Fast Convergence Meets Practical Efficiency

• Zohar Feldman
• Carmel Domshlak

Popular Monte-Carlo tree search (MCTS) algorithms for online planning, such as ε-greedy tree search and UCT, aim at rapidly identifying a reasonably good action, but provide rather poor worst-case guarantees on performance improvement over time. In contrast, a recently introduced MCTS algorithm BRUE guarantees exponential-rate improvement over time, yet it is not geared towards identifying reasonably good choices right at the go. We take a stand on the individual strengths of these two classes of algorithms, and show how they can be effectively connected. We then rationalize a principle of “selective tree expansion”, and suggest a concrete implementation of this principle within MCTS. The resulting algorithms favorably compete with other MCTS algorithms under short planning times, while preserving the attractive convergence properties of BRUE.

AIJ Journal 2013 Journal Article

On the complexity of planning for agent teams and its implications for single agent planning

• Ronen I. Brafman
• Carmel Domshlak

If the complexity of planning for a single agent is described by some function f of the input, how much more difficult is it to plan for a team of n cooperating agents? If these agents are completely independent, we can simply solve n single agent problems, scaling linearly with the number of agents. But if all the agents interact tightly, we really need to solve a single problem that is n times larger, which could be exponentially (in n) harder to solve. Is a more general characterization possible? To formulate this question precisely, we minimally extend the standard STRIPS model to describe multi-agent planning problems. Then, we identify two problem parameters that help us answer our question. The first parameter is independent of the precise task the multi-agent system should plan for, and it captures the structure of the possible direct interactions between the agents via the tree-width of a graph induced by the team. The second parameter is task-dependent, and it captures the minimal number of interactions by the “most interacting” agent in the team that is needed to solve the problem. We show that multi-agent planning problems can be solved in time exponential only in these parameters. Thus, when these parameters are bounded, the complexity scales only polynomially in the size of the agent team. These results also have direct implications for the single-agent case: by casting single-agent planning tasks as multi-agent planning tasks, we can devise novel methods for decomposition-based planning for single agents. We analyze one such method, and use the techniques developed to provide some of the strongest tractability results for classical single-agent planning to date.

AAAI Conference 2013 Conference Paper

Red-Black Relaxed Plan Heuristics

• Michael Katz
• Joerg Hoffmann
• Carmel Domshlak

Despite its success, the delete relaxation has significant pitfalls. Recent work has devised the red-black planning framework, where red variables take the relaxed semantics (accumulating their values), while black variables take the regular semantics. Provided the red variables are chosen so that redblack plan generation is tractable, one can generate such a plan for every search state, and take its length as the heuristic distance estimate. Previous results were not suitable for this purpose because they identified tractable fragments for redblack plan existence, as opposed to red-black plan generation. We identify a new fragment of red-black planning, that fixes this issue. We devise machinery to efficiently generate redblack plans, and to automatically select the red variables. Experiments show that the resulting heuristics can significantly improve over standard delete relaxation heuristics.

ICAPS Conference 2013 Conference Paper

Symmetry Breaking: Satisficing Planning and Landmark Heuristics

• Carmel Domshlak
• Michael Katz 0001
• Alexander Shleyfman

Searching for computational tools that can further push the boundary of satisficing planning, we show that reasoning about state-space symmetries can substantially improve even the most effective heuristic-search satisficing planners, with respect to all standard performance measures. The improvement comes from the state-space pruning, as well as from transparent cost-to-state updates and heuristic enhancement by information obtained during the search at different symmetric states.

SoCS Conference 2013 Conference Paper

To UCT, or not to UCT? (Position Paper)

• Carmel Domshlak
• Zohar Feldman

Monte-Carlo search is successfully used in simulation-based planning for various large-scale sequential decision problems, and the UCT algorithm seems to be the choice in most (if not all) such recent success stories. Based on some recent discoveries in theory and empirical analysis of Monte-Carlo search, here we argue that, if online sequential decision making is your problem, and Monte-Carlo tree search is your way to go, then UCT is unlikely to be the best fit for your needs.

ICAPS Conference 2013 Conference Paper

Who Said We Need to Relax All Variables?

• Michael Katz 0001
• Jörg Hoffmann 0001
• Carmel Domshlak

Despite its success in both satisficing and optimal planning, thedelete relaxation has significant pitfalls in many important classesof planning domains, and it has been a challenge from the outset todevise heuristics that take some deletes into account. Weherein devise an elegant and simple method for doing just that. In thecontext of finite-domain state variables, we define red variables to take the relaxed semantics, in which they accumulate their values rather than switching between them, as opposed to black variables that take the regular semantics. Red-black planning then interpolates between relaxed planning and regular planning simply by allowing a subset of variables to be painted red. Of course, this relaxation is useful as a basis for devising heuristic functions only if the resulting red-black planning task is polynomial-time solvable. We herein investigate the tractability region of red-black planning, extending Chen and Gimenez' characterization theorems for regular planning to the more generalred-black setting. In particular, we identify significant islands of tractable red-black planning, opening the road to the efficient computation of very powerful heuristics.

ICAPS Conference 2012 Conference Paper

Enhanced Symmetry Breaking in Cost-Optimal Planning as Forward Search

• Carmel Domshlak
• Michael Katz 0001
• Alexander Shleyfman

The paper illustrates a novel approach to conformant planning using classical planners. The approach relies on two core ideas developed to deal with incomplete information in the initial situation: the use of a classical planner to solve non-classical planning problems, and the reduction of the size of the initial belief state. Differently from previous uses of classical planners to solve non-classical planning problems, the approach proposed in this paper creates a valid plan from a possible plan---by inserting actions into the possible plan and maintaining only one level of non-deterministic choice (i. e. , the initial plan being modified). The algorithm can be instantiated with different classical planners---the paper presents the GC[LAMA] implementation, whose classical planner is LAMA. We investigate properties of the approach, including conditions for completeness. GC[LAMA] is empirically evaluated against state-of-the-art conformant planners, using benchmarks from the literature. The experimental results show that GC[LAMA] is superior to other planners, in both performance and scalability. GC[LAMA] is the only planner that can solve the largest instances from several domains. The paper investigates the reasons behind the good performance and the challenges encountered in GC[LAMA].

AIJ Journal 2012 Journal Article

Landmark-enhanced abstraction heuristics

• Carmel Domshlak
• Michael Katz
• Sagi Lefler

Abstractions and landmarks are two of the key mechanisms for devising admissible heuristics for domain-independent planning. Here we aim at combining them by integrating landmark information into abstractions. We propose a concrete scheme for compiling landmarks into the problem specification. This scheme, which preserves all reachable properties of the original problem, is especially suited to implicit abstraction heuristics. Our formal and empirical analysis shows that landmark information can substantially improve the quality of heuristic estimates.

ICAPS Conference 2012 Conference Paper

Optimal Search with Inadmissible Heuristics

• Erez Karpas
• Carmel Domshlak

Considering cost-optimal heuristic search, we introduce the notion of global admissibility of a heuristic, a property weaker than standard admissibility, yet sufficient for guaranteeing solution optimality within forward search. We describe a concrete approach for creating globally admissible heuristics for domain independent planning; it is based on exploiting information gradually gathered by the search via a new form of reasoning about what we call existential optimal-plan landmarks. We evaluate our approach on some state-of-the-art heuristic search tools for cost-optimal planning, and discuss the results of this evaluation.

AAAI Conference 2011 Conference Paper

Planning for Operational Control Systems with Predictable Exogenous Events

• Ronen Brafman
• Carmel Domshlak
• Yagil Engel
• Zohar Feldman

Various operational control systems (OCS) are naturally modeled as Markov Decision Processes. OCS often enjoy access to predictions of future events that have substantial impact on their operations. For example, reliable forecasts of extreme weather conditions are widely available, and such events can affect typical request patterns for customer response management systems, the flight and service time of airplanes, or the supply and demand patterns for electricity. The space of exogenous events impacting OCS can be very large, prohibiting their modeling within the MDP; moreover, for many of these exogenous events there is no useful predictive, probabilistic model. Realtime predictions, however, possibly with a short lead-time, are often available. In this work we motivate a model which combines offline MDP in- finite horizon planning with realtime adjustments given specific predictions of future exogenous events, and suggest a framework in which such predictions are captured and trigger real-time planning problems. We propose a number of variants of existing MDP solution algorithms, adapted to this context, and evaluate them empirically.

AIJ Journal 2011 Journal Article

Preferences in AI: An overview

• Carmel Domshlak
• Eyke Hüllermeier
• Souhila Kaci
• Henri Prade

This editorial of the special issue “Representing, Processing, and Learning Preferences: Theoretical and Practical Challenges” surveys past and ongoing research on preferences in AI, including references and pointers to the literature. It covers approaches to representation, reasoning and learning of preferences. Methods in AI are contrasted with those in related areas, such as operations research and databases. Finally, we also give a brief introduction to the contents of the special issue.

AAMAS Conference 2010 Conference Paper

A General, Fully Distributed Multi-Agent Planning Algorithm

• Raz Nissim
• Ronen Brafman
• Carmel Domshlak

We present a fully distributed multi-agent planning algorithm. Our methodology uses distributed constraint satisfaction tocoordinate between agents, and local planning to ensure theconsistency of these coordination points. To solve the distributedCSP efficiently, we must modify existing methods to takeadvantage of the structure of the underlying planning problem. Inmulti-agent planning domains with limited agent interaction, ouralgorithm empirically shows scalability beyond state of the artcentralized solvers. Our work also provides a novel, real-worldsetting for testing and evaluating distributed constraint satisfactionalgorithms in structured domains and illustrates how existingtechniques can be altered to address such structure.

AIJ Journal 2010 Journal Article

Optimal admissible composition of abstraction heuristics

• Michael Katz
• Carmel Domshlak

Additive ensembles of admissible heuristics constitute the most general form of exploiting the individual strengths of numerous admissible heuristics in optimal planning. However, the same set of heuristics can be additively composed in infinitely many ways and the quality of the resulting heuristic estimate depends directly on the choice of the composition. Focusing on abstraction heuristics, we describe a procedure that takes a deterministic planning problem, a forward-search state, and a set of abstraction-based admissible heuristics, and derives an optimal additive composition of these heuristics with respect to the given state. Most importantly, we show that this procedure is polynomial-time for arbitrary sets of all abstraction heuristics with which we are acquainted, including explicit abstractions such as pattern databases (regular or constrained) and merge-and-shrink, and implicit abstractions such as fork-decomposition and abstractions based on tractable constraint optimization over tree-shaped constraint networks.

AAAI Conference 2010 Conference Paper

To Max or Not to Max: Online Learning for Speeding Up Optimal Planning

• Carmel Domshlak
• Erez Karpas
• Shaul Markovitch

It is well known that there cannot be a single “best” heuristic for optimal planning in general. One way of overcoming this is by combining admissible heuristics (e. g. by using their maximum), which requires computing numerous heuristic estimates at each state. However, there is a tradeoff between the time spent on computing these heuristic estimates for each state, and the time saved by reducing the number of expanded states. We present a novel method that reduces the cost of combining admissible heuristics for optimal search, while maintaining its benefits. Based on an idealized search space model, we formulate a decision rule for choosing the best heuristic to compute at each state. We then present an active online learning approach for that decision rule, and employ the learned model to decide which heuristic to compute at each state. We evaluate this technique empirically, and show that it substantially outperforms each of the individual heuristics that were used, as well as their regular maximum.

AAAI Conference 2010 Conference Paper

Transferable Utility Planning Games

• Ronen Brafman
• Carmel Domshlak
• Yagil Engel
• Moshe Tennenholtz

Connecting between standard AI planning constructs and a classical cooperative model of transferable-utility coalition games, we introduce the notion of transferable-utility (TU) planning games. The key representational property of these games is that coalitions are valued implicitly based on their ability to carry out efficient joint plans. On the side of the expressiveness, we show that existing succinct representations of monotonic TU games can be efficiently compiled into TU planning games. On the side of computation, TU planning games allow us to provide some of the strongest to date tractability results for core-existence and core-membership queries in succinct TU coalition games.

ICAPS Conference 2010 Conference Paper

When Abstractions Met Landmarks

• Carmel Domshlak
• Michael Katz 0001
• Sagi Lefler

Abstractions and landmarks are two powerful mechanisms for devising admissible heuristics for classical planning. Here we aim at putting them together by integrating landmark information into abstractions, and propose a concrete realization of this direction suitable for structural-pattern abstractions, as well as for other abstraction heuristics. Our empirical evaluation shows that landmark information can substantially improve the quality of abstraction heuristic estimates.

IJCAI Conference 2009 Conference Paper

• Erez Karpas
• Carmel Domshlak

Planning landmarks are facts that must be true at some point in every solution plan. Previous work has very successfully exploited planning landmarks in satisficing (non-optimal) planning. We propose a methodology for deriving admissible heuristic estimates for cost-optimal planning from a set of planning landmarks. The resulting heuristics fall into a novel class of multi-path dependent heuristics, and we present a simple best-first search procedure exploiting such heuristics. Our empirical evaluation shows that this framework favorably competes with the state-of-the-art of cost-optimal heuristic search.

IJCAI Conference 2009 Conference Paper

• Ronen I. Brafman
• Carmel Domshlak
• Yagil Engel
• Moshe Tennenholtz

We introduce planning games, a study of interactions of self-motivated agents in automated planning settings. Planning games extend STRIPS-like models of single-agent planning to systems of multiple self-interested agents, providing a rich class of structured games that capture subtle forms of local interactions. We consider two basic models of planning games and adapt game-theoretic solution concepts to these models. In both models, agents may need to cooperate in order to achieve their goals, but are assumed to do so only in order to increase their net benefit. For each model we study the computational problem of finding a stable solution and provide efficient algorithms for systems exhibiting acyclic interaction structure.

ICAPS Conference 2009 Conference Paper

Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?

• Malte Helmert
• Carmel Domshlak

Current heuristic estimators for classical domain-independent planning are usually based on one of four ideas: delete relaxations, critical paths, abstractions, and, most recently, landmarks. Previously, these different ideas for deriving heuristic functions were largely unconnected. We prove that admissible heuristics based on these ideas are in fact very closely related. Exploiting this relationship, we introduce a new admissible heuristic called the landmark cut heuristic, which compares favourably with the state of the art in terms of heuristic accuracy and overall performance.

ICAPS Conference 2009 Conference Paper

Structural-Pattern Databases

• Michael Katz 0001
• Carmel Domshlak

Explicit abstraction heuristics, notably pattern-database and merge-and-shrink heuristics, are employed by some state-of-the-art optimal heuristic-search planners. The major limitation of these abstraction heuristics is that the size of the abstract space has to be bounded by a (large) constant. Targeting this issue, Katz and Domshlak (2008b) introduced structural, and in particular fork-decomposition, abstractions, in which the planning task is abstracted by an instance of a tractable fragment of optimal planning. At first view, however, the lunch was not free. Some of the power of the explicit abstraction heuristics comes from pre-computing the heuristic function offline, and then determine h(s) for each evaluated state s by a very fast lookup in a "database. " In contrast, fork-decomposition offer a poly-time, yet far from being fast, computation. In this contribution, we show that the time-per-node complexity bottleneck of the fork-decomposition heuristics can be successfully overcome. Specifically, we show that an equivalent of the explicit abstractions' notion of "database" exists for the fork-decomposition abstractions as well, and this despite of their exponential-size abstract spaces. Experimentally, we show that heuristic search with such "databased" fork-decomposition heuristics favorably competes with the state-of-the-art of optimal planning.

ICAPS Conference 2008 Conference Paper

From One to Many: Planning for Loosely Coupled Multi-Agent Systems

• Ronen I. Brafman
• Carmel Domshlak

Loosely coupled multi-agent systems are perceived as easier to plan for because they require less coordination between agent sub-plans. In this paper we set out to formalize this intuition. We establish an upper bound on the complexity of multi-agent planning problems that depends exponentially on two parameters quantifying the level of agents' coupling, and on these parameters only. The first parameter is problem-independent, and it measures the inherent level of coupling within the system. The second is problem-specific and it has to do with the minmax number of action-commitments per agent required to solve the problem. Most importantly, the direct dependence on the number of agents, on the overall size of the problem, and on the length of the agents' plans, is only polynomial. This result is obtained using a new algorithmic methodology which we call "planning as CSP+planning". We believe this to be one of the first formal results to both quantify the notion of agents' coupling, and to demonstrate a multi-agent planning algorithm that, for fixed coupling levels, scales polynomially with the size of the problem.

AIJ Journal 2008 Journal Article

Graphically structured value-function compilation

• Ronen I. Brafman
• Carmel Domshlak

Classical work on eliciting and representing preferences over multi-attribute alternatives has attempted to recognize conditions under which value functions take on particularly simple and compact form, making their elicitation much easier. In this paper we consider preferences over discrete domains, and show that for a certain class of simple and intuitive qualitative preference statements, one can always generate compact value functions consistent with these statements. These value functions maintain the independence structure implicit in the original statements. For discrete domains, these representation theorems are much more general than previous results. However, we also show that it is not always possible to maintain this compact structure if we add explicit ordering constraints among the available outcomes.

ICAPS Conference 2008 Conference Paper

Optimal Additive Composition of Abstraction-based Admissible Heuristics

• Michael Katz 0001
• Carmel Domshlak

We describe a procedure that takes a classical planning task, a forward-search state, and a set of abstraction-based admissible heuristics, and derives an optimal additive composition of these heuristics with respect to the given state. Most importantly, we show that this procedure is polynomial-time for arbitrary sets of all known to us abstraction-based heuristics such as PDBs, constrained PDBs, merge-and-shrink abstractions, fork-decomposition structural patterns, and structural patterns based on tractable constraint optimization.

ICAPS Conference 2008 Conference Paper

Structural Patterns Heuristics via Fork Decomposition

• Michael Katz 0001
• Carmel Domshlak

We consider a generalization of the PDB homomorphism abstractions to what is called "structural patterns". The basic idea is in abstracting the problem in hand into provably tractable fragments of optimal planning, alleviating by that the constraint of PDBs to use projections of only low dimensionality. We introduce a general framework for additive structural patterns based on decomposing the problem along its causal graph, suggest a concrete non-parametric instance of this framework called fork-decomposition, and formally show that the admissible heuristics induced by the latter abstractions provide state-of-the-art worst-case informativeness guarantees on several standard domains.

ICAPS Conference 2007 Conference Paper

Cost-Sharing Approximations for h+

• Vitaly Mirkis
• Carmel Domshlak

Relaxations based on (either complete or partial) ignoring delete effects of the actions provide the basis for some seminal classical planning heuristics. However, the palette of the conceptual tools exploited by these heuristics remains rather limited. We study a framework for approximating the optimal cost solutions for problems with no delete effects that bridges between certain works on heuristic search for probabilistic reasoning and classical planning. In particular, this framework generalizes some previously known, as well as suggests some novel, tools for heuristic estimates for Strips planning.

ICAPS Conference 2007 Conference Paper

Structural Patterns of Tractable Sequentially-Optimal Planning

• Michael Katz 0001
• Carmel Domshlak

We study the complexity of sequentially-optimal classical planning, and discover new problem classes for whose such optimization is tractable. The results are based on exploiting numerous structural characteristics of planning problems, and a constructive proof technique that connects between certain tools from planning and tractable constraint optimization. In particular, we believe that structure-based tractability results of this kind may help devising new admissible search heuristics. We discuss the prospects of this direction along a principled extension of pattern-database heuristics to "structural patterns" of unlimited dimensionality.

ICAPS Conference 2006 Conference Paper

Fast Probabilistic Planning through Weighted Model Counting

• Carmel Domshlak
• Jörg Hoffmann 0001

We present a new algorithm for probabilistic planning with no observability. Our algorithm, called Probabilistic-FF, extends the heuristic forward-search machinery of Conformant-FF to problems with probabilistic uncertainty about both the initial state and action effects. Specifically, Probabilistic-FF combines Conformant-FF's techniques with a powerful machinery for weighted model counting in (weighted) CNFs, serving to elegantly define both the search space and the heuristic function. Our evaluation of Probabilistic-FF on several probabilistic domains shows an unprecedented, several orders of magnitude improvement over previous results in this area.

ICAPS Conference 2006 Conference Paper

Friends or Foes? An AI Planning Perspective on Abstraction and Search

• Jörg Hoffmann 0001
• Ashish Sabharwal
• Carmel Domshlak

There is increasing awareness that planning and model checking are closely related fields. Abstraction means to perform search in an over-approximation of the original problem instance, with a potentially much smaller state space. This is the most essential method in model checking. One would expect that it can also be made successful in planning. We show, however, that this is likely to not be the case. The main reason is that, while in model checking one traditionally uses blind search to exhaust the state space and prove the absence of solutions, in planning informed search is used to find solutions. We give an exhaustive theoretical and practical account of the use of abstraction in planning. For all abstraction (over-approximation) methods known in planning, we prove that they cannot improve the best-case behavior of informed search. While this is easy to see for heuristic search, we were quite surprised to find that it also holds, in most cases, for the resolution-style proofs of unsolvability underlying SAT-based optimal planners. This result is potentially relevant also for model checking, where SAT-based techniques have recently been combined with abstraction. Exploring the issue in planning practice, we find that even hand-made abstractions do not tend to improve the performance of planners, unless the attacked task contains huge amounts of irrelevance. We relate these findings to the kinds of application domains that are typically addressed in model checking.

AIJ Journal 2005 Journal Article

Sensor networks and distributed CSP: communication, computation and complexity

• Ramón Béjar
• Carmel Domshlak
• Cèsar Fernández
• Carla Gomes
• Bhaskar Krishnamachari
• Bart Selman
• Magda Valls

We introduce SensorDCSP, a naturally distributed benchmark based on a real-world application that arises in the context of networked distributed systems. In order to study the performance of Distributed CSP (DisCSP) algorithms in a truly distributed setting, we use a discrete-event network simulator, which allows us to model the impact of different network traffic conditions on the performance of the algorithms. We consider two complete DisCSP algorithms: asynchronous backtracking (ABT) and asynchronous weak commitment search (AWC), and perform performance comparison for these algorithms on both satisfiable and unsatisfiable instances of SensorDCSP. We found that random delays (due to network traffic or in some cases actively introduced by the agents) combined with a dynamic decentralized restart strategy can improve the performance of DisCSP algorithms. In addition, we introduce GSensorDCSP, a plain-embedded version of SensorDCSP that is closely related to various real-life dynamic tracking systems. We perform both analytical and empirical study of this benchmark domain. In particular, this benchmark allows us to study the attractiveness of solution repairing for solving a sequence of DisCSPs that represent the dynamic tracking of a set of moving objects.

UAI Conference 2005 Conference Paper

Unstructuring User Preferences: Efficient Non-Parametric Utility Revelation

• Carmel Domshlak
• Thorsten Joachims

UAI Conference 2004 Conference Paper

Compact Value-Function Representations for Qualitative Preferences

• Ronen I. Brafman
• Carmel Domshlak
• Tanya Kogan

We consider the challenge of preference elicitation in systems that help users discover the most desirable item(s) within a given database. Past work on preference elicitation focused on structured models that provide a factored representation of users' preferences. Such models require less information to construct and support efficient reasoning algorithms. This paper makes two substantial contributions to this area: (1) Strong representation theorems for factored value functions. (2) A methodology that utilizes our representation results to address the problem of optimal item selection.

AIJ Journal 2003 Journal Article

Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks

• Solomon E Shimony
• Carmel Domshlak

Directed-path (DP) singly-connected Bayesian networks are an interesting special case that, in particular, includes both polytrees and two-level networks. We analyze the computational complexity of these networks. The prediction problem is shown to be easy, as standard message passing can perform correct updating. However, diagnostic reasoning is hard even for DP singly-connected networks. In addition, finding the most-probable explanation (MPE) is hard, even without evidence. Finally, complexity of nearly DP singly-connected networks is analyzed.

KR Conference 2002 Conference Paper

CP-nets - Reasoning and Consistency Testing

• Carmel Domshlak
• Ronen I. Brafman

UAI Conference 2002 Conference Paper

Introducing Variable Importance Tradeoffs into CP-Nets

• Ronen I. Brafman
• Carmel Domshlak

The ability to make decisions and to assess potential courses of action is a corner-stone of many AI applications, and usually this requires explicit information about the decision-maker s preferences. IN many applications, preference elicitation IS a serious bottleneck.The USER either does NOT have the time, the knowledge, OR the expert support required TO specify complex multi - attribute utility functions. IN such cases, a method that IS based ON intuitive, yet expressive, preference statements IS required. IN this paper we suggest the USE OF TCP - nets, an enhancement OF CP - nets, AS a tool FOR representing, AND reasoning about qualitative preference statements.We present AND motivate this framework, define its semantics, AND show how it can be used TO perform constrained optimization.

ICAPS Conference 2002 Conference Paper

Structure and Complexity in Planning with Unary Operators

• Carmel Domshlak
• Ronen I. Brafman

Unary operator domains - i. e., domains in which operators have a single effect - arise naturally in many control problems. In its most general form, the problem of STRIPS planning in unary operator domains is known to be as hard as the general STRIPS planning problem - both are PSPACE-complete. However, unary operator domains induce a natural structure, called the domain’s causal graph. This graph relates between the preconditions and effect of each domain operator. Causal graphs were exploited by Williams and Nayak in order to analyze plan generation for one of the controllers in NASA’s Deep-Space One spacecraft. There, they utilized the fact that when this graph is a tree, a serialization ordering over any subgoal can be obtained quickly. In this paper we conduct a comprehensive study of the relationship between the structure of a domain’s causal graph and the complexity of planning in this domain. On the positive side, we show that a non-trivial polynomial time plan generation algorithm exists for domains whose causal graph induces a polytree with a constant bound on its node indegree. On the negative side, we show that even plan existence is hard when the graph is a singly connected DAG. More generally, we show that the number of paths in the causal graph is closely related to the complexity of planning in the associated domain. Finally we relate our results to the question of complexity of planning with serializable subgoals.

UAI Conference 1997 Conference Paper

Cost-Sharing in Bayesian Knowledge Bases

• Solomon Eyal Shimony
• Carmel Domshlak
• Eugene Santos Jr.

Bayesian knowledge bases (BKBs) are a generalization of Bayes networks and weighted proof graphs (WAODAGs), that allow cycles in the causal graph. Reasoning in BKBs requires finding the most probable inferences consistent with the evidence. The cost-sharing heuristic for finding least-cost explanations in WAODAGs was presented and shown to be effective by Charniak and Husain. However, the cycles in BKBs would make the definition of cost-sharing cyclic as well, if applied directly to BKBs. By treating the defining equations of cost-sharing as a system of equations, one can properly define an admissible cost-sharing heuristic for BKBs. Empirical evaluation shows that cost-sharing improves performance significantly when applied to BKBs.