CAHC:A General Conflict-Aware Heuristic Caching Framework for Multi-Agent Path Finding

• URL: http://arxiv.org/abs/2512.12243v2
• Date: Sat, 17 Jan 2026 09:48:21 GMT
• Title: CAHC:A General Conflict-Aware Heuristic Caching Framework for Multi-Agent Path Finding
• Abstract summary: We present textbfCAHC (Conflict-Aware Heuristic Caching), a general framework that caches values based on both state and relevant constraint context.<n>We demonstrate CAHC through a case study on CL-CBS for car-like robots, where we combine conflict-aware caching with an adaptive hybrid in textbfCARCHASE (Car-Like Robot Conflict-Aware Heuristic Adaptive Search Enhancement)<n>Our key innovations are (1) a compact emphconflict fingerprint that efficiently encodes which constraints affect a state's context, (2) a domain-adaptable
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• optimize_anything: A Universal API for Optimizing any Text Parameter [98.42497715725356]
  We show a single AI-based optimization system-supporting single-task search, multi-task search with cross-problem transfer, and generalization to unseen inputs.<n>We show for the first time that text optimization with LLM-based search is a general-purpose problem-solving paradigm.
  arXiv  Detail & Related papers  (2026-05-19T10:18:12Z)
• DyACE: Dynamic Algorithm Co-evolution for Online Automated Heuristic Design with Large Language Model [12.490525543266807]
  We introduce DyACE (Dynamic Co-evolution) as a Non-stationary Bi-level Control problem.<n>A core element of DyACE is the Look-Ahead Rollout Search, which queries the landscape geometry to extract Search Tray Features.<n>Results demonstrate that DyACE significantly outperforms state-of-the-art static baselines.
  arXiv  Detail & Related papers  (2026-03-07T06:46:53Z)
• Hyperparameter Optimization of Constraint Programming Solvers [2.4915743991417547]
  We introduce probe and solve algorithm, a framework for automated hyperparameter optimization integrated into the CPMpy library.<n>We evaluate the algorithm on two different constraint solvers, ACE and Choco, across 114 problem instances.<n>Results show that using Bayesian optimization, the algorithm outperforms the solver's default configurations.
  arXiv  Detail & Related papers  (2026-01-16T16:02:36Z)
• Neural Nonmyopic Bayesian Optimization in Dynamic Cost Settings [73.44599934855067]
  LookaHES is a nonmyopic BO framework designed for dynamic, history-dependent cost environments.<n>LookaHES combines a multi-step variant of $H$-Entropy Search with pathwise sampling and neural policy optimization.<n>Our innovation is the integration of neural policies, including large language models, to effectively navigate structured, domain-specific action spaces.
  arXiv  Detail & Related papers  (2026-01-10T09:49:45Z)
• From HNSW to Information-Theoretic Binarization: Rethinking the Architecture of Scalable Vector Search [0.7804710977378487]
  This paper analyzes the architectural limitations of the dominant "HNSW + float32 + cosine similarity" stack.<n>We introduce and empirically evaluate an alternative information-theoretic architecture based on maximally informative binarization (MIB)<n>Results demonstrate retrieval quality comparable to full-precision systems, while achieving substantially lower latency and maintaining constant throughput at high request rates.
  arXiv  Detail & Related papers  (2025-12-16T23:24:37Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  This paper proposes a novel combination of constraint encoding methods for the Quantum Approximate Optimization Ansatz.<n>One-hot constraints are enforced through $XY$-mixers that restrict the search space to the feasible sub-space naturally.<n>Since $XY$-mixers restrict the search space, specific state vector entries are always zero and can be omitted from the simulation, saving valuable memory and computing resources.
  arXiv  Detail & Related papers  (2025-06-03T17:46:53Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations. Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential. We introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms.
  arXiv  Detail & Related papers  (2024-01-30T14:26:04Z)
• Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation [84.0621253654014]
  We propose a framework, called BALLET, which adaptively filters for a high-confidence region of interest. We show theoretically that BALLET can efficiently shrink the search space, and can exhibit a tighter regret bound than standard BO.
  arXiv  Detail & Related papers  (2023-07-25T09:45:47Z)
• AutoSpace: Neural Architecture Search with Less Human Interference [84.42680793945007]
  Current neural architecture search (NAS) algorithms still require expert knowledge and effort to design a search space for network construction. We propose a novel differentiable evolutionary framework named AutoSpace, which evolves the search space to an optimal one. With the learned search space, the performance of recent NAS algorithms can be improved significantly compared with using previously manually designed spaces.
  arXiv  Detail & Related papers  (2021-03-22T13:28:56Z)
• ISTA-NAS: Efficient and Consistent Neural Architecture Search by Sparse Coding [86.40042104698792]
  We formulate neural architecture search as a sparse coding problem. In experiments, our two-stage method on CIFAR-10 requires only 0.05 GPU-day for search. Our one-stage method produces state-of-the-art performances on both CIFAR-10 and ImageNet at the cost of only evaluation time.
  arXiv  Detail & Related papers  (2020-10-13T04:34:24Z)
• Artificial Intelligence Assisted Collaborative Edge Caching in Small Cell Networks [19.605382256630538]
  This paper considers heterogeneous content preference of the users with heterogeneous caching models at the edge nodes. We propose a modified particle swarm optimization (M-PSO) algorithm that efficiently solves the complex constraint problem in a reasonable time.
  arXiv  Detail & Related papers  (2020-05-16T10:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.