Author name cluster

David Klaška

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

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

Highlights Conference 2020 Conference Abstract

Adversarial Patrolling with Drones

David Klaška

We investigate adversarial patrolling where the Defender is an autonomous device with a limited energy resource (e. g. , a drone). Every eligible Defender’s policy must prevent draining the energy resource before arriving to a refill station, and this constraint substantially complicates the problem of computing an efficient Defender’s policy. Furthermore, the existing infinite-horizon models assume Attackers with unbounded patience willing to wait arbitrarily long for a good attack opportunity. We show this assumption is inappropriate in the setting with drones because here the expected waiting time for an optimal attack opportunity can be extremely large. To overcome this problem, we introduce and justify a new concept of impatient Attacker, and design a polynomial time algorithm for computing a Defender’s policy achieving protection close to the optimal value against an impatient Attacker. Since our algorithm can quickly evaluate the protection achievable for various topologies of refill stations, we can also optimize their displacement. We implement the algorithm and demonstrate its functionality on instances of realistic size.

Details

Highlights Conference 2019 Conference Abstract

Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games

David Klaška
Antonín Kučera
Tomáš Lamser
Vojtěch Řehák.

We give a polynomial-time algorithm for synthesizing efficient regular strategies in adversarial patrolling games with general topology. Regular strategies use finite memory to gather some relevant information about the history of Defender’s moves which results in substantially better protection of the targets. So far, the scope of automatic strategy synthesis was limited to positional strategies (which ignore the history) or to regular strategies where the underlying finite-memory observer had to be supplied \emph{manually}. Furthermore, the existing methods do not give any information on how far are the constructed strategies from being optimal. In this paper, we try to overcome these limitations. We develop a novel \emph{gradient-based} algorithm for synthesizing regular strategies where the underlying finite-memory observers are constructed \emph{algorithmically}. The running time of our algorithm is \emph{polynomial} which makes the algorithm applicable to instances of \emph{realistic size}. Furthermore, we develop an algorithm for computing an \emph{upper bound} on the best achievable protection, and compare the quality of the constructed strategies against this bound. Thus, we can effectively measure the “distance” of the constructed strategies from optimal strategies, and our experiments show that this distance is often quite small.

Details