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

Result code in 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>

Result on the web

<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

—

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/8G15027" target="_blank" >8G15027: INTEGRATION OF HEURISTIC SEARCH AND COMPILATION-BASED TECHNIQUES FOR MULTI-AGENT PATH-FINDING</a><br>

Continuities

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

Publication year

2018

Confidentiality

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

Article name in the collection

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

Number of pages

9

Pages from-to

748-756

Publisher name

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

Place of publication

Neuveden

Event location

Stockholm, Sweden

Event date

Jul 11, 2018

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—