Altruistic coordination for multi-robot cooperative pathfinding

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

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

When multiple robots perform tasks in a shared workspace, they might be confronted with the risk of blocking each other’s ways, which will lead to conflicts or interference among them. Planning collision-free paths for all the robots is a challenge for a multi-robot system, which is also known as 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 the other robots. In this paper, we present a novel fully decentralized approach to this problem. Our approach allows robots to make real-time responses to dynamic environments and can resolve a set of benchmark deadlock situations subject to complex spatial constraints in a shared workspace by means of altruistic coordination. Specifically, when confronted with congested situations, each robot can employ waiting, moving-forwards, dodging, retreating and turning-head strategies to make local adjustments. Most importantly, each robot only needs to coordinate and communicate with the others that are located within its coordinated network in our approach, which can reduce communication overhead in fully decentralized multi-robot systems. In addition, experimental results also show that our proposed approach provides an efficient and competitive solution to this problem.

Original languageEnglish
Pages (from-to)269-281
Number of pages13
JournalApplied Intelligence
Volume44
Issue number2
DOIs
Publication statusPublished - 1 Mar 2016
Externally publishedYes

Keywords

  • Collision avoidance
  • Cooperative pathfinding
  • Coordination
  • Multi-robot systems

Fingerprint Dive into the research topics of 'Altruistic coordination for multi-robot cooperative pathfinding'. Together they form a unique fingerprint.

Cite this