Author name cluster

Vojtech Rehak

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.

4 papers

1 author row

Highlights Conference 2023 Conference Abstract

Mean Payoff Optimization for Systems of Periodic Service and Maintenance

Vojtech Rehak

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. This is a joint work with David Klaška, Antonín Kučera, and Vít Musil and it has been accepted as a full paper for the main track of the IJCAI 2023 conference. Contributed talk given by Vojtech Rehak

Details

IJCAI Conference 2022 Conference Paper

General Optimization Framework for Recurrent Reachability Objectives

David Klaska
Antonin Kucera
Vit Musil
Vojtech Rehak

We consider the mobile robot path planning problem for a class of recurrent reachability objectives. These objectives are parameterized by the expected time needed to visit one position from another, the expected square of this time, and also the frequency of moves between two neighboring locations. We design an efficient strategy synthesis algorithm for recurrent reachability objectives and demonstrate its functionality on non-trivial instances.

PDF Details DOI

IJCAI Conference 2018 Conference Paper

Solving Patrolling Problems in the Internet Environment

Tomas Brazdil
Antonin Kucera
Vojtech Rehak

We propose an algorithm for constructing efficient patrolling strategies in the Internet environment, where the protected targets are nodes connected to the network and the patrollers are software agents capable of detecting/preventing undesirable activities on the nodes. The algorithm is based on a novel compositional principle designed for a special class of strategies, and it can quickly construct (sub)optimal solutions even if the number of targets reaches hundreds of millions.

PDF Details

Highlights Conference 2014 Conference Abstract

Solving Adversarial Patrolling Games with Bounded Error

Vojtech Rehak

Patrolling games are partially observable games played by two players, the defender and the attacker. The defender aims for detecting intrusions into vulnerable targets by following randomized routes among them. The time needed to complete an intrusion at each target is finite, and the aim of the attacker is to maximize the probability of a successful (i. e. , undetected) intrusion. The attacker knows the defender's strategy and may observe her moves and her current position. We show how to translate patrolling games into turn-based perfect information stochastic games with safety objectives so that optimal strategies in the perfect information games can be transferred back to patrolling games. We design, to the best of our knowledge, the first algorithm which can compute an ε -optimal strategy for the defender among all (history-dependent) strategies.

PDF Details