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%2F68407700%3A21730%2F18%3A00323840" target="_blank" >RIV/68407700:21730/18:00323840 - isvavai.cz</a>

Result on the web

<a href="http://www.ifaamas.org/Proceedings/aamas2018/pdfs/p748.pdf" target="_blank" >http://www.ifaamas.org/Proceedings/aamas2018/pdfs/p748.pdf</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

—

Continuities

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

Proceedings of International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018)

ISBN

978-1-4503-5649-7

ISSN

1548-8403

e-ISSN

2523-5699

Number of pages

9

Pages from-to

748-756

Publisher name

IFAAMAS

Place of publication

County of Richland

Event location

Stockholm

Event date

Jul 10, 2018

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000468231300091