Negotiation-based decentralized conflict resolution in multi-agent path finding

Abstract

This thesis addresses the problem of Multi-Agent Path Finding problem where multiple agents aim to reach their destination in a grid world without any colli sion. It aims to provide a solution achieving good trade-off between the privacy of the agents and the effectiveness of solutions. Accordingly, a token-based bilateral negotiation approach is presented to solve this problem in a distributed way. The proposed approach is evaluated empirically in various scenarios by comparing it with state-of-the-art centralized approaches such as Conflict Based Search and its variants. The experimental results showed that the proposed approach can find conflict-free path solutions albeit suboptimally, especially when the search space is large and high-density, whereas centralized approaches struggle to find optimal solutions. Despite being outperformed by suboptimal centralized solvers, the pro posed decentralized approach can achieve considerable results with naive agents by sharing minimal information about themselves. The proposed approach also enables agents to have their autonomy; thus, the proposed approach is convenient for MAPF problems involving self-interested agents.Bu tez, coklu etmenli sistemlerde yol planlamas problemine, muzakere yontemi tabanl bir yakla s m geli stirmeyi hede iyor. Bu yakla s mda, sistemdeki etkenlerin verilerinin gizlili gi ve cozumlerin efekti i gi aras nda kayda de ger bir denge kurulmas ama clanm st r. Bunun i cin, jeton tabanl ikili muzakere protokolu ve bu protokol ile uyumlu muzakere stratejileri sunulmaktad r. Onerilen yakla s m, ce sitli senaryolarda, C ak sma Tabanl Arama (CBS) ve benzer geli smi s merkezi sonu c uretme cozumlerine kar s sonu clar de gerlendirilmi stir. Deney sonu clar nda sunulan da g t k sorun cozme yakla s m n n merkezil cozum yakla s mlar na kar s n kayda de ger sonu clar uretebildi gini gostermektedir. Onerilen yakla s m, sistem etmenlerinin kendi karar vermelerini sa glamaktad r. Bu sebepten oturu, bu yakla s m, bireyselli gini gerektiren durumlar i cin idealdir.