.png){kind=icon}
Return
Customer satisfaction optimization in due-aware multi-agent path finding
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ins.2025.122782.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we formalize the due-aware multi-agent path finding (DA-MAPF) by integrating temporal constraints into the classical multi-agent path finding problem. Finding optimal solutions for the DA-MAPF problem is NP-hard. To tackle this, we introduce two search-based algorithms: the optimal Due-Aware Conflict-Based Search (DA-CBS) and the bounded suboptimal Satisfaction-Based Search (SBS). Despite their effectiveness, both algorithms face scalability challenges in high-agent-density scenarios. To overcome these limitations, we introduce a reinforcement learning-based algorithm, called Priority-aware Dynamic Communication Learning (PDCL), which incorporates a novel multi-agent communication message aggregation mechanism, two-head priority-aware graph dynamic attention network. We conduct empirical evaluations of the DA-CBS, SBS and PDCL algorithms using a range of benchmark maps. Our evaluations demonstrate that the SBS algorithm performs nearly optimally and achieves higher success rates, particularly in environments with dense obstacles. PDCL provides acceptable solutions more quickly in dense agent scenarios. Furthermore, PDCL surpasses existing multi-agent path finding algorithms by delivering higher average customer satisfaction in the DA-MAPF problem. Additionally, the two-head priority-aware graph dynamic attention network within PDCL outperforms other methods in multi-agent communication.
Keywords:
Multi-agent systems
Path planning for multiple agents
Collision avoidance
Temporal constraints
Journal
IF:
6.8
Papers:
553
Citations:
6.2W
Organization
Cited Papers
.png){kind=icon}
ShareSaveShareSave
View more