Arrow Research search

Author name cluster

Alexander Shleyfman

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.

30 papers
2 author rows

Possible papers

30

AAAI Conference 2026 Conference Paper

Managing Infinite Abstractions in Numeric Pattern Database Heuristics

  • Markus Fritzsche
  • Daniel Gnad
  • Mikhail Gruntov
  • Alexander Shleyfman

Pattern Database (PDB) heuristics are an established approach in optimal classical planning that is used in state-of-the-art planning systems. PDBs are based on projections, which induce an abstraction of the original problem. Computing all cheapest plans in the abstraction yields an admissible heuristic. Despite their success, PDBs have only recently been adapted to numeric planning, which extends classical planning with numeric state variables. The difficulty in supporting numeric variables is that the induced abstractions, in contrast to classical planning, are generally infinite. Thus, they cannot be explored exhaustively to compute a heuristic. The foundational work that introduced numeric PDBs employed a simple approach that computes only a finite part of the abstraction. We analyze this framework and identify cases where it necessarily results in an uninformed heuristic. We propose several improvements over the basic variant of numeric PDBs that lead to enhanced heuristic accuracy.

PDF Details DOI

AAAI Conference 2025 Conference Paper

PDBs Go Numeric: Pattern-Database Heuristics for Simple Numeric Planning

  • Daniel Gnad
  • Lee-Or Alon
  • Eyal Weiss
  • Alexander Shleyfman

Despite the widespread success of pattern database (PDB) heuristics in classical planning, to date there has been no application of PDBs to planning with numeric variables. In this paper we attempt to close this gap. We address optimal numeric planning involving conditions characterized by linear expressions and actions that modify numeric variables by constant quantities. Building upon prior research, we present an adaptation of PDB heuristics to numeric planning, introducing several approaches to deal with the unbounded nature of numeric variable projections. These approaches aim to restrict the initially infinite projections, thereby bounding the number of states and ultimately constraining the resulting PDBs. We show that the PDB heuristics obtained with our approach can provide strong guidance for the search.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

Towards a Unified View of Social Laws with Instantaneous Actions

  • Alexander Tuisov
  • Evgeny Mishlyakov
  • Alexander Shleyfman
  • Erez Karpas

Multiple agents operating in a shared environment can interfere with each other’s ability to reach their goals. One of the approaches to address this issue is enacting a social law – a set of rules that restricts some possible behaviors of the agents. A social law is considered robust if it guarantees that each agent can achieve its goal independently of the actions of other agents. Recent work has shown how to verify that a given social law, encoded in an MA-STRIPS formalism, is robust by compilation to classical planning. Follow-up work presented an extended compilation which can handle numeric multi-agent planning. In this paper, we present a new compilation, which can handle both classical and numeric multi-agent planning formalisms, as well as any other multi-agent planning formalism with instantaneous actions, in which action preconditions can be negated using first-order logic with equality. This opens the door to using social laws in even richer planning formalisms. Our empirical evaluation shows that the added expressivity of the new compilation does not hurt its performance, and it achieves comparable performance to the previous state-of-the-art compilations.

PDF Details DOI

SoCS Conference 2024 Conference Paper

A Deterministic Search Approach for Solving Stochastic Drone Search and Rescue Planning Without Communications

  • Evgeny Mishlyakov
  • Mikhail Gruntov
  • Alexander Shleyfman
  • Erez Karpas

In disaster relief efforts, delivering aid to areas with no communication poses a significant challenge. Unmanned aerial vehicles (UAVs) can be utilized to deliver aid kits to survivors in hard-to-reach areas; unfortunately, in some areas, lack of communication and infrastructure presents a key problem. In this paper, we address a stochastic planning problem of planning for a set of UAVs that deliver aid kits to areas that lack communications, where we do not know in advance the locations where aid kits need to be delivered, but rather have probabilistic information about the locations of aid targets. Our main insight is that, despite the stochastic nature of this problem, we can solve it through deterministic search by monitoring the expected reward for each partial solution. This insight enables the application of deterministic planning techniques, empirically demonstrating a notable improvement in efficiency and response speed. Our approach presents a promising solution to addressing the challenge of delivering aid in regions with limited radio infrastructure, as well as similar planning problems.

Details

ECAI Conference 2024 Conference Paper

Good Things Come to Those Who Wait: The Power of Sensing in Social Laws

  • Alexander Tuisov
  • Alexander Shleyfman
  • Erez Karpas

Multiple agents operating in a shared environment can interfere with each other’s ability to reach their goals. One of the approaches to address this issue is enacting a social law – a set of rules that restricts some possible behaviors of the agents. A social law that ensures that each agent can achieve its goal, regardless of what the other agents do, is called robust. Recent work has shown how to verify that a given social law, encoded in an MA-STRIPS formalism, is robust by compilation to classical planning. That work also introduced the notion of waitfor preconditions, which assumes that the agent can check if these preconditions hold before executing its scheduled action and withhold from acting otherwise. In this work, we explore the connection between waitfor preconditions and sensing. In particular, we establish the semantics behind the waitfor mechanism and connect it to the agent’s sensing capabilities. Moreover, we reason about the expressive power of waitfors by juxtaposing environments where some sensing is allowed with “blind” environments. Using these insights, we derive methods for faster robustness validation, and present an empirical evaluation of these methods.

Details

ECAI Conference 2024 Conference Paper

Planning to be Healthy: Towards Personalized Medication Planning

  • Lee-or Alon
  • Hana Weitman
  • Alexander Shleyfman
  • Gal A. Kaminka

Personalized medication plans determine the selection, dosage, and administration schedule of medications, to achieve medical goals that are specific to the patient and to its individual health constraints. This paper introduces medication planning as a novel domain for artificial intelligence planning, using PDDL+. We evaluate the suggested representation via experiments based on data collected from medical studies conducted on mice and rats.

Details

AAAI Conference 2023 Conference Paper

Automated Verification of Social Laws in Numeric Settings

  • Ronen Nir
  • Alexander Shleyfman
  • Erez Karpas

It is possible for agents operating in a shared environment to interfere with one another. One mechanism of coordination is called Social Law. Enacting such a law in a multi-agent setting restricts agents' behaviors. Robustness, in this case, ensures that the agents do not harmfully interfere with each other and that each agent achieves its goals regardless of what other agents do. Previous work on social law verification examined only the case of boolean state variables. However, many real-world problems require reasoning with numeric variables. Moreover, numeric fluents allow a more compact representation of multiple planning problems. In this paper, we develop a method to verify whether a given social law is robust via compilation to numeric planning. A solution to this compilation constitutes a counterexample to the robustness of the problem, i.e., evidence of cross-agent conflict. Thus, the social law is robust if and only if the proposed compilation is unsolvable. We empirically verify robustness in multiple domains using state-of-the-art numeric planners. Additionally, this compilation raises a challenge by generating a set of non-trivial numeric domains where unsolvability should be either proved or disproved.

PDF Details DOI

ECAI Conference 2023 Conference Paper

Extracting and Exploiting Bounds of Numeric Variables for Optimal Linear Numeric Planning

  • Ryo Kuroiwa 0002
  • Alexander Shleyfman
  • J. Christopher Beck

In numeric AI planning, a state is represented by propositions and numeric variables, actions change the values of numeric variables in addition to adding and deleting propositions, and goals and preconditions of actions may include conditions over numeric variables. While domains of numeric variables are rational numbers in general, upper and lower bounds on variables affected only by constant increase and decrease can sometimes be determined and exploited by a heuristic function. In this paper, we generalize the existing method to variables that are changed by linear effects. We exploit the extracted bounds to improve the numeric LM-cut heuristic, a state-of-the-art admissible heuristic for linear numeric planning. Empirical evaluation shows that our method improves the performance of LM-cut in multiple domains. The proposed method can also detect unsolvability of some numeric tasks in polynomial time.

Details

ICAPS Conference 2023 Conference Paper

Planning over Integers: Compilations and Undecidability

  • Daniel Gnad 0001
  • Malte Helmert
  • Peter Jonsson
  • Alexander Shleyfman

Restricted Tasks (RT) are a special case of numeric planning characterized by numeric conditions that involve one numeric variable per formula and numeric effects that allow only the addition of constants. Despite this, RTs form an expressive class whose planning problem is undecidable. The restricted nature of RTs often makes problem modeling awkward and unnecessarily complicated. We show that this can be alleviated by compiling mathematical operations that are not natively supported into RTs using macro-like action sequences. With that, we can encode many features found in general numeric planning such as constant multiplication, addition of linear formulas, and integer division and residue. We demonstrate how our compilations can be used to capture challenging mathematical problems such as the (in)famous Collatz conjecture. Our approach additionally gives a simple undecidability proof for RTs, and the proof shows that the number of variables needed to construct an undecidable class of RTs is surprisingly low: two numeric and one propositional variable.

Details

AAAI Conference 2023 Conference Paper

Structurally Restricted Fragments of Numeric Planning – a Complexity Analysis

  • Alexander Shleyfman
  • Daniel Gnad
  • Peter Jonsson

Numeric planning is known to be undecidable even under severe restrictions. Prior work has investigated the decidability boundaries by restricting the expressiveness of the planning formalism in terms of the numeric functions allowed in conditions and effects. We study a well-known restricted form of Hoffmann's simple numeric planning, which is undecidable. We analyze the complexity by imposing restrictions on the causal structure, exploiting a novel method for bounding variable domain sizes. First, we show that plan existence for tasks where all numeric variables are root nodes in the causal graph is in PSPACE. Second, we show that for tasks with only numeric leaf variables the problem is decidable, and that it is in PSPACE if the propositional state space has a fixed size. Our work lays a strong foundation for future investigations of structurally more complex tasks. From a practical perspective, our method allows to employ heuristics and methods that are geared towards finite variable domains (such as pattern database heuristics or decoupled search) to solve non-trivial families of numeric planning problems.

PDF Details DOI

ICAPS Conference 2023 Conference Paper

Symmetry Detection and Breaking in Linear Cost-Optimal Numeric Planning

  • Alexander Shleyfman
  • Ryo Kuroiwa 0002
  • J. Christopher Beck

One of the main challenges of domain-independent numeric planning is the complexity of the search problem. The exploitation of structural symmetries in a search problem can constitute an effective method of pruning search branches that may lead to exponential improvements in performance. For over a decade, symmetry breaking techniques have been successfully used within both optimal and satisficing classical planning. In this work, we show that symmetry detection methods applied in classical planning with some effort can be modified to detect symmetries in linear numeric planning. The detected symmetry group, thereafter, can be used almost directly in the A*-based symmetry breaking algorithms such as DKS and Orbit Space Search. We empirically validate that symmetry pruning can yield a substantial reduction in the search effort, even if algorithms are equipped with a strong heuristic, such as LM-cut.

Details

ICAPS Conference 2022 Conference Paper

LM-Cut Heuristics for Optimal Linear Numeric Planning

  • Ryo Kuroiwa 0002
  • Alexander Shleyfman
  • J. Christopher Beck

While numeric variables play an important, sometimes central, role in many planning problems arising from real world scenarios, most of the currently available heuristic search planners either do not support such variables or impose heavy restrictions on them. In particular, most admissible heuristics are restricted to domains where actions can only change numeric variables by predetermined constants. In this work, we consider the setting of optimal numeric planning with linear effects, where actions can have numeric effects that assign the result of the evaluation of a linear formula. We extend a recent formulation of Numeric LM-cut for simple effects by adding conditional effects and second-order simple effects, allowing the heuristic to produce admissible estimates for tasks with linear numeric effects. Empirical comparison shows that the proposed LM-cut heuristics favorably compete with the currently available state-of-the-art heuristics and achieve significant improvement in coverage in the domains with second-order simple effects.

Details

JAIR Journal 2022 Journal Article

The LM-Cut Heuristic Family for Optimal Numeric Planning with Simple Conditions

  • Ryo Kuroiwa
  • Alexander Shleyfman
  • Chiara Piacentini
  • Margarita P. Castro
  • J. Christopher Beck

The LM-cut heuristic, both alone and as part of the operator counting framework, represents one of the most successful heuristics for classical planning. In this paper, we generalize LM-cut and its use in operator counting to optimal numeric planning with simple conditions and simple numeric effects, i.e., linear expressions over numeric state variables and actions that increase or decrease such variables by constant quantities. We introduce a variant of hmaxhbd (a previously proposed numeric hmax heuristic) based on the delete-relaxed version of such planning tasks and show that, although inadmissible by itself, our variant yields a numeric version of the classical LM-cut heuristic which is admissible. We classify the three existing families of heuristics for this class of numeric planning tasks and introduce the LM-cut family, proving dominance or incomparability between all pairs of existing max and LM-cut heuristics for numeric planning with simple conditions. Our extensive empirical evaluation shows that the new LM-cut heuristic, both on its own and as part of the operator counting framework, is the state-of-the-art for this class of numeric planning problem.

PDF Details DOI

JAIR Journal 2021 Journal Article

Computational Complexity of Computing Symmetries in Finite-Domain Planning

  • Alexander Shleyfman
  • Peter Jonsson

Symmetry-based pruning is a powerful method for reducing the search effort in finitedomain planning. This method is based on exploiting an automorphism group connected to the ground description of the planning task { these automorphisms are known as structural symmetries. In particular, we are interested in the StructSym problem where the generators of this group are to be computed. It has been observed in practice that the StructSym problem is surprisingly easy to solve. We explain this phenomenon by showing that StructSym is GI-complete, i.e., the graph isomorphism problem is polynomial-time equivalent to it and, consequently, solvable in quasi-polynomial time. This implies that it is solvable substantially faster than most computationally hard problems encountered in AI. We accompany this result by identifying natural restrictions of the planning task and its causal graph that ensure that StructSym can be solved in polynomial time. Given that the StructSym problem is GI-complete and thus solvable quite efficiently, it is interesting to analyse if other symmetries (than those that are encompassed by the StructSym problem) can be computed and/or analysed efficiently, too. To this end, we present a highly negative result: checking whether there exists an automorphism of the state transition graph that maps one state s into another state t is a PSPACE-hard problem and, consequently, at least as hard as the planning problem itself.

PDF Details DOI

IJCAI Conference 2021 Conference Paper

Counterfactual Explanations for Optimization-Based Decisions in the Context of the GDPR

  • Anton Korikov
  • Alexander Shleyfman
  • J. Christopher Beck

The General Data Protection Regulations (GDPR) entitle individuals to explanations for automated decisions. The form, comprehensibility, and even existence of such explanations remain open problems, investigated as part of explainable AI. We adopt the approach of counterfactual explanations and apply it to decisions made by declarative optimization models. We argue that inverse combinatorial optimization is particularly suited for counterfactual explanations but that the computational difficulties and relatively nascent literature make its application a challenge. To make progress, we address the case of counterfactual explanations that isolate the minimal differences for an individual. We show that under two common optimization functions, full inverse optimization is unnecessary. In particular, we show that for functions of the form of the sum of weighted binary variables, which includes frameworks such as weighted MaxSAT, a solution can be found by solving a slightly modified version of the original optimization model. In contrast, the sum of weighted integer variables can be solved with a binary search over a series of modifications to the original model.

PDF Details DOI

SoCS Conference 2021 Conference Paper

Learning-Based Synthesis of Social Laws in STRIPS

  • Ronen Nir
  • Alexander Shleyfman
  • Erez Karpas

In a multi-agent environment, each agent must take into account not only the actions it must perform to achieve its goals, but also the behavior of other agents in the system, which usually requires some sort of coordination between the agents. One way to avoid the complexity of centralized planning and online negotiation between agents is to design an artificial social system. This system enacts a social law that restricts the behavior of the agents. A robust social law enables the agents to reach their goals while keeping them from interfering with each other. However, the problem of efficient synthesis of such laws is computationally hard, and previously proposed search techniques do not scale well. In this paper, we propose the use of graph neural networks to predict social laws from a graph-based representation of multi-agent systems. However, as this prediction can be wrong, we use heuristic search to correct possible mistakes in the network

Details

ICAPS Conference 2021 Conference Paper

LM-cut and Operator Counting Heuristics for Optimal Numeric Planning with Simple Conditions

  • Ryo Kuroiwa 0002
  • Alexander Shleyfman
  • Chiara Piacentini
  • Margarita P. Castro
  • J. Christopher Beck

We consider optimal numeric planning with numeric conditions consisting of linear expressions of numeric state variables and actions that increase or decrease numeric state variables by constant quantities. We build on previous research to introduce a new variant of the numeric hmax heuristic based on the delete-relaxed version of such planning tasks. Although our hmax heuristic is inadmissible, it yields a numeric version of the classical LM-cut heuristic which is admissible. Further, we prove that our LM-cut heuristic neither dominates nor is dominated by the existing numeric heuristic hmax(hbd). We show that admissibility also holds when integrating the numeric cuts into the operator-counting (OC) heuristic producing an admissible numeric version of the OC heuristic. Through experiments, we demonstrate that both these heuristics compete favorably with the state-of-the-art heuristics: in particular, while sometimes expanding more nodes than other heuristics, numeric OC solves 19 more problem instances than the next closest heuristic.

Details

AAAI Conference 2020 Conference Paper

Automated Synthesis of Social Laws in STRIPS

  • Ronen Nir
  • Alexander Shleyfman
  • Erez Karpas

Agents operating in a multi-agent environment must consider not just their actions, but also those of the other agents in the system. Artificial social systems are a well-known means for coordinating a set of agents, without requiring centralized planning or online negotiation between agents. Artificial social systems enact a social law which restricts the agents from performing some actions under some circumstances. A robust social law prevents the agents from interfering with each other, but does not prevent them from achieving their goals. Previous work has addressed how to check if a given social law, formulated in a variant of MA-STRIPS, is robust, via compilation to planning. However, the social law was manually specified. In this paper, we address the problem of automatically synthesizing a robust social law for a given multi-agent environment. We treat the problem of social law synthesis as a search through the space of possible social laws, relying on the robustness verification procedure as a goal test. We also show how to exploit additional information produced by the robustness verification procedure to guide the search.

PDF Details

ICAPS Conference 2019 Conference Paper

On Computational Complexity of Automorphism Groups in Classical Planning

  • Alexander Shleyfman

Symmetry-based pruning is a family of powerful methods for reducing search effort in planning as heuristic search. Applying these methods requires first establishing an automorphism group that is then used for pruning within the search process. Despite the growing popularity of state-space symmetries in planning techniques, the computational complexity of finding the automorphism group of a compactly represented planning task has not been formally established. In a series of reductions, we show that computing the automorphism group of a grounded planning task is GI-hard. Furthermore, we discuss the presentations of these symmetry groups and list some of their drawbacks.

Details

AAAI Conference 2019 Conference Paper

Operator Mutexes and Symmetries for Simplifying Planning Tasks

  • Daniel Fišer
  • Álvaro Torralba
  • Alexander Shleyfman

Simplifying classical planning tasks by removing operators while preserving at least one optimal solution can significantly enhance the performance of planners. In this paper, we introduce the notion of operator mutex, which is a set of operators that cannot all be part of the same (strongly) optimal plan. We propose four different methods for inference of operator mutexes and experimentally verify that they can be found in a sizable number of planning tasks. We show how operator mutexes can be used in combination with structural symmetries to safely remove operators from the planning task.

PDF Details

ICAPS Conference 2017 Conference Paper

Automated Verification of Social Law Robustness in STRIPS

  • Erez Karpas
  • Alexander Shleyfman
  • Moshe Tennenholtz

Agents operating in a multi-agent environment must consider not just their own actions, but also those of the other agents in the system. Artificial social systems are a well known means for coordinating a set of agents, without requiring centralized planning or online negotiation between agents. Artificial social systems enact a social law which restricts the agents from performing some actions under some circumstances. A good social law prevents the agents from interfering with each other, but does not prevent them from achieving their goals. However, designing good social laws, or even checking whether a proposed social law is good, are hard questions. In this paper, we take a first step towards automating these processes, by formulating criteria for good social laws in a multi-agent planning framework. We then describe an automated technique for verifying if a proposed social law meets these criteria, based on a compilation to classical planning.

Details

ICAPS Conference 2017 Conference Paper

Symmetry Breaking in Star-Topology Decoupled Search

  • Daniel Gnad 0001
  • Álvaro Torralba
  • Alexander Shleyfman
  • Jörg Hoffmann 0001

Symmetry breaking is a well-known method for search reduction. It identifies state-space symmetries prior to search, and prunes symmetric states during search. A recent proposal, star-topology decoupled search, is to search not in the state space, but in a factored version thereof, which avoids the multiplication of states across leaf components in an underlying star-topology structure. We show that, despite the much more complex structure of search states -- so-called decoupled states -- symmetry breaking can be brought to bear in this framework as well. Starting from the notion of structural symmetries over states, we identify a sub-class of such symmetries suitable for star-topology decoupled search, and we show how symmetries from that sub-class induce symmetry relations over decoupled states. We accordingly extend the routines required for search pruning and solution reconstruction. The resulting combined method can be exponentially better than both its components in theory, and this synergetic advantage is also manifested in practice: empirically, our method reliably inherits the best of its base components, and often outperforms them both.

Details

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.

PDF Details

AAAI Conference 2015 Conference Paper

Factored Symmetries for Merge-and-Shrink Abstractions

  • Silvan Sievers
  • Martin Wehrle
  • Malte Helmert
  • Alexander Shleyfman
  • Michael Katz

Merge-and-shrink heuristics crucially rely on effective reduction techniques, such as bisimulation-based shrinking, to avoid the combinatorial explosion of abstractions. We propose the concept of factored symmetries for merge-andshrink abstractions based on the established concept of symmetry reduction for state-space search. We investigate under which conditions factored symmetry reduction yields perfect heuristics and discuss the relationship to bisimulation. We also devise practical merging strategies based on this concept and experimentally validate their utility.

PDF Details

AAAI Conference 2015 Conference Paper

Heuristics and Symmetries in Classical Planning

  • Alexander Shleyfman
  • Michael Katz
  • Malte Helmert
  • Silvan Sievers
  • Martin Wehrle

Heuristic search is a state-of-the-art approach to classical planning. Several heuristic families were developed over the years to automatically estimate goal distance information from problem descriptions. Orthogonally to the development of better heuristics, recent years have seen an increasing interest in symmetry-based state space pruning techniques that aim at reducing the search effort. However, little work has dealt with how the heuristics behave under symmetries. We investigate the symmetry properties of existing heuristics and reveal that many of them are invariant under symmetries.

PDF Details

IJCAI Conference 2015 Conference Paper

Integrating Partial Order Reduction and Symmetry Elimination for Cost-Optimal Classical Planning

  • Martin Wehrle
  • Malte Helmert
  • Alexander Shleyfman
  • Michael Katz

Pruning techniques based on partial order reduction and symmetry elimination have recently found increasing attention for optimal planning. Although these techniques appear to be rather different, they base their pruning decisions on similar ideas from a high level perspective. In this paper, we propose safe integrations of partial order reduction and symmetry elimination for cost-optimal classical planning. We show that previously proposed symmetrybased search algorithms can safely be applied with strong stubborn sets. In addition, we derive the notion of symmetrical strong stubborn sets as a more tightly integrated concept. Our experiments show the potential of our approaches.

PDF Details

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.

PDF Details

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.

Details

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.

Details

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].

Details
v2026.09.13