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.
|
