Heuristically Guided Compilation for Multi-Agent Path Finding

• URL: http://arxiv.org/abs/2212.06940v1
• Date: Tue, 13 Dec 2022 23:19:15 GMT
• Title: Heuristically Guided Compilation for Multi-Agent Path Finding
• Authors: Pavel Surynek
• Abstract summary: We focus on compilation-based solvers in which the MAPF problem is expressed in a different well established formalism. We show in this work how the build a MAPF encoding for the target SAT solver in which domain specific knowledge is reflected. The conducted experiments show that guided compilation outperforms the vanilla variants of the SAT-based MAPF solver.
• Score: 15.99072005190786
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-agent path finding (MAPF) is a task of finding non-conflicting paths connecting agents' specified initial and goal positions in a shared environment. We focus on compilation-based solvers in which the MAPF problem is expressed in a different well established formalism such as mixed-integer linear programming (MILP), Boolean satisfiability (SAT), or constraint programming (CP). As the target solvers for these formalisms act as black-boxes it is challenging to integrate MAPF specific heuristics in the MAPF compilation-based solvers. We show in this work how the build a MAPF encoding for the target SAT solver in which domain specific heuristic knowledge is reflected. The heuristic knowledge is transferred to the SAT solver by selecting candidate paths for each agent and by constructing the encoding only for these candidate paths instead of constructing the encoding for all possible paths for an agent. The conducted experiments show that heuristically guided compilation outperforms the vanilla variants of the SAT-based MAPF solver.

Related papers

• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale [46.35418789518417]
  Multi-agent pathfinding is a challenging computational problem that typically requires to find collision-free paths for multiple agents in a shared environment. We have created a foundation model for the MAPF problems called MAPF-GPT. Using imitation learning, we have trained a policy on a set of sub-optimal expert trajectories that can generate actions in conditions of partial observability. We show that MAPF-GPT notably outperforms the current best-performing learnable-MAPF solvers on a diverse range of problem instances.
  arXiv  Detail & Related papers  (2024-08-29T12:55:10Z)
• 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)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  Multi-Agent Pathfinding problem involves finding a set of conflict-free paths for a group of agents confined to a graph. In this study, we focus on the decentralized MAPF setting, where the agents may observe the other agents only locally. We propose a decentralized multi-agent Monte Carlo Tree Search (MCTS) method for MAPF tasks.
  arXiv  Detail & Related papers  (2023-12-26T06:57:22Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
  arXiv  Detail & Related papers  (2023-07-25T12:33:53Z)
• Semi-DETR: Semi-Supervised Object Detection with Detection Transformers [105.45018934087076]
  We analyze the DETR-based framework on semi-supervised object detection (SSOD) We present Semi-DETR, the first transformer-based end-to-end semi-supervised object detector. Our method outperforms all state-of-the-art methods by clear margins.
  arXiv  Detail & Related papers  (2023-07-16T16:32:14Z)
• Counterexample Guided Abstraction Refinement with Non-Refined Abstractions for Multi-Agent Path Finding [15.99072005190786]
  We propose a novel CEGAR-style solver for MAPF based on SAT in which some abstractions are deliberately left non-refined. Non-refining however yields order-of-magnitude smaller SAT encodings than those of the previous approach.
  arXiv  Detail & Related papers  (2023-01-20T17:18:49Z)
• Conflict-Based Search for Explainable Multi-Agent Path Finding [7.734726150561088]
  In safety-critical applications, a human supervisor may want to verify that the plan is indeed collision-free. MAPF problem asks for a set of non-colliding paths that admits a short-enough explanation. Traditional MAPF algorithms are not equipped to directly handle explainable-MAPF. We adapt Conflict Based Search (CBS), a well-studied algorithm for MAPF, to handle explainable MAPF.
  arXiv  Detail & Related papers  (2022-02-20T23:13:14Z)
• DPLL(MAPF): an Integration of Multi-Agent Path Finding and SAT Solving Technologies [7.766921168069532]
  In multi-agent path finding (MAPF), the task is to find non-conflicting paths for multiple agents. We present a novel compilation scheme called DPLL(MAPF) in which the consistency checking of partial assignments of decision variables is integrated directly into the SAT solver.
  arXiv  Detail & Related papers  (2021-11-11T23:06:00Z)
• Compilation-based Solvers for Multi-Agent Path Finding: a Survey, Discussion, and Future Opportunities [7.766921168069532]
  We show the lessons learned from past developments and current trends in the topic and discuss its wider impact. Two major approaches to optimal MAPF solving include (1) dedicated search-based methods, which solve MAPF directly, and (2) compilation-based methods that reduce a MAPF instance to an instance in a different well established formalism.
  arXiv  Detail & Related papers  (2021-04-23T20:13:12Z)

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.