내비게이션 경로설정에서 최단거리경로 탐색을 위한 A*와 Dijkstra 알고리즘의 하이브리드 검색법 (A Hybrid Search Method of A* and Dijkstra Algorithms to Find Minimal Path Lengths for Navigation Route Planning)

서지정보

· 발행기관 : 대한전자공학회
· 수록지 정보 : 전자공학회논문지 / 51권 / 10호 / 109 ~ 117페이지
· 저자명 : 이용후, 김상운

초록

내비게이션 경로탐색 시스템에서 A* 알고리즘을 사용할 경우 경로거리가 멀수록 Open 리스트(최적의 경로를 선택하기 위해 탐색된 예비경로들의 집합)의 크기가 증가하며, 이로 인해 비교연산이 증가하게 된다. 본 논문에서는 Dijkstra의 알고리즘과 A* 알고리즘을 주기적으로 교체 적용하여 Open 리스트의 크기를 줄일 수 있는 검색 방법을 제안한다. 여기서 두 알고리즘을 교체 적용하기 위하여 이라는 이름의 파라미터를 사용한다. 미리 정해진 레벨(깊이)만큼 Dijkstra의 알고리즘으로 탐색한 다음 A* 알고리즘으로 교체되도록 한다. 이 때 Dijkstra 알고리즘의 Open 리스트에 있는 노드들을 A* 알고리즘의 평가함수로 적합도를 평가하여 가능성이 있는 노드만을 A* 알고리즘의 Open 리스트로 전달한다. 따라서 계속되는 검색과정에서 Open 리스트의 크기가 불필요하게 증가되는 것을 억제할 수 있다. 또한 Dijkstra와 A* 알고리즘을 번갈아 적용하기 때문에 A* 알고리즘으로는 찾지 못할 최적 또는 준 최적 경로를 Dijkstra의 알고리즘으로 탐색한 결과와 비슷한 수준으로 찾을 수 있게 된다. 제안한 하이브리드 검색 알고리즘을 인공 및 실제의 지도 데이터를 이용하며 실험한 결과, 기존의 탐색 알고리즘과 비슷한 수준의 최단경로거리를 유지하면서 비교연산의 수를 더 줄일 수 있었다. 이 실험에서는 Level 값은 임의로 선정하였다. 따라서 실제의 도로 상황에서 최적 Level 값을 자동 선정하는 연구는 앞으로의 과제이다.

영어초록

In navigation route planning systems using A* algorithms, the cardinality of an Open list, which is a list of candidate nodes through which a terminal node can be accessed, increases as the path length increases. In this paper, a method of alternately utilizing the Dijkstra's algorithm and the A* algorithm to reduce the cardinality of the Open list is investigated. In particular, by employing a depth parameter, named Level, the two algorithms are alternately performed depending on the Level's value. Using the hybrid searching approach, the Open list constructed in the Dijkstra's algorithm is transferred into the Open list of the A* algorithm, and consequently, the unconstricted increase of the cardinality of the Open list of the former algorithm can be avoided and controlled appropriately. In addition, an optimal or nearly optimal path similar to the Dijkstra's route, but not available in the A* algorithm, can be found. The experimental results, obtained with synthetic and real-life benchmark data, demonstrate that the computational cost, measured with the number of nodes to be compared, was remarkably reduced compared to the traditional searching algorithms, while maintaining the similar distance to those of the latter algorithms. Here, the values of Level were empirically selected. Thus, a study on finding the optimal Level values, while taking into consideration the actual road conditions remains open.

참고자료

· 없음