Unassigned Agents in Compilation-based Multi-agent Path Finding
Compilation-based techniques represent an important stream of solvers for multi-agent path finding (MAPF) due to their modularity and adaptability for non-standard variants of the problem. While in the standard MAPF the task is to navigate all agents from their initial positions to given individual goal positions without any collision, variants where a different requirement for agents is used are also relevant. Such a variant is MAPF with unassigned agents (UA-MAPF) where some agents have the same setting as in the standard MAPF with initial positions and goals while the remaining agents have the initial position but have no goal - unassigned agents. Despite unassigned agent do not need to reach any goal position they have to be moved out of the way of the standard agents if needed which represent a specific challenge. We show in this paper that UA-MAPF can be expressed in recent compilation-based techniques for MAPF based on formulating the problem as Boolean satisfiability, namely we adapt SMT-CBS and NRF-SAT, the recent solvers based on counterexample guided abstraction refinement and non-refined abstractions.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Heuristically Guided Compilation for Multi-Agent Path Finding
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 …
Multi-Agent Path FindingCompilation-based Solvers for Multi-Agent Path Finding: a Survey, Discussion, and Future Opportunities
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 th…
Multi-Agent Path FindingNavigateMulti-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering
We introduce multi-goal multi agent path finding (MAPF$^{MG}$) which generalizes the standard discrete multi-agent path finding (MAPF) problem. While the task in MAPF is to navigate agents in an undirected graph from the…
Heuristic SearchMulti-Agent Path FindingNavigateSymbolic Planning and Multi-Agent Path Finding in Extremely Dense Environments with Unassigned Agents
We introduce the Block Rearrangement Problem (BRaP), a challenging component of large warehouse management which involves rearranging storage blocks within dense grids to achieve a goal state. We formally define the BRaP…
A Summary of Adaptation of Techniques from Search-based Optimal Multi-Agent Path Finding Solvers to Compilation-based Approach
In the multi-agent path finding problem (MAPF) we are given a set of agents each with respective start and goal positions. The task is to find paths for all agents while avoiding collisions aiming to minimize an objectiv…
Multi-Agent Path Finding