최저 속력 동적 휴리스틱을 이용한 경로탐색 (Path Finding with Minimum Speed Dynamic Heuristic)

서지정보

· 발행기관 : 한국공간정보시스템학회
· 수록지 정보 : 한국공간정보시스템학회 논문지 / 10권 / 2호 / 35 ~ 48페이지
· 저자명 : 문대진, 조대수

초록

이 논문에서는 단말기 기반 시스템에서 경로를 탐색할 때 탐색비용을 줄이고, 경로탐색의 질을 높이기 위해 동적 휴리스틱을 제안한다. 동적 휴리스틱이란 고정된 정보가 아닌 서버로부터 지속적으로 전송받는 휴리스틱으로, 교통정보를 계산한 데이터이다. 서버 기반의 경로탐색 서비스는 서버에서 경로를 탐색하여 결과를 클라이언트에 제공하지만, 제안하는 방법은 휴리스틱 정보만을 클라이언트에 전송하고 이를 활용하여 경로탐색을 하게 된다. 이 논문에서는 제안하는 동적 휴리스틱을 적용하기 위해 새로운 알고리즘을 제안한다. 제안하는 동적 휴리스틱은 지도를 그리드로 나누고, 각 그리드는 구역 내 간선들의 최저속도 정보를 가진다. 그리드의 최저속도가 기준치에 미달되면 해당 그리드를 제거하고 경로를 탐색한다.

영어초록

In this paper, we propose a Dynamic Heuristic to reduce the number of node accesses and
improve quality of path in the client-based navigation service. The Dynamic Heuristic is to
use heuristic data from server that is calculated with traffic data. The server-based
navigation service provides a path searched on server and transmits it to client, but we
propose that server only provide heuristic data to client. The proposed client searches a path
with heuristic transmitted data from server. We present a new algorithm for using Dynamic
Heuristic in the path-finding. The algorithm bases Grid Based Path-Finding, and has
minimum speed data of edges in grid. It removes several grids whose minimum speed is less
than limited speed.

참고자료

· 없음