Towards Smart Behavior of Agents in Evacuation Planning Based on Local Cooperative Path Finding

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F19%3A00348035" target="_blank" >RIV/68407700:21240/19:00348035 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/chapter/10.1007%2F978-3-030-66196-0_14" target="_blank" >https://link.springer.com/chapter/10.1007%2F978-3-030-66196-0_14</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Towards Smart Behavior of Agents in Evacuation Planning Based on Local Cooperative Path Finding

Popis výsledku v původním jazyce

We address engineering of smart behavior of agents in evacuation problems from the perspective of cooperative path finding (CPF) in this paper.We introduce an abstract version of evacuation problems we call multi-agent evacuation (MAE) that consists of an undirected graph representing the map of the environment and a set of agents moving in this graph. The task is to move agents from the endangered part of the graph into the safe part as quickly as possible. Although the abstract evacuation task can be solved using centralized algorithms based on network flows that are near-optimal with respect to various objectives, such algorithms would hardly be applicable in practice since real agents will not be able to follow the centrally created plan. Therefore we designed a decentralized evacuation planning algorithm called LC-MAE based on local rules derived from local cooperative path finding (CPF) algorithms. We compared LC-MAE with near-optimal centralized algorithm using agent-based simulations in multiple real-life scenarios. Our finding it that LC-MAE produces solutions that are only worse than the optimum by a small factor. Moreover our approach led to important observations about how many agents need to behave rationally to increase the speed of evacuation. A small fraction of rational agents can speed up the evacuation dramatically.

Název v anglickém jazyce

Towards Smart Behavior of Agents in Evacuation Planning Based on Local Cooperative Path Finding

Popis výsledku anglicky

We address engineering of smart behavior of agents in evacuation problems from the perspective of cooperative path finding (CPF) in this paper.We introduce an abstract version of evacuation problems we call multi-agent evacuation (MAE) that consists of an undirected graph representing the map of the environment and a set of agents moving in this graph. The task is to move agents from the endangered part of the graph into the safe part as quickly as possible. Although the abstract evacuation task can be solved using centralized algorithms based on network flows that are near-optimal with respect to various objectives, such algorithms would hardly be applicable in practice since real agents will not be able to follow the centrally created plan. Therefore we designed a decentralized evacuation planning algorithm called LC-MAE based on local rules derived from local cooperative path finding (CPF) algorithms. We compared LC-MAE with near-optimal centralized algorithm using agent-based simulations in multiple real-life scenarios. Our finding it that LC-MAE produces solutions that are only worse than the optimum by a small factor. Moreover our approach led to important observations about how many agents need to behave rationally to increase the speed of evacuation. A small fraction of rational agents can speed up the evacuation dramatically.

Druh

D - Stať ve sborníku

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/GA19-17966S" target="_blank" >GA19-17966S: intALG-MAPFg: Inteligentní algoritmy pro zobecněné varianty multi-agetního hledání cest</a><br>

Návaznosti

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

Rok uplatnění

2019

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ů

Název statě ve sborníku

Knowledge Discovery, Knowledge Engineering and Knowledge Management - 11th International Joint Conference (IC3K/KEOD 2020), Revised Selected Papers

ISBN

978-3-030-66195-3

ISSN

—

e-ISSN

—

Počet stran výsledku

20

Strana od-do

302-321

Název nakladatele

Springer-Verlag

Místo vydání

Berlin

Místo konání akce

Vídeň

Datum konání akce

17. 9. 2019

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—