A Decentralized Token-Based Negotiation Approach for Multi-Agent Path Finding

Cihan Eran*, M. Onur Keskin, Furkan Cantürk, Reyhan Aydoğan

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

2 Citations (Scopus)


This paper introduces a negotiation approach to solve the Multi-Agent Path Finding problem. The approach aims to achieve a good trade-off between the privacy of the agents and the effectiveness of solutions. Accordingly, a token-based bilateral negotiation protocol and a compatible negotiation strategy are presented. The proposed approach is evaluated in a variety of scenarios by comparing it with state-of-the-art centralized approaches such as Conflict Based Search and its variant. The experimental results showed that the proposed approach can find conflict-free path solutions with a higher success rate, especially when the search space is large and high-density compared to centralized approaches while the gap between path cost differences is reasonably low. The proposed approach enables agents to have their autonomy; thus, it is convenient for MAPF problems involving self-interested agents.

Original languageEnglish
Title of host publicationMulti-Agent Systems - 18th European Conference, EUMAS 2021, Revised Selected Papers
EditorsAriel Rosenfeld, Nimrod Talmon
Number of pages17
ISBN (Print)9783030822538
Publication statusPublished - 2021
Event18th European Conference on Multi-Agent Systems, EUMAS 2021 - Virtual, Online
Duration: 28 Jun 202129 Jun 2021

Publication series

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


Conference18th European Conference on Multi-Agent Systems, EUMAS 2021
CityVirtual, Online


  • Decentralized coordination
  • Multi-Agent Path Finding
  • Negotiation
  • Self-interested agents


Dive into the research topics of 'A Decentralized Token-Based Negotiation Approach for Multi-Agent Path Finding'. Together they form a unique fingerprint.

Cite this