2621. Spatially-robust discretization for the graph-free multi-agent pathfinding problem
Invited abstract in session WC-56: Logistics, stream Vehicle Routing and Logistics.
Wednesday, 12:30-14:00Room: Liberty 1.11
Authors (first author is the speaker)
| 1. | Seyoung Oh
|
| Industrial engineering, Seoul National University | |
| 2. | Kyungsik Lee
|
| Industrial Engineering, Seoul National University |
Abstract
The Multi-Agent Pathfinding (MAPF) problem involves finding collision-free paths for multiple agents navigating a predefined graph. In classical MAPF, agents move along edges in discrete time steps, assuming a fixed underlying graph structure. However, these assumptions fail to capture the actual movement dynamics of agents and the flexibility required in real-world applications, limiting the applicability of traditional solutions. In this talk, we introduce Graph-Free MAPF, where agents move in continuous space rather than on a given graph. To ensure collision-free coordination while maintaining computational efficiency, we propose a spatially robust discretization method that divides space into overlapping regions and schedules agent occupancy over time. Unlike traditional grid-based approaches, our method allows greater movement flexibility while maintaining safety guarantees. We formulate the problem as an integer optimization model and develop several solution approaches. The performance of the proposed approaches is evaluated across various scenarios and compared with existing methods.
Keywords
- Logistics
- Warehouse Design, Planning, and Control
Status: accepted
Back to the list of papers