추상 그래프를 활용한 경로 탐색 알고리즘의 구현 및 성능 평가 = Implementation and Evaluation of Path-Finding Algorithm using Abstract Graphs

국문 초록 (Abstract)

최근 단말기 기반의 경로 탐색에서도 동적인 정보를 반영하기 위한 연구가 진행되고 있다. 제시하는 대부분의 알고리즘은 $A^*$알고리즘을 기반으로 한다. 휴리스틱을 이용한 알고리즘에서는 탐색 비용이 증가하는 문제가 발생할 수 있다. 추상 그래프는 실제 도로 네트워크를 단순화한 그래프로, 휴리스틱 의존성과 탐색 비용을 줄이기 위해 제안된 방법이다. 이 논문에서는 생성방법이 다른 두 가지의 추상 그래프를 이용하여 성능 평가하였다. 추상 그래프는 생성 방법에 따라 동일 특성 노드 합병을 통한 추상 그래프($AG^H$)와 연결 노드 합병을 통한 추상 그래프($AG^C$)로 구별된다. 성능 실험 결과 생성 비용과 노드 접근 비용 측면에서 $AG^C$가 좋은 성능을 보였지만, 탐색된 경로의 이동시간측면에서는 $AG^H$가 좋은 성능을 보였다.

다국어 초록 (Multilingual Abstract)

Recently, Many studies have been progressing to path-finding adapted dynamic information on the Terminal Based Navigation System(TBNS). The algorithms proposed are based on $A^*$ algorithm. Path-finding algorithms which use heuristic function may occur a problem of the increase of exploring cost. Path-finding with an abstract graph which expresses real road network as a simple graph is proposed for reducing dependency of heuristic and exploring cost. In this paper, two abstract graph that are different method of construction, Homogeneous Node merging($AG^H$) and Connected Node Merging($AG^C$), are implemented. In result of evaluation of performance, $AG^C$ has better performance than $AG^H$ at construction cost and the number of node access but $AG^C$ has worse performance than AGH at exploring cost.

참고문헌 (Reference)

1 문대진, "최저 속력 동적 휴리스틱을 이용한 경로탐색" 한국공간정보시스템학회 10 (10): 35-48, 2008

2 문대진, "실시간 도로 정보를 이용한 최고속력 동적 휴리스틱의 설계" 12 (12): 827-830, 2008

3 이지완, "동적정보를 이용하는 환경에서 탐색영역 최소화를 위한 이웃노드 병합 추상그래프 설계" 220-226, 2009

4 김지수, "동적 교통 정보를 적용하기 위한 도로망 추상화 기법의 설계" 13 (13): 199-202, 2009

5 이현섭, "고정 그리드 기반 가변 휴리스틱을 이용한 최적경로 탐색" 9 (9): 137-141, 2005

6 김진덕, "가변 휴리스틱 기반 추정치 간소화를 통한 경로 탐색 기법의 설계 및 성능 평가" 한국정보통신학회 10 (10): 2002-2007, 2006

7 "http://en.wikipedia.org/wiki/TPEG"

8 EBU B/TPEG, "Transport Protocol Experts Group (TPEG) TPEG specifications - Part 1: Introduction, Numbering and Versions, TPEG-INV/002"

9 Peter E. Hart, "Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs" SSC (SSC): 100-107, 1968