Author name cluster

Rostislav Horcík

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.

10 papers

1 author row

ECAI Conference 2025 Conference Paper

Action Costs Prediction by Multiplicative Weights Update

Rostislav Horcík

This paper proposes a novel method to predict uncertain action costs in classical planning, considering the resulting plan’s quality rather than the prediction’s quality. Unlike the solution offered by decision-focused learning (DFL), our method does not compute a gradient of the regret loss function. Instead, it starts with any trained model, e. g. by the usual mean square error (MSE), to obtain a tuple of the approximate model’s parameters. Next, it randomly samples a collection of tuples of parameters in the neighborhood of the approximate parameters. Finally, it employs the Multiplicative Weights Update algorithm to compute a probability distribution over this collection reflecting the quality of the sampled tuples of parameters w. r. t. the regret loss function. A weighted average of the predictions w. r. t. the sampled tuples of parameters gives us the resulting action costs prediction that considerably reduces the average regret compared to the MSE-trained predictor.

Details

ICAPS Conference 2024 Conference Paper

Expressiveness of Graph Neural Networks in Planning Domains

Rostislav Horcík
Gustav Sír

Graph Neural Networks (GNNs) have become the standard method of choice for learning with structured data, demonstrating particular promise in classical planning. Their inherent invariance under symmetries of the input graphs endows them with superior generalization capabilities, compared to their symmetry-oblivious counterparts. However, this comes at the cost of limited expressive power. Particularly, GNNs cannot distinguish between graphs that satisfy identical sentences of C2 logic. To leverage GNNs for learning policies in PDDL domains, one needs to encode the contextual representation of the planning states as graphs. The expressiveness of this encoding, coupled with a specific GNN architecture, then hinges on the absence of indistinguishable states necessitating distinct actions. This paper provides a comprehensive theoretical and statistical exploration of such situations in PDDL domains across diverse natural encoding schemes and GNN models.

Details

ECAI Conference 2023 Conference Paper

Gaifman Graphs in Lifted Planning

Rostislav Horcík
Daniel Fiser

We introduce the metric induced by Gaifman graphs into lifted planning. We analyze what kind of information this metric carries and how it can be utilized for constructing lifted delete-free relaxation heuristics. In particular, we prove how the action dynamics influence the distances between objects. As a corollary, we derive a lower bound on the length of any plan. Finally, we apply our theoretical findings on the Gaifman graphs to improve the delete-free relaxation heuristics induced by PDDL homomorphisms.

Details

SoCS Conference 2022 Conference Paper

Effective Planning in Resource-Competition Problems by Task Decomposition

Lukás Chrpa
Pavel Rytír
Andrii Nyporko
Rostislav Horcík
Stefan Edelkamp

Effective planning while competing for limited resources is crucial in many real-world applications such as on-demand transport companies competing for passengers. Planning techniques therefore have to take into account possible actions of an adversarial agent. Such a challenge that can be tackled by leveraging game-theoretical methods such as Double Oracle. This paper aims at the scalability issues arising from combining planning techniques with Double Oracle. In particular, we propose an abstraction-based heuristic for deciding how resources will be collected (e. g. which car goes for which passenger and in which order) and we propose a method for decomposing planning tasks into smaller ones (e. g. generate plans for each car separately). Our empirical evaluation shows that our proposed approach considerably improves scalability compared to the state-of-the-art techniques.

Details

ICAPS Conference 2022 Conference Paper

Optimal Mixed Strategies for Cost-Adversarial Planning Games

Rostislav Horcík
Álvaro Torralba
Pavel Rytír
Lukás Chrpa
Stefan Edelkamp

This paper shows that domain-independent tools from classical planning can be used to model and solve a broad class of game-theoretic problems we call Cost-Adversarial Planning Games (CAPGs). We define CAPGs as 2-player normal-form games specified by a planning task and a finite collection of cost functions. The first player (a planning agent) strives to solve a planning task optimally but has limited knowledge about its action costs. The second player (an adversary agent) controls the actual action costs. Even though CAPGs need not be zero-sum, every CAPG has an associated zero-sum game whose Nash equilibrium provides the optimal randomized strategy for the planning agent in the original CAPG. We show how to find the Nash equilibrium of the associated zero-sum game using a cost-optimal planner via the Double Oracle algorithm. To demonstrate the expressivity of CAPGs, we formalize a patrolling security game and several IPC domains as CAPGs.

Details

SoCS Conference 2021 Conference Paper

Adversary Strategy Sampling for Effective Plan Generation

Lukás Chrpa
Pavel Rytír
Rostislav Horcík
Jan Cuhel
Anastasiia Livochka
Stefan Edelkamp

Effective plan generation in adversarial environments has to take into account possible actions of adversary agents, i. e. , the agent should know what the competitor will likely do. In this paper we propose a novel approach for estimating strategies of the adversary, sampling actions that interfere with the agent

Details

ICAPS Conference 2021 Conference Paper

Endomorphisms of Lifted Planning Problems

Rostislav Horcík
Daniel Fiser

Classical planning tasks are usually modelled in the PDDL which is a schematic language based on first-order logic. Nevertheless, most of the current planners turn this first-order representation into a propositional one via the grounding process. It is well known that the grounding process may cause an exponential blowup. Therefore it is important to detect which grounded atoms are redundant in a sense that they are not necessary for finding a plan and therefore the grounding process does not need to generate them. This is usually done by a relaxed reachability analysis, which can be improved by employing structural symmetries. Symmetries are bijective self-maps preserving the structure of the PDDL task. In this paper, we introduce a new method which is based on self-maps preserving the structure but which need not be bijective. We call these maps PDDL endomorphisms and we show that they can be used for pruning of redundant objects even if they appear in a reachable atom. We formulate the computation of endomorphisms as a constraint satisfaction problem (CSP) that can be solved by an off-the-shelf CSP solver.

Details

SoCS Conference 2020 Conference Paper

Planning Against Adversary in Zero-Sum Games: Heuristics for Selecting and Ordering Critical Actions

Lukás Chrpa
Pavel Rytír
Rostislav Horcík

Effective and efficient reasoning in adversarial environments is important for many real-world applications ranging from cybersecurity to military operations. Deliberative reasoning techniques, such as Automated Planning, often restrict to static environments where only an agent can make changes by its actions. On the other hand, such techniques are effective and can generate non-trivial solutions. To explicitly reason in environments with an active adversary such as zero-sum games, the game-theoretic framework such as the Double Oracle algorithm can be leveraged. In this paper, we leverage the notions of critical and adversary actions, where critical actions should be applied before the adversary ones. We propose heuristics that provide a guidance for planners about what (critical) actions and in which order have to be applied in a good plan. We empirically evaluate our approach in terms of quality of generated strategies (by leveraging Double Oracle) and CPU time required to generated such strategies.

Details

ICAPS Conference 2020 Conference Paper

Strengthening Potential Heuristics with Mutexes and Disambiguations

Daniel Fiser
Rostislav Horcík
Antonín Komenda

Potential heuristics assign a numerical value (potential) to each fact and compute the heuristic value for a given state as the sum of these potentials. A mutex is an invariant stating that a certain combination of facts cannot be part of any reachable state. In this paper, we use mutexes to improve potential heuristics in two ways. First, we show that the mutex-based disambiguations of the goal and preconditions of operators leads to a less constrained linear program yielding stronger heuristics. Second, we utilize mutexes in a construction of new optimization functions based on counting of the number of states containing certain sets of facts. The experimental evaluation shows a significant increase in the number of solved tasks.

Details

CSL Conference 2017 Conference Paper

An Algebraic Approach to Valued Constraint Satisfaction

Rostislav Horcík
Tommaso Moraschini
Amanda Vidal

We study the complexity of the valued CSP (VCSP, for short) over arbitrary templates, taking the general framework of integral bounded linearly order monoids as valuation structures. The class of problems considered here subsumes and generalizes the most common one in VCSP literature, since both monoidal and lattice conjunction operations are allowed in the formulation of constraints. Restricting to locally finite monoids, we introduce a notion of polymorphism that captures the pp-definability in the style of Geiger’s result. As a consequence, sufficient conditions for tractability of the classical CSP, related to the existence of certain polymorphisms, are shown to serve also for the valued case. Finally, we establish the dichotomy conjecture for the VCSP, modulo the dichotomy for classical CSP.

Details