Scheduling Models for Multi-Agent Path Finding

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10372051" target="_blank" >RIV/00216208:11320/17:10372051 - isvavai.cz</a>

Výsledek na webu

<a href="http://svancara.net/files/MISTA_2017_paper_44.pdf" target="_blank" >http://svancara.net/files/MISTA_2017_paper_44.pdf</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Scheduling Models for Multi-Agent Path Finding

Popis výsledku v původním jazyce

Multi-agent path finding (MAPF) deals with the problem of finding a colli- sion free path for a set of agents. The agents are located at nodes of a directed graph, they can move over the arcs, and each agent has its own destination node. It is not possible for two agents to be at the same node at the same time. This paper suggests to model the MAPF problem using scheduling techniques, namely, nodes are seen as unary resources. We present three models of the problem. One model is motivated by network flows, another model uses classical unary resource constraints together with path constraints, and the last model works with optional activities. We compare the efficiency of models experimentally.

Název v anglickém jazyce

Scheduling Models for Multi-Agent Path Finding

Popis výsledku anglicky

Multi-agent path finding (MAPF) deals with the problem of finding a colli- sion free path for a set of agents. The agents are located at nodes of a directed graph, they can move over the arcs, and each agent has its own destination node. It is not possible for two agents to be at the same node at the same time. This paper suggests to model the MAPF problem using scheduling techniques, namely, nodes are seen as unary resources. We present three models of the problem. One model is motivated by network flows, another model uses classical unary resource constraints together with path constraints, and the last model works with optional activities. We compare the efficiency of models experimentally.

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/8G15027" target="_blank" >8G15027: INTEGRACE HEURISTICKÉHO PROHLEDÁVÁNÍ A KOMPILAČNÍCH TECHNIK PRO HLEDÁNÍ CEST S MNOHA AGENTY</a><br>

Návaznosti

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

Rok uplatnění

2017

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

Proceedings of the 8th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2017)

ISBN

—

ISSN

2305-249X

e-ISSN

neuvedeno

Počet stran výsledku

12

Strana od-do

189-200

Název nakladatele

Neuveden

Místo vydání

Neuveden

Místo konání akce

Kuala Lumpur, Malaysia

Datum konání akce

5. 12. 2017

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

WRD - Celosvětová akce

Kód UT WoS článku

—