KR20140034869A

KR20140034869A - 정보 수집 및 검색을 통한 루트의 제공 기법

Info

Publication number: KR20140034869A
Application number: KR1020137034648A
Authority: KR
Inventors: 이얄 오펙; 제프리 쿡쿠이트; 구르 킴치; 브라이언 벡맨
Original assignee: 마이크로소프트 코포레이션
Priority date: 2011-06-28
Filing date: 2012-06-02
Publication date: 2014-03-20
Anticipated expiration: 2032-06-02
Also published as: WO2013002961A2; EP2726818A4; WO2013002961A3; US8954266B2; KR101994496B1; CN103620345A; EP2726818A2; CN103620345B; US20130006517A1; JP2014527617A

Abstract

포인트 A로부터 포인트 B로의 이동 방향을 제공하는 것은 정보 검색의 문제로 다뤄질 수 있다. 일 예에서, 사람들에 의해 여행된 실제 루트가 수신되고 데이터베이스에 저장된다. 어떤 사람이 포인트 A로부터 포인트 B로의 이동 방향을 요청하면, 시스템은 데이터베이스를 검색하여 A로부터 B로의 루트가 존재하는지 판정한다. 만약 위 루트가 존재하면, 루트는 상기 요청에 응답하여 이동 방향으로서 제공될 수 있다. 위 루트가 존재하지 않으면, 시스템은 데이터베이스를 탐색하여 서로 어느 정도 중첩되는 루트들을 찾으며, 서로 중첩되는 알려진 루트들을 결합하여 A로부터 B로의 루트를 설계하려고 시도한다. 루트들이 결합되기 이전에, 규칙은 루트들이 중첩되어야 하는 정도를 관리할 수 있다.

Description

정보 수집 및 검색을 통한 루트의 제공 기법{PROVIDING ROUTES THROUGH INFORMATION COLLECTION AND RETRIEVAL}

많은 시스템들이 드라이빙, 도보(walking), 또는 공공 교통 이동 방향(direction)을 제공한다. BING Maps 및 MapQuest와 같은 웹 사이트들은 특정 장소에서 다른 장소로의 이러한 종류의 이동 방향을 제공할 수 있다. 또한 자동차 네비게이션 박스 및 대쉬보드 콘솔(dashboard consoles)와 같은 다양한 독립 시스템도 이동 방향을 제공할 수 있다. 일반적으로, 특정 지점에서 다른 지점으로의 이동 방향을 탐색하는 과제는 맵을 나타내는 에지-가중된 이동 방향 그래프(edge-weighted directed graph)를 사용하고 이러한 그래프를 통해 최저 비용 경로를 탐색하기 위해 Dijkstra's algorithm 또는 A*과 같은 알고리즘을 적용하는 것에 의해 해결된다.

이러한 방식으로 이동 방향을 제공하는 것의 문제점은, 이러한 방식이 그래프가 정확한 연결 정보를 가지고 있으며 최신의 것(up-to-date)이라는 가정한다는 점에 있다. 연결성은 그래프 상의 브랜치(branch)들이 실제 지형에서 이루어질 수 있는 턴(turn)들을 나타내는지를 가리키는 속성이다. 예를 들어, 만약 노드 A, B 및 C가 맵 상에 위치하고 그래프가 노드 A로부터 노드 B 및 노드 C 둘 다로 브랜치 가능하다고 도시하는 경우, 실생활에서도 양쪽 브랜치 모두를 선택하는 것이 가능하다고 가정된다. 만약 실생활에서 이러한 브랜치들에 대응하는 턴이 이루어질 수 없다면, 그래프의 연결성 정보가 부정확한 것이다. 또한, 실생활에서, 도로가 추가되거나 공사를 위해 폐쇄되거나 재정렬되기 때문에 그래프 내의 정보는 최신의 것이 아니게 된다.

디지털 맵 제공자들은 자신들의 지도를 정확하고 최신으로 유지하기 위해 노력을 기울인다. 그러나 이는 어려운 작업이며, 그들의 기술에 의해 제공되는 많은 이동 방향은 부정확할 수 있다.

이미 존재하는 루트에 대한 정보는 사람들이 실제로 여행하는 루트에 기초하여 지속적으로 수집될 수 있다. 이러한 루트들은 저장될 수 있다. 특정 사람이 이동 방향을 요청하면, 루트들은 실시간으로 검색되어 이동 방향을 제공할 수 있다. 저장소 내에 포인트 A로부터 포인트 B로의 완전한 루트가 없는 경우, 저장소 내에 존재하는 루트들은 그들이 특정한 속성을 만족하여 서로 중첩되는 한 서로 패치(patch)되어 완전한 루트를 생성할 수 있다. 이러한 방법으로, 이동 방향을 제공하는 과제는, 추상적인 그래프로부터 연산을 수행하는 문제가 아닌 정보 검색의 문제로 효율적으로 감소된다. 사람들이 여행한 루트들을 사용하는 것은 어떠한 루트들이 존재하는지에 대한 정보를 보다 신뢰성 있게 만든다. 또한, 어떠한 루트로 사람들에 의해 여행되는지에 대한 정보가 지속적으로 수집되므로, 어떤 루트가 사용 가능한지에 대한 정보는 최신의 것일 가능성이 높다.

사람들이 여행하는 루트에 대한 정보를 수집하기 위해, 많은 사람들의 그들의 위치를 정확히 찾아낼 수 있는(pinpoint) 장치들, 예를 들어, 네비게이션 박스, GPS 수신기를 구비한 스마트폰 등을 가지고 다닌다는 점이 주시된다. 몇몇 사람들은 프라이버시의 목적으로 이들 특징들을 비활성화(turn-off)하지만, 다른 사람들은 장치가 그들의 위치를 지속적으로 판정하고 서비스에 의해 이러한 정보가 수집되는 것에 사전동의(opt-in)하길 바랄 수 있다. 만약 충분한 수의 사람이 이러한 유형의 정보가 수집되는 것을 꺼리지 않는다면, 수집된 순수한 지리 좌표들은 사람들이 여행하는 루트들에 대한 지속적으로 업데이트된 정보를 제공한다. 또한, 수집된 정보가 실제 루트들을 나타내므로, 이러한 정보는 맵 상에 나타나는 턴들 중 어떤 것들이 실생활에서도 실제로 일어날 수 있는지, 루트를 여행하기 위해 어느 정도의 시간이 소요되는지, 하루 중의 시기에 여행 시간 및 턴의 사용가능성이 어떻게 연관되는지, 자동자 내의 사람의 수가 여행 시간 및 턴의 사용가능성과 어떻게 연관되는지, 및 기타 요소들을 지속적으로 인증한다.

루트들에 대한 데이터베이스가 수집되면, 데이터베이스는 이동 방향에 대한 요청에 응답하기 위해 사용될 수 있다. 누군가 포인트 A로부터 포인트 B로의 루트를 요청하면, 데이터베이스는 검색되어 이러한 루트가 데이터베이스 내에 저장되어 있는지 판정한다. 만약 루트가 저장되어 있으면, 이는 검색되어 이동 방향으로서 제공될 수 있다. 만약 루트가 저장소 내에 저장되어 있지 않으면, 데이터베이스는 포인트 A의 근방에서 포인트 B의 근방으로 가는 가장 긴 루트를 탐색하기 위해 검색되고(또는, 일 예로서, 가장 긴 루트는 가장 긴 루트의 레그(legs)들이 보다 짧은 루트들과 일치한다는 측면에서 제공됨), 데이터베이스는 이러한 긴 루트의 출발 및 도착 지점으로부터 실제 포인트 A 및 포인트 B로 가는 루트를 탐색하기 위해 검색될 수 있다. 실제적으로, 이러한 프로세스는 먼저 긴 루트를 찾은 다음 함께 패치될 수 있는 작은 루트들을 이동 방향의 완전한 세트가 생성될 때까지 찾을 수 있다.

맵 상에 존재하는 턴들이 실생활에 존재할 수도 존재하지 않을 수도 있으므로, 완전한 루트를 생성하기 위해 부분적인 루트들을 결합하는 시스템은 결합될 루트들이 서로 공통으로 몇 개의 턴들을 공유할 것을 요구할 수 있다. 이러한 조건은 시스템이 실생활에 인증되지 않은 루트들을 제공하는 것을 방지한다. 루트를 결합하기 위한 이러한 기준은 루트들이 전술한 것과 같은 실생활 데이터를 통해 결정되는지 또는 루트들이 관련된 지형의 추상적인 표현으로부터 연산된 루트일 뿐인지에 무관하게 사용될 수 있다.

본 요약은 이하의 상세한 설명에서 보다 자세히 설명될 선택적인 개념들의 단순화된 형태를 소개하기 위해 제시된다. 본 요약은 청구된 발명의 핵심적 특징 또는 필수적 특징을 식별하기 위한 것이 아니며, 청구된 발명의 범위를 한정하고자는 의도를 가지지도 않는다.

도 1은 어떤 루트들이 여행 가능한지에 대한 예시적인 맵의 블록 다이어그램이다.
도 2는 알려진 루트의 데이터베이스를 형성하기 위해 사용 가능한 컴포넌트들의 예시적인 세트의 블록 다이어그램이다.
도 3은 GPS 트레일(trail)에 기초하여 루트들의 데이터베이스를 형성하는 예시적인 프로세스의 흐름도이다.
도 4는 루트 질의에 응답하기 위해 사용 가능한 예시적인 시스템의 블록 다이어그램이다.
도 5는 이미 존재하는 알려진 루트들을 검색하는 것에 의해 루트 질의에 응답하는 예시적인 프로세스의 흐름도이다.
도 6은 본 발명의 구현 예들과 관련하여 사용 가능한 예시적인 컴포넌트들의 블록 다이어그램이다.

많은 시스템들이 포인트 A로부터 포인트 B로의 이동 방향(direction)을 제공한다. 예를 들어, BING Maps 및 MapQuest와 같은 웹 사이트들은 맵 상의 임의의 위치들 사이에서 드라이빙, 도보, 또는 공공 교통 이동 방향을 제공할 수 있다. 마찬가지로 자동차 네비게이션 박스 및 대쉬보드 콘솔(dashboard consoles)도 이동 방향을 제공할 수 있다. 일반적으로, 맵을 나타내는 에지-가중된 이동 방향 그래프(edge-weighted directed graph)로부터 이동 방향이 연산된다. 구체적으로, 맵은 노드들의 세트, 노드들 사이의 방향을 갖는 에지(directed edges), 각 에지와 연관된 가중치로서 나타난다. 각 노드는 맵 상의 교차점(intersection)을 나타낸다. 각 에지는 하나의 교차점에서 다른 교차점으로의 경로를 나타내며, 에지는 교차점들 사이의 경로가 존재한다고 추정되는 한 존재하고, 또한, 각 에지와 연관된 가중치는 해당 경로를 따라 여행하는 것의 비용(예: 여행 시간)이다. 그래프 내의 하나의 노드에서 다른 노드로의 최저 비용 경로를 탐색하기 위해 Dijkstra's algorithm 또는 A*과 같은 알고리즘이 사용될 수 있다. 이러한 방식에 의해, 그래프는 포인트 A로부터 포인트 B로부터의 이동 방향을 연산하기 위해 사용될 수 있다.

이러한 방식으로 이동 방향을 제공하는 경우, 몇 가지 문제점들이 발생할 수 있다. 먼저, 그래프는 이미 존재하는 맵들 또는 지형의 대형 사진(large scale photography)으로부터 생성되며, 이러한 데이터 소스들은 연결성에 대한 정보를 정확히 제공하지 않을 수 있다. 맵은 두 개의 도로가 교차한다고 보여줄 수 있지만, 이러한 경우에도 예를 들어 하나의 도로가 다른 도로의 고가 도로(overpass)이거나, 로컬 정부가 턴 불가능(no-turn) 표지를 설치했거나, 교통 체증이 너무 심해서 실제 운전자들이 해당 교차점에서 턴을 하지 않는 등의 이유로 하나의 도로에서 다른 도로로 턴하는 것이 가능하지 않을 수 있다. 예를 들어, 만약 맨하탄(Manhattan)에 있는 어떤 사람이 11th Avenue 및 42nd Street의 코너로부터 6to Avenue 및 Central Park South의 코너로 여행하고 싶다면, 그래프는 42nd Street에서 동쪽으로 여행한 다음 6th Avenue에서 왼쪽으로 턴하고 북쪽으로 진행하여 Central Park로 가는 것이 가능하다고 나타낼 수 있다. 이러한 루트는 이론적으로는 실생활에서 가능하지만, 뉴욕시가 6th Avenue의 42nd Street에서 왼쪽 턴을 하는 것에 시간 제한을 부여하고 있으며, 이러한 턴이 가능한 시간대에 있어서도 교통 체증 때문에 이러한 턴을 하기 위해서는 너무 많은 시간이 소요되어 오직 매우 용감한 운전자들만이 이러한 턴을 시도한다는 사실을 고려하고 있지 않다. 특히 전술한 맨하탄 교차점과 같은 주지의 병리학적 케이스의 경우, 맵 제공자는 이러한 이슈에 대한 지식을 수집하고 그들의 지형 모델에 이러한 지식을 빌딩하기 위해 자원을 투자할 수 있다. 그러나, 맵 상에 도시된 것이 실제로는 매칭되지 않는 많은 장소가 있으며, 이러한 상황을 모두 식별하고 모델링하기는 어렵다. 전술한 예들은 연결성 문제들, 즉, 맵 상에는 두 도로 사이의 연결이 존재하는 것으로 보이지만 실제로는 이러한 연결이 존재하지 않는 경우, 하루 중 특정 시간에만 연결이 존재하는 경우, 이러한 연결을 운전 이동 방향의 세트에 포함하는 것을 피하는 이유가 있어서 연결되기 어려운 경우를 설명한다.

두 번째 문제는 여행 가능한 루트들이 시간에 따라 변하는 경향을 가진다는 점에서 발생한다. 새로운 도로가 추가된다. 오래된 도로는 유지보수를 위해 일시적으로 사용되지 않거나 재정렬된다. 교통 패턴도 바뀌어, 한 때는 여행하기 쉬웠던 루트들이 여행하기 어려워질 수도 있다. 새로운 교통 제한들이 추가되어, 한 때는 허용되었던 턴들이 불법이 될 수 있다. 맵 제공자가 이러한 종류의 변화에 계속 부응하는 것은 정보를 수집하고 분석하고 이러한 정보를 이동 방향이 연산되는 지형 모델(그래프 등)에 추가하기 위해 자원의 소비가 필요하다는 점에서 어렵다.

또한, 에지 가중된 방향 그래프(edge-weighted directed graph)는 일반적으로 가중치(비용)을 그래프 상의 에지(즉, 하나의 노드로부터 다른 노드로의 경로)와 연관시킨다. 그러나, 실생활에서, 여행의 가장 고비용(예, 시간 소비적)의 부분은 교차점일 수 있으며 직선 도로가 아닐 수 있다. 예를 들어, 전술한 맨하탄의 예에서, 42nd Street을 운전해 지나가는데 1분만 소요되고, 6th Avenue까지 운전하는 것은 또 1분이 소요되지만, (턴이 허용되는 시간대에서조차도) 하나의 도로에서 다른 도로로 좌측으로 턴하는 것은 5분이 소요될 수 있다. 다시 말해서, 에지 가중된 방향 그래프는 특정 노드로부터의 특정 브랜치(branch)를 선택함에 따라 턴을 하는 것의 비용을 감소시키는 것에 대한 비용을 고려하지 않으며, 이에 따라, 모든 루트들이 실생활보다 저비용으로 보이게끔 만든다. 그러나 포인트 A로부터 포인트 B로의 가장 빠른 루트를 찾고 있는 운전자는 이러한 턴이 얼마나 오래 소요되는지에 대해 많은 관심을 가질 수 있다.

본 발명은 운전 이동 방향을 제공하는 문제를 정보 수집 및 검색의 문제로서 다룬다. 실제로 여행될 수 있는 루트들에 대한 정보는 사람들이 실제로 여행하는 루트에 기초하여 실시간으로 수집된다. 모든 교차점을 그래프 내의 노드로서 처리하는 맵의 추상 모델로부터 이동 방향으로 설계하는 것 대신에, 본 발명은 이미 알려진 정보의 세트를 사람들이 실제로 여행하는 루트의 세트로 모델링하고, 알려진 중첩되는 루트들로부터 루트를 합침으로써 이동 방향의 세트를 설계한다.

루트들에 대한 정보는 사람들이 들고 다니는 장치들 또는 사람들이 그들의 자동차 내에 빌트-인 되어 있는 GPS(Global Positioning System) 트레일들로부터 수집된다. (전술한 것처럼, 프라이버시를 위해 어떤 사람들은 그들의 위치가 추적되는 것을 사전 동의하지 않겠지만, 많은 사람들이 그들의 위치 및 움직임이 추적되는 것을 동의할 수 있다. 몇 가지 경우에, 사람들이 이러한 유형의 추적에 명시적으로 동의하도록 인센티브가 제공될 수 있다.) 시간 경과에 따른 GPS 구비된 장치들로부터의 순수 지형 좌표는 맵에 대하여 상호 참조되어, 이러한 순수 데이터가 사람들에 의해 여행되는 실제 루트로 변환될 수 있다. (예를 들어, 좌표는 10초마다 수신될 수 있으며, 실제 맵 상에서 시간에 걸친 좌표의 변화를 비교함으로써, 특정 사람이 여행한 루트를 판정하는 것이 가능할 수 있다.) 여행된 루트들은 데이터베이스에 저장된다. 루트들과 함께 루트가 여행된 시간대에 대한 정보, 루트를 여행하기 위해 얼마나 소요되었는지에 대한 정보, 루트가 여행될 때 얼마나 많은 사람들이 차량에 탑승하고 있었는지에 대한 정보, 어떤 유형의 차량이 사용되었는지에 대한 정보, 또는 임의의 유형의 정보가 있을 수 있다. 이러한 정보는 어떤 루트가 하루 중 어떤 시간대에 붐비는지, 또는 루트의 어느 영역이 시간 제한에 걸리는지 (예: 오전 9시부터 오후 5시까지 좌회전 금지), 또는 루트의 어느 부분이 탑승 인원 또는 차량 유형 제한(occupancy or vehicle type restrictions)에 걸리는지 (예: 루트가 차량에 적어도 세 명을 타고 있을 것을 요구하는 다수 탑승 인원 차량(High Occupancy Vehicle, HOV) 차선을 가지만, 버스나 1인 탑승 오토바이는 허용되는 경우)를 판정하는데 관련될 수 있다. (이상과 같은 예들이 GPS 트레일들로부터 위치 정보가 수집되는 것을 가정하지만, 이는 다른 기술들, 예를 들어, WiFi localization, 관성 센서, 삼각 측량(triangulation) 등으로부터 수집될 수도 있다. GPS 트레일과 마찬가지로, 이러한 정보는 사용자로부터 수신된 적절한 허가에 의거하여 수집될 수 있다.)

(전술한 기술을 사용하여 수집된 것과 같은) 이미 알려진 루트들의 세트를 가지는 몇 개의 데이터베이스가 존재한다는 가정 하에, 이동 방향을 제공하는 시스템은 이미 존재하는 루트들로부터의 이동 방향의 세트를 함께 합칠 수 있다(patch together). 루트들은 "레그(legs)"로 만들어지는데 이들은 교차점들 사이의 세그먼트들이다. (이 경우에서의 "교차점"은 하나 이상의 이동 방향으로 턴할 수 있는 포인트이다.) 만약 어떤 사람이 포인트 A와 포인트 B 사이의 이동 방향을 요청하면, 시스템은 이들 두 개의 포인트 사이에 알려진 실제 루트가 존재하는지 여부를 판정하기 위해 데이터베이스를 탐색한다. 만약 이러한 루트가 존재하면, 해당 루트가 이동 방향으로서 제공될 수 있다 (시스템은 작은 루트들의 세트로부터 보다 저비용인 루트를 설계하려고 시도할 수도 있다). 일반적으로, 긴 루트일수록 하나의 포인트로부터 다른 포인트로 도달하기 위해 실제 사람들에 의해 내려진 더 많은 결정들의 세트를 가지기 때문에 긴 루트가 더 많은 도움이 된다고 여겨진다. (이러한 상황을 뷰하기 위한 하나의 방법은 짧은 루트들로부터 합쳐진 루트에 비해 보다 긴 루트가 보다 신뢰성이 있다는 것은 하나의 언어로부터 다른 언어로 번역을 할 때 문장 내의 개별 단어들을 번역한 후 합친 것보다 전체 문장을 번역하는 것이 더 정확한 것과 동일한 맥락이다.) 긴 루트는 하나의 포인트로부터 다른 포인트로의 많은 부분을 커버할 수 있으므로, 긴 루트들은 루팅 프로세스(routing process)를 단순화 및 가속화할 수 있으며, 이에, 짧은 루트들이 사용되는 경우 수행되었어야 할 짜집기(splicing)의 양을 감소시킬 수 있다. (긴 루트가 특정인에 의해 우연하게 여행될 수 있으므로, 특정 경우에 있어서는, 몇 명의 사람들이 시간에 걸쳐 루트를 여행해야만 해당 루트가 신뢰될 수 있다. 또는, 긴 루트는 그들의 레그가 다른 짧은 루트들의 일부로서 집합적으로 여행되어야만 신뢰될 수도 있으며, 이에, 긴 루트의 정확성 및/또는 타당성을 강화할 수 있다.) 그러나, 만약 포인트 A로부터 포인트 B로의 전체 거리를 커버하는 루트가 사용 가능하지 않다면, 시스템은 다른 루트들을 조합하는 시도를 할 수 있다.

루트들을 조합하기 위해, 시스템은 적어도 하나의 레그가 중첩되고 적어도 하나의 턴을 공통으로 갖는 루트들을 탐색한다. 루트들이 턴을 공통으로 갖는다는 조건은 시스템이 실생활에서 입증되지 않은 하나의 루트로부터 다른 루트로의 턴을 이동 방향의 세트에 포함시키지 않는 것을 보증하기 위한 것이다. 이러한 턴들을 회피하는 것은 전술한 것과 같이 맵 상에는 나타나지만 실생활에서는 불가능하거나 실제적이지 않은 턴을 포함하는 것의 문제를 피할 수 있다. 결합될 루트들이 턴을 공통으로 갖는 조건을 적용함으로써 실제 사람들에게 가능하고 실제적이라고 입증된 턴들이 이동 방향에 포함될 것을 보증한다 (적어도 루트들이 사람들이 취한 실제 생활 여행으로부터 도출되는 예시들에서는 적어도 그렇다). (몇몇 경우, 시스템은 두 개, 세 개 또는 n 개의 연속적인 턴을 공통으로 갖는 것을 루트들을 결합하기 위한 조건으로 할 수도 있으며, 이는 보다 실제적인 루트들을 형성할 수 있다. 그러나 본 발명은 이러한 조건을 사용하는 시스템들에 한정되지는 않는다.)

전술한 것처럼, 긴 루트들은 짧은 루트들보다 더 정보량이 많다고 여겨지며, 이에 따라, 알려진 루트들로부터 이동 방향의 세트를 조합해나갈 때, 시스템은 (가능하게는, 긴 루트들의 레그가 다른 짧은 루트들의 일부로서 여행된 것에 의해 입증된다는 조건에 따라) 긴 루트들로부터 시작하되, 짧은 루트들을 엔드 포인트(endpoints)들끼리 연결하거나 빈 공간을 채울 때 사용할 수 있다. 예를 들어, 만약 어떤 사람이 Berkeley, California로부터 Princeton, New Jersey로 여행하고 싶다면, 이에 대한 루트를 Berkeley로부터 Winnemucca, Nevada, Winnemucca로부터 Pocatello, Idaho, Pocatello로부터 West Yellowstone, Montana, 그리고 West Yellowstone으로부터 Cody, Wyoming 등의 루트들을 결합하여 형성하는 것이 가능하다. 그러나, 이러한 방식으로 루트들을 결합하는 것 대신, 일 실시예에서 시스템은 Berkeley 근처의 포인트로부터 Princeton 근처의 포인트들로의 보다 긴 루트들을 탐색할 수도 있다. 따라서, 시스템은 San Francisco로부터 New York까지의 루트로 시작하여, Berkeley로부터 루트를 따라 가장 가까운 고속도로 입구로의 짧은 루트 및 고속도로 출구부터 Princeton으로의 짧은 루트를 탐색할 수 있다. 만약, Berkeley로부터 근방의 고속도로 입구로의 알려진 루트가 없다면, 시스템은 보다 세밀한 루트들, 예를 들어, Berkeley의 다운 타운으로부터 Berkeley의 Shattuck Avenue로의 루트 및 Shattuck Avenue로부터 I-580으로의 루트를 탐색할 수 있다. 일반적으로, 시스템은 포인트 A로부터 포인트 B로의 이동 방향의 완전한 세트가 생성될 때까지, 긴 루트들로 시작하여, 후속하여 결합될 보다 세밀한 루트들을 탐색할 수 있다.

도면을 참조하면, 도 1은 루트들이 여행될 수 있는 예시적인 맵(100)을 도시한다. 본 예에서, 맵(100)은 오른쪽 각도에 도로들을 갖는 직사각형 그리드로서 도시된다. 그러나, 맵이 임의의 모양의 경로를 따르는 임의의 세트의 도로로서 임의의 방식으로 교차되도록 도시될 수 있다는 것이 이해되어야 할 것이다.

맵(100)은 번호가 매겨진 도로들(1st Street 내지 7th Street)을 수평으로 가지고, 및 글자로된 도로들(A Street 내지 G Street)을 수직으로 가진다. 이들 도로들을 따라 알려진 루트들은 어둡고 두꺼운 라인들로서 도로들을 따라 도시되었다. 전술한 것처럼, 이들 루트들은 사람이 실제로 이들 루트들을 따라 여행하는 것이 관측되었다는 면에서 "알려진" 것이다. 그러나, 사람이 루트를 여행하는 것에 대한 실제 관측 이외에 특정 매커니즘을 통해 루트가 알려질 수도 있다. 도 1에 도시된 루트들은 루트들 및 루트들이 존재하는 맵의 다양한 속성을 나타낸다. 이러한 속성들에 대해서는 이하 설명한다.

루트(102)는 6th 및 A Streets의 코너로부터 시작되고 7th 및 B Streets의 코너에서 종료되는 루트이다. 루트(102)는 레그(104) 및 레그(106)의 두 개의 레그를 가진다. "레그"는 루트에서 턴 오프할 가능성이 없는 루트의 일부이다. 따라서, 레그(104)는 6th 및 A Streets의 코너로부터 6th 및 B Streets의 코너로의 루트(102)의 일부를 커버한다. 이들 두 코너 사이에 교차점이 없으므로, 이들 두 코너 사이의 루트(102)의 일부는 레그이다. 유사하게, 6th 및 B Streets의 코너와 7th 및 B Streets의 코너 사이에도 교차점이 없으며, 루트(102)의 해당 부분도 역시 레그(레그 106)이다. 유사하게, 루트(108)는 레그들(110, 112, 114)을 포함하는 세 개의 레그로 이루어진 루트이다. 비록 루트(108)가 (6th Street로 똑바로 진행하여) 어떠한 "턴"도 하지 않는 것으로 보이지만, 루트(108)는 여행자가 어디로 갈지에 대한 결정을 해야하는 두 개의 교차점을 건넌다는 점에서 "턴"들을 가진다고 여겨진다. 예를 들어, 6th 및 D Street의 교차점에서 왼쪽 턴, 우측 턴, 또는 직진이 가능하므로, 6th Street에서의 교차점에서 직진을 계속하는 결정은 "턴"으로서 이해된다. 이러한 루트(108)에 따른 두 개의 교차점은 루트를 세 개의 레그로 분리한다.

교차점을 직진으로 통과하는 것이 "턴"으로서 해석 가능한 것처럼, 물리적인 코너를 통해 진행하는 것도 "턴이 아닌" 것으로 이해될 수 있다. 예를 들어, 루트(116)은 G Street를 따라 아래로 진행하고 Null Street의 코너에서 90도 각도로 진행한다. 그러나, 이러한 90도 각도 지점에서 G Street가 끝나고 Null Street가 시작되므로, G Street를 따라 내려와 Null Street로 여행하는 사람은 Null Street로 좌측 턴을 하는 것 이외에 선택 사항이 없으므로, 이러한 각도를 따라 진행하는 것이 루트 상에 얼마나 많은 레그가 있는지를 판정하는 목적을 위한 "턴"으로 여겨지지 않는다.

다른 다양한 루트들도 도시되었다. 루트(118)는 1st 및 A Streets의 코너로부터 3rd 및 C Streets의 코너로 진행한다. 전술한 것과 같은 이유로, 1st 및 B, 1st 및 C, 및 2nd 및 C에서의 교차점은 모두 턴으로서 여겨진다. 이러한 세 개의 교차점이 있으므로, 루트(118)는 4개의 레그로 이루어진 루트이다. 루트(120)는 1st 및 C Streets로부터 4th 및 E Streets로 진행하는 5개의 레그로 이루어진 루트이다. 루트(122)는 3rd 및 D Streets로부터 5th 및 F Streets로 진행하는 6개의 레그로 이루어진 루트이다. 루트(124)는 1st 및 C Streets로부터 5th 및 F Streets로 진행하는 7개의 레그로 이루어진 루트이다. 이러한 루트들은 이동 방향의 세트를 제공하기 위해 알려진 루트들이 어떻게 결합될 수 있는지에 대한 다양한 예시를 설명하기 위해 아래에서 사용된다.

루트들(102, 108, 116, 118, 120, 122 및 124)이 데이터베이스에 저장되어 있고, 어떤 사람이 포인트 X (1st 및 A의 코너)로부터 포인트 Y (5th 및 F의 코너)로의 이동 방향을 요청했다고 가정한다. 포인트 X로부터 포인트 Y로 실제로 가는 단일의 알려진 루트는 없다고 관측된다. 그러나, 위 요청을 처리하는 시스템(예를 들어, 자동 네비게이션 시스템 또는 BING Maps와 같은 웹 사이트)은 이미 존재하는 루트들을 결합하여 X에서 Y로의 이동 방향을 생성하려고 시도할 것이다. 시스템은 먼저 루트(124) 전체를 루트(118)의 처음 두 개의 레그들과 결합하려고 시도할 수 있다. 그러나, 루트(118) 및 루트(124)는 레그나 턴을 공통으로 가지지 않는다. 전술한 것처럼, 본 발명의 일 실시예에서는 실생활에서 입증되지 않은 턴들을 생성하는 것을 피하며, 따라서 시스템은 위 두 개의 루트들을 결합하는 것을 회피할 수 있다. 루트들이 교차점을 공통으로 가지는 것으로 보일 수 있지만(즉, 1st 및 C Streets의 코너), 이들 루트들은 어떤 사람이 1st Street를 직진하여 C Street에서의 교차점을 지나는 것을 나타내지 않기 때문에, 위 교차점은 공통적인 턴을 나타내지 않는다. 다시 말해, C Street를 직진하여 지나가는 것은 특정 사람이 이 루트를 여행했다는 증거가 없기 때문에 시스템에 "알려진" 루트의 일부가 아니다. (예를 들어, 해당 교차점에 콘크리트 장벽이 있어 직진 통과가 불가능할 수도 있는데, 이것이 맵 상에 명확히 나타나지 않을 수도 있다.)

시스템은 루트(118), 루트(120), 및 루트(124)를 결합하려고 시도할 수도 있다. 도시된 것처럼, 루트(118) 및 루트(120)는 두 개의 중첩된 레그(1st 및 C에서 2nd 및 C로의 레그와, 2nd 및 C에서 3rd 및 C로의 레그)를 가진다. 그러나 루트(124)의 끝이 루트(120)이 종료되는 곳을 픽업(pick up)할 수 있는 것처럼 보이지만, 루트(120) 및 루트(124)가 공통적으로 레그나 턴을 가지지 않는다는 점을 눈여겨봐야 한다. 루트(120)가 4th 및 E Street의 코너에서 루트(124)의 수직 방향으로 종결되는데, 4th Street에서 E Street로 턴하는 알려진 루트는 존재하지 않는다. 따라서, 루트(124)는 루트(118) 및 루트(120)의 결합에 추가될 수 없다. 그러나, 루트(122)는 루트(120)와 두 개의 레그(3rd 및 D에서 4th 및 D로의 레그와 4th 및 D에서 4th 및 E로의 레그)를 공통으로 가진다. 따라서, X에서 Y로의 루트는 루트(118, 120, 122)의 일부를 결합하는 것에 의해 설계될 수 있다. 루트(118, 120, 122)를 결합하여 생성된 루트는 E Street를 따라 5th Street에서 6th Street로 가고 F Street의 아래 방향으로 6th Street에서 5th Street로 가므로 빙 돌아가는 것처럼 보인다. 그러나, 이 루트는 루트(122) 및 루트(124)를 결합함으로써 조금 짧아질 수 있다. 루트(122) 및 루트(124)가 4th 및 E에서 5th 및 E로의 레그를 공통으로 가지므로, 루트(122)를 루트(124)의 마지막 두 개의 레그와 결합하여 이러한 빙 돌아가는 루트를 회피할 수 있다. (그러나, 몇 구현 예에서는 둘 이상의 레그가 공통이어야 두 개의 루트를 결합할 수 있다고 할 수 있다. 보다 많은 수의 레그들을 공통으로 갖는 루트들은 사람들에 의해 실제로 여행된 복수의 레그들을 가지므로 실생활 여행을 보다 부드럽고 끊기지 않는 느낌으로 할 수 있도록 한다.)

만약 루트(118, 120, 122 및 124)들로부터 이동 방향의 세트가 생성되면, 포인트 X로부터 포인트 Y로의 완전한 이동 방향은 점 및 대쉬(dash) 처리된 라인(라인 126)으로 도시된다. 알려진 루트들의 세트를 합침으로써 설계된 이러한 이동 방향은, 포인트 A에서 포인트 B로 도달하는 방법으로서 요청자에게 제공될 수 있다. 이러한 방법에 의해, 이동 방향을 제공하는 문제는 이미 알려진 루트들의 데이터베이스로부터 루트들의 올바른 조합을 검색하고 이들 루트들을 합치기 위한 특정 규칙을 준수하는 문제로 귀결된다.

도 1의 예에 도시된 루트들은 화살표로 표시된 것처럼 방향성을 가진다. 예를 들어, 루트(102)는 6th 및 A Streets의 코너로부터 7th 및 B Streets의 코너로 가는 루트이다. 7th 및 B Streets의 코너로부터 6th 및 A Streets의 코너로 반대 방향으로 가는 루트가 아니다. 본 발명의 일 실시예에서는 사람들이 실제로 여행한 루트에 대한 정보를 제공하는 것이며, 특정 루트를 하나의 방향으로 여행하는 것은 해당 루트를 반대 방향으로 여행하는 것과 상이한 이슈들을 제시할 수 있다. (예를 들어, 도로들은 일방 통행이거나, 사람이 여행하는 길이나 턴의 방향에 따라 특정 턴들이 불법일 수 있다.) 그러나, 본 발명은 방향성을 갖는 루트들에 한정되지는 않으며, 방향성을 가지지 않는 루트들을 사용하는 시스템을 포함한다.

도 2는 알려진 루트들의 데이터베이스를 설계하는데 사용되는 컴포넌트들의 에시적인 세트를 도시한다. 도 2의 에시는 사람들이 실제 여행한 루트들로부터 설계된 데이터베이스를 도시한다. 그러나, 전술한 것처럼, 본 발명의 특정 예시들은 이러한 방식으로 알려진 루트들이 수집되는 경우에 한정되지는 않는다.

도 2에서, 차량(202)은 루트(화살표 204에 의해 표시됨)를 따라 여행한다. 차량(202)은, 예를 들어, 차로 도시되었지만, 차량(202)은 버스, 트럭, 오토바이, 자전거 등과 같은 임의의 유형의 차량이 될 수 있다. 또한, 도 2의 예시에서는 루트가 차량에 의해 여행되는 것으로 도시되었지만, 다른 예에서 루트는 임의의 유형의 차량으로 움직이지 않는 보행자에 의해 여행될 수도 있다.

차량(202)은 GPS 장치(206)를 구비한다. GPS 장치(206)는 휴대용 네비게이션 박스, 대쉬보드 탑재 네비게이션 콘솔, GPS 수신기를 구비하는 스마트폰, 또는 임의의 다른 유형의 장치일 수 있다. GPS 장치(206)는 스스로의 지구상의 현재 위치를 판정하고 해당 위치의 좌표를 수신기에 전송할 수 있다. (전술한 것처럼, 프라이버시를 위해 어떤 사람은 그 또는 그녀의 위치가 추적 및 전송되는 것을 선택하지 않을 수 있으나, 어떤 사람들은 그들의 위치가 전송되는 것을 자발적으로 선택할 것이다.) GPS 장치(206)는 자신의 정보를 예를 들어 휴대폰 네트워크를 통해 GPS 트레일 수신기(208)로 전송한다.

GPS 트레일 수신기(208)가 수신하는 정보는 특정 기간 동안에 전파되는 좌표의 스트림이 될 수 있다. 예를 들어, GPS 트레일 수신기(208)는 차량(202)이 여행하는 전체 시간 동안에 매 10초마다 좌표를 수신할 수 있다. 이러한 좌표들을 사용하여, 차량(202)에 의해 어떤 루트가 여행되는지, 여행을 위해 해당 루트가 얼마나 소요되었는지, 및 해당 루트의 특정 부분이 얼마나 소요되었는지를 판정하는 것이 가능하다. GPS 트레일 수신기는 이러한 정보를 GPS 트레일들에 기초하여 루트들을 생성하는 역할을 하는 GPS 트레일-대-맵 대응 엔진(GPS trail-to-map correspondence engine, 210)에 제공할 수 있다. 좌표들은 단순한 순수 위치 데이터(예를 들어, 위도 및 경도 좌표)이므로, 엔진(210)은 이러한 좌표들을 실제 맵 상에 적용하여 차량(202)에 의해 어떤 루트들이 여행되었는지 판정할 수 있다. 예를 들어, GPS 트레일 수신기는 차량(202)이 다음과 같은 위치에 다음과 같은 시간에 있었다는 것을 탐지할 수 있다.

그러나, 엔진(210)은 이러한 시간 및 좌표가 차량(202)이 시애틀의 4th Street에서 Madison 및 Union Streets 사이로 북쪽으로 여행한다는 것을 나타낼 수 있다.

엔진(210)이 실제 루트(212)가 GPS 트레일에 대응한다는 것을 판정하면, 엔진(210)은 루트(212)를 루트 데이터베이스(214)에 제정할 수 있다. 루트 데이터베이스(214)는 차량(202)(및 수많은 다른 차량들)의 GPS 트레일로부터 식별된 루트(212) 각각을 포함할 수 있다. 또한, 각 루트에 대해서, 데이터베이스(214)는 시간 정보(216) 및/또는 비용 정보(218)를 저장할 수 있다. 시간 정보(216)는 루트가 관측된 시간 및 해당 루트의 여행에 얼마나 소요되었는지를 나타낸다. 전술한 것처럼, 어떤 루트들은 하루의 특정 시간대에 사용 가능하지만 다른 시간대에는 사용 불가능할 수 있다(예를 들어, 러시 아워 동안 왼쪽 턴을 하는 것에 대해 제한이 있거나, 특정 차선은 러시 아워의 아침 및 저녁 시간 사이에 방향을 바꿀 수 있다). 따라서, 알려진 루트들로부터 이동 방향의 세트를 생성하는데 있어서, 루트들이 언제 관측되었는지에 대해 아는 것이 필요할 수 있다. 비용 정보(218)는 특정 루트를 여행하는데 있어서의 비용을 나타낸다. 비용은 시간에 기초할 수 있다(예를 들어, 여행하는데 긴 시간이 소요되는 루트들은 적은 시간이 소요되는 루트들에 비해 "고비용"으로 표시될 수 있다). 그러나, 비용은 거리, 속도 제한, 속도 측정기의 존재, 톨의 존재, 또는 다른 임의의 정보와 같은 다른 요소들에 기초할 수도 있다. 루트를 여행하는 비용은 위와 같은 요소들(또는 다른 요소들)을 고려하여 임의의 주어진 루트에 대한 비용 정보(218)를 판정할 수 있는 비용 분석기(220)에 의해 판정될 수 있다.

도 3은, 흐름도의 형태로서, GPS 트레일에 기초하여 루트들의 데이터베이스를 설계하는 예시적인 프로세스를 도시한다. 도 3에 대한 설명으로 들어가기 전에, 본 상세한 설명에 포함된 흐름도(도 3 및 도 5 포함)들은 예시로서 도 1, 도 2, 도 4에 도시된 컴포넌트들을 참조하여 설명되었지만, 이들 프로세스들은 임의의 시스템에서 수행될 수 있으며 도 1, 도 2 및 도 4에 도시된 시나리오에 한정되는 것이 아니다. 또한, 도 3 및 도 5의 흐름도 각각은 예시적으로 블록들을 연결하는 라인들에 의해 특정 순서에 따라 프로세스의 단계들이 수행되는 것으로 도시되었지만, 이들 흐름도에 도시된 다양한 단계들은 임의의 순서, 임의의 조합 또는 서브 조합으로 수행될 수 있다.

단계(302)에서, GPS 트레일이 수신될 수 있다. 단계(304)에서, GPS 트레일들은 GPS 트레일들에 의해 나타나는 루트들을 획득하기 위해 맵에 적용될 수 있다. 예를 들어, 좌표 및 이들 좌표들이 수신된 시간이 수신되어 이들 좌표들을 보고하는 GPS 장치에 의해 여행되는 도로(들)가 무엇이며 해당 도로들이 언제 어느 방향으로 여행되었는지 판정하기 위해 분석될 수 있다.

단계(306)에서, 루트가 하나보다 많은 레그를 가지는지 여부가 판정된다. 전술한 것처럼, 레그는 루트 중 턴이 불가능한 부분이다. 하나의 레그만을 가지는 루트는 다른 루트로 턴할 수 없기 때문에, 다른 루트들과 결합될 수 없는 루트이다. 따라서, 만약 루트가 하나보다 많은 레그를 가지지 않는다면, 루트는 저장되지 않는다(단계 308). 반면에, 만약 루트가 하나보다 많은 레그를 가진다면, 단계 310에서, 루트는 데이터베이스에 저장된다.

저장된 루트 각각에 대하여, 루트와 연관된 비용은 연산될 수 있다(단계 312). 비용은 다양한 요소들에 기초할 수 있다. 이러한 요소들(314)의 몇 예시들이 도 3에 도시된다.

하나의 예시적인 요소는 루트를 여행하기 위해 소요되는 시간이다(블록 316). 사람들이 한 장소에서 다른 장소로 가장 빠른 루트를 원하는 경향이 있다고 가정할 때, 보다 오랜 시간이 소요되는 루트는 보다 적은 시간이 소요되는 루트에 비해 고비용을 가지는 것으로 표시될 수 있다. 고려될 수 있는 다른 요소는 루터 내의 각 턴에 연관된 시간이다(블록 318). (교통 체증 없이) 직선 도로를 똑바로 여행하는 것이 상대적으로 신속할 수 있음에 비하여, 루트의 여행에서 턴을 하는데 많은 시간이 소요될 수 있다. 따라서, 턴에 얼마나 시간-비용이 드는지 아는 것이 필요하다. 또한, 루트들의 부분들이 이동 방향의 세트를 생성하기 위해 결합될 수 있는데, 두 개의 루트를 합치는데 있어서 비용이 타당한지 여부가 턴의 비용에 의해 판정될 수 있으므로, 루트를 여행하는데 전체 비용으로부터 별개로 분리하여 특정 턴을 하기 위해 어느 정도의 시간이 소요되는지 여부를 아는 것이 필요할 수 있다. 따라서, 루트 내에서 턴을 하기 위해 소요되는 시간은 전체 비용을 계산하는데 있어서 고려될 수 있으며, 전체 비용과 별도로 저장될 수도 있다.

고려될 또 다른 요소는 루트가 여행되는 하루 중의 시간대이다(블록 320). 예를 들어, 만약 루트가 오전 3시에 여행되었고 20분이 소요되었다면, 사람들은 오후 5시에 보다 많은 교통이 있다고 기대할 것이 때문에, 이러한 사실은 해당 루트가 오후 5시에 20분이 소요되어 여행되었다는 사실과는 비용 계산에 있어서 다르게 다뤄질 수 있다. 따라서, 루트가 실제 여행된 하루 중의 시간대는 루트의 전체 비용을 판정하는데 고려될 수 있다. 특정한 경우, 여행이 실행되는 하루 중의 시간대는 사람에게 추천할 루트를 결정하는데 매우 관련성이 높을 수 있으므로, 하루 중 상이한 시간대에 대해 상이한 비용이 계산될 수 있다.

고려될 또 다른 요소는 루트가 관측된 시간에 차량 내의 탑승자의 수이다(블록 322). (이 정보는 차량의 운전자에 의해 스스로 보고될 수 있다.) 탑승자의 수가 관련성이 있을 수 있는 이유는, 어떤 차선들은 탑승 인원 제한(occupancy restrictions)을 두며(예를 들어, 워싱턴의 SR-520은 적어도 세 명의 탑승자가 탑승한 차량만이 사용할 수 있는 HOV 차선을 가짐), 톨비를 부과하는 어떤 도로들은 차량의 탑승자 수에 기초하여 할인을 제공하기 때문이다(예를 들어, 적어도 세 명의 탑승자를 갖는 차량은 Lincoln Tunnel eastbound를 통과하는데 $2을 지불하는데, 정상 비용은 $8이다). 따라서, 비용은 차량 내의 탑승자 수에 기초할 수 있다. 루트를 여행하는데 있어서 러시 아워에 HOV 차선을 사용 가능한 것은 시간을 많이 감소시킬 수 있으며, 톨비를 줄이는 것은 여행의 비용을 다른 방법으로 감소시킨다. 따라서, 특정 예에서, 차량 내의 사람의 상이한 수에 대해 루트의 상이한 비용들이 계산될 수 있다.

앞서 설명한 것은 루트의 비용과 연관된 예시적인 요소들의 목록으로, 어떤 루트를 추천할 것인지 판정하는데 사용될 수 있다. 그러나, 특정 영역에 있어서 운전자가 거주자인지 또는 방문자인지(방문자들은 거주자들에 비해 단순한 루트를 선호함), 또는 차량의 유형(높은 차량들은 고가 도로 아래를 통과하기 어려울 수 있고, 긴 차량은 턴을 하는데 어려움을 가질 수 있으며, 상업용 트럭은 Weigh Station에 정지해야할 수 있음)과 같이 다른 요소들도 고려될 수 있다.

단계(324)에서, 계산된 비용이 저장될 수 있다. 비용은 숫자가 될 수 있지만, 특정 변수에 기초하여 숫자를 생성하는데 사용되는 함수일 수도 있다. 예를 들어, 만약 루트 여행 비용이 루트가 여행되는 하루 중의 시간대(t) 및/또는 차량 내의 사람의 수(n)에 기초한다면, "비용"은 실질적으로 루트 여행 비용의 판정에 있어서 시간 및 차량의 탑승 인원을 고려하는 C(t,n)과 같은 함수일 수 있다. 상황 및 맥락에 따라 다른 유형의 비용들도 계산될 수 있다. 예를 들어, 쇼핑 여행에 있어서, (비록 정거장들이 여행을 길게 만들지만) 많은 수의 정거장은 여행의 비용을 감소시키도록 해석된다. 왜냐하면, 사람들이 많은 가게들을 방문하는 쇼핑 여행이 사람들이 도로를 신속히 정거 없이 지나가는 쇼핑 여행에 비해 효율적으로 여겨질 수 있기 때문이다.

루트들의 데이터베이스가 생성되면, 이들 루트들은 루트에 대한 질의에 응답하기 위해 사용될 수 있다. (그러나, 전술한 것처럼, 본 명세서에서 설명된 기술은 실제적인 GPS 트레일들로부터 알려진 루트의 데이터베이스가 생성되었는지 여부에 무관하게 루트에 대한 질의에 응답하는데 사용될 수 있다.) 도 4는 루트에 대한 질의에 응답하기 위해 사용될 수 있는 예시적인 시스템을 도시한다.

질의 프로세서(402)는 루트 질의(404)를 수신한다. 예시적인 루트 질의는 "Berkeley, CA로부터 Princeton, NJ"이고, 이러한 질의는 맵 웹 사이트 내에 입력될 수 있는 형태이다. 그러나, 질의는 임의의 형태를 가질 수 있다. 예를 들어, 네비게이션 박스 내에 목적지를 입력하는 것으로서, 이에 따라 목적지가 어디든 간에 네비게이션 박스의 현재 위치로부터 이동 방향에 대한 질의를 효율적으로 구성할 수 있다 (이에 따라 현재 위치 및 지정된 목적지가 질의의 두 개의 엔드포인트들로서 다뤄짐).

알려진 루트들은 루트 데이터베이스(214)에 저장된다. 따라서, 질의 프로세서(402)는 루트 데이터베이스(214)를 참고하여 질의(404)에 응답하는데 사용될 알려진 루트가 무엇인지를 판정한다. 만약 루트 데이터베이스(214) 내에 질의에 의해 지정된 엔드포인트들 사이를 통과하는 루트가 있다면, 이 루트는 검색될 수 있고, 이동 방향(406)으로서 제공될 수 있다. (도 4에 도시된 것처럼, 예시적인 이동 방향(406)은 "Main에서 좌측 턴. I-80 고속도로 진입. 900마일 동쪽으로 이동.."이다.)

질의 프로세서(402)는 새로운 루트를 구성하기 위해 데이터베이스(214) 내의 루트들을 합치는 소프트웨어 및/또는 하드웨어를 포함하는 루트 구성기(route compositor)(408)를 포함할 수 있다. 만약 루트 데이터베이스(214) 내에 질의의 엔드포인트들 사이에 루트가 없다면, 루트 구성기(408)는 존재하는 알려진 루트들로부터 루트들 설계할 수 있으며, 이와 같이 설계된 루트는 이동 방향(406)을 제공할 수 있다. 루트 구성기(408)는 도 1과 관련하여 앞서 설명된 기술들 및 도 5에 관련하여 추가적으로 후술할 기술들을 사용하여 이러한 루트를 설계할 수 있다.

도 5는 존재하는 알려진 루트들을 검색하는 것에 의해 루트 질의에 응답하는 예시적인 프로세스를 도시한다. 단계(502)에서, 루트 질의(예를 들어, "Berkeley, CA로부터 Princeton, NJ")가 수신될 수 있다. 단계(504)에서, 프로세스는 루트 데이터베이스(214)에서 질의의 엔드포인트들에 접근하는 가장 긴 루트를 탐색할 수 있다. 몇몇 경우, 루트 데이터베이스(214)는 질의 내의 두 개의 엔드포인트들 사이의 루트를 실질적으로 포함할 수 있으며, 이 경우 프로세스는 이러한 루트를 이동 방향의 세트의 형태로 제공하는 것에 의해 단순히 응답할 수 있다. 그러나, 많은 경우에 있어서, 루트 데이터베이스(214)는 질의의 엔드포인트들에 정확히 일치하는 루트를 가지지 않을 것이다. 이러한 경우, 도 5의 프로세스는 다른 루트들로부터 위 엔드포인트들 사이의 루트를 설계하려고 시도한다.

이와 같은 루트를 설계하기 위해, 프로세스는 먼저, 질의 내의 시작점 근처의 위치로부터 질의 내의 종료 지점 근방의 위치로 가는 긴 루트를 탐색하는 것을 시도함으로써 이미 존재하는 루트의 길이를 고려할 수 있다. 예를 들어, Berkeley로부터 Princeton에 대한 질의를 참고하면, San Francisco는 Berkeley 근방이며, New York은 Princeton 근방이다. 만약 데이터베이스(214)가 San Francisco로부터 New York까지의 루트를 포함한다면, 이러한 루트가 Berkeley로부터 Princeton까지의 루트를 설계하는데 기초로서 사용될 수 있다. San Francisco로부터 New York까지의 루트가 시작점으로 선택될 수 있는데, 이 경우 San Francisco로부터 New York까지의 루트의 선택은 특히 질의 내에서 지정된 엔드포인트들과 이 루트의 시작점 및 종료점의 근접성 때문이다. 데이터베이스 내에 존재하는 긴 루트는 특히 신뢰성 있는 것으로 여겨지는데, 이는 하나의 포인트에서 다른 포인트로 가기 위한 사람의 실제 선택을 나타내기 때문이다. 따라서, 도 5의 프로세스는 긴 루트들을 탐색하는 것에 의해 시작할 수 있고, 빈 공간을 채우기 위해 짧은 루트들이 사용될 수 있다. 따라서, 데이터베이스로부터 검색된 하나 이상의 루트들은 루트 질의에서 명시된 하나의 엔드포인트로부터 다른 엔드포인트로의 단일 또는 조합된 루트들이다.

따라서, 긴 루트가 선택되면, 프로세스는 단계(506)에서 긴 루트에 엔드포인트들을 접합할 작은 루트들을 탐색한다. 예를 들어, 만약 San Francisco로부터 New York까지의 긴 루트가 Berkeley로부터 Princeton까지의 루트를 설계하기 위한 기초로서 선택되면, 프로세스는 Berkeley로부터 위 긴 루트의 교차점으로 가는 루트들을 탐색할 수 있고, 위 긴 루트의 교차점으로부터 Princeton으로 가는 다른 루트들을 탐색할 수 있다. 만약 Berkeley와 San Francisco로부터 New York까지의 루트의 교차점 사이에 루트가 존재하지 않는다면, 프로세스는 이러한 루트를 설계하기 위해 계속하여 보다 작은 루트들을 탐색할 수 있다. 전술한 것처럼, 루트들을 선택하는 프로세스를 관리하는 하나의 예시적인 규칙은, 루트들이 중첩된 정도가 특정 기준을 충족하는 경우(예를 들어, 만약 두 개의 루트가 몇 개의 레그를 공통으로 가지며 하나의 루트로부터 다른 루트로의 턴이 존재하는 경우)에만 두 개의 루트들을 결합하는 것이다.

공통적인 레그를 가지는 루트들이 식별되면, 이들 루트들은 공통 레그들에서 결합될 수 있다(단계 508). 루트들을 탐색하는 프로세스는 반복적으로 수행될 수 있으며 몇 개의 루트들이 생성될 수 있다. 단계(510)에서, 경쟁 관계의 루트들의 비용이 계산될 수 있다. 단계(512)에서는, 가장 낮은 비용의 루트에 기초하여 이동 방향을 제공하는 것에 의해 단계(502)에서 수신된 질의에 응답할 수 있다.

도 6은 본 발명에 따른 실시예들이 사용될 수 있는 예시적인 환경을 도시한다.

컴퓨터(600)는 하나 이상의 프로세서들(602) 및 하나 이상의 데이터 기억 컴포넌트(604)들을 포함한다. 프로세서(들)(602)는 일반적으로 개인용 데스크탑, 랩탑 컴퓨터, 서버, 휴대용 컴퓨터 또는 다른 유형의 컴퓨팅 장치에서 발견될 수 있는 마이크로프로세서이다. 데이터 기억 컴포넌트(들)(604)은 짧은 기간 또는 긴 기간 동안에 데이터를 저장 가능한 컴포넌트들이다. 데이터 기억 컴포넌트(들)(604)는 하드디스크, 제거가능한 디스크(광학 및 자기 디스크 포함), 휘발성 및 비휘발성 RAM, ROM, 플래쉬 메모리, 자기 테이프 등을 포함할 수 있다. 데이터 기억 컴포넌트(들)(604)는 컴퓨터 판독가능한 저장 매체의 예이다. 컴퓨터(600)는 디스플레이(612)를 포함하거나 연관될 수 있으며, 디스플레이(612)는 CRT 모니터, LCD 모니터, 또는 임의의 다른 유형의 모니터가 될 수 있다.

소프트웨어는 데이터 기억 컴포넌트(들)(604) 내에 저장될 수 있으며 하나 이상의 프로세서(들)(602) 상에서 실행될 수 있다. 이러한 소프트웨어의 예시는 루트 검색 및 설계 소프트웨어(606)로서, 도 1 내지 도 5와 관련하여 전술한 기능 중 일부 또는 전부를 구현할 수 있는데, 이를 위해 임의의 유형의 소프트웨어가 사용될 수 있다. 소프트웨어(606)는 예를 들어, 분산 시스템, 별개 파일들, 별개 함수들, 별개 객체들, 코드의 별개 라인 등 내의 하나 이상의 컴포넌트들을 통해 구현될 수 있다. 프로그램이 하드 디스크 상에 저장되어 RAM 상에 로딩되고 컴퓨터의 프로세서(들) 상에서 실행되는 컴퓨터(예를 들어, 개인용 컴퓨터, 서버 컴퓨터, 휴대용 컴퓨터 등)는 도 6에 도시된 전형적 시나리오이지만, 본 발명은 이러한 예에 한정되지는 않는다.

본 발명은 하나 이상의 데이터 기억 컴포넌트(들)(604) 내에 저장되고 하나 이상의 프로세서(들)(602) 상에서 실행되는 소프트웨어로서 구현 가능하다. 다른 예로서, 본 발명은 하나 이상의 컴퓨터 판독가능 저장 매체 또는 컴퓨터 판독가능 저장 메모리에 저장된 명령어로서 구현 가능하다. 광학 디스크 또는 자기 디스크와 같은 유형의 매체가 저장 매체의 예시이다. 명령어들은 비 일시적 매체 상에 존재할 수도 있다. 이러한 명령어들은, 컴퓨터 또는 다른 머신에 의해 실행되면, 컴퓨터 또는 다른 머신으로 하여금 방법의 하나 이상의 동작들을 수행하도록 한다. 이러한 동작들을 수행하기 위한 명령어는 하나의 매체 상에 저장되거나 복수의 매체에 걸쳐 저장될 수 있으며, 이에 따라 명령어는 동일한 매체에 모든 명령어들이 존재하는지 여부에 무관하게 집합적으로 하나 이상의 컴퓨터 판독 가능 저장 매체 상에서 나타날 수 있다. 신호들이 "저장"되는 매체("저장 매체"로 지칭됨)와, 이에 대조적으로 전파 신호를 전송하는 매체 사이에는 구분이 된다. DVD, 플래쉬 메모리, 자기 디스크 등은 저장 매체의 예이다. 이에 비하여, 신호들이 순간적으로 존재하는 와이어 또는 섬유는 일시적 신호 매체의 예이다.

또한, 본 명세서에서 설명된 임의의 동작(다이어그램 내에 도시되었든 도시되지 않았는지와 상관없음)은 프로세서(예를 들어, 하나 이상의 프로세서들(602))에 의해 방법의 일부로서 실행될 수 있다. 따라서, 만약 동작들 A, B 및 C가 설명되었다면, 방법은 동작들 A, B 및 C를 포함하여 수행될 수 있다. 또한, 동작들 A, B 및 C가 본 명세서에서 설명된 경우, 방법은 동작들 A, B 및 C를 수행하기 위해 프로세서를 사용하여 수행될 수 있다.

하나의 예시적인 환경에서, 컴퓨터(600)는 네트워크(608)를 통해 하나 이상의 다른 장치에 통신 가능하게 연결될 수 있다. 컴퓨터(610)는 컴퓨터(600)에 구조 면에서 유사할 수 있으며, 컴퓨터(600)에 연결 가능한 예시적인 장치이지만, 다른 유형의 장치들도 또한 연결될 수 있다.

비록 본 명세서의 설명들이 구조적 특징들 및/또는 방법적 동작들에 언어 지정적으로 설명되었지만, 첨부된 청구항들에 정의된 본 발명이 전술한 특정적 특징 또는 동작들에 한정되지 않는다는 것이 이해되어야 할 것이다. 오히려, 전술한 특정직 특징들 및 동작들은 청구항을 구현하는 예시적인 형태로서 개시된 것이다.

Claims

이동 방향(directions)을 제공하는 방법으로서,
GPS(Global Positioning System) 데이터를 수집하고 상기 GPS 데이터를 맵에 적용하는 것에 의해 사람들이 여행한 복수의 루트를 획득하는 단계와,
상기 복수의 루트를 데이터베이스에 저장하는 단계와,
제1 엔드포인트(endpoint) 및 제2 엔드포인트를 나타내는 질의를 수신하는 단계와,
상기 제1 엔드포인트로부터 상기 제2 엔드포인트로 가는 하나 이상의 단일 또는 조합된 루트를 상기 데이터베이스 내에서 검색(search)하는 단계와,
상기 데이터베이스로부터 상기 하나 이상의 루트를 발견(retrieve)하는 단계와,
상기 하나 이상의 루트에 기초하여 이동 방향의 세트를 생성하는 단계와,
상기 이동 방향의 세트를 개인에게 제공하는 단계
를 포함하는 이동 방향 제공 방법.
제1항에 있어서,
상기 방법은,
상기 제1 엔드포인트로부터 상기 제2 엔드포인트로의 완성된 루트를 생성하기 위해 상기 하나 이상의 루트들을 결합하는 단계를 더 포함하고, 상기 결합하는 단계는 루트들이 결합되기 위해 결합될 루트들이 가져야 할 중첩의 양을 지정하는 규칙에 의해 관리되고, 상기 규칙은 루트들이 결합되기 위해 공통으로 가져야할 레그(leg)들의 수를 지정하며, 상기 레그 각각은 루트의 부분 중 턴(turn)이 없는 부분인
이동 방향 제공 방법.
제1항에 있어서,
상기 데이터베이스 내의 루트 각각은 상기 루트가 여행된 하루 중의 시간대 또는 상기 루트를 여행한 차량 내의 사람의 수를 고려하는 비용과 연관되며,
상기 방법은, 상기 질의가 수신된 하루 중의 시간 또는 상기 이동 방향이 사용될 차량 내의 사람의 수 중 하나와 상기 비용에 기초하여 상기 하나 이상의 루트들 중 상기 이동 방향에 사용될 루트들을 선택하는
이동 방향 제공 방법.
제1항에 있어서,
상기 검색하는 단계는, 먼저 긴 루트들을 탐색한 다음 보다 짧은 루트들을 탐색하여, 상기 루트들의 길이에 기초하여 루트들을 검색하는 단계를 더 포함하는
이동 방향 제공 방법.
제1항에 있어서,
상기 검색하는 단계는,
상기 데이터베이스 내에서 제1 루트를 찾는 단계를 더 포함하되, 상기 제1 루트의 시작 포인트와 상기 제1 엔드포인트의 근접성 및 상기 제1 루트의 종료 포인트와 상기 제2 엔드포인트의 근접성에 기초하여 상기 제1 루트를 찾는
이동 방향 제공 방법.
제1항 내지 제5항 중 어느 하나에 따른 방법을 실행하는 컴퓨터 실행가능한 명령어들을 갖는 컴퓨터 판독가능 매체.
이동 방향(directions)을 제공하는 시스템으로서,
장치들로부터 GPS 트레일(GPS trail)들을 수신하는 GPS 트레일 수신기와,
루트 데이터베이스와,
상기 GPS 트레일들에 기초하여, 여행된 루트들을 식별하고 상기 루트들을 상기 루트 데이터베이스에 저장하는 루트 생성기와,
메모리와,
상기 메모리에 저장된 질의 프로세싱 컴포넌트 - 상기 질의 프로세싱 컴포넌트는 제1 엔드포인트 및 제2 엔드포인트를 포함하는 루트 질의를 수신하며, 상기 질의 프로세싱 컴포넌트는 상기 데이터베이스로부터 상기 제1 엔드포인트로부터 상기 제2 엔드포인트로 집합하여 진행하는 복수의 중첩되는 루트들을 검색함 - 와,
상기 제1 엔드포인트로부터 상기 제2 엔드포인트로의 완성된 루트를 생성하기 위한 루트들의 중첩의 정도를 관리하는 규칙을 충족하는 상기 중첩된 루트들 중의 루트들에 기초하여, 상기 중첩되는 루트들을 결합하는 루트 구성기(route compositor) - 상기 질의 프로세싱 컴포넌트는 상기 완성된 루트에 기초하여 개인에게 이동 방향의 세트를 제공함 -
를 포함하는 이동 방향 제공 시스템.
제7항에 있어서,
상기 루트 구성기는 상기 완성된 루트 내에 상기 GPS 트레일들로부터 생성된 루트들에서 행해진 턴(turn)들만을 포함시키는
이동 방향 제공 시스템.
제7항에 있어서,
상기 루트 구성기는, 상기 완성된 루트에 사용될 루트들을 판정할 때, 상기 루트들 각각의 비용을 고려하며, 상기 비용은 상기 루트가 여행된 하루 중의 시간대 또는 상기 루트를 여행한 차량 내의 사람의 수에 기초하는
이동 방향 제공 시스템.
제7항에 있어서,
상기 질의 프로세싱 컴포넌트는, 상기 데이터베이스 내에서, 제1 루트의 시작 포인트와 상기 제1 엔드포인트의 근접성 및 상기 제1 루트의 종료 포인트와 상기 제2 엔드포인트의 근접성에 기초하여 상기 제1 루트를 찾고,
상기 질의 프로세싱 컴포넌트는, 상기 데이터베이스 내에서, 상기 제1 엔드포인트로부터 상기 제1 루트를 따르는 교차점까지의 제2 루트를 찾으며, 상기 질의 프로세서 컴포넌트는, 상기 데이터베이스 내에서, 상기 제1 루트를 따르는 교차점으로부터 상기 제2 엔드포인트까지의 제3 루트를 찾는
이동 방향 제공 시스템.