Hierarchical Path Planning for Multi-Robot Systems

Hierarchical Path Planning for Multi-Robot Systems Marianna Turr` a, Silvia Proia, Alessandro Bonetti, Lorenzo Sabattini Department of Sciences and Methods for Engineering University of Modena and Reggio Emilia Reggio Emilia, Italy {marianna.turra, silvia.proia, alessandro.bonetti, lorenzo.sabattini}@unimore.it Abstract—This paper presents a hierarchical planning architecture for multi-vehicle autonomous systems in dynamic industrial environments, built on a novel hybrid roadmap that integrates static and dynamic areas. The approach addresses a multi-objective optimization problem, balancing high-level criteria and generating feasible low-level paths. Experimental results demonstrate improved mission efficiency and reduced travel time variability. Index Terms—Multi-vehicles autonomous system, roadmap, path planning, multi-objective optimization. I. INTRODUCTION In the evolving landscape of industrial automation, an increasing emphasis has been placed on robust and scalable multi-vehicle path planning. Within the Industry 4.0 paradigm, cyber-physical systems and real-time decision-making are promoted, highlighting the necessity for autonomous navigation in complex environments [1]. In response to this demand, the present work proposes a novel hierarchical path planning strategy that enables adaptive, efficient, and responsive planning for fleets of autonomous vehicles operating in mixed-layout industrial environments [2]. This paper presents a multi-vehicle path planning architecture based on a novel hybrid roadmap that combines the deterministic advantages of structured areas with the flexibility of dynamic environments. Unlike previous methods that address static [3] or dynamic [4] environments separately, the proposed hybrid roadmap integrates both approaches. Specifically, static regions are modeled using predefined graphs [5], while dynamic areas are represented through dense gridmaps that facilitate obstacle avoidance and continuous replanning [6]. The main contributions of this paper are: •Introduction of an innovative hierarchical multi-vehicle path planning strategy within a hybrid roadmap, enabling deterministic control in static environments and adaptive real-time decision-making for dynamic conditions. The system supports continuous replanning and real-time operation in industrial settings; •Formulation of a multi-objective optimization (MOO) problem integrated into a hierarchical architecture, where the high-layer determines the optimal sequence of area crossings for each vehicle, and the low-layer generates corresponding feasible physical paths. The evaluation of multiple and potentially conflicting criteria enables more robust and responsive path planning, particularly within dynamic environments; •Experimental validation in realistic industrial scenarios through the comparison of planning and replanning strategies across hybrid roadmap configurations and varying fleet sizes. Performance is evaluated using selected MOO criteria, showing that the replanning-based approach improves efficiency, robustness, and scalability in dynamic industrial environments. In the considered industrial environment, a fleet of Γautonomous vehicles, indexed by γ∈ F := {1,...,Γ} ⊆ N, operates within a hybrid roadmap. It partitions the environment into Aareas ai∈ A := {a1, . . . , aA}, comprising a set of S static areas ai∈ S := {a1, . . . , aS}, and a set of Ddynamic areas ai∈ D := {aS+1, . . . , aA}, with A=S+D. A subset of the dynamic areas is the set of storage areas, represented as W ⊆ D, which are primarily designated for material storage. However, when not fully occupied, they may also be utilized for path planning, similar to other dynamic areas. In detail, feasible paths over the hybrid roadmap are generated through a hierarchical path planning architecture, in which two planner layers are employed. Specifically, the area path φγis produced by the high-layer planner, and the corresponding physical path πγis computed by the low-layer planner, ∀γ∈ F. The two layers continuously interact to compute the optimal paths πγ,∀γ∈ F, ensuring the successful execution. Formulated as an integer linear programming (ILP) problem, the high-layer planner utilizes a scalarized MOO framework that balances set of criteria, and associated weights, reflecting their relative importance in the decision-making process, to define the optimal overall path strategy. Among the various criteria applied in the high-level planning process, a few key examples are highlighted for clarity. A preferability criterion discourages traversal through specific areas according to user-defined preferences. Meanwhile, an occupancy criterion quantifies the degree of obstruction within a storage area caused by obstacles, enabling its consideration as an alternative path when feasible. Furthermore, the spatial coherence between consecutive regions and the vehicle’s heading direction is evaluated to promote smoother and more direct transitions. Lastly, traffic density is estimated to avoid paths through highly congested zones and to encourage a balanced distribution of vehicles throughout the environment. Specifically, for each γ∈ F, the high-layer planner determines the optimal sequence of areas φγ, referred to as the area path, which defines the connectivity between the start area as γ– containing the start vertex vs γ– and the goal area ag γ, associated 2025 I-RIM Conference October 17-19, Rome, Italy ISBN: 9788894580570 =CONCATENATE("10.5281/zenodo.", J2) 1 with the goal vertex vg γ, by solving the scalarized ILP problem using the Dijkstra’s algorithm [7], with the criteria weights estimated via a genetic algorithm [8]. The area path φγis defined as the sequence of areas to be traversed by the γ-th vehicle and is provided as input to the low-layer planner. Instead, the low-layer planner refines the area path φγby computing the physical path πγ, for the γ-th vehicle, which optimizes travel cost while ensuring a seamless connection from vs γto vg γ, and avoiding obstacles. For each γ∈ F, the low-layer planner is implemented using the A* algorithm [9] –applied on a graph-based representation for static areas and on a gridmap-based representation for dynamic areas. II. CASE STUDY The effectiveness and adaptability of the proposed hybrid architecture are evaluated across two distinct configurations representing an industrial plant environment. In both cases, the layout spans 100 ×110 m2and is designed to accommodate up to 30 vehicles. For each configuration, tests are conducted both with and without the replanning strategy, and under three fleet size scenarios, defined by deployments of 10, 20, and 30 vehicles. To ensure statistical robustness and capture consistent performance trends, each scenario is repeated over 50 independent simulations, resulting in a total of 600 simulations. On the one hand, the first configuration (see Fig. 1(a)) is a layout without a central corridor. The plant comprises multiple functional areas –either static or dynamic– interconnected via a hybrid roadmap. On the other hand, the second configuration (see Fig. 1(b)), features a central corridor running longitudinally through the plant layout. The corridor provides alternative paths that enhance connectivity between functional areas. As a result, efficiency improves through a more even distribution of vehicle movement across the facility. The results demonstrate that the proposed strategy significantly improves total mission time (i.e., the overall duration of mission execution), cumulative mission efficiency (i.e., the cumulative mission time across all simulation runs) –both statistically validated– as well as path diversity, particularly in highly congested environments. Dynamic replanning, facilitated by the hybrid roadmap and hierarchical architecture, proves especially effective in layouts characterized by obstacle fluctuations and varying traffic densities. The planner efficiently utilizes partially occupied storage areas as alternative paths, enhancing space utilization and reducing bottlenecks. III. CONCLUSION This work presents a comprehensive and adaptive solution for industrial multi-vehicle navigation, integrating static and dynamic representations through a hybrid roadmap. The proposed hierarchical architecture efficiently balances multiple criteria and adapts to real-time changes, offering enhanced mission performance, scalability, and robustness. REFERENCES [1] Y. Lu, “Industry 4.0: A survey on technologies, applications and open research issues,” Journal of Ind. Inf. Integr., 2017. (a) Legend v2VA e2EAKS(VS,ES) KD(VD,ED) o2O 1 24 5 25 4 3 2 19 15 13 10 23 17 11 14 6 9 16 18 20 21 22 8 Legend n X [m] Y [m] 7 12 Iron (b) Fig. 1. Hybrid roadmap for autonomous vehicle navigation without a central corridor (a) and with a central corridor (b). The storage area, labeled as Area 21, exhibits high occupancy density in (a), restricting vehicle movement, while in (b) it shows medium obstacle occupancy density –as indicated by the orange color– allowing for feasible navigation. [2] I. P. Vlachos, R. M. Pascazzi, G. Zobolas, P. Repoussis, and M. Giannakis, “Lean manufacturing systems in the area of industry 4.0: A lean automation plan of agvs/iot integration,” Production planning &control, 2023. [3] M. De Ryck, M. Versteyhe, and F. Debrouwere, “Automated guided vehicle systems, state-of-the-art control algorithms and techniques,” Journal of Manuf. Syst., 2020. [4] T. Lackner, J. Hermann, C. Kuhn, and D. Palm, “Review of autonomous mobile robots in intralogistics: state-of-the-art, limitations and research gaps,” Procedia CIRP, 2024. [5] F. Menebr¨ oker, D. L¨ unsch, M. Hantzsch, and U. Pazarci, “Generalization of a stateful graph search algorithm applied to heterogeneous mobile robot path planning,” in Int. Conf. on Autom. Sci. and Eng. IEEE, 2024. [6] R. Stern, N. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, T. Kumar, E. Boyarski and R. Bart´ ak, “Multi-agent pathfinding: Definitions, variants, and benchmarks” in Proceedings of the Int. Symposium on Combinatorial Search, 2019. [7] E. W. Dijkstra, “A note on two problems in connexion with graphs,” in Edsger Wybe Dijkstra: His Life, Work, and Legacy, 2022. [8] S. Katoch, S. S. Chauhan, and V. Kumar, “A review on genetic algorithm: past, present, and future,” Multimedia tools and Appl., 2021 [9] P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Trans. on Syst. Sci. and Cybern., 1968. 2