Multi-Agent Pathfinding with Non-Unit Integer Edge Costs via Enhanced Conflict-Based Search and Graph Discretization

📰 ArXiv cs.AI

Enhanced Conflict-Based Search and Graph Discretization for Multi-Agent Pathfinding with non-unit integer edge costs

advanced Published 8 Apr 2026

Action Steps

Identify the limitations of traditional MAPF methods
Extend MAPF to handle non-unit edge costs and continuous-time actions
Apply Enhanced Conflict-Based Search to reduce conflicts between agents
Use Graph Discretization to bound the state space and improve solver efficiency

Who Needs to Know This

AI engineers and researchers working on multi-agent systems and pathfinding algorithms can benefit from this research to improve the efficiency and applicability of their solutions

Key Insight

💡 Graph Discretization can bound the state space and improve solver efficiency in MAPF with non-unit edge costs

Key Takeaways

Enhanced Conflict-Based Search and Graph Discretization for Multi-Agent Pathfinding with non-unit integer edge costs

Full Article

Title: Multi-Agent Pathfinding with Non-Unit Integer Edge Costs via Enhanced Conflict-Based Search and Graph Discretization

Abstract:
arXiv:2604.05416v1 Announce Type: new Abstract: Multi-Agent Pathfinding (MAPF) plays a critical role in various domains. Traditional MAPF methods typically assume unit edge costs and single-timestep actions, which limit their applicability to real-world scenarios. MAPFR extends MAPF to handle non-unit costs with real-valued edge costs and continuous-time actions, but its geometric collision model leads to an unbounded state space that compromises solver efficiency. In this paper, we propose MAPF

Read full paper → ← Back to Reads