Compilation-based Solvers for Multi-Agent Path Finding: a Survey, Discussion, and Future Opportunities

• URL: http://arxiv.org/abs/2104.11809v1
• Date: Fri, 23 Apr 2021 20:13:12 GMT
• Title: Compilation-based Solvers for Multi-Agent Path Finding: a Survey, Discussion, and Future Opportunities
• Authors: Pavel Surynek
• Abstract summary: 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.
• Score: 7.766921168069532
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-agent path finding (MAPF) attracts considerable attention in artificial intelligence community as well as in robotics, and other fields such as warehouse logistics. The task in the standard MAPF is to find paths through which agents can navigate from their starting positions to specified individual goal positions. The combination of two additional requirements makes the problem computationally challenging: (i) agents must not collide with each other and (ii) the paths must be optimal with respect to some objective. 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, for which an efficient solver exists. The compilation-based MAPF solving can benefit from advancements accumulated during the development of the target solver often decades long. We summarize and compare contemporary compilation-based solvers for MAPF using formalisms like ASP, MIP, and SAT. We show the lessons learned from past developments and current trends in the topic and discuss its wider impact.

Related papers

• Transient Multi-Agent Path Finding for Lifelong Navigation in Dense Environments [9.000023855628958]
  The Lifelong MAPF (LMAPF) problem is a well-studied online version of MAPF in which an agent receives a new target when it reaches its current target. We propose to solve LMAPF problems by solving a sequence of modified MAPF problems, in which the objective is for each agent to eventually visit its target. We refer to this MAPF variant as Transient MAPF (TMAPF) and propose several algorithms for solving it based on existing MAPF algorithms.
  arXiv  Detail & Related papers  (2024-12-05T15:37:29Z)
• MALT: Improving Reasoning with Multi-Agent LLM Training [64.13803241218886]
  We present a first step toward "Multi-agent LLM training" (MALT) on reasoning problems. Our approach employs a sequential multi-agent setup with heterogeneous LLMs assigned specialized roles. We evaluate our approach across MATH, GSM8k, and CQA, where MALT on Llama 3.1 8B models achieves relative improvements of 14.14%, 7.12%, and 9.40% respectively.
  arXiv  Detail & Related papers  (2024-12-02T19:30:36Z)
• 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 (MAPF) is a problem that generally requires finding collision-free paths for multiple agents in a shared environment. Recently, learning-based approaches to MAPF have gained attention, particularly those leveraging deep reinforcement learning. 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)
• Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning [46.354187895184154]
  Multi-agent Pathfinding (MAPF) problem generally asks to find a set of conflict-free paths for a set of agents confined to a graph. In this work, we investigate the decentralized MAPF setting, when the central controller that posses all the information on the agents' locations and goals is absent. We focus on the practically important lifelong variant of MAPF, which involves continuously assigning new goals to the agents upon arrival to the previous ones.
  arXiv  Detail & Related papers  (2023-10-02T13:51:32Z)
• Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding [29.76466191644455]
  Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics that asks us to compute collision-free paths for a team of agents. We propose a new approach for MAPF where agents are guided to their destination by following congestion-avoiding paths. We evaluate the idea in two large-scale settings: one-shot MAPF, where each agent has a single destination, and lifelong MAPF, where agents are continuously assigned new destinations.
  arXiv  Detail & Related papers  (2023-08-22T07:17:39Z)
• Heuristically Guided Compilation for Multi-Agent Path Finding [15.99072005190786]
  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.
  arXiv  Detail & Related papers  (2022-12-13T23:19:15Z)
• 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)

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.