Fast Algorithm for Centralized Multi-Agent Maze Exploration
- 1Faculty of Mathematics, University of Rijeka, 51000 Rijeka, Croatia
- 2Faculty of Engineering, University of Rijeka, 51000 Rijeka, Croatia
- 3Faculty of Science and Education, University of Mostar, 88000 Mostar, Bosnia and Herzegovina
Abstract
Recent advances in robotics have paved the way for robots to replace humans in perilous situations, such as searching for victims in burning buildings, in earthquake-damaged structures, in uncharted caves, traversing minefields or patrolling crime-ridden streets. These challenges can be generalized as problems where agents have to explore unknown mazes. We propose a cooperative multi-agent system of automated mobile agents for exploring unknown mazes and localizing stationary targets. The Heat Equation-Driven Area Coverage (HEDAC) algorithm for maze exploration employs a potential field to guide the exploration of the maze and integrates cooperative behaviors of the agents such as collision avoidance, coverage coordination, and path planning. In contrast to previous applications for continuous static domains, we adapt the HEDAC method for mazes on expanding rectilinear grids. The proposed algorithm guarantees the exploration of the entire maze and can ensure the avoidance of collisions and deadlocks. Moreover, this is the first application of the HEDAC algorithm to domains that expand over time. To cope with the dynamically changing domain, a red–black successive over-relaxation (SOR) iterative linear solver has been adapted and implemented, which significantly reduced the computational complexity of the presented algorithm when compared to a dense direct solver and to matrix-free BiCGSTAB and GMRES solvers applied to the same linear system. The results highlight significant improvements and show the applicability of the algorithm in different mazes. They confirm its robustness, adaptability, scalability and simplicity, which enables centralized parallel computation to control multiple agents in the maze.
Related
- Fast and Scalable Multi-Agent Distribution Matching via Partitioned Optimal Transport
- Centralized Multi-Objective UAV–UGV Task Allocation for Disaster Relief Material Distribution with Mobile UAV Bases
- PaNGEA: Parallel Node Generation and Exploration Algorithm on GPU
- SCOPE Before You Sample: Conformal Scores Guide Posterior Exploration for Fast and Calibrated Bayesian Predictive Inference
- Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling
BibTeX
@article{crnkovic2026fast,
title = {{Fast Algorithm for Centralized Multi-Agent Maze Exploration}},
author = {Bojan Crnković and Stefan Ivić and Mila Zovko},
journal = {Mathematics},
year = {2026},
month = oct,
doi = {10.3390/math14193613},
url = {https://www.mdpi.com/2227-7390/14/19/3613},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Fast Algorithm for Centralized Multi-Agent Maze Exploration
AU - Bojan Crnković
AU - Stefan Ivić
AU - Mila Zovko
PY - 2026
DA - 2026/10/05
JO - Mathematics
DO - 10.3390/math14193613
UR - https://www.mdpi.com/2227-7390/14/19/3613
AB - Recent advances in robotics have paved the way for robots to replace humans in perilous situations, such as searching for victims in burning buildings, in earthquake-damaged structures, in uncharted caves, traversing minefields or patrolling crime-ridden streets. These challenges can be generalized as problems where agents have to explore unknown mazes. We propose a cooperative multi-agent system of automated mobile agents for exploring unknown mazes and localizing stationary targets. The Heat Equation-Driven Area Coverage (HEDAC) algorithm for maze exploration employs a potential field to guide the exploration of the maze and integrates cooperative behaviors of the agents such as collision avoidance, coverage coordination, and path planning. In contrast to previous applications for continuous static domains, we adapt the HEDAC method for mazes on expanding rectilinear grids. The proposed algorithm guarantees the exploration of the entire maze and can ensure the avoidance of collisions and deadlocks. Moreover, this is the first application of the HEDAC algorithm to domains that expand over time. To cope with the dynamically changing domain, a red–black successive over-relaxation (SOR) iterative linear solver has been adapted and implemented, which significantly reduced the computational complexity of the presented algorithm when compared to a dense direct solver and to matrix-free BiCGSTAB and GMRES solvers applied to the same linear system. The results highlight significant improvements and show the applicability of the algorithm in different mazes. They confirm its robustness, adaptability, scalability and simplicity, which enables centralized parallel computation to control multiple agents in the maze.
SN - 2227-7390
ER -