Arrow Research search

Author name cluster

Vojtěch Řehá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.

7 papers
1 author row

Possible papers

7

AAAI Conference 2025 Conference Paper

Multiple Mean-Payoff Optimization Under Local Stability Constraints

  • David Klaška
  • Antonín Kučera
  • Vojtěch Kůr
  • Vít Musil
  • Vojtěch Řehák

The long-run average payoff per transition (mean payoff) is the main tool for specifying the performance and dependability properties of discrete systems. The problem of constructing a controller (strategy) simultaneously optimizing several mean payoffs has been deeply studied for stochastic and game-theoretic models. One common issue of the constructed controllers is the instability of the mean payoffs, measured by the deviations of the average rewards per transition computed in a finite "window" sliding along a run. Unfortunately, the problem of simultaneously optimizing the mean payoffs under local stability constraints is computationally hard, and the existing works do not provide a practically usable algorithm even for non-stochastic models such as two-player games. In this paper, we design and evaluate the first efficient and scalable solution to this problem applicable to Markov decision processes.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Optimizing Local Satisfaction of Long-Run Average Objectives in Markov Decision Processes

  • David Klaška
  • Antonín Kučera
  • Vojtěch Kůr
  • Vít Musil
  • Vojtěch Řehák

Long-run average optimization problems for Markov decision processes (MDPs) require constructing policies with optimal steady-state behavior, i.e., optimal limit frequency of visits to the states. However, such policies may suffer from local instability in the sense that the frequency of states visited in a bounded time horizon along a run differs significantly from the limit frequency. In this work, we propose an efficient algorithmic solution to this problem.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Mean Payoff Optimization for Systems of Periodic Service and Maintenance

  • David Klaška
  • Antonín Kučera
  • Vít Musil
  • Vojtěch Řehák

Consider oriented graph nodes requiring periodic visits by a service agent. The agent moves among the nodes and receives a payoff for each completed service task, depending on the time elapsed since the previous visit to a node. We consider the problem of finding a suitable schedule for the agent to maximize its long-run average payoff per time unit. We show that the problem of constructing an epsilon-optimal schedule is PSPACE-hard for every fixed non-negative epsilon, and that there exists an optimal periodic schedule of exponential length. We propose randomized finite-memory (RFM) schedules as a compact description of the agent's strategies and design an efficient algorithm for constructing RFM schedules. Furthermore, we construct deterministic periodic schedules by sampling from RFM schedules.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Synthesizing Resilient Strategies for Infinite-Horizon Objectives in Multi-Agent Systems

  • David Klaška
  • Antonín Kučera
  • Martin Kurečka
  • Vít Musil
  • Petr Novotný
  • Vojtěch Řehák

We consider the problem of synthesizing resilient and stochastically stable strategies for systems of cooperating agents striving to minimize the expected time between consecutive visits to selected locations in a known environment. A strategy profile is resilient if it retains its functionality even if some of the agents fail, and stochastically stable if the visiting time variance is small. We design a novel specification language for objectives involving resilience and stochastic stability, and we show how to efficiently compute strategy profiles (for both autonomous and coordinated agents) optimizing these objectives. Our experiments show that our strategy synthesis algorithm can construct highly non-trivial and efficient strategy profiles for environments with general topology.

PDF Details DOI

AAMAS Conference 2022 Conference Paper

Minimizing Expected Intrusion Detection Time in Adversarial Patrolling

  • David Klaška
  • Antonín Kučera
  • Vit Musil
  • Vojtěch Řehák

In adversarial patrolling games, a mobile Defender strives to discover intrusions at vulnerable targets initiated by an Attacker. The Attacker’s utility is traditionally defined as the probability of completing an attack, possibly weighted by target costs. However, in many real-world scenarios, the actual damage caused by the Attacker depends on the time elapsed since the attack’s initiation to its detection. We introduce a formal model for such scenarios, and we show that the Defender always has an optimal strategy achieving maximal protection. We also prove that finite-memory Defender’s strategies are sufficient for achieving protection arbitrarily close to the optimum. Then, we design an efficient strategy synthesis algorithm based on differentiable programming and gradient descent. We evaluate the efficiency of our method experimentally.

PDF

I&C Journal 2009 Journal Article

Reachability is decidable for weakly extended process rewrite systems

  • Mojmír Křetínský
  • Vojtěch Řehák
  • Jan Strejček

Process rewrite systems (PRS) are widely accepted as a formalism for the description of infinite-state systems. It is known that the reachability problem for PRS is decidable. The problem becomes undecidable when PRS are extended with a finite-state control unit. In this paper, we show that the problem remains decidable when PRS are extended with a weak (i. e. acyclic except for self-loops) finite-state control unit. We also present some applications of this decidability result.

Details DOI
v2026.09.13