A* Algorithm with Expected Value: Path Planning That Avoids Stochastic Traffic Obstacles
Yoshiyuki Kozuka, Toshiyuki Hayashi, Takashi Syamoto, Nobuhiro Ito, Kazunori Iwata, Yoshinobu Kawabe · 2016
We propose an extended algorithm for path planning within environments in which there are stochastic traffic obstacles. Related works on path planning (e.g., works employing the A* algorithm) have not considered traffic obstacles but how quickly the optimal path is found. Our algorithm improves on the A* algorithm by considering probabilities of traffic obstacles and difficulty levels in taking detours within the post-disaster environment. The proposed algorithm appends expected values of passing probabilities to h(v) of the A* algorithm. We also perform evaluation experiments using real map data, and compare the performance of our algorithm with that of the A* algorithm in a Welch's t-test. The comparison reveals that agents of our algorithm can travel more quickly than those of the A* algorithm in the environment where some roads are blocked by liquefaction and traffic obstacles, and as quickly as those of the A* algorithm in the environment where there is rarely liquefaction or traffic obstacles.