Mgr. Pavel Rytíř, Ph.D.

Effective decision making while competing for limited resources in adversarial environments is important for many real-world applications (e.g. two Taxi companies competing for customers). Decision-making techniques such as Automated planning have to take into account possible actions of adversary (or competing) agents. That said, the agent should know what the competitor will likely do and then generate its plan accordingly. In this paper we propose a novel approach for estimating strategies of the adversary (or the competitor), sampling its actions that might hinder agent's goals by interfering with the agent's actions. The estimated competitor strategies are used in plan generation such that agent's actions have to be applied prior to the ones of the competitor, whose estimated times dictate the deadlines. We empirically evaluate our approach leveraging sampling of competitor's actions by comparing it to the naive approach optimizing the make-span (not taking the competing agent into account at all) and to Nash Equilibrium (mixed) strategies.

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.

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.

Effective plan generation in adversarial environments has totake 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 estimatingstrategies of the adversary, sampling actions that interferewith the agent’s ones. The estimated competitor strategies areused in plan generation by considering that agent’s actionshave to be applied prior to the ones of the competitor, whoseestimated times dictate the agent’s deadlines. Missing thesedeadlines entails additional plan cost

In real-world scenarios the environment is rarely static. Ex-ogenous events might occur without the consent of the agentacting in such a dynamic environment. Events account foracts of nature without specific intentions, or actions of otheragents having their own intentions.Restricting on two actors, an agent applying actions and anenvironment applying events, we, in this paper, elaborate onfive different models of how these actors can interact. Foreach actor, we assume full observability and full knowledgeof actions and events. In particular, we focus on action-eventconflicts that arise from the fact that one actor cannot con-trol the other actor while concerning a classical and temporalsettings.

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.

In a nutshell, zero-sum games represent scenarios where twoagents compete for the same goals such that each goal canbe achieved by at most one of the agents. The goals are, forexample, collecting limited resources or transporting passen-gers from their given location of origin to a required destina-tion. To achieve the goals, the agent might generate a plan.Plan generation, however, has to take possible actions of theadversary into consideration.In this paper, considering planning in zero-sum games, wepropose a heuristic approach for estimating strategies of theadversary, more specifically distribution of possible applica-tion times of its actions interfering with some of the agent’sactions. The agent’s actions in question have to be appliedbefore those of the adversary, whose estimated times hencerepresent their deadlines. Missing the deadlines can be repre-sented by action cost, so generated plans can be optimised forminimum total action cost. We empirically evaluate our ap-proach by comparing it to the baseline approach (plan gener-ation without taking adversary into account) and to the state-of-the-art approach leveraging the Double Oracle algorithmfor computing adversary strategies.

Many problems from classical planning are applied in the environment with other, possibly adversarial agents. However, plans found by classical planning algorithms lack the robustness against the actions of other agents - the quality of computed plans can be significantly worse compared to the model. To explicitly reason about other (adversarial) agents, the game-theoretic framework can be used. The scalability of game-theoretic algorithms, however, is limited and often insufficient for real-world problems. In this paper, we combine classical domain-independent planning algorithms and game-theoretic strategy-generation algorithm where plans form strategies in the game. Our contribution is threefold. First, we provide the methodology for using classical planning in this game-theoretic framework. Second, we analyze the trade-off between the quality of the planning algorithm and the robustness of final randomized plans and the computation time. Finally, we analyze different variants of integration of classical planning algorithms into the game-theoretic framework and show that at the cost a minor loss in the robustness of final plans, we can significantly reduce the computation time.