Multi-Agent Path Finding with Deadlines: Preliminary Results
We formalize the problem of multi-agent path finding with deadlines (MAPF-DL). The objective is to maximize the number of agents that can reach their given goal vertices from their given start vertices within a given deadline, without colliding with each other. We first show that the MAPF-DL problem is NP-hard to solve optimally. We then present an optimal MAPF-DL algorithm based on a reduction of the MAPF-DL problem to a flow problem and a subsequent compact integer linear programming formulation of the resulting reduced abstracted multi-commodity flow network.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Agent Path FindingSimilar Papers 제목 키워드 기반
Multi-Agent Path Finding with Deadlines
We formalize Multi-Agent Path Finding with Deadlines (MAPF-DL). The objective is to maximize the number of agents that can reach their given goal vertices from their given start vertices within the deadline, without coll…
Multi-Agent Path FindingMulti-agent Path Finding for Timed Tasks using Evolutionary Games
Autonomous multi-agent systems such as hospital robots and package delivery drones often operate in highly uncertain environments and are expected to achieve complex temporal task objectives while ensuring safety. While …
Multi-Agent Path FindingReinforcement Learning (RL)Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results
In this work we study a well-known and challenging problem of Multi-agent Pathfinding, when a set of agents is confined to a graph, each agent is assigned a unique start and goal vertices and the task is to find a set of…
Heuristic SearchMulti UAVs Preflight Planning in a Shared and Dynamic Airspace
Preflight planning for large-scale Unmanned Aerial Vehicle (UAV) fleets in dynamic, shared airspace presents significant challenges, including temporal No-Fly Zones (NFZs), heterogeneous vehicle profiles, and strict deli…
Routing and Scheduling in Answer Set Programming applied to Multi-Agent Path Finding: Preliminary Report
We present alternative approaches to routing and scheduling in Answer Set Programming (ASP), and explore them in the context of Multi-agent Path Finding. The idea is to capture the flow of time in terms of partial orders…
Multi-Agent Path FindingScheduling