Doc. dr. Andrej Zdešar, univ. dipl. inž., dr. Matevž Bošnak, univ. dipl. inž., oba Univerza v Ljubljani, Fakulteta za elektrotehniko; Viktor Zaletelj, Epilog, d. o. o., Ljubljana; doc. dr. Rok Vrabič, univ. dipl. inž., Univerza v Ljubljani, Fakulteta za strojništvo; prof. dr. Gregor Klančar, univ. dipl. inž., Univerza v Ljubljani, Fakulteta za elektrotehniko

Ventil Vol. 31 (2025) 4 / Review articles / Technical Article – 1.01

Abstract:

The paper presents an approach that enables efficient multi-agent path planning. The environment is described by a graph that represents a network of roads and crossroads for vehicles of different shapes and velocities. The multi-agent pathfinding approach is based on a safe interval path planning algorithm with priorities and safe locations, which together allow for lifelong operation. The algorithm is complete and it produces near-optimal plans that are continuous in time and space. We have extended the algorithm with battery energy estimation, which allows finding only feasible plans. Since we also added an option that implicitly selects an optimal goal in a set of goals, we can achieve selection of a safe location or charging station already during planning. The proposed approach is practically applicable in a wide variety of realistic industrial scenarios for material handling within industrial setting, where charging of the agents during execution of the tasks is also considered. We also analysed the computational efficiency of the algorithm with respect to the number of vehicles and the size of the map. The results show that the presented approach is computationally efficient even in the case of a large number of vehicles and large maps.

Keywords:
path planning, multi-agent system, automated guided vehicles, industrial logistics, graphs, safe intervals, safe locations, charging stations, priorities

Copyright (c) 2025 Andrej Zdešar, Matevž Bošnak, Viktor Zaletelj, Rok Vrabič, Gregor Klančar

This work is licensed under a
Creative Commons Attribution 4.0 International License.

Except where otherwise noted, articles in
this journal are published under the
Creative Commons Attribution 4.0 International License.