Efficient Optimal Path-Planning for Congestion Mitigation in Large-Scaled Autonomous Driving

This paper reveals that there is a greedy characteristic in the pathfinding algorithm that finds the optimal route based on individual vehicles, and because of that characteristic, unexpected congestion can occur when several vehicles search for a route in their optimal way, resulting in a loss in the overall travel time. To solve this problem, we will modify the $\mathrm{A}^{*}$ algorithm, a well-known algorithm in pathfinding. The heuristic function of $\mathrm{A}^{*}$ is a function that determines the performance of the algorithm, and if information about other vehicles is included in this function, the greedy characteristic decreases. The resulting path may not be optimal for each vehicle. But overall, the path can be determined to mitigate congestion. Finally, we argue for an arbiter who collects information about other vehicles and assigns heuristics to each vehicle’s pathfinding algorithm.