[논문]수집된 경로데이터를 사용하는 내비게이션을 위한 대용량 경로조합 방법

구광민; 이태호; 박희민

doi:10.9717/kmms.2016.19.2.386

수집된 경로데이터를 사용하는 내비게이션을 위한 대용량 경로조합 방법
A Big-Data Trajectory Combination Method for Navigations using Collected Trajectory Data 원문보기

멀티미디어학회논문지 = Journal of Korea Multimedia Society, v.19 no.2, 2016년, pp.386 - 395

구광민 (Department of Computer Software Engineering, Sangmyung University) , 이태호 (Department of Computer Software Engineering, Sangmyung University) , 박희민 (Department of Computer Software Engineering, Sangmyung University)

Abstract ▼ AI-Helper

In trajectory-based navigation systems, a huge amount of trajectory data is needed for efficient route explorations. However, it would be very hard to collect trajectories from all the possible start and destination combinations. To provide a practical solution to this problem, we suggest a method combining collected GPS trajectories data into additional generated trajectories with new start and destination combinations without road information. We present a trajectory combination algorithm and its implementation with Scala programming language on Spark platform for big data processing. The experimental results proved that the proposed method can effectively populate the collected trajectories into valid trajectory paths more than three hundred times.

주제어

AI 본문요약
AI-Helper

문제 정의

기존의 관련 연구 문헌을 면밀히 조사한 바로는 GPS 경로데이터를 조합하거나 수집된 경로데이터를 이용해 새로운 경로를 조합해 내는 연구는 시도된 적이 없는 것으로 파악되었다. 본 논문에서는 경로데이터 수집의 제약을 극복하는 방안으로 경로조합 알고리즘을 고안하여 제안한다.
본 논문에서는 도로상의 실제적인 상황과 운전자의 축적된 경험을 활용할 수 있는 경로데이터 기반으로 내비게이션 시스템을 위한 경로조합 방법에 대해 제안하였다. 도로정보에 의존하지 않고 수집된 경로데이터의 GPS 위치정보 만을 이용해 경로를 조합하는 방법이다.
또한, 특정 출발점과 도착점 사이에도 수많은 대안 경로들이 존재하기 때문에 모든 가능한 경로에 대해 각각 별도의 데이터를 수집하는 것은 불가능하게 된다. 이러한 문제점을 해결하기 위해 본 논문에서는 수집된 일부의 대용량 경로데이터를 조합하여 기존에 수집되지 않은 새로운 경로데이터로 생성하는 방법을 제안한다.

가설 설정

1) 경로데이터는 순서(방향)가 있는 GPS 지점들의 집합이어야 한다.
3) GPS 지점들의 위치정보 오류는 경로를 판단하기에 문제없는 수준이어야 한다.

제안 방법

출발-도착점이 다른 두 경로가 교차로에서 교차할 경우 경로의 진행방향을 판단하고 조합할 가치가 있는지 판단하는 알고리즘을 고안하였다. 경로데이터는 특성상 빅데이터화되고 경로내 GPS 지점의 수가 많으므로 빅데이터 처리 플랫폼 상에서 알고리즘을 구현하였다. 함수형 언어인 스칼라를 이용해 스파크 상에서 구현하였다.
본 논문에서 제안하는 알고리즘은 도로정보를 사용하지 않으며, GPS 위치정보의 집합으로 이루어진 경로데이터만 다룬다. 수집된 경로데이터를 두 경로씩 서로 비교하고, 같은 교차로를 사용하는 지점을 기준으로 경로를 나눈 후, 나누어진 경로 중 서로 다른 부분을 교환하여 조합하는 방식이다.
예를 들어, 기존 경로데이터에 존재하지 않는 다른 방향으로 진행하는 경로로 조합될 때 새로운 경로로 생성하게 된다. 제안하는 알고리즘은 GPS 위치정보로 구성된 대용량 경로데이터를 처리해야 하기 때문에 경로조합 알고리즘은 스칼라 프로그래밍 언어[3]를 이용해 스파크[4] 빅데이터 처리 플랫폼상에서 구현하였다.
도로정보에 의존하지 않고 수집된 경로데이터의 GPS 위치정보 만을 이용해 경로를 조합하는 방법이다. 출발-도착점이 다른 두 경로가 교차로에서 교차할 경우 경로의 진행방향을 판단하고 조합할 가치가 있는지 판단하는 알고리즘을 고안하였다. 경로데이터는 특성상 빅데이터화되고 경로내 GPS 지점의 수가 많으므로 빅데이터 처리 플랫폼 상에서 알고리즘을 구현하였다.

대상 데이터

실험을 위한 경로데이터는 차량을 운행하며 직접 수집하였으며 Table 1에 수집한 경로데이터에 대한 설명을 보인다. 경로데이터는 GPS의 XML포맷인 GPX[9]이며 참여형 오픈소스 지도인 오픈스트리트 맵[10]을 기반으로 한 개발된 OsmAnd[11]을 사용했다.

이론/모형

실험을 위한 경로데이터는 차량을 운행하며 직접 수집하였으며 Table 1에 수집한 경로데이터에 대한 설명을 보인다. 경로데이터는 GPS의 XML포맷인 GPX[9]이며 참여형 오픈소스 지도인 오픈스트리트 맵[10]을 기반으로 한 개발된 OsmAnd[11]을 사용했다. 아래 Fig.
제안한 알고리즘은 빅데이터 처리 플랫폼인 스파크[4,13]를 사용하기 위해 함수형 프로그래밍 언어인 스칼라[3,14]를 사용하여 구현하였다. 스파크 클러스터는 3대의 슬레이브 노드와 1대의 마스터 노드, 총 4대의 서버로 설정되었으며 서버의 사양 및 스파크 버전은 다음 Table 2와 같다.

성능/효과

12에서 볼 수 있듯이 경로 조합을 통해 한군데의 출발점에서 시작 가능한 경로의 수가 매우 늘어났음을 알 수 있다. 이는 경로조합을 통해 내비게이션 시스템은 경로안내를 할 수 있는 경로의 수가 증가했으며 또한 목적지까지 더 다양한 방법의 경로를 생성함으로써, 전보다 더 최적의 경로를 찾는 것이 가능하게 되었다. 이를 통해 경로조합이 경로데이터 기반 내비게이션의 성능을 향상시킬 수 있음을 알 수 있다.
따라서, 목적지까지의 더 다양한 방법의 경로를 생성함으로써 더 최적의 경로를 찾는 것이 가능하다. 이를 통해 경로조합이 경로데이터 기반 내비게이션의 성능을 향상시키는 것을 보였다. 향후 연구로는 GPS 오류값에 강인한 알고리즘 개발 및 보다 많은 경로데이터 수집을 통해 실제 서비스 가능한 내비게이션 시스템 구축을 진행할 계획이다.
이는 경로조합을 통해 내비게이션 시스템은 경로안내를 할 수 있는 경로의 수가 증가했으며 또한 목적지까지 더 다양한 방법의 경로를 생성함으로써, 전보다 더 최적의 경로를 찾는 것이 가능하게 되었다. 이를 통해 경로조합이 경로데이터 기반 내비게이션의 성능을 향상시킬 수 있음을 알 수 있다.
직접 수집한 경로데이터를 이용해 실험한 결과 약 300배 이상의 개수의 경로를 조합해 내는 것이 가능함을 보였다. 이를 통해 내비게이션 시스템이 경로안내를 할 수 있는 경로의 수를 증가시킬 수 있었다. 따라서, 목적지까지의 더 다양한 방법의 경로를 생성함으로써 더 최적의 경로를 찾는 것이 가능하다.
함수형 언어인 스칼라를 이용해 스파크 상에서 구현하였다. 직접 수집한 경로데이터를 이용해 실험한 결과 약 300배 이상의 개수의 경로를 조합해 내는 것이 가능함을 보였다. 이를 통해 내비게이션 시스템이 경로안내를 할 수 있는 경로의 수를 증가시킬 수 있었다.

후속연구

이를 통해 내비게이션 시스템이 경로안내를 할 수 있는 경로의 수를 증가시킬 수 있었다. 따라서, 목적지까지의 더 다양한 방법의 경로를 생성함으로써 더 최적의 경로를 찾는 것이 가능하다. 이를 통해 경로조합이 경로데이터 기반 내비게이션의 성능을 향상시키는 것을 보였다.
이를 통해 경로조합이 경로데이터 기반 내비게이션의 성능을 향상시키는 것을 보였다. 향후 연구로는 GPS 오류값에 강인한 알고리즘 개발 및 보다 많은 경로데이터 수집을 통해 실제 서비스 가능한 내비게이션 시스템 구축을 진행할 계획이다.

참고문헌 (15)

Advanced Traffic Prediction of T-map, http://readme.skplanet.com/?p8870 (accessed Jan., 17, 2016).
K.M. Koo, T. Lee, and H. Park, "Navigation System Using Big Trajectory Data Based on Empirical Knowledge," Proceeding of the Summer Conference of Korea Information Science Society, pp. 2150-2152, 2015.
The Scala Programming Language, http://www.scala-lang.org/ (accessed Jan., 17, 2016).
Apache Spark-Lightning-Fast Cluster Computting, http://spark.apache.org/ (accessed Jan., 17 2016).
J. Lim, K. Kim, J. Kim, H. Oh, S. Yoon, J. Yoo, et al., "Design and Implementation of a Realtime Optimal Traffic Route Guidance System Through Big Data Analysis," Proceeding of 2014 Fall Conference of Korea Contents Association, pp. 297-298, 2014.
S. Yang, C. Choi, and H. Choi, "Design and Implementation of Vehicle Route Tracking System using Hadoop-Based Bigdata Image Processing," Journal of Digital Contents Society, Vol. 14, No. 4, pp. 447-454, 2013.

원문보기 상세보기
K. H. Lee, Y. H. Jo, T. Lee, and H. Park, “Recommendation of Best Empirical Route Based on Classification of Large Trajectory Data,” KIISE Transactions on Computing Practices, Vol. 21, No. 2, pp. 101-108, 2015.

원문보기 상세보기
W. Sagong, “Design and Implementation of Optimized Route Search Technique based on User Experience Using Open APIs,” Journal of Korea Multimedia Society, Vol. 18, No. 5, pp. 682-690, 2015.

원문보기 상세보기
GPX: The GPX Exchange Format, http://www.topografix.com/gpx.asp (accessed Jan., 17, 2016).
OpenStreetMap, https://www.openstreetmap.org (accessed Jan., 17, 2016).
OsmAnd: Offline Mobile Maps & Navigation, http://osmand.net/ (accessed Jan., 17, 2016).
uMap, http://umap.openstreetmap.fr/en/ (accessed Jan., 17, 2016).
H. Karau, A. Konwinski, P. Wendell, and M. Zaharia, Learning Spark, O'Reilly Media, 2015.
M. Odersky, L. Spoon, and B. Venners, Programming in Scala, A Comprehensive Step-by-Step Guide, 2 nd Edition, Artima Inc, 2011.
JOSM: Extensible Editor for OpenStreetMap, https://josm.openstreetmap.de/ (accessed Jan., 17, 2016).

저자의 다른 논문 :

LOADING...

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증