Towards Generating Effective Plans in Zero-sum Games by Estimating Strategy ofan Adversary

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00347228" target="_blank" >RIV/68407700:21230/20:00347228 - isvavai.cz</a>

Výsledek na webu

<a href="https://plansig2020.files.wordpress.com/2020/12/plansig_2020_paper_5.pdf" target="_blank" >https://plansig2020.files.wordpress.com/2020/12/plansig_2020_paper_5.pdf</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Towards Generating Effective Plans in Zero-sum Games by Estimating Strategy ofan Adversary

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Towards Generating Effective Plans in Zero-sum Games by Estimating Strategy ofan Adversary

Popis výsledku anglicky

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.

Druh

O - Ostatní výsledky

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA18-07252S" target="_blank" >GA18-07252S: MoRePlan: Modelování a reformulace plánovacích problémů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů