Karel Horák
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Karel Horák has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- Branislav Bosansky
Dept. of Computer Science Faculty of Electrical Engineering Czech Technical University Prague Czech Republic
3 shared publications Branislav Bošanský
Czech Technical University in Prague
2 shared publications- Charles Kamhoua
DEVCOM Army Research Laboratory
1 shared publication - Christopher Kiekintveld
University of Texas at El Paso
1 shared publication - Jiri Cermak
Dept. of Computer Science Faculty of Electrical Engineering Czech Technical University Prague Czech Republic
1 shared publication - Michal Pechoucek
Dept. of Computer Science Faculty of Electrical Engineering Czech Technical University Prague Czech Republic
1 shared publication
Latest Publications
- Open Access
Compact Representation of Value Function in Partially Observable Stochastic Games
Value methods for solving stochastic games with partial observability model the uncertainty about states of the game as a probability distribution over possible states. The dimension of this belief space is the number of states. For many practical problems, for example in security, there are exponentially many possible states which causes an insufficient scalability of algorithms for real-world problems. To this end, we propose an abstraction technique that addresses this issue of the curse of dimensionality by projecting high-dimensional beliefs to characteristic vectors of significantly lower dimension (e.g., marginal probabilities). Our two main contributions are (1) novel compact representation of the uncertainty in partially observable stochastic games and (2) novel algorithm based on this compact representation that is based on existing state-of-the-art algorithms for solving stochastic games with partial observability. Experimental evaluation confirms that the new algorithm over the compact representation dramatically increases the scalability compared to the state of the art.
Open AccessCompact Representation of Value Function in Partially Observable Stochastic Games
Value methods for solving stochastic games with partial observability model the uncertainty about states of the game as a probability distribution over possible states. The dimension of this belief space is the number of states. For many practical problems, for example in security, there are exponentially many possible states which causes an insufficient scalability of algorithms for real-world problems. To this end, we propose an abstraction technique that addresses this issue of the curse of dimensionality by projecting high-dimensional beliefs to characteristic vectors of significantly lower dimension (e.g., marginal probabilities). Our two main contributions are (1) novel compact representation of the uncertainty in partially observable stochastic games and (2) novel algorithm based on this compact representation that is based on existing state-of-the-art algorithms for solving stochastic games with partial observability. Experimental evaluation confirms that the new algorithm over the compact representation dramatically increases the scalability compared to the state of the art.
- 4 October 2017
- Published by Springer Nature
- p. 273-294
Manipulating Adversary’s Belief: A Dynamic Game Approach to Deception by Design for Proactive Network Security
- 4 October 2017
- Published by Springer Nature
- p. 273-294
Manipulating Adversary’s Belief: A Dynamic Game Approach to Deception by Design for Proactive Network Security
- Open Access
Computing Maxmin Strategies in Extensive-Form Zero-Sum Games with Imperfect Recall
Extensive-form games with imperfect recall are an important game-theoretic model that allows a compact representation of strategies in dynamic strategic interactions. Practical use of imperfect recall games is limited due to negative theoretical results: a Nash equilibrium does not have to exist, computing maxmin strategies is NP-hard, and they may require irrational numbers. We present the first algorithm for approximating maxmin strategies in two-player zero-sum imperfect recall games without absentmindedness. We modify the well-known sequence-form linear program to model strategies in imperfect recall games and use a recent technique to approximate bilinear terms. Our main algorithm is a branch-and-bound search over these linear programs that provably reaches a desired approximation after an exponential number of steps in the size of the game. Experimental evaluation shows that the proposed algorithm can approximate maxmin strategies of randomly generated imperfect recall games of sizes beyond toy-problems within few minutes.
Open AccessComputing Maxmin Strategies in Extensive-Form Zero-Sum Games with Imperfect Recall
Extensive-form games with imperfect recall are an important game-theoretic model that allows a compact representation of strategies in dynamic strategic interactions. Practical use of imperfect recall games is limited due to negative theoretical results: a Nash equilibrium does not have to exist, computing maxmin strategies is NP-hard, and they may require irrational numbers. We present the first algorithm for approximating maxmin strategies in two-player zero-sum imperfect recall games without absentmindedness. We modify the well-known sequence-form linear program to model strategies in imperfect recall games and use a recent technique to approximate bilinear terms. Our main algorithm is a branch-and-bound search over these linear programs that provably reaches a desired approximation after an exponential number of steps in the size of the game. Experimental evaluation shows that the proposed algorithm can approximate maxmin strategies of randomly generated imperfect recall games of sizes beyond toy-problems within few minutes.
- 5 October 2016
- Published by Springer Nature
- p. 435-454
A Point-Based Approximate Algorithm for One-Sided Partially Observable Pursuit-Evasion Games
- 5 October 2016
- Published by Springer Nature
- p. 435-454
A Point-Based Approximate Algorithm for One-Sided Partially Observable Pursuit-Evasion Games
- Open Access
Dynamic Programming for One-Sided Partially Observable Pursuit-Evasion Games
Pursuit-evasion scenarios appear widely in robotics, security domains, and many other real-world situations. We focus on two-player pursuit-evasion games with concurrent moves, infinite horizon, and discounted rewards. We assume that the players have a partial observability, however, the evader is given an advantage of knowing the current position of the units of the pursuer. This setting is particularly interesting for security domains where a robust strategy, designed to maximize the utility in the worst-case scenario, is often desirable. We provide, to the best of our knowledge, the first algorithm that provably converges to the value of a partially observable pursuit-evasion game with infinite horizon. Our algorithm extends well-known value iteration algorithm by exploiting that (1) the value functions of our game depend only on position of the pursuer and the belief he has about the current position of the evader, and (2) that these functions are piecewise linear and convex in the belief space.
Open AccessDynamic Programming for One-Sided Partially Observable Pursuit-Evasion Games
Pursuit-evasion scenarios appear widely in robotics, security domains, and many other real-world situations. We focus on two-player pursuit-evasion games with concurrent moves, infinite horizon, and discounted rewards. We assume that the players have a partial observability, however, the evader is given an advantage of knowing the current position of the units of the pursuer. This setting is particularly interesting for security domains where a robust strategy, designed to maximize the utility in the worst-case scenario, is often desirable. We provide, to the best of our knowledge, the first algorithm that provably converges to the value of a partially observable pursuit-evasion game with infinite horizon. Our algorithm extends well-known value iteration algorithm by exploiting that (1) the value functions of our game depend only on position of the pursuer and the belief he has about the current position of the evader, and (2) that these functions are piecewise linear and convex in the belief space.