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

A pathfinding method performed by a computer, comprising:

• acquiring vehicle information, obstacle information, and map information, the vehicle information including a current location and a goal location for each of multiple vehicles, the obstacle information including history of locations of one or more moving obstacles, the map information including a map of a space in which the vehicles and the moving obstacles travel;
• generating one or more obstacle paths for each moving obstacle during a target time window of a predefined length based on the obstacle information and the map information;
• generating multiple candidate path sets based on the vehicle information, the obstacle paths, and the map information, the candidate path set including a vehicle path during the target time window for each vehicle, the vehicle path being conflict-free with the other vehicle paths and the obstacle paths;
• evaluating the candidate path sets through a heuristic search of continuations of the vehicles paths in the candidate path sets;
• and
• selecting one of the candidate path sets based their evaluations to output the selected candidate path set.

A non-transitory computer-readable storage medium storing a program that causes a computer to execute:

• acquiring vehicle information, obstacle information, and map information, the vehicle information including a current location and a goal location for each of multiple vehicles, the obstacle information including history of locations of one or more moving obstacles, the map information including a map of a space in which the vehicles and the moving obstacles travel;
• generating one or more obstacle path for each moving obstacle during a target time window of a predefined length based on the obstacle information and the map information;
• generating multiple candidate path sets based on the vehicle information, the obstacle paths, and the map information, the candidate path set including a vehicle path during the target time window for each vehicle, the vehicle path being conflict-free with the other vehicle paths and the obstacle paths;
• evaluating the candidate path sets through a heuristic search of continuations of the vehicles paths in the candidate path sets;
• and
• selecting one of the candidate path sets based their evaluations to output the selected candidate path set.