Path search engine for fast optimal path search using efficient hardware architecture

摘要

Recently, the optimal path search based on real-time traffic information is becoming more important in car navigation industries. The preference-based Ant Colony Optimization algorithm is suitable for the path search in a real-time traffic circumstance. However, this algorithm is not applicable to current car navigation due to the slow search time caused by the complex calculations. Likewise, sub-optimal problem is occurred according to circumstances of probability-based search and parameter settings in this algorithm. This paper presents a path search engine for the fast optimal path search, using simplified calculation and parallel architectures to apply path search algorithm. Also, A∗ architecture is added in the path search engine to supplement sub-optimal problem. The path search engine obtains the accurate optimal path and the search time improvement compared to the software-based path search in a general purpose processor that is typically used for car navigation.