Multi-robot cooperative pathfinding: A decentralized approach

Changyun Wei, Koen V. Hindriks, Catholijn M. Jonker

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

When robots perform teamwork in a shared workspace, they might be confronted with the risk of blocking each other's ways, which will result in conflicts or interference among the robots. How to plan collision-free paths for all the robots is the major challenge issue in the multi-robot cooperative pathfinding problem, in which each robot has to navigate from its starting location to the destination while keeping avoiding stationary obstacles as well as its teammates. In this paper, we present a novel fully decentralized approach to this problem. Our approach allows the robots to make real-time responses to the dynamic environment and can resolve a set of benchmark deadlock situations subject to complex spatial constraints in the robots' workspace. When confronted with conflicting situations, robots can employ waiting, dodging, retreating and turning-head strategies to make local adjustments. In addition, experimental results show that our proposed approach provides an efficient and competitive solution to this problem.

Original languageEnglish
Title of host publicationModern Advances in Applied Intelligence
Subtitle of host publication27th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2014, Proceedings
EditorsMoonis Ali, Shyi-Ming Chen, Jeng-Shyang Pan, Mong-Fong Horng
PublisherSpringer/Verlag
Pages21-31
Number of pages11
VolumePart 1
ISBN (Electronic)97833190745-9
ISBN (Print)9783319074542
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event27th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2014 - Kaohsiung, Taiwan, Province of China
Duration: 3 Jun 20146 Jun 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume8481 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2014
CountryTaiwan, Province of China
CityKaohsiung
Period3/06/146/06/14

Fingerprint

Multi-robot
Decentralized
Robot
Robots
Workspace
Team Work
Deadlock
Dynamic Environment
Resolve
Adjustment
Collision
Interference
Benchmark
Real-time
Path
Experimental Results

Keywords

  • collision avoidance
  • Cooperative pathfinding
  • coordination

Cite this

Wei, C., Hindriks, K. V., & Jonker, C. M. (2014). Multi-robot cooperative pathfinding: A decentralized approach. In M. Ali, S-M. Chen, J-S. Pan, & M-F. Horng (Eds.), Modern Advances in Applied Intelligence: 27th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2014, Proceedings (Vol. Part 1, pp. 21-31). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8481 LNAI, No. PART 1). Springer/Verlag. https://doi.org/10.1007/978-3-319-07455-9_3
Wei, Changyun ; Hindriks, Koen V. ; Jonker, Catholijn M. / Multi-robot cooperative pathfinding : A decentralized approach. Modern Advances in Applied Intelligence: 27th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2014, Proceedings. editor / Moonis Ali ; Shyi-Ming Chen ; Jeng-Shyang Pan ; Mong-Fong Horng. Vol. Part 1 Springer/Verlag, 2014. pp. 21-31 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).
@inproceedings{6d1762e83ef247c8a9473eefdced2191,
title = "Multi-robot cooperative pathfinding: A decentralized approach",
abstract = "When robots perform teamwork in a shared workspace, they might be confronted with the risk of blocking each other's ways, which will result in conflicts or interference among the robots. How to plan collision-free paths for all the robots is the major challenge issue in the multi-robot cooperative pathfinding problem, in which each robot has to navigate from its starting location to the destination while keeping avoiding stationary obstacles as well as its teammates. In this paper, we present a novel fully decentralized approach to this problem. Our approach allows the robots to make real-time responses to the dynamic environment and can resolve a set of benchmark deadlock situations subject to complex spatial constraints in the robots' workspace. When confronted with conflicting situations, robots can employ waiting, dodging, retreating and turning-head strategies to make local adjustments. In addition, experimental results show that our proposed approach provides an efficient and competitive solution to this problem.",
keywords = "collision avoidance, Cooperative pathfinding, coordination",
author = "Changyun Wei and Hindriks, {Koen V.} and Jonker, {Catholijn M.}",
year = "2014",
doi = "10.1007/978-3-319-07455-9_3",
language = "English",
isbn = "9783319074542",
volume = "Part 1",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer/Verlag",
number = "PART 1",
pages = "21--31",
editor = "Moonis Ali and Shyi-Ming Chen and Jeng-Shyang Pan and Mong-Fong Horng",
booktitle = "Modern Advances in Applied Intelligence",

}

Wei, C, Hindriks, KV & Jonker, CM 2014, Multi-robot cooperative pathfinding: A decentralized approach. in M Ali, S-M Chen, J-S Pan & M-F Horng (eds), Modern Advances in Applied Intelligence: 27th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2014, Proceedings. vol. Part 1, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 8481 LNAI, Springer/Verlag, pp. 21-31, 27th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2014, Kaohsiung, Taiwan, Province of China, 3/06/14. https://doi.org/10.1007/978-3-319-07455-9_3

Multi-robot cooperative pathfinding : A decentralized approach. / Wei, Changyun; Hindriks, Koen V.; Jonker, Catholijn M.

Modern Advances in Applied Intelligence: 27th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2014, Proceedings. ed. / Moonis Ali; Shyi-Ming Chen; Jeng-Shyang Pan; Mong-Fong Horng. Vol. Part 1 Springer/Verlag, 2014. p. 21-31 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8481 LNAI, No. PART 1).

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Multi-robot cooperative pathfinding

T2 - A decentralized approach

AU - Wei, Changyun

AU - Hindriks, Koen V.

AU - Jonker, Catholijn M.

PY - 2014

Y1 - 2014

N2 - When robots perform teamwork in a shared workspace, they might be confronted with the risk of blocking each other's ways, which will result in conflicts or interference among the robots. How to plan collision-free paths for all the robots is the major challenge issue in the multi-robot cooperative pathfinding problem, in which each robot has to navigate from its starting location to the destination while keeping avoiding stationary obstacles as well as its teammates. In this paper, we present a novel fully decentralized approach to this problem. Our approach allows the robots to make real-time responses to the dynamic environment and can resolve a set of benchmark deadlock situations subject to complex spatial constraints in the robots' workspace. When confronted with conflicting situations, robots can employ waiting, dodging, retreating and turning-head strategies to make local adjustments. In addition, experimental results show that our proposed approach provides an efficient and competitive solution to this problem.

AB - When robots perform teamwork in a shared workspace, they might be confronted with the risk of blocking each other's ways, which will result in conflicts or interference among the robots. How to plan collision-free paths for all the robots is the major challenge issue in the multi-robot cooperative pathfinding problem, in which each robot has to navigate from its starting location to the destination while keeping avoiding stationary obstacles as well as its teammates. In this paper, we present a novel fully decentralized approach to this problem. Our approach allows the robots to make real-time responses to the dynamic environment and can resolve a set of benchmark deadlock situations subject to complex spatial constraints in the robots' workspace. When confronted with conflicting situations, robots can employ waiting, dodging, retreating and turning-head strategies to make local adjustments. In addition, experimental results show that our proposed approach provides an efficient and competitive solution to this problem.

KW - collision avoidance

KW - Cooperative pathfinding

KW - coordination

UR - http://www.scopus.com/inward/record.url?scp=84958533348&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958533348&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-07455-9_3

DO - 10.1007/978-3-319-07455-9_3

M3 - Conference contribution

SN - 9783319074542

VL - Part 1

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 21

EP - 31

BT - Modern Advances in Applied Intelligence

A2 - Ali, Moonis

A2 - Chen, Shyi-Ming

A2 - Pan, Jeng-Shyang

A2 - Horng, Mong-Fong

PB - Springer/Verlag

ER -

Wei C, Hindriks KV, Jonker CM. Multi-robot cooperative pathfinding: A decentralized approach. In Ali M, Chen S-M, Pan J-S, Horng M-F, editors, Modern Advances in Applied Intelligence: 27th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2014, Proceedings. Vol. Part 1. Springer/Verlag. 2014. p. 21-31. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). https://doi.org/10.1007/978-3-319-07455-9_3