提出冲突感知缓存框架，显著加速多智能体路径规划。
CAHC:A General Conflict-Aware Heuristic Caching Framework for Multi-Agent Path Finding
- 基于状态与冲突上下文双重信息缓存启发式值
- 平均提速2.46倍，求解成功率提升至84.8%
- 适用于各类基于约束的路径规划算法
多智能体路径规划（MAPF）算法在处理类车机器人和网格场景时，因启发式计算开销大而面临严重计算挑战。传统启发式缓存假设启发函数仅依赖状态，但在基于约束的搜索算法（如CBS、MAPF-LNS、MAP2）中，冲突消解产生的约束使搜索空间具有上下文依赖性，此假设不成立。本文提出 extbf{CAHC}（冲突感知启发式缓存）通用框架，基于状态与相关约束上下文共同缓存启发式值，解决这一根本局限。通过在类车机器人场景下的CL-CBS案例研究，结合冲突感知缓存与自适应混合启发式，构建 extbf{CAR-CHASE}（Car-Like Robot Conflict-Aware Heuristic Adaptive Search Enhancement）。关键创新包括：(1) 紧凑的 extit{冲突指纹}，高效编码影响状态启发式的约束；(2) 基于空间、时间、几何标准的领域可调相关性过滤器；(3) 模块化架构，支持在多种MAPF算法中系统应用。在480个CL-CBS基准实例上评估显示，几何均值提速2.46×，保持解最优性。成功率达84.8%（原77.9%），总运行时间减少70.1%，可求解额外33个实例。该框架通用性强，可作为可靠优化手段应用于MAP2、MAPF-LNS等约束型MAPF算法。
原文摘要 · Abstract (English)
Multi-Agent Path Finding (MAPF) algorithms, including those for car-like robots and grid-based scenarios, face significant computational challenges due to expensive heuristic calculations. Traditional heuristic caching assumes that the heuristic function depends only on the state, which is incorrect in constraint-based search algorithms (e.g., CBS, MAPF-LNS, MAP2) where constraints from conflict resolution make the search space context-dependent. We propose \textbf{CAHC} (Conflict-Aware Heuristic Caching), a general framework that caches heuristic values based on both state and relevant constraint context, addressing this fundamental limitation. We demonstrate CAHC through a case study on CL-CBS for car-like robots, where we combine conflict-aware caching with an adaptive hybrid heuristic in \textbf{CAR-CHASE} (Car-Like Robot Conflict-Aware Heuristic Adaptive Search Enhancement). Our key innovations are (1) a compact \emph{conflict fingerprint} that efficiently encodes which constraints affect a state's heuristic, (2) a domain-adaptable relevance filter using spatial, temporal, and geometric criteria, and (3) a modular architecture that enables systematic application to diverse MAPF algorithms. Experimental evaluation on 480 CL-CBS benchmark instances demonstrates a geometric mean speedup of 2.46$\times$ while maintaining solution optimality. The optimizations improve success rate from 77.9\% to 84.8\% (+6.9 percentage points), reduce total runtime by 70.1\%, and enable solving 33 additional instances. The framework's general architecture makes it applicable as a reliable optimization technique for MAP2, MAPF-LNS, and other constraint-based MAPF algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。