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

1 . A pathfinding apparatus comprising:

at least one processor; and

memory storing instructions;

wherein the at least one processor is configured to execute the instructions to:

acquire 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;

generate 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;

generate, for each of the multiple vehicles, 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;

evaluate the candidate path sets through a heuristic search of continuations of the vehicle paths in the candidate path sets; and

for each of the multiple vehicles, select one of the candidate path sets corresponding to the vehicle based on their evaluations and output the selected candidate path set to the vehicle,

wherein the candidate path sets are evaluated by executing a Monte Carlo Tree Search algorithm that includes:

generating a search tree whose root node has a child node for each candidate path set, the child node having a parent edge that represents a set of actions of the moving obstacles and the vehicles during the target time window that are represented by the candidate path set and the obstacle paths; and

repeatedly executing a set comprising a selection operation, an expansion operation, a rollout operation, and a backpropagations operation,

wherein, in the selection operation, a node to be expanded is selected based on an evaluation score of each node,

wherein, in the expansion operation, a pair of a new edge and a new node is generated and appended to the node to be expanded, the new edge representing one or more actions for one or more of the vehicles and the moving obstacles,

wherein, in the rollout operation, a rollout is performed to generate continuations of paths of the vehicles and the moving obstacles until all vehicles reach their goal or until a deadlock occurs,

wherein, in the backpropagation operation, the evaluation score is computed for the node to be expanded and ancestors thereof based on a result of the rollout, and

wherein at least one of the multiple vehicles is an autonomous vehicle.

2 . The pathfinding apparatus according to claim 1 , wherein the generation of the candidate path sets includes performing a variant of Conflict-based Search algorithm, and

wherein the variant of Conflict-based Search algorithm includes:

generating, based on the obstacle paths, constraints to avoid conflicts between the vehicle and the moving obstacle, and adding the generated constraints to a root node of a conflict tree;

resolving conflicts during the target time window; and

outputting two or more solutions to generate the multiple candidate path sets.

3 . The pathfinding apparatus according to claim 1 , wherein the new edge represents an action at a time step for the vehicle or the moving obstacle, and

wherein the new edge is generated for each vehicle and moving obstacle in turn in the repetitive execution of the expansion operation.

4 . The pathfinding apparatus according to claim 1 , wherein the new edge represents a set of actions of the vehicles and the moving obstacles during a time window.

5 . The pathfinding apparatus according to claim 1 , wherein the evaluation score is computed based on: a cost of the paths of the vehicles obtained as a result of the rollout; a number of conflicts that happened in the rollout; and whether or not a deadlock happened in the rollout; or two or more thereof.

6 . A pathfinding method performed by a computer, the pathfinding method 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, for each of the multiple vehicles, 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 vehicle paths in the candidate path sets; and

for each of the multiple vehicles, selecting one of the candidate path sets corresponding to the vehicle based on their evaluations and output the selected candidate path set to the vehicle,

wherein the candidate path sets are evaluated by executing a Monte Carlo Tree Search algorithm that includes:

generating a search tree whose root node has a child node for each candidate path set, the child node having a parent edge that represents a set of actions of the moving obstacles and the vehicles during the target time window that are represented by the candidate path set and the obstacle paths; and

repeatedly executing a set comprising a selection operation, an expansion operation, a rollout operation, and a backpropagations operation,

wherein, in the selection operation, a node to be expanded is selected based on an evaluation score of each node,

wherein, in the expansion operation, a pair of a new edge and a new node is generated and appended to the node to be expanded, the new edge representing one or more actions for one or more of the vehicles and the moving obstacles,

wherein, in the rollout operation, a rollout is performed to generate continuations of paths of the vehicles and the moving obstacles until all vehicles reach their goal or until a deadlock occurs,

wherein, in the backpropagation operation, the evaluation score is computed for the node to be expanded and ancestors thereof based on a result of the rollout, and

wherein at least one of the multiple vehicles is an autonomous vehicle.

7 . The pathfinding method according to claim 6 , wherein the generation of the candidate path sets includes performing a variant of Conflict-based Search algorithm, and

wherein the variant of Conflict-based Search algorithm includes:

generating, based on the obstacle paths, constraints to avoid conflicts between the vehicle and the moving obstacle, and adding the generated constraints to a root node of a conflict tree;

resolving conflicts during the target time window; and

outputting two or more solutions to generate the multiple candidate path sets.

8 . The pathfinding method according to claim 6 , wherein the new edge represents an action at a time step for the vehicle or the moving obstacle, and

wherein the new edge is generated for each vehicle and moving obstacle in turn in the repetitive execution of the expansion operation.

9 . The pathfinding method according to claim 6 , wherein the new edge represents a set of actions of the vehicles and the moving obstacles during a time window.

10 . The pathfinding method according to claim 6 , wherein the evaluation score is computed based on: a cost of the paths of the vehicles obtained as a result of the rollout; a number of conflicts that happened in the rollout; and whether or not a deadlock happened in the rollout; or two or more thereof.

11 . 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, for each of the multiple vehicles, 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 vehicle paths in the candidate path sets; and

for each of the multiple vehicles, selecting one of the candidate path sets corresponding to the vehicle based on their evaluations and output the selected candidate path set to the vehicle,

wherein the candidate path sets are evaluated by executing a Monte Carlo Tree Search algorithm that includes:

generating a search tree whose root node has a child node for each candidate path set, the child node having a parent edge that represents a set of actions of the moving obstacles and the vehicles during the target time window that are represented by the candidate path set and the obstacle paths; and

repeatedly executing a set comprising a selection operation, an expansion operation, a rollout operation, and a backpropagations operation,

wherein, in the selection operation, a node to be expanded is selected based on an evaluation score of each node,

wherein, in the expansion operation, a pair of a new edge and a new node is generated and appended to the node to be expanded, the new edge representing one or more actions for one or more of the vehicles and the moving obstacles,

wherein, in the rollout operation, a rollout is performed to generate continuations of paths of the vehicles and the moving obstacles until all vehicles reach their goal or until a deadlock occurs, and

wherein, in the backpropagation operation, the evaluation score is computed for the node to be expanded and ancestors thereof based on a result of the rollout, and

wherein at least one of the multiple vehicles is an autonomous vehicle.

12 . The storage medium according to claim 11 , wherein the generation of the candidate path sets includes performing a variant of Conflict-based Search algorithm, and

wherein the variant of Conflict-based Search algorithm includes:

generating, based on the obstacle paths, constraints to avoid conflicts between the vehicle and the moving obstacle, and adding the generated constraints to a root node of a conflict tree;

resolving conflicts during the target time window; and

outputting two or more solutions to generate the multiple candidate path sets.

13 . The storage medium according to claim 11 , wherein the new edge represents an action at a time step for the vehicle or the moving obstacle, and

wherein the new edge is generated for each vehicle and moving obstacle in turn in the repetitive execution of the expansion operation.

14 . The storage medium according to claim 11 , wherein the new edge represents a set of actions of the vehicles and the moving obstacles during a time window.

15 . The storage medium according to claim 11 , wherein the evaluation score is computed based on: a cost of the paths of the vehicles obtained as a result of the rollout; a number of conflicts happened that in the rollout; and whether or not a deadlock happened in the rollout; or two or more thereof.