In metropolitan areas, there are many intersections having turn prohibitions and it is important to consider them in computing a shortest path. This paper presents an efficient path planning method considering turn prohibitions. A new road network model is proposed in which a turn-prohibited route is replaced by an alternative route to make a turn using U-turn or P-turn. The proposed network model is efficient since it requires no virtual nodes that are used in conventional networks to represent turns at intersections. Since the conventional Dijkstra's shortest path algorithm cannot be applied to the proposed network due to its own nature, in this paper a modified algorithm is proposed to find an optimal path. With the proposed network model and algorithm, a fast path planning method is realized and it provides a practical path utilizing U-turn or P-turn if necessary.
Abstract