Energy-Aware Spatio-Temporal Multi-Agent Route Planning for AGVs

This article addresses the problem of finding the shortest route for Automated Guided Vehicles (AGVs) in a production environment with constrained battery state-of-charge (SoC) and time-dependent operating conditions. The route map is divided into a uniform grid containing stationary obstacles and two types of dynamic obstacles: human, for which AGV transportation is prohibited, and inanimate (moving objects), which impose a penalty function. A key contribution of the proposed methodology is the introduction of a battery residual charge matrix, which embeds cell-level energy feasibility directly into the grid-based environment representation by determining minimum admissible SoC constraints and accounting for transition-dependent energy costs. This matrix restricts the set of traversable cells under low-energy conditions, enabling energy-aware route feasibility evaluation during both initial planning and adaptive replanning. The proposed approach is based on the A* and D* Lite algorithms, providing shortest-path construction that explicitly integrates battery SoC into the spatio-temporal cost function. To avoid collisions in a multi-agent environment during routing, a simplified hybrid scheme with M* elements performs local coordination and adaptive trajectory replanning. The effectiveness of the proposed methodology was assessed using travel time, temporal complexity, and spatial complexity metrics. Simulation results on a 10×10 grid showed that agents with sufficient battery completed routes of 8 and 11 cells with travel times of 7.2 to 10.7 conventional units. A critically low-energy agent was initially unable to move, but after adjusting the minimum SoC constraint, all agents completed their routes with travel times up to 11.4 conventional units, demonstrating the direct impact of energy constraints on system performance. Additional experiments with varying agent counts and SoC thresholds confirmed reliable balancing of route feasibility and energy constraints across configurations.