내비게이션은 차량 운전자에게 경로탐색과 길안내 서비스의 제공을 기본으로 한다. 그러나 현재의 경로탐색에서는 운전자의 안전을 지키기 위해 다양한 도로 상황을 고려하지 않고, 안전운전 DB만을 이용하여 최단경로를 찾는 서비스만을 제공하고 있다. 따라서 안전운전을 위해서는 단순한 최단경로 검색 서비스를 벗어나, 위험지역이나 위험시간대를 고려한 경로탐색이 필요하다. 본 논문에서는 A* 알고리즘을 이용하여 안전운전을 위해 위험지역을 회피할 수 있는 경로탐색 방법을 제안한다. 이 경로탐색에서 탐색노드의 경로 적합 도를 측정할 때 위험지역 종류별로 서로 다른 휴리스틱 가중치를 적용하였다. 특히 경로 탐색에서 회피할 위험지역으로는 사고가 자주 발생하는 사고 다발구간, 어린이 보호구역, 교차로지역, 그리고 위험시간대를 고려하여 동적으로 위험지역별 가중치를 부여하였다. 컴퓨터 시뮬레이션 결과, 안전운전을 위해 위험지역을 회피할 수 있는 경로탐색 서비스를 제공할 수 있는 가능성을 확인하였다.
내비게이션은 차량 운전자에게 경로탐색과 길안내 서비스의 제공을 기본으로 한다. 그러나 현재의 경로탐색에서는 운전자의 안전을 지키기 위해 다양한 도로 상황을 고려하지 않고, 안전운전 DB만을 이용하여 최단경로를 찾는 서비스만을 제공하고 있다. 따라서 안전운전을 위해서는 단순한 최단경로 검색 서비스를 벗어나, 위험지역이나 위험시간대를 고려한 경로탐색이 필요하다. 본 논문에서는 A* 알고리즘을 이용하여 안전운전을 위해 위험지역을 회피할 수 있는 경로탐색 방법을 제안한다. 이 경로탐색에서 탐색노드의 경로 적합 도를 측정할 때 위험지역 종류별로 서로 다른 휴리스틱 가중치를 적용하였다. 특히 경로 탐색에서 회피할 위험지역으로는 사고가 자주 발생하는 사고 다발구간, 어린이 보호구역, 교차로지역, 그리고 위험시간대를 고려하여 동적으로 위험지역별 가중치를 부여하였다. 컴퓨터 시뮬레이션 결과, 안전운전을 위해 위험지역을 회피할 수 있는 경로탐색 서비스를 제공할 수 있는 가능성을 확인하였다.
The primary function of navigation system is to provide route search and road guidance for safe driving for drivers. However, the existing route search system provides a simple service that looks up the shortest route using a safe driving DB without considering different road characteristics for the...
The primary function of navigation system is to provide route search and road guidance for safe driving for drivers. However, the existing route search system provides a simple service that looks up the shortest route using a safe driving DB without considering different road characteristics for the safety of the drivers. In order to maintain the safe driving, rather than searching the shortest path, a navigation system, in which the danger areas and/or the dangerous time zones have been considered, is required. Therefore, in this paper we propose a strategy of searching a navigation path to avoid danger areas for safe driving by using the A* algorithm. In the strategy, when evaluating the path-specific fitness of the navigation nodes, different heuristic weights were assigned to different types of risk areas. In particular, we considered three kinds of danger areas, such as accident-prone sections where accidents occur frequently, school zones, and intersection regions, as well as the time slots when the probability of danger is high. From computer simulation, the results demonstrate that the proposed scheme can provide the way to avoid danger areas on the route searching and confirm the possibility of providing the actual service.
The primary function of navigation system is to provide route search and road guidance for safe driving for drivers. However, the existing route search system provides a simple service that looks up the shortest route using a safe driving DB without considering different road characteristics for the safety of the drivers. In order to maintain the safe driving, rather than searching the shortest path, a navigation system, in which the danger areas and/or the dangerous time zones have been considered, is required. Therefore, in this paper we propose a strategy of searching a navigation path to avoid danger areas for safe driving by using the A* algorithm. In the strategy, when evaluating the path-specific fitness of the navigation nodes, different heuristic weights were assigned to different types of risk areas. In particular, we considered three kinds of danger areas, such as accident-prone sections where accidents occur frequently, school zones, and intersection regions, as well as the time slots when the probability of danger is high. From computer simulation, the results demonstrate that the proposed scheme can provide the way to avoid danger areas on the route searching and confirm the possibility of providing the actual service.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 A* 알고리즘을 이용하여 위험지역을 회피한 경로를 탐색하여 안전운전 경로를 서비스하는 방법을 연구한다. 즉 기존의 단순한 최단경로 탐색 방식과는 달리, 운전자가 원하는 운행구간에서 위험지역을 회피하면서 목적지에 빠르게 도착할 수 있도록 하는 안전운전 경로탐색 방법을 검토한다.
그러나 이들 연구는 차량사고가 많이 발생하는 위험지역을 회피하지 못하는 문제점을 가진다. 본 논문에서는 안전운전을 위해 위험지역을 회피하는 내비게이션 경로탐색 기법을 연구하였다. A* 알고리즘을 기본 탐색방식으로 사용하였으며, 위험지역과 위험시간대에서 가중치를 사용한 경로탐색을 사용하였다.
제안 방법
*이 실험에서 노드와 노드 사이에 거리에 따른 주행 시간이며, 교차로 방향전환 시간은 속도에 따라서 1초에서 20초까지 서로 다른 감속 및 가속지연을 적용하였다
이 때 문헌[5]에서와 같이 A* 알고리즘에 교통이 혼잡한 시간과 검색 영역을 세부 분리한 후 경로를 탐색하는 방법을 고려하여, 최단 시간 내에 목적지점에 도착할 수 있는 경로를 제시한다. 또한 본 논문에서는 사고발생이 높은 위험지역과 위험빈도가 높은 시간대를 고려하는 가중치를 사용하며, 지역과 시간대에 따라 동적으로 위험지역을 회피할 수 있는 탐색 방식을 사용한다.
따라서 실제의 도로 상황을 염두에 둔 최적의 αA값을 산출하기 위한 추가적인 연구가 필요하다. 또한 최단경로 탐색을 위한 연산비용과 주행시간의 산출에서 선형 식을 모든 노드에 일률적으로 적용하였다. 그러나 지역에 따라 또 시간대에 따라 비선형 관계식이 적용될 수 있으며, 앞으로 이에 대한 연구도 필요하다.
A* 알고리즘을 기본 탐색방식으로 사용하였으며, 위험지역과 위험시간대에서 가중치를 사용한 경로탐색을 사용하였다. 먼저, 위험지역은 사고 다발구간, 어린이 보호구역, 교차로지역에서 분류하여 사용하며, 위험시간대는 어린이 보호구역에서 사용한다.
본 논문에서는 A* 알고리즘의 탐색방향 데이터(이를 h라 함)를 사용하여 출발지점에서 목적지점까지 최단경로를 검색한다. 이 때 문헌[5]에서와 같이 A* 알고리즘에 교통이 혼잡한 시간과 검색 영역을 세부 분리한 후 경로를 탐색하는 방법을 고려하여, 최단 시간 내에 목적지점에 도착할 수 있는 경로를 제시한다.
본 논문의 향상된 안전운전 경로탐색은 위험지역과 위험시간대를 회피하는 경로탐색으로, 위험지역은 사고다발구간, 어린이 보호구역, 교차로지역이 포함된다. 이중에서 어린이 보호구역은 위험시간대에 따라 서로 다르게 취급된다.
시각적인 관찰이 가능한 컴퓨터 시뮬레이션을 통해서 1600(40*40)개의 노드와 세 종류 위험지역을 표기할수 있는 지도 데이터를 생성하였고, 이 지도 데이터를 대상으로 기존의 대표적인 경로탐색 알고리즘(Dijkstra 와 A*)과 제안된 알고리즘(A+S+DAS)에 대한 최단 경로 탐색과 연산비용 및 운행시간을 비교 분석하였다. 본 시뮬레이션 결과로부터 A+S +DAS가 기존 알고리즘에 비해 교통사고가 빈번히 발생하는 위험지역을 회피하면서 효율적인 탐색비용으로 출발지점에서 목적지 점까지의 최단경로를 탐색할 수 있음을 보였다.
표 1은 그림 1의 테스트 지도를 대상으로 Dijkstra, A* 알고리즘, 제안 알고리즘으로 경로를 탐색한 결과이다. 앞의 두 알고리즘은 (위험지역을 회피하지 않는) 기존 경로탐색 알고리즘으로, 제안 알고리즘과의 비교를 위하여 실험하였다. 본 논문에서 제안한 알고리즘의 경우(이하 A+S+DAS로 표기함) Dijkstra와 A* 알고리즘과 달리 세 가지 위험도 가중치 A, S, DAS를 결합하여 경로를 탐색한 결과이다.
마지막으로, 그림 4 (a), (b), (c)는 각각 그림 3의 최단경로를 찾기 위한 연산비용(탐색영역)을 나타낸다. 여기서 세 알고리즘으로 탐색(방문평가)하였을 경우의 탐색영역(노드)를 검은 실선으로 표기하였으며, 최종 목적지 도착까지 경로는 분홍색실선으로 표시하였다.
본 논문에서는 A* 알고리즘의 탐색방향 데이터(이를 h라 함)를 사용하여 출발지점에서 목적지점까지 최단경로를 검색한다. 이 때 문헌[5]에서와 같이 A* 알고리즘에 교통이 혼잡한 시간과 검색 영역을 세부 분리한 후 경로를 탐색하는 방법을 고려하여, 최단 시간 내에 목적지점에 도착할 수 있는 경로를 제시한다. 또한 본 논문에서는 사고발생이 높은 위험지역과 위험빈도가 높은 시간대를 고려하는 가중치를 사용하며, 지역과 시간대에 따라 동적으로 위험지역을 회피할 수 있는 탐색 방식을 사용한다.
본 논문에서는 A* 알고리즘을 이용하여 위험지역을 회피한 경로를 탐색하여 안전운전 경로를 서비스하는 방법을 연구한다. 즉 기존의 단순한 최단경로 탐색 방식과는 달리, 운전자가 원하는 운행구간에서 위험지역을 회피하면서 목적지에 빠르게 도착할 수 있도록 하는 안전운전 경로탐색 방법을 검토한다.
대상 데이터
본 논문에서는 사고 다발구간의 가중치 계산에 사용되는 비례상수 αA값을 2로 선정하였다.
내비게이션 경로탐색은 출발지점에서 목적지점까지 위험지역을 회피한 루트를 사전에 파악하여, 안전운전에 도움을 줄 수 있도록 하는 것으로, 본 논문에서는 탐색엔진으로 A* 알고리즘을 이용한다. 위험지역으로는 사고 다발구간, 어린이 보호구역 및 교차로지역 등 세 종류를 고려한다. 또한 어린이 보호구역은 위험시간대 별로 경로탐색 회피여부를 결정한다.
이론/모형
본 논문에서는 안전운전을 위해 위험지역을 회피하는 내비게이션 경로탐색 기법을 연구하였다. A* 알고리즘을 기본 탐색방식으로 사용하였으며, 위험지역과 위험시간대에서 가중치를 사용한 경로탐색을 사용하였다. 먼저, 위험지역은 사고 다발구간, 어린이 보호구역, 교차로지역에서 분류하여 사용하며, 위험시간대는 어린이 보호구역에서 사용한다.
차량용 내비게이션 시스템은 출발지점에서 목적지점 까지의 최적경로를 탐색하고, 탐색된 경로를 이용하여 길을 안내하는 시스템이다. 내비게이션은 차량위치를 파악하기 위해 GPS(global positioning system)[1]를 활용한다. GPS 기술은 1990년대부터 산업, 운송, 레저, 스포츠 분야에서 광범위하게 사용되기 시작하였으며, 2000년대부터 차량용 내비게이션으로 빠르게 성장하고 있다.
이 중에서 내비게이션 경로탐색 알고리즘은 Dijkstra와 A*를 기반으로 경로탐색 시간을 단축하기 위해 양방향 검색 방식을 사용하는 Bi-directional Dijkstra와 Bi-directional A*를 사용한다[5]. 또한 검색 영역을 작은 영역으로 분할하여 검색하는 Stochastic time-dependent planning 방식[6]을 사용하였으며, 그 밖에 다양한 차량운행 환경에서 최단 경로탐색 알고리즘 연구[7-8]가 진행되었다.
특히 A* 알고리즘을 활용하는 방법에 대한 다양한 연구[4]가 진행되었으며, 검색 속도, 검색 장비에 따른 메모리용량 최소화, 실시간 검색 등의 응용으로 대별할 수 있다. 이 중에서 내비게이션 경로탐색 알고리즘은 Dijkstra와 A*를 기반으로 경로탐색 시간을 단축하기 위해 양방향 검색 방식을 사용하는 Bi-directional Dijkstra와 Bi-directional A*를 사용한다[5]. 또한 검색 영역을 작은 영역으로 분할하여 검색하는 Stochastic time-dependent planning 방식[6]을 사용하였으며, 그 밖에 다양한 차량운행 환경에서 최단 경로탐색 알고리즘 연구[7-8]가 진행되었다.
성능/효과
둘째, 어린이 보호구역은 교통사고의 위험으로부터 어린이를 보호하기 위한 지역으로, 어린이집, 유치원, 초등학교, 특수학교 등이 해당되며, 자동차 등의 통행속도를 시속 30km 이내로 제한한다.[10]
표 4에서 A* 알고리즘의 연산비용은 74이며, A+S +DAS 알고리즘에서 g+w+h 연산비용은 113이다. 따라서 그림 1에서 링크의 수가 60개 이므로 A* 알고리즘의 연산비용은 123% 증가한 반면 A+S+DAS 연산비용은 188% 증가함을 알 수 있다.
끝으로 운행 시간은 노드와 노드 사이를 주행하는데 필요한 시간과 교차로 지역에서 방향변경에 기인한 감속 및 가속 지연시간을 합한 값이다. 따라서 방향을 바꾼 교차로 수를 크게 줄인 제안 알고리즘이 A*보다 더 빨리 도착지점에 도달할 수 있음을 보인다. 그러나 Dijkstra보다는 다소 증가하게 된다.
모의실험 결과, 제안한 방법으로 기존 경로탐색인 Dijkstra와 A* 알고리즘보다 향상된 경로탐색으로 위험지역을 회피할 수 있음을 보이고, 위험지역의 유형과 위험시간대에 따라 경로탐색 결과가 달라질 수 있음을 보인다. 즉, 운전 경로를 탐색할 때 사고발생 가능성이 높은 지역과 위험시간대를 회피하는 방법으로 안전운전에 도움을 줄 수 있도록 한다.
앞의 두 알고리즘은 (위험지역을 회피하지 않는) 기존 경로탐색 알고리즘으로, 제안 알고리즘과의 비교를 위하여 실험하였다. 본 논문에서 제안한 알고리즘의 경우(이하 A+S+DAS로 표기함) Dijkstra와 A* 알고리즘과 달리 세 가지 위험도 가중치 A, S, DAS를 결합하여 경로를 탐색한 결과이다. 여기서 pn1n2은 그림 1에서 표시된 노드 N1에서 노드 N2까지의 경로를 나타낸다.
시각적인 관찰이 가능한 컴퓨터 시뮬레이션을 통해서 1600(40*40)개의 노드와 세 종류 위험지역을 표기할수 있는 지도 데이터를 생성하였고, 이 지도 데이터를 대상으로 기존의 대표적인 경로탐색 알고리즘(Dijkstra 와 A*)과 제안된 알고리즘(A+S+DAS)에 대한 최단 경로 탐색과 연산비용 및 운행시간을 비교 분석하였다. 본 시뮬레이션 결과로부터 A+S +DAS가 기존 알고리즘에 비해 교통사고가 빈번히 발생하는 위험지역을 회피하면서 효율적인 탐색비용으로 출발지점에서 목적지 점까지의 최단경로를 탐색할 수 있음을 보였다.
이는 αA 값이 일정 범위보다 커지는 경우, 사고 다발구간을 회피하는 대신 어린이 보호구역이나 교차로지역을 통과하게 되는 경우가 발생하기 때문이다. 즉, 사고다발 구간의 가중치 값이 다른 위험지역의 가중치에 영향을 줄 수 있음을 알 수 있다. 이와 같은 실험결과에 따라 본 연구에서는 αA = 2로 선정하였다.
후속연구
또한 최단경로 탐색을 위한 연산비용과 주행시간의 산출에서 선형 식을 모든 노드에 일률적으로 적용하였다. 그러나 지역에 따라 또 시간대에 따라 비선형 관계식이 적용될 수 있으며, 앞으로 이에 대한 연구도 필요하다.
따라서 실제의 도로 상황을 염두에 둔 최적의 αA값을 산출하기 위한 추가적인 연구가 필요하다.
질의응답
핵심어
질문
논문에서 추출한 답변
차량용 내비게이션 시스템이란?
차량용 내비게이션 시스템은 출발지점에서 목적지점 까지의 최적경로를 탐색하고, 탐색된 경로를 이용하여 길을 안내하는 시스템이다. 내비게이션은 차량위치를 파악하기 위해 GPS(global positioning system)[1]를 활 용한다.
내비게이션은 무엇을 위해 GPS를 활용하는가?
차량용 내비게이션 시스템은 출발지점에서 목적지점 까지의 최적경로를 탐색하고, 탐색된 경로를 이용하여 길을 안내하는 시스템이다. 내비게이션은 차량위치를 파악하기 위해 GPS(global positioning system)[1]를 활 용한다. GPS 기술은 1990년대부터 산업, 운송, 레저, 스 포츠 분야에서 광범위하게 사용되기 시작하였으며, 2000년대부터 차량용 내비게이션으로 빠르게 성장하고 있다.
차량위치를 파악하기 위해 사용되는 GPS기술는 어떻게 발전되고 있는가?
내비게이션은 차량위치를 파악하기 위해 GPS(global positioning system)[1]를 활 용한다. GPS 기술은 1990년대부터 산업, 운송, 레저, 스 포츠 분야에서 광범위하게 사용되기 시작하였으며, 2000년대부터 차량용 내비게이션으로 빠르게 성장하고 있다.
참고문헌 (14)
Hofmann-Wellenhof, B., Lichtenegger, H., Collins, J., Global Positioning System: Theory and Practice, Springer-Verlag, New York, 2001.
Dijkstra, E. W., "A note on two problems in connextion with graphs", Numerische Mathematik, vol. 1, no. 1, pp. 269-271, 1959.
Hart, P. E., Nilsson, N. J., Raphael, B., "A formal basis for the heuristic determination of minimum cost paths", IEEE Transactions on System Science and Cybernetics, vol. 4, no. 2, pp. 100-107, 1968.
Rios, L. H. O., Chaimowicz, L., "A survey and classification of A* based best-first heuristic search algorithms", Proceeding of the 20th Brazilian Symposium on Artificial Intelligence (SBIA 2010), vol. 6404, pp. 253-262, 2010.
이재무, 김종훈, 전홍식, "차량 항법 시스템의 경로 탐색을 위한 탐색 알고리즘의 성능 비교", 정보교육학회 논문지, 제2권, 제2호, 252-259쪽, 1998년
※ AI-Helper는 부적절한 답변을 할 수 있습니다.