A Scheduling-Based Approach to Multi-Agent Path Finding with Weighted and Capacitated Arcs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10388811" target="_blank" >RIV/00216208:11320/18:10388811 - isvavai.cz</a>

Výsledek na webu

<a href="https://dl.acm.org/citation.cfm?id=3237494" target="_blank" >https://dl.acm.org/citation.cfm?id=3237494</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

A Scheduling-Based Approach to Multi-Agent Path Finding with Weighted and Capacitated Arcs

Popis výsledku v původním jazyce

Multi-agent path finding (MAPF) deals with the problem of finding a collision-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. The usual setting is that each arc has length one so at any time step, each agent either stays in the node, where it is, or moves to one of its neighboring nodes. This paper suggests to model the MAPF problem using scheduling techniques, namely, nodes and arcs are seen as resources. The concept of optional activities is used to model which nodes and arcs an agent will visit. We first describe a model, where each agent can visit each node at most once. Then, we extend the model to allow agents re-visiting the nodes. The major motivation for the scheduling model of MAPF is its capability to naturally include other constraints. We will study particularly the problems, where the capacity of arcs can be greater than one (more agents can use the same arc at the same time), and the lengths of arcs can be greater than one (moving between different pairs of nodes takes different times). These extensions make the model closer to reality than the original MAPF formulation. We compare the efficiency of models experimentally.

Název v anglickém jazyce

A Scheduling-Based Approach to Multi-Agent Path Finding with Weighted and Capacitated Arcs

Popis výsledku anglicky

Multi-agent path finding (MAPF) deals with the problem of finding a collision-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. The usual setting is that each arc has length one so at any time step, each agent either stays in the node, where it is, or moves to one of its neighboring nodes. This paper suggests to model the MAPF problem using scheduling techniques, namely, nodes and arcs are seen as resources. The concept of optional activities is used to model which nodes and arcs an agent will visit. We first describe a model, where each agent can visit each node at most once. Then, we extend the model to allow agents re-visiting the nodes. The major motivation for the scheduling model of MAPF is its capability to naturally include other constraints. We will study particularly the problems, where the capacity of arcs can be greater than one (more agents can use the same arc at the same time), and the lengths of arcs can be greater than one (moving between different pairs of nodes takes different times). These extensions make the model closer to reality than the original MAPF formulation. 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)<br>S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2018

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

Proc. of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018)

ISBN

978-1-5108-6808-3

ISSN

1548-8403

e-ISSN

neuvedeno

Počet stran výsledku

9

Strana od-do

748-756

Název nakladatele

International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org)

Místo vydání

Neuveden

Místo konání akce

Stockholm, Sweden

Datum konání akce

11. 7. 2018

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

WRD - Celosvětová akce

Kód UT WoS článku

—