Pathfinding apparatus, pathfinding method, and non-transitory computer-readable storage medium

Abstract

A pathfinding apparatus acquires vehicle information, map information, obstacle information. The vehicle information includes a current location and a goal location for multiple vehicles. The map information includes a map of a target space. The obstacle information includes history of locations of one or more moving obstacles. The pathfinding apparatus generates one or more obstacle path for each moving obstacle during a target time window, and generates multiple candidate path sets each of which includes a vehicle path during the target time window for each vehicle. The vehicle path is conflict-free with the other vehicle paths and the obstacle paths. The pathfinding apparatus evaluates the candidate path sets through a heuristic search of continuations of the vehicles paths in the candidate path sets, selects one of the candidate path sets based their evaluations, and outputs the selected candidate path set.