Open Access
Open access
volume 2019-August ,  pages 39-45

Multi-agent pathfinding with continuous time

Publication type: Proceedings Article
Publication date: 2019-08-01
Abstract

Multi-Agent Pathfinding (MAPF) is the problem of finding paths for multiple agents such that every agent reaches its goal and the agents do not collide. Most prior work on MAPF were on grids, assumed agents' actions have uniform duration, and that time is discretized into timesteps. In this work, we propose a MAPF algorithm that do not assume any of these assumptions, is complete, and provides provably optimal solutions. This algorithm is based on a novel combination of Safe Interval Path Planning (SIPP), a continuous time single agent planning algorithms, and Conflict-Based Search (CBS). We analyze this algorithm, discuss its pros and cons, and evaluate it experimentally on several standard benchmarks.

Found 

Top-30

Journals

1
2
3
4
5
6
7
8
Lecture Notes in Computer Science
Lecture Notes in Computer Science, 8, 21.62%
Lecture Notes in Computer Science
8 publications, 21.62%
IEEE Transactions on Robotics
IEEE Transactions on Robotics, 2, 5.41%
IEEE Transactions on Robotics
2 publications, 5.41%
ACM Computing Surveys
ACM Computing Surveys, 1, 2.7%
ACM Computing Surveys
1 publication, 2.7%
ACM Transactions on Knowledge Discovery from Data
ACM Transactions on Knowledge Discovery from Data, 1, 2.7%
ACM Transactions on Knowledge Discovery from Data
1 publication, 2.7%
International Journal of Game Theory
International Journal of Game Theory, 1, 2.7%
International Journal of Game Theory
1 publication, 2.7%
Knowledge-Based Systems
Knowledge-Based Systems, 1, 2.7%
Knowledge-Based Systems
1 publication, 2.7%
International Journal of Intelligent Systems
International Journal of Intelligent Systems, 1, 2.7%
International Journal of Intelligent Systems
1 publication, 2.7%
Theory and Practice of Logic Programming
Theory and Practice of Logic Programming, 1, 2.7%
Theory and Practice of Logic Programming
1 publication, 2.7%
Artificial Intelligence
Artificial Intelligence, 1, 2.7%
Artificial Intelligence
1 publication, 2.7%
Communications in Computer and Information Science
Communications in Computer and Information Science, 1, 2.7%
Communications in Computer and Information Science
1 publication, 2.7%
Electronic Proceedings in Theoretical Computer Science, EPTCS, 1, 2.7%
Electronic Proceedings in Theoretical Computer Science, EPTCS
1 publication, 2.7%
Machines
Machines, 1, 2.7%
Machines
1 publication, 2.7%
IEEE Transactions on Neural Networks and Learning Systems
IEEE Transactions on Neural Networks and Learning Systems, 1, 2.7%
IEEE Transactions on Neural Networks and Learning Systems
1 publication, 2.7%
ROBOMECH Journal
ROBOMECH Journal, 1, 2.7%
ROBOMECH Journal
1 publication, 2.7%
1
2
3
4
5
6
7
8

Publishers

2
4
6
8
10
12
14
16
Institute of Electrical and Electronics Engineers (IEEE)
Institute of Electrical and Electronics Engineers (IEEE), 16, 43.24%
Institute of Electrical and Electronics Engineers (IEEE)
16 publications, 43.24%
Springer Nature
Springer Nature, 12, 32.43%
Springer Nature
12 publications, 32.43%
Association for Computing Machinery (ACM)
Association for Computing Machinery (ACM), 2, 5.41%
Association for Computing Machinery (ACM)
2 publications, 5.41%
Elsevier
Elsevier, 2, 5.41%
Elsevier
2 publications, 5.41%
Wiley
Wiley, 1, 2.7%
Wiley
1 publication, 2.7%
Cambridge University Press
Cambridge University Press, 1, 2.7%
Cambridge University Press
1 publication, 2.7%
electronic proceedings in theoretical computer science, eptcs, 1, 2.7%
electronic proceedings in theoretical computer science, eptcs
1 publication, 2.7%
MDPI
MDPI, 1, 2.7%
MDPI
1 publication, 2.7%
2
4
6
8
10
12
14
16
  • We do not take into account publications without a DOI.
  • Statistics recalculated weekly.

Are you a researcher?

Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
37
Share
Cite this
GOST |
Cite this
GOST Copy
Andreychuk A. et al. Multi-agent pathfinding with continuous time // IJCAI International Joint Conference on Artificial Intelligence. 2019. Vol. 2019-August. pp. 39-45.
GOST all authors (up to 50) Copy
Andreychuk A., Yakovlev K., Atzmon D., Stern R. Multi-agent pathfinding with continuous time // IJCAI International Joint Conference on Artificial Intelligence. 2019. Vol. 2019-August. pp. 39-45.
RIS |
Cite this
RIS Copy
TY - CPAPER
DO - 10.24963/ijcai.2019/6
UR - https://doi.org/10.24963/ijcai.2019/6
TI - Multi-agent pathfinding with continuous time
T2 - IJCAI International Joint Conference on Artificial Intelligence
AU - Andreychuk, Anton
AU - Yakovlev, Konstantin
AU - Atzmon, Dor
AU - Stern, Roni
PY - 2019
DA - 2019/08/01
PB - International Joint Conferences on Artificial Intelligence
SP - 39-45
VL - 2019-August
ER -
BibTex
Cite this
BibTex (up to 50 authors) Copy
@inproceedings{2019_Andreychuk,
author = {Anton Andreychuk and Konstantin Yakovlev and Dor Atzmon and Roni Stern},
title = {Multi-agent pathfinding with continuous time},
year = {2019},
volume = {2019-August},
pages = {39--45},
month = {aug},
publisher = {International Joint Conferences on Artificial Intelligence}
}