A Cooperative Reservation and Deadline-Aware Routing Algorithm for Multi-Agent Pathfinding Problem

Liviu Octavian Mafteiu-Scai, Gicu Rata

© 2025 Liviu Octavian Mafteiu-Scai, published by UIKTEN. This work is licensed under the Creative Commons Attribution-NonCommercial 4.0 International. (CC BY-NC 4.0).

Citation Information: SAR Journal. Volume 8, Issue 3, Pages 240-247, ISSN 2619-9955, https://doi.org/10.18421/SAR83-04, September 2025.

Received: 18 July 2025.
Revised:   03 September 2025.
Accepted: 09 September 2025.
Published: 27 September 2025.

Abstract:

Multi-Agent Pathfinding (MAPF) is an optimization problem for the multi-agent scheduling problem, in which collision-free paths are determined for a group of agents for each agent's routes. In this paper, a dynamic priority-based algorithm is proposed to solve the MAPF problem. Robots are assigned dynamic priorities based on factors like deadlines and distance to goal. The simulation proceeds in discrete time steps, where at each step active robots are processed sequentially according to their current priority. Each robot validates its existing path and checks for potential dynamic conflicts with higher-priority robots processed earlier in the same step. If the path is invalid or a conflict is detected, the robot attempts to replan using a time-expanded A* search that respects a shared reservation table. This table stores planned space-time occupations to prevent collisions. The A* search explicitly avoids vertex conflicts (same cell, same time) and edge conflicts (swapping adjacent cells). Experiments demonstrate that the proposed algorithm (hereinafter called CREDAR - Cooperative REservation & Deadline-Aware Routing) finds valid paths satisfying time constraints in various test scenarios, dynamically resolving conflicts through prioritized replanning.

Keywords – Multi-agent pathfinding, robot, path conflict, collision.

                   

                                                                      Full text PDF