KR102319535B1 - 대안 경로를 생성하기 위한 방법 및 시스템 - Google Patents

Abstract

전자 지도에 의해 커버되는 영역 내의 경로들을 생성하는 방법이 개시된다. 상기 지도는 상기 전자 지도에 의해 커버되는 영역 내에 있는 가항 네트워크(navigable network)의 가항 구간들을 나타내는 다수의 구간들을 포함한다. 제1 경로는 상기 영역 내에서 제1 위치 및 제2 위치 사이에 생성된다. 상기 제1 경로의 중앙 부분이 한정되며, 이 때, 상기 중앙 부분은 상기 제1 위치 및 상기 제2 위치 사이의 거리에 기초하여 결정되는, 상기 제1 경로를 따르는 범위(extent)를 갖는다. 상기 제1 경로를 따르는 상기 중앙 부분의 상대적 범위는 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있다. 상기 제1 경로를 따르는 상기 한정된 중앙 부분을 형성하는 하나 이상의 가항 구간들이 식별되며, 상기 식별된 가항 구간(들)에 비용 불이익이 적용되어, 상기 가항 네트워크를 통해 경로가 생성될 때 상기 가항 구간(들)이 덜 선호되도록 만든다. 그 다음, 상기 제1 위치 및 상기 제2 위치 사이에서 대안 경로가 생성된다.

Description

대안 경로를 생성하기 위한 방법 및 시스템{Methods and systems for generating alternative routes}

본 발명은 대안 경로들을 생성하기 위한 방법들 및 시스템들에 관한 것이다. 또한, 본 발명은 대안 경로를 생성하도록 조정된 내비게이션 기기들 및 서버들까지 연장된다. 본 발명의 예시적 실시예들은 (소위 PND들이라 불리는) 휴대용 내비게이션 기기들에 관한 것이며, 특히, 위성 위치 확인 시스템(Global positioning system; GPS) 신호 수신 및 처리 기능을 포함하는 PND들에 관한 것이다. 더 일반적으로, 다른 실시예들은 경로 계획(route planning) 기능을 제공하기 위해, 바람직하게는 내비게이션 기능 또한 제공하기 위해, 내비게이션 소프트웨어를 실행하도록 구성된 임의의 유형의 처리 기기에 관한 것이다. 일반적으로, 본 발명의 추가 양상들은 경로 생성에 관한 것이다.

GPS(위성 항법 시스템) 신호 수신 및 처리 기능을 포함하는 휴대용 내비게이션 기기(PND)들은 잘 알려져 있으며, 자동차 내(in-car) 또는 다른 차량 내비게이션 시스템들로 널리 사용된다.

보편적으로, 최신 PND는 프로세서, 메모리(휘발성 및 비-휘발성 중 적어도 하나, 그리고 일반적으로는 둘 다), 그리고 상기 메모리 내에 저장된 지도 데이터를 포함한다. 상기 프로세서 및 메모리는 소프트웨어 운영 시스템이 구축될 수 있는 실행 환경을 제공하기 위해 협력하며, 부가적으로, 상기 PND의 기능이 제어될 수 있게 하기 위해, 그리고 다른 다양한 기능들을 제공하기 위해, 하나 이상의 부가적인 소프트웨어 프로그램들이 제공되는 것은 흔한 일이다.

일반적으로 이러한 기기들은 사용자가 상기 기기와 상호작용하고 상기 장치를 제어할 수 있도록 하는 하나 이상의 입력 인터페이스들, 그리고 정보가 사용자에게 전달될 수 있도록 하는 하나 이상의 출력 인터페이스들을 더 포함한다. 출력 인터페이스들의 예시적 예들은 영상 디스플레이 및 음성 출력을 위한 스피커를 포함한다. 입력 인터페이스들의 예시적 예들은 상기 기기의 온/오프 작동이나 또는 다른 기능들을 제어하기 위한 하나 이상의 물리적 버튼들(상기 버튼들이 반드시 상기 기기 자체에 있을 필요는 없지만, 상기 기기가 차량에 내장되어 있다면 핸들 상에 있을 수 있다), 그리고 사용자의 음성을 검출하기 위한 마이크로폰을 포함한다. 특히 바람직한 구성에서, 상기 출력 인터페이스 디스플레이는 사용자가 터치함으로써 기기를 작동시킬 수 있게 하는 입력 인터페이스를 추가로 제공하기 위해 (터치 감지 오버레이 또는 다른 것들의 수단으로) 터치 감지 디스플레이로서 구성될 수 있다.

또한 이러한 유형의 기기들은, 전력이, 그리고 선택적으로 데이터 신호들이, 상기 기기들에게 송신될 수 있게하고 상기 기기들로부터 수신될 수 있게 하는 하나 이상의 물리적 커넥터 인터페이스들을 종종 포함할 것이며, 셀룰러 통신, 그리고 다른 신호 및 데이터 네트워크들(예를 들어, Wi-Fi, Wi-Max GSM 등)을 통한 통신을 허용하는 하나 이상의 무선 송신기들/수신기들을 옵션으로 포함할 것이다.

또한 이러한 유형의 PND 기기들은 GPS 안테나도 포함하며, 이러한 GPS 안테나를 이용하여, 위치 데이터를 포함하는 위성-방송 신호들이 수신될 수 있고 이어서 상기 위성-방송 신호들은 상기 기기의 현재 위치를 판단하기 위해 처리될 수 있다.

또한 상기 PND 기기는, GPS 신호, 상기 기기의 속도 및 상대적 변위, 그리고 이로써 상기 기기가 장착된 차량의 속도 및 상대적 변위로부터 얻어진 위치 정보와 함께, 현재 각도 및 선형 가속도를 판단하기 위해 처리될 수 있는 신호들을 생성하는 전자 자이로스코프들 및 가속계들을 포함할 수 있다. 일반적으로 이러한 기능들은 가장 일반적으로 차량-내 내비게이션 시스템들 내에서 제공되지만, PND 기기들 내에 제공되는 것이 편리하다면 PND 장치들 내에서 제공될 수도 있다.

이러한 PND들의 활용은 제1 위치(일반적으로 시작 위치 또는 현재 위치)와 제2 위치(일반적으로 목적지) 사이의 경로(route)를 판단하는 능력에서 주로 드러난다. 이러한 위치들은 서로 다른 다양한 방법들 중 임의의 방법에 의한, 상기 기기의 사용자에 의한 입력일 수 있으며, 이러한 다양한 방법들의 예로는, 우편번호, 거리 이름 및 집 번호, (유명한 장소들, (운동장들 또는 수영장들 같은) 지방 자치제 장소들 또는 다른 관심 포인트들 같은) 이전에 저장된 "잘 알려진" 목적지들, 그리고 좋아하거나 최근에 방문한 목적지들이 있다.

일반적으로, 상기 PND는 상기 지도 데이터에서의 시작 주소 위치 및 목적지 주소 위치 간의 "최고의" 또는 "최적의" 경로를 계산하기 위해 소프트웨어에 의해 활성화된다. "최고의" 또는 "최적의" 경로는 미리 정해놓은 기준에 기초하여 결정되며, 반드시 가장 빠른 경로 또는 가장 짧은 경로일 필요는 없다. 운전자를 안내하는 경로의 선택은 매우 복잡하며, 선택된 경로는 이력의(historical), 기존의(existing), 그리고/또는 예측된 교통 및 도로 정보를 고려할 수 있다.

또한, 상기 기기는 지속적으로 도로 및 교통 상황들을 모니터링 할 수 있으며, 변경된 조건들로 인해 남은 여정이 수행되는 경로를 변경하는 것을 제공하거나 선택할 수 있다. 다양한 기술들(예를 들어, 모바일 전화 데이터 교환, 고정 카메라들, GPS의 신속한 트래킹)에 기초한 실시간 교통 모니터링 시스템들은, 교통 지체를 식별하고 알림 시스템들에 상기 정보를 공급하기 위해 사용되고 있다.

이러한 유형의 PND들은 일반적으로 차량의 계기판 또는 앞유리에 장착될 수 있지만, 또한 차량의 라디오의 온-보드 컴퓨터의 일부로서 또는 실제로 차량 자체의 제어 시스템의 일부로서 형성될 수도 있다. 또한 상기 내비게이션 기기는 휴대용 정보 단말기(Portable Digital Assistant; PDA), 미디어 플레이어, 모바일 폰 등과 같은 휴대용 시스템의 일부일 수도 있으며, 이러한 경우, 상기 휴대용 시스템의 일반적인 기능은 상기 기기 상의 소프트웨어 설치에 의해 확장되어, 경로 계산 및 계산된 경로에 따른 경로 안내 모두를 수행한다.

또한 경로 계획 및 내비게이션 기능은 적절한 소프트웨어를 실행하는 데스크탑 또는 모바일 컴퓨팅 자원에 의해 제공될 수 있다. 예를 들어, 온라인 경로 계획 및 내비게이션 기능은 routes.tomtom.com에서 제공되며, 상기 기능은 사용자가 시작점 및 목적지를 입력할 수 있게 해서, 상기 사용자의 PC에 연결된 서버는 경로(사용자가 지정한 것일 수도 있다)를 계산하며, 그리고 상기 선택된 시작점으로부터 상기 선택된 목적지까지 사용자를 안내하기 위해 포괄 내비게이션 지침들의 집합을 생성한다. 또한 이러한 기능은 계산된 경로의 의사(pseudo) 3차원 렌더링을 가능하게 하며, 그리고 상기 경로를 따라 이동하는 사용자를 시뮬레이션하는 경로 미리보기 기능을 가능하게 하여, 사용자에게 산출된 경로의 미리보기를 제공한다.

PND의 관점에서, 일단 경로가 계산되면, 상기 사용자는, 옵션으로 제안된 경로들의 리스트로부터, 원하는 계산된 경로를 선택하기 위해 상기 내비게이션 기기와 상호작용한다. 옵션으로, 상기 사용자는, 예를 들어 특정 경로들, 도로들, 위치들 또는 기준들이 피해져야 한다거나 또는 특정 여정에 필수적임을 명시함으로써, 상기 경로 선택 프로세스에 개입하거나 또는 이를 지도할 수 있다. 상기 PND의 경로 계산 양상은 하나의 주요 기능을 형성하며, 그리고 이러한 경로를 따른 경로 안내는 또 다른 주요 기능이다.

계산된 경로를 따라 길 안내를 하는 동안, 이러한 PND들이 상기 경로의 종점까지, 즉 원하는 목적지까지, 선택된 경로를 따라 사용자를 안내하기 위해 시각적 및/또는 청각적 안내들을 제공하는 것이 일반적이다. 또한, PND들은 길 안내를 하는 동안 스크린에 지도 정보를 디스플레이하는 것이 일반적이며, 이러한 정보는 스크린 상에서 주기적으로 갱신되어, 상기 디스플레이된 지도 정보가 상기 기기의 현재 위치를 나타내도록 하며, 따라서, 상기 기기가 차량 내부에서 내비게이션을 위해서 사용되고 있다면 상기 사용자의 위치 또는 상기 사용자 차량의 위치를 나타내도록 한다.

스크린 상에 디스플레이된 아이콘은 보통은 현재 기기 위치를 나타내며, 그리고 현재 기기 위치의 인근에 있는 현재 도로 및 주변 도로들에 대한 지도 정보에 대해서는 중심에 위치하며, 다른 지도 특징들 역시 디스플레이된다. 추가로, 내비게이션 정보가 디스플레이될 수 있으며, 옵션으로는, 상기 내비게이션 정보는 상기 디스플레이된 지도 정보의 위에, 아래에, 또는 상기 지도 정보의 한 쪽에서 상태 바에 디스플레이될 수 있으며, 내비게이션 정보의 예들은 사용자가 필요하다고 채택한 현재 도로로부터 다음 갈래길까지의 거리를 포함하며, 그 갈래길의 속성은 아마도 특정 유형의 갈래길(예를 들면 좌회전 또는 우회전)을 제시하는 추가 아이콘에 의해서 표시된다. 또한 상기 내비게이션 기능은 사용자가 상기 경로를 따라서 안내받을 수 있게 하는 청각적인 명령어들의 내용, 지속 시간 및 타이밍을 결정한다. 이해될 수 있는 것처럼, "100 m에서 좌회전"과 같은 단순한 명령은 상당한 프로세싱과 분석을 필요로 한다. 이전에 언급된 바와 같이, 상기 기기와의 사용자 상호작용은 터치 스크린에 의해서, 또는 추가적으로 또는 대안적으로는 운전대 기둥(steering column)에 설치된 원격 제어에 의해서, 음성 구동(voice activation)에 의해서, 또는 임의의 다른 적절한 방법에 의한 것일 수 있다.

상기 기기에 의해 제공되는 추가의 중요한 기능은 자동적인 경로 재-계산이며, 다음과 같은 경우에 이루어진다 : 길 안내를 하는 동안, 사용자가(우연히 또는 의도적으로 중 어느 하나로 인해서) 이전에 계산된 경로를 이탈한 경우; 실-시간 교통 상황이, 대안 경로가 더욱 유리할 것이라는 것을 지시하고, 그리고 상기 기기가 그러한 상황들을 자동적으로 적절하게 인식할 수 있거나, 또는 어떤 이유에선가 사용자가 상기 기기로 하여금 경로 재-계산을 수행하도록 하는 경우.

비록 경로 계산 및 내비게이션 기능들이 PND들의 전반적인 활용에 기초가 되는 것이지만, 상기 장치를 정보 표시 용도만으로, 또는 "프리-드라이빙" 용도만으로 사용하는 것도 가능하며, 이 경우 현재 기기 위치와 관련된 지도 정보만이 디스플레이되며, 상기 기기에 의해 어떠한 경로도 계산되지 않고 어떠한 내비게이션도 현재 수행되지 않는다. 그러한 동작 모드는 사용자가 주행하고자 하는 경로를 이미 알고 있고 내비게이션 지원을 필요로 하지 않을 때에 종종 적용될 수 있다.

전술한 유형의 기기들은 사용자들이 일 위치에서 다른 위치로 찾아가는 것을 가능하게 하는 신뢰할만한 수단을 제공한다.

경로를 따라 길 안내를 할 때, 또는 경로를 계획할 때, 사용자들은 내비게이션 기기에 의해, 또는 경로 생성 기능을 갖는 다른 시스템에 의해, 기점 및 목적지 사이의 대안 경로들을 제공 받을 수 있다. 이는 시간, 거리 또는 연비와 같은 다른 기준에 대해 최적화된 단일 경로를 사용자에게 단순히 제공하는 대신, 사용자에게, 어떤 이유에선가 그들이 선호하는 많은 가능한 경로들 중 어느 하나를 결정할 기회를 제공한다. 이러한 경로들은 통상적으로 주어진 기준에 대해, 즉 시간에 대해, 최적화되지 않을 것이며, 그러나 다른 이유로 사용자에게 바람직할 수 있다. 예를 들어, 상기 경로들이, 사용자들이 싫어하는 도로의 특정 교차점 또는 길게 뻗어있는 특정 도로 구간을 피한다는 점에서, 또는 상기 경로들이 더 경치가 좋다는 점에서 사용자에게 바람직할 수 있다. 사용자에게 대안 경로 옵션들을 제공하기 위한 시스템은 본 출원인의 동시-계류중인 출원, 특허 공보 WO 2012/034581 A1의 "Navigation Device with Alternative Navigation Instructions"에 기술되어 있으며, 상기 공보의 전체 내용은 본원에 참조로 인용된다.

사용자가 사용하고자 할 수 있는 합리적인 경로들을 생성하고 선택하는 것은 몇 가지 과제들을 제시한다. 어떤 점에서 제1 경로(예를 들어, 가장 빠른 경로)와 상이한 다양한 경로들이 이론적으로 제공될 수 있음이 이해될 것이다. 특히, 사용자에게 더 도움이 될 것 같은 더 유용한 대안 경로들을 제공하기 위해, 상기 대안 경로들이 상기 제1 경로(예를 들어, 가장 빠른 경로)와 적절한 정도로 상이한 것이 바람직하다. 본 발명은 제1 경로와 적당히 상이한 대안 경로들을 생성하기 위한 방법들 및 시스템들에 관한 것이다.

본 발명의 제1 양상에 따르면, 전자 지도에 의해 커버되는 영역 내에 있는 경로들을 생성하는 방법으로서, 상기 지도는 상기 전자 지도에 의해 커버되는 영역 내에 있는 가항 네트워크(navigable network)의 가항 구간들(navigable segments)을 나타내는 다수의 구간들을 포함하며, 상기 방법은 :

상기 영역 내에서, 제1 위치 및 제2 위치 사이의 제1 경로를 획득하는 단계;

상기 제1 경로의 중앙 부분을 한정하는 단계로서, 상기 중앙 부분은 상기 제1 위치 및 상기 제2 위치 사이의 거리에 기초하여 결정되는, 상기 제1 경로를 따르는 범위(extent)를 가지며, 상기 제1 경로를 따르는 상기 중앙 부분의 상대적 범위는 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있는, 단계;

상기 제1 경로를 따르는 상기 한정된 중앙 부분을 형성하는 하나 이상의 가항 구간들을 식별하는 단계;

상기 가항 네트워크를 통한 경로 생성을 위해, 상기 가항 구간 또는 각각의 가항 구간이 상기 가항 네트워크를 통해 생성된 경로에 포함되는 것에 대해 덜 유리하도록 만듦으로써, 상기 중앙 부분의 상기 식별된 가항 구간 또는 식별된 각각의 가항 구간에 불이익(penalty)을 가하는 단계; 및

상기 제1 위치 및 상기 제2 위치 사이에 있는, 상기 가항 네트워크를 통한 대안 경로를 생성하는 단계를 포함하는, 대안 경로 생성 방법이 제공된다.

본 발명에 따르면, 이에 따라, 제1 경로는 제1 위치 및 제2 위치 사이에서 획득된다. 그 다음, 상기 제1 경로를 따라 중앙 부분이 한정된다. 상기 중앙 부분은 상기 제1 위치 및 상기 제2 위치 사이의 거리를 참고하여 결정되는 상기 제1 경로를 따르는 범위(extent)를 가지며, 상기 제1 경로를 따르는 상기 중앙 부분의 상대적 범위는 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있다. 상기 중앙 부분의 일부를 형성하는 것으로 식별된 하나 이상의 가항 구간들에 불이익이 가해지며, 이로써, 상기 구간들은 상기 가항 네트워크를 통해 경로가 생성될 때 불리하게 취급될 것이다. 그 다음 대안 경로가 생성된다. 상기 대안 경로의 생성은 상기 중앙 부분의 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 적용된 불이익(penalty)을 고려할 것이다.

상기 대안 경로를 생성하기 위해 상기 제1 경로의 중앙 부분을 한정하는 그러한 구간들에 불이익이 가해짐에 따라, 상기 대안 경로는 상기 제1 경로의 상기 중앙 부분으로부터 "멀어질(pushed away from)" 것이다. 상기 제1 위치 및 상기 제2 위치 사이의 거리가 증가함에 따라, 상기 제1 경로를 따르는 상기 중앙 부분의 상대적 범위는 감소한다. 따라서 대안 경로 생성에 있어서 가항 구간들을 덜 유리하게 만들기 위해 상기 가항 구간들에게 불이익이 가해지는 상기 제1 경로의 비율은 상기 제1 위치 및 상기 제2 위치 사이의 거리에 따라 달라지며, 이로써, 상기 제1 위치 및 상기 제2 위치 사이의 더 긴 거리들에 대해서보다, 더 짧은 거리들에 대해서, 상기 제1 경로의 더욱 많은 비율에게 불이익이 가해질 것이다. 상기 제1 위치 및 상기 제2 위치 사이의 거리는 상기 제1 경로의 길이의 측정이다. 따라서 더 긴 제1 경로들에 대해 생성된 대안 경로들은, 더 짧은 제1 경로들에 대한 경우보다, 상기 제1 경로와 더욱 유사할 수 있다.

본 발명은, 운전자들은 더 짧은 제1 경로들에 대해, 제1 경로와 상당히 상이한 대안 경로들을 원하는 반면, 더 긴 제1 경로들에 대해서는, 동일한 정도로 유용한 대안 경로가 상기 제1 경로와 상이할 필요는 없다는 것을 인식한다. 예를 들어, 더 긴 거리를 주행할 때, 상기 제1 경로가 고속도로의 사용을 포함한 경우, 운전자는 고속도로를 회피하는 대안 경로에 관심이 없을 수 있다. 그러나 그 대신, 상기 고속도로의 특정 부분 이후에 상기 제1 경로와 갈라지는 경로에는 관심이 있을 수 있다. 본 발명에 따르면, 상기 제1 경로의 중앙 부분의 구간들을 차단하여 그 구간들이 대안 경로의 일부를 형성할 수 없게 하지 않고, 상기 구간들은 단지, 상기 구간들이 경로 결정에 있어서 덜 유리하도록 만듦으로써, 차후 대안 경로 생성에서 불이익을 받는 것뿐이다. 이는 사용시 더 안정적인 대안 경로 알고리즘을 야기할 수 있다.

상기 제1 경로는 "메인" 경로로서, 즉 초기 경로로서, 간주될 수 있으며, 상기 대안 경로 또는 대안 경로들은 이러한 제1 경로 또는 "메인" 경로에 대한 대안이라는 것이 이해될 것이다. 따라서 상기 "제1" 경로는 "메인 경로"로 지칭될 수 있다.

본 발명은 본원에 설명된 본 발명의 양상들 또는 실시예들 중 임의의 것에 따른 방법을 수행하는 시스템으로 확장한다.

본 발명의 제2 양상에 따르면, 전자 지도에 의해 커버되는 영역 내에 있는 경로들을 생성하는 시스템으로서, 상기 지도는 상기 전자 지도에 의해 커버되는 영역 내에 있는 가항 네트워크(navigable network)의 가항 구간들을 나타내는 다수의 구간들을 포함하며, 상기 시스템은 :

상기 영역 내에서, 제1 위치 및 제2 위치 사이의 제1 경로를 획득하는 수단;

상기 제1 경로의 중앙 부분을 한정하는 수단으로서, 상기 중앙 부분은 상기 제1 위치 및 상기 제2 위치 사이의 거리에 기초하여 결정되는, 상기 제1 경로를 따르는 범위를 가지며, 상기 제1 경로를 따르는 상기 중앙 부분의 상대적 범위는 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있는, 한정 수단;

상기 제1 경로를 따르는 상기 한정된 중앙 부분을 형성하는 하나 이상의 가항 구간들을 식별하는 수단;

상기 가항 네트워크를 통한 경로 생성을 위해, 상기 가항 구간 또는 각각의 가항 구간이 상기 가항 네트워크를 통해 생성된 경로에 포함되는 것에 대해 덜 유리하도록 만듦으로써, 상기 중앙 부분의 상기 식별된 가항 구간 또는 식별된 각각의 가항 구간에 불이익(penalty)을 가하는 수단; 및

상기 제1 위치 및 상기 제2 위치 사이에 있는, 상기 가항 네트워크를 통한 대안 경로를 생성하는 수단을 포함하는, 대안 경로 생성 시스템이 제공된다.

당업자에 의해 이해될 수 있는 바와 같이, 본 발명의 이러한 추가 양상은, 적절하다면 본 발명의 다른 양상들 중 임의의 양상에 관하여, 본원에 설명된 본 발명의 바람직한 그리고 옵션의 특징들 중 임의의 것 또는 임의의 것들 또는 모두를 포함할 수 있으며, 바람직하게는 포함한다. 달리 명시되지 않았다면, 본원에서 본 발명의 시스템은 본 발명의 양상들 또는 실시예들의 임의의 것에서, 본 발명의 방법과 관련하여 설명된 임의의 단계를 수행하는 수단을 포함할 수 있으며, 그 역 또한 같다.

본 발명은 컴퓨터 구현 발명이며, 본 발명의 양상들 또는 실시예들 중 임의의 것과 관련하여 설명된 단계들 중 임의의 단계는 하나 이상의 프로세서들의 세트의 제어 하에 수행될 수 있다. 상기 시스템과 관련하여 설명된 단계들 중 임의의 단계를 수행하는 수단은 하나 이상의 프로세서들의 세트일 수 있다.

일반적으로, 본 발명의 실시예들 중 임의의 실시예에서 본 발명의 시스템은 적어도 하나의 처리 장치일 수 있다. 처리 장치 또는 상기 처리 장치는, PND 이든 통합 장치이든 관계 없이, 내비게이션 기기 같은, 모바일 장치의 장치일 수 있으며, 또는 서버의 장치일 수 있다.

바람직하게는, 본 발명의 방법은 내비게이션 동작의 맥락으로 구현된다. 따라서 바람직하게는, 본 발명은 내비게이션 기능을 갖는 장치 또는 시스템의 하나 이상의 프로세서들의 세트에 의해 수행된다. 그러나 본 발명들은 또한, 경로 생성 기능을 갖지만 내비게이션 기능을 가질 필요는 없는 임의의 적절한 시스템에 의해 수행될 수도 있다는 것이 이해될 것이다. 예를 들어, 본 발명들은 내비게이션 기능을 가지고 있지 않은 컴퓨터 시스템(예를 들어, 데스크톱 또는 휴대용 노트북 시스템)에 의해 구현될 수 있다. 사용자는, 그 후 프린트되거나 그렇지 않으면 차후에 경로 선택을 돕기 위해 사용될 수 있는, 생성된 대안 경로를 제공받을 수 있으며, 또는 예를 들어, 상기 경로들은 나중에 사용하기 위해, 예를 들어 내비게이션 기기에 다운로드하기위해, 저장될 수 있다.

바람직한 실시예들에서, 본 발명의 양상들 또는 실시예들 중 임의의 것에서 본 발명의 방법은 내비게이션 기기를 사용하여 수행되며, 본 발명은 본 발명의 양상들 또는 실시예들 중 임의의 것의 방법의 단계들을 수행하도록 조정된 내비게이션 기기로 확장한다. 상기 내비게이션 기기는 PND(Portable Navigation Device) 또는 통합 장치(예를 들어, 차량 내 장치)일 수 있다.

본 발명의 양상들 또는 실시예들 중 임의의 것에 따르면, 상기 내비게이션 기기는 : 사용자에게 전자 지도를 디스플레이하기 위한 디스플레이; 디지털 지도 데이터에 액세스하도록 구성된, 그리고 전자 지도가 디스플레이를 통해 사용자에게 디스플레이되는 것을 유발하도록 구성된 하나 이상의 프로세서들의 세트; 및 사용자가 상기 장치와 상호작용할 수 있게 하는, 사용자에 의해 작동 가능한 사용자 인터페이스를 포함할 수 있다. 이에 따라, 본 발명의 시스템은 예를 들어 내비게이션 기기의 처리 장치인, 시스템일 수 있다.

다른 실시예들에서, 본 발명의 양상들 또는 실시예들 중 임의의 것에서 본 발명의 방법은 서버에 의해 수행될 수 있으며, 본 발명은 본 발명의 양상들 또는 실시예들 중 임의의 것의 방법의 단계들을 수행하도록 조정된 서버로 확장한다. 본 발명의 양상들 또는 실시예들 중 임의의 것에서 본 발명의 시스템은, 예를 들어 서버의 처리 장치인, 시스템일 수 있다.

당업자에 의해 이해될 수 있는 바와 같이, 본 발명의 이러한 추가 양상들은, 적절하다면 본 발명의 다른 양상들 중 임의의 양상에 관하여, 본원에 설명된 본 발명의 바람직한 그리고 옵션의 특징들 중 임의의 것 또는 임의의 것들 또는 모두를 포함할 수 있으며, 바람직하게는 포함한다.

물론, 본 발명의 양상들 또는 실시예들 중 임의의 것에서 본 발명의 방법의 단계들은 서버에 의해 부분적으로 수행되고 내비게이션 기기에 의해 부분적으로 수행될 수 잇다. 예를 들어, 경로 생성은, 예를 들어 내비게이션 기기의 요청시, 서버에 의해 수행될 수 있으며, 그리고 사용자에게 출력하기 위해 상기 장치에게 제공될 수 있다. 상기 방법의 단계들은 서버에서 전적으로 수행될 수 있으며, 또는 임의의 조합으로 일부는 서버에서 수행되고 나머지는 내비게이션 기기에서 수행될 수 있으며, 또는 내비게이션 기기에서 전적으로 수행될 수 있다. 상기 서버 상에서의 하나 이상의 단계들의 성능은 효율적일 수 있으며, 그리고 내비게이션 기기에 배치된 계산 부담을 줄일 수 있다. 대안적으로, 하나 이상의 단계들이 상기 내비게이션 기기 상에서 수행된다면, 이는 네트워크 통신에 필요한 대역폭을 감소시킬 수 있다. 따라서 본 발명의 시스템은 내비게이션 기기 또는 다른 모바일 장치에 의해 부분적으로 제공될 수 있으며, 그리고 부분적으로 서버에 의해 제공될 수 있다.

예를 들어, 상기 제1 경로를 획득하는(예를 들어, 생성하는) 단계 및 상기 대안 경로를 생성하는 단계는 내비게이션 기기에 의해 수행될 수 있다. 또한 상기 내비게이션 기기는 상기 제1 경로의 중앙 부분을 결정할 수도 있다. 다른 구성들에서, 상기 제1 경로 및 상기 대안 경로 중 하나 또는 둘 모두는 상기 서버에 의해 획득되거나 생성될 수 있다. 또 다른 가능성에서, 모든 단계들은 서버에 의해 수행될 수 있다. 따라서 상기 방법의 임의의 단계 또는 단계들은 서버 또는 내비게이션 기기 중 하나에서 수행될 수 있다. 서버 또는 내비게이션 기기는 상기 대안 경로를 생성하는데 사용하기 위해 임의의 적절한 방식으로 상기 중앙 부분의 각 구간 또는 상기 구간에 불이익을 가하도록 조정될 수 있으며, 그리고 적절하다면, 대안 경로를 생성할 때 상기 시스템의 다른 부분에 의해 사용하기 위해 데이터를 송신할 수 있다.

본원에서 사용된 "구간"이란 용어는 본원 기술 분야에서의 통상의 의미를 취한다. 구간은 두 개의 노드들을 연결하는 가항 링크(navigable link)이거나 또는 그것의 임의의 부분일 수 있다. 본 발명의 실시예들이 도로 구간들을 참조하여 설명되지만, 본 발명은 또한, 길, 강, 운하, 사이클 경로, 예선로(tow path), 철도선 등의 구간들 같은, 다른 가항 구간들에도 적용될 수 있다는 것이 인식되어야 한다. 편의를 위해, 이러한 것들은 일반적으로 도로 구간으로 지칭되지만, "도로 구간"에 대한 임의의 언급은 "가항 구간", 또는 그러한 구간들의 임의의 특정 유형 또는 유형들에 대한 언급으로 대체될 수 있다.

상기 방법은 제1 위치 및 제2 위치 사이의 제1 경로를 획득하는 단계를 포함한다. 일부 실시예들에서, 상기 제1 경로는 시작점 및 목적지 사이에서 생성된 경로에 해당하며, 상기 제1 위치 및 상기 제2 위치는 각각 상기 생성된 경로의 시작점 및 목적지에 해당한다. 상기 방법은 시작점 및 목적지 사이의 경로를 생성함으로써 상기 제1 경로를 획득하는 단계를 포함할 수 있으며, 이 경우, 상기 제1 경로는 상기 생성된 경로에 해당하며, 상기 제1 위치 및 상기 제2 위치는 각각 상기 생성된 경로의 시작점 및 목적지이다. 이러한 실시예들은 특히, 상기 대안 경로의 생성을 포함하는 상기 방법의 단계들이 상기 제1 경로를 따른 길 안내가 시작하기 전에 수행되는 경우에, 적용될 수 있다. 상기 경로는 임의의 적절한 방식으로 생성될 수 있다. 바람직하게는, 상기 경로는 상기 가항 네트워크의 가항 구간들을 통과하는 비용에 기초하여 생성된다. 가항 구간을 통과하는 비용은 비용 함수를 사용하여 결정될 수 있다. 적절한 비용 함수들은 당업계에 공지되어 있다. 구간을 통과하는 비용은 상기 구간과 연관된 하나 이상의 속성들에 기초하여 결정될 수 있다. 바람직하게는, 상기 제1 경로는 상기 제1 위치 및 상기 제2 위치 사이의 최소 비용 경로이다. 최소 비용 경로는 상기 가항 네트워크의 구간들을 통과하는 것과 연관된 비용을 최소화시키는 것에 기초할 수 있으며, 이 비용은 적절한 비용 함수를 사용하여 결정된다. 예를 들어, 상기 비용 함수는 적절하게, 예를 들어 사용자 입력에 기초하여, 선택될 수 있어, 가장 짧은 경로, 가장 빠른 경로, 가장 환경 친화적인 경로 등인 최소 비용 경로를 야기한다.

대안적으로 시작점 및 (상기 제1 위치 및 상기 제2 위치에 대응하는) 위치 사이의 제1 경로는 다른 미리 정해진 경로를 따라 주행하는 동안 생성될 수 있음이 이해될 것이다. 예를 들어, 상기 제1 경로는 따라가지고 있는 미리 정해진 경로 상에 위치하는 제1 경로 시작점에 관해 생성될 수 있다. 그 다음, 상기 제1 경로는 상기 미리 정해진 경로에 대한 연장(continuation)을, 예를 들어 상기 미리 정해진 경로의 범위(extension)를 제공할 수 있으며, 또는 따라가질 새로운 경로가 되는 상기 미리 정해진 경로의 변경된 나머지 또는 부분을 제공할 수 있다. 이러한 상황들에서, 상기 제1 경로 시작점은 자동으로 선택될 수 있다. 상기 제1 경로 시작점은 미리 정해진 경로를 따르는 현재 위치이거나 또는 현재 위치 앞에 있는 지점일 수 있다.

다른 실시예들에서, 상기 제1 경로는 길 안내되고 있는 미리 정해진 경로의 나머지 중 적어도 일부에 해당할 수 있다. 바람직하게는, 상기 제1 경로는 길 안내되고 있는 미리 정해진 경로의 나머지에, 즉 상기 경로의 현재 위치 및 목적지 사이에 있는 전체 나머지에 해당한다. 상기 미리 정해진 경로는 이전에 생성된 경로이다. 상기 미리 정해진 경로는 시작점 및 목적지 사이에 생성된 경로이다. 이러한 실시예들은 특히, 본 발명이 미리 정해진 경로를 따르는 길 안내가 시작된 후 구현될 때, 즉 "도중에(en route)" 대안 경로들을 생성하기 위해 구현될 때, 적용 가능하며, 이는 후술된다. 상기 방법은 길 안내되고 있는 미리 정해진 경로의 나머지 중 적어도 일부를 식별함으로써 상기 제1 경로를 획득하는 단계를 포함할 수 있다. 그렇다면, 상기 제1 위치는 길 안내되고 있는 상기 미리 정해진 경로를 따르는 위치(예를 들어, 현재 위치 또는 현재 위치 앞에 있는 위치)이다. 예를 들어, 상기 제1 위치는 미래의 특정 시간에 도달될 것인, 상기 미리 정해진 경로를 따르는 포지션일 수 있으며, 또는 상기 미리 정해진 경로의 나머지를 따르는 결심 지점(decision point)에 해당하는 상기 미리 정해진 경로를 따르는 포지션 등일 수 있다. 바람직하게는, 상기 제1 위치는 현재 위치이다. 바람직하게는, 상기 제2 위치는 길 안내가 되고 있는 상기 미리 정해진 경로의 목적지이다. 그러나 반드시 이러한 경우일 필요가 없다. 상기 제2 위치는 주행 방향으로 상기 제1 위치 너머에 있는, 상기 미리 정해진 경로를 따르는 임의의 위치일 수 있다. 상기 방법은 길 안내되고 있는 상기 미리 정해진 경로를 생성하는 단계로 확장하거나 확장하지 않을 수 있다는 것이 이해될 것이다. 상기 방법은, 상기 제1 경로를 획득하는 단계에 앞서, 길 안내되고 있는 미리 정해진 경로를 제공하기 위해, 시작점 및 목적지 사이의 경로를 생성하는 단계까지 연장할 수 있다. 상기 방법은 시작점 및 목적지 사이의 경로를 생성하는 단계, 그리고 상기 경로를 따른 길 안내가 시작된 후, 길 안내되고 있는 상기 경로의 나머지 중 적어도 일부를 식별함으로써 상기 제1 경로를 획득하는 단계를 포함할 수 있다. 상기 경로는, 예를 들어 최소 비용 경로 등인, 제1 경로가 생성되는 실시예들과 관련하여 상술된 방식들 중 임의의 방식으로 생성될 수 있다.

상기 제1 경로가 시작점 및 목적지 사이에서 생성된 경로인지, 또는 미리 정해진 경로의 나머지 부분인지, 또는 그 밖의 경우인지 여부와 관계없이, 바람직하게는, 상기 제1 경로는 최소 비용 경로이다. 이러한 실시예들에서, 상기 경로는 상기 네트워크의 상기 가항 요소들과 연관된 하나 이상의 속성들에 기초하여 비용 함수를 최소화시키기 위해 결정된 경로이다.

상기 제1 위치 및 상기 제2 위치는, 그리고 상기 방법이 상기 제1 경로를 생성하는 단계까지 연장하지 않는 일부 실시예들에서 상기 제1 경로는, 임의의 적절한 소스 또는 소스들로부터 획득될 수 있다. 상기 제1 위치 및 상기 제2 위치는 원하는 대로 선택될 수 있으며, 그리고 사용자에 의해 지정되거나 또는 자동으로 선택되거나 또는 이들의 조합들일 수 있다. 예를 들어, 상기 제1 위치, 상기 제2 위치, 그리고/또는 상기 제1 경로는 통신 네트워크를 통해 수신될 수 있다. 예를 들어, 상기 방법은 길 안내되고 있는, 그리고 상기 제1 경로를 제공하기 위한 것인 미리 정해진 경로의 나머지를 나타내는 데이터를 수신하는 단계를 포함할 수 있다. 서버는 내비게이션 기기로부터 그러한 데이터를 수신할 수 있으며, 이 역 또한 같다. 상기 제1 경로가 획득되는 방법과 무관하게, 즉 상기 제1 경로가 미리 정해진 경로로부터 생성되거나 결정되었는지 여부와 무관하게, 상기 제1 위치 및 상기 제2 위치는 통신 네트워크를 통해 수신될 수 있다. 상기 제1 위치 및 상기 제2 위치는 상기 네트워크의 임의의 컴포넌트들 사이에서 송신될 수 있다. 다시 말해, 상기 제1 경로의 시작점 및 목적지는 서버에 의해 내비게이션 기기로부터 수신될 수 있거나, 또는 내비게이션 기기에 의해 서버로부터 수신될 수 있을 것으로 예상된다. 일부 실시예들에서, 상기 제1 위치 및/또는 상기 제2 위치는 사용자에 의한 입력일 수 있다. 상기 제1 위치 및/또는 상기 제2 위치는 사용자에 의한, 내비게이션 기기 또는 서버에 대한 입력일 수 있다. 이러한 구성들은 특히, 상기 제1 위치 및 상기 제2 위치가 생성된 경로의 시작점 및 목적지에 해당하는 경우, 적용될 수 있다. 예를 들어 상기 제2 위치가, 사용자가 지정한 시작점 및 목적지 사이에서 생성된, 길 안내되고 있는 미리 정해진 경로의 나머지의 목적지에 해당한다면, 상기 제2 위치만이 사용자에 의해 지정될 수 있다는 것이 이해될 것이다.

상기 대안 경로를 생성하는 단계는 임의의 스테이지에서 구현될 수 있으며, 그리고 미리 정해진 경로를 따라 길 안내를 하기 전에, 또는 미리 정해진 경로를 따라 길 안내를 하는 동안 구현될 수 있다. 예를 들어, 상기 대안 경로는 내비게이션 기기 또는 다른 경로 탐색 시스템에 의한 경로 탐색 작업 시작 시에 상기 제1 경로와 함께 생성될 수 있다. 이러한 실시예들에서, 상기 제1 위치 및 상기 제2 위치는, 각각 상기 제1 경로의 시작점 및 목적지일 수 있다. 그 다음, 사용자는 길 안내가 시작되면, 처음 생성된 경로보다 우선적으로, 대안 경로 또는 상기 대안 경로를 따를지의 여부를 결정할 수 있다. 상기에 명시된 바와 같이, 본 발명은 내비게이션 기능을 가진 시스템에 의한 구현으로 제한되지 않으며, 상기 대안 경로는 사용자에 의한 평가를 위한 경로 생성 시스템에 의해 생성될 수 있으며, 이로써, 상기 경로들은 내비게이션 작업 중에 차후에 사용될 수 있으며, 또는 그 다음 경로 안내에서 사용되지 않으면서 단순히 사용자에 의해 검토될 수 있다. 예를 들어, 상기 사용자는 차후 사용을 위해 상기 경로를 프린트하거나 저장할 수 있다.

그러나 유리하게는, 본 발명은 "즉석으로(on the fly)" 구현될 수 있다. 이러한 실시예들에서, 상기 대안 경로는 "도중 대안 경로(en route alternative route)"로 지칭될 수 있다. 예를 들어, 길 안내되고 있는 미리 정해진 경로가 앞쪽에서 트래픽에 의해 영향을 받는다는 것이 판단되면, 대안 경로 생성이 개시될 수 있다. 이에 따라 바람직한 실시예들에서, 상기 대안 경로는 즉석으로, 그리고/또는 미리 정해진 경로를 따르는 길 안내 중에 생성된다. 그렇다면, 상기 제1 경로는 길 안내되고 있는 상기 미리 정해진 경로의 나머지일 수 있다.

사용자는 다양한 이유로 인해 그들이, 경로를 따른 주행이 시작된 후 다른 적절한 대안 경로들이 존재하는지의 여부를 보길 원한다는 것을 결정할 수 있다. 상기 대안 경로의 생성은 자동적으로, 또는 사용자 입력에 응답하여 발생할 수 있다. 상기 대안 경로는 길 안내되고 있는 미리 정해진 경로를 따르는 결심 지점 또는 결심 지점들과 관련하여 자동적으로 생성될 수 있다. 이러한 실시예들에서, 상기 경로는, 종래 시스템들에서 미리 정해진 경로를 따른 길 안내 중에 새로운 "가장 빠른" 경로들이 생성되는 것과 유사한 방식으로, 미리 정해진 경로를 따른 길 안내 중에 백그라운드 태스크(background task)로서 자동적으로 생성된다.

상기 제1 경로는, 자동적으로이든 또는 사용자 요청에 응답하여서이든, 어떤 이유로 인해 대안을 획득하는 것이 요구되는 경로이다. 상기 제1 경로는 상기 제1 위치 및 상기 제2 위치 사이에서 한정된 상기 제1 경로를 따라 측정된 길이를 갖는다. 따라서 상기 제1 위치 및 상기 제2 위치는 각각 상기 제1 경로의 제1 말단 및 제2 말단에 해당한다. 이하에서 더 상세히 설명되는 바와 같이, 상기 제1 위치 및 상기 제2 위치는 상기 제1 경로를 제공하는 생성된 경로의 시작점 및 목적지에 해당할 수 있다는 것이 이해될 것이다. 상기 제1 경로가 시작점 및 목적지 사이에서 생성된 미리 정해진 경로의 나머지 중 적어도 일부인 다른 실시예들에서, 상기 제1 위치는, 상기 경로의 나머지의 시작점을 정의하는 현재 위치에 해당할 수 있거나, 또는 현재 위치 앞에 있는 포지션에 해당할 수 있다. 그렇다면, 상기 제2 위치는 상기 미리 정해진 생성된 경로의 목적지에 해당할 수 있다. 상기 제1 경로가 미리 정해진 경로의 나머지인 경우들에서, 상기 제2 위치가 반드시 미리 정해진 경로의 목적지에 해당하지 않을 수 있다는 것이 예상된다. 상기 대안 경로가 오직 상기 미리 정해진 경로의 나머지 중 일부분과 관련하여서만 제공되는 것이 바람직할 수 있다. 그러나 바람직하게는, 상기 제1 위치는 상기 미리 정해진 경로에 따른 현재 위치에 해당하며, 상기 제2 위치는 상기 미리 정해진 경로의 목적지에 해당한다.

본 발명에 따르면, 상기 제1 경로의 중앙 부분이 한정된다. 상기 중앙 부분은 상기 제1 위치 및 상기 제2 위치 사이에 있는 상기 제1 경로의 길이 방향의 위치와 관련하여 "중심"이다. 상기 중심 부분은 오직 상기 제1 경로의 길이의 중앙 부분 걸쳐 길이방향으로 연장한다.

본 발명에 따르면, 상기 제1 경로를 따르는, 즉 상기 제1 경로의 길이를 따르는, 상기 중앙 부분의 범위는 상기 제1 위치 및 상기 제2 위치 사이의 거리에 기초하여 결정되며, 이 경우, 상기 제1 경로를 따르는 상기 중앙 부분의 상대적 범위는 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있다. 상기 상대적 범위는 상기 제1 경로의 범위에 대한 상기 중앙 부분의 범위를 말한다. 상기 범위들은 길이방향 범위들이다. 상기 제1 경로를 따르는 상기 중앙 부분의 범위는 상기 제1 경로를 따르는 상기 중앙 부분의 길이이며, 상기 중앙 부분의 상대적 범위는 상기 제1 경로를 따르는 상기 제1 경로의 길이에 대한 상기 중앙 부분의 길이를 말한다. 즉, 상기 중앙 부분이 연장하는 상기 제1 경로의 비율은 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있다. 본원의 "반비례 관계"란 용어는, 중앙 부분에 대해 결정된 상대적 범위가 상기 제1 위치 및 상기 제2 위치 사이의 거리가 증가함에 따라 감소할 것이며, 상기 제1 위치 및 상기 제2 위치 사이의 거리가 감소함에 따라 증가할 것이라는 것을 의미한다.

상기 중앙 부분의 범위는, 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있는 상기 제1 경로를 따르는 상기 중앙 부분의 상대적 범위를 야기하는 상기 제1 위치 및 상기 제2 위치 사이의 거리를 사용하여, 임의의 방식으로 결정될 수 있다. 상기 중앙 부분의 범위는 결정된 상기 중앙 부분의 상대적 범위가 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있는 함수를 사용하여 결정될 수 있다. 예를 들어, 상기 중앙 부분의 상대적 범위는, 결정된 상대적 범위가 상기 제1 위치 및 상기 제2 위치 사이의 거리의 역수와 관련되도록 하게 하는 함수를 사용하여 획득될 수 있다. 상기 방법은 : 상기 제1 위치 및 상기 제2 위치 사이의 거리로 작동하는 함수에 상기 제1 위치 및 상기 제2 위치 사이의 거리를 입력하여, 그 거리에 대한 제1 경로를 따르는 중앙부의 상대적 범위인 출력을 제공하는 단계를 포함할 수 있으며, 이 때, 상기 함수는 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있는, 제1 위치 및 제2 위치 사이의 임의의 입력 거리의 상기 중앙 부분에 대한 상대적 범위 출력을 제공하도록 조정되며, 상기 제1 경로는 상기 제1 위치 및 상기 제2 위치 사이에서 연장한다.

상기 방법은 상기 중앙 부분이 연장할 상기 제1 경로의 길이의 백분율을 결정하는 단계를 포함할 수 있다. 결정된 백분율은 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있다.

상기 제1 경로를 따르는 상기 중앙 부분의 상대적 범위를 결정하는데 사용되는 상기 제1 위치 및 상기 제2 위치 사이의 거리는 상기 제1 위치 및 상기 제2 위치 사이의 거리를 임의로 측정한 값일 수 있다. 바람직하게는, 상기 중앙 부분의 상대적 범위를 결정하는데 사용되는 상기 제1 위치 및 상기 제2 위치 사이의 거리는 상기 제1 위치 및 상기 제2 위치 사이의 상기 제1 경로를 따라 측정된 거리이다. 그러나 대안적으로 상기 제1 위치 및 상기 제2 위치 사이의 직선거리가 사용될 수 있다는 것이 예상된다. 상기 제1 위치 및 상기 제2 위치 사이의 거리의 두 측정치들 모두, 상기 위치들 간의 거리와 반비례 관계에 있는 상기 중앙 부분의 상대적 범위가 결정될 수 있게 할 것이다.

바람직한 실시예들에서, 상기 방법은 상기 제1 위치 및 상기 제2 위치 사이에서 상기 제1 경로의 길이를 따른 중앙 지점을 식별하는 단계를 포함하며, 상기 중앙 부분은 중앙부로부터, 그것이 원하는 정도가 될 때까지, 양방향으로 동등하게 연장한다. 상기 제1 경로의 중앙 지점은 상기 경로를 따라 상기 제1 위치 및 상기 제2 위치로부터 등거리에 있다. 바람직하게는, 상기 중앙 부분의 시작점 및 끝점은 상기 경로를 따르는 상기 제1 경로의 중앙 지점으로부터 등거리에 있다.

본 발명에 따르면, 상기 방법은 상기 제1 경로를 따르는 상기 한정된 중앙 부분을 형성하는, 상기 가항 네트워크의 하나 이상의 가항 구간들을 식별하는 단계를 포함한다. 이러한 가항 구간들은 본 발명에 따라 대안 경로를 생성하기 위해 불이익이 가해지는 가항 구간들이다. 상기 중앙 부분을 "형성"하는 것으로 간주되는 그러한 가항 구간들은 그 전체가 상기 중앙 부분에 포함되는 가항 구간들을 포함할 것이다. 그러나 상기 제1 경로를 따르는 상기 중앙 부분의 시작점 및 끝점이 반드시 가항 구간들의 끝점들과 일치할 필요가 없을 수 있다는 것이 이해될 것이며, 이로써, 오직 일부 가항 구간들의 일부만이 상기 중앙 영역에 포함될 수 있다. 오직 가항 구간의 일부만이 상기 중앙 부분에 포함되는 경우, 상기 구간을 상기 중앙 부분을 형성하는 구간으로 간주할지의 여부를 결정할 수 있다. 예를 들어, 오직 전부가 상기 중앙 부분 내에 있는 구간들만이 상기 중앙 부분을 형성하는 것으로 간주될 수 있으며, 또는 적어도 일부가 상기 중앙 지점 내에 있는 모든 구간들이 상기 중앙 부분을 형성하는 것으로 간주될 수 있으며, 또는 오직 상기 중앙 영역 내에 있는 부분이 특정 임계값 이상인 구간들만이 포함될 수 있다.

본 발명에 따르면, 상기 중앙 부분의 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간은, 상기 가항 네트워크를 통한 경로 생성을 위해, 상기 가항 구간이 상기 가항 네트워크를 통해 생성된 경로에 포함되는 것에 대해 덜 유리하도록 만듦으로써, 불이익을 받을 수 있다. 따라서 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간은 상기 가항 네트워크를 통한 대안 경로 생성에 있어서 불이익을 받는다.

상기 가항 구간 또는 각각의 가항 구간은 상기 가항 네트워크를 통한 경로 생성을 위해 임의의 적절한 방식으로 불이익을 받을 수 있으며, 이로써, 대안 경로가 생성될 때, 상기 구간 또는 각각의 구간은 포함에 있어서 덜 유리하게, 즉 다른 경우들보다 불리하게, 고려된다. 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간은, 상기 가항 구간을 상기 가항 네트워크를 통한 경로에 포함되는 것에 대해 덜 유리하도록 만들기 위해, 그곳에 불이익을 적용함으로써 불이익이 가해질 수 있다. 생성된 대안 경로는 불이익이 가해진 가항 구간(들)을, 즉 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 적용된 불이익을, 고려한다. 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간이 상기 중앙 부분의 일부를 형성하기 때문에 나타난 결과로서 경로 생성을 위해 그 식별된 가항 구간에 적용된 불이익은, 그렇지 않았다면 그 구간에 적용되었을 임의의 불이익 보다 크거나 같다. 상기 방법은 불이익을 가하는 단계, 예를 들어 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 불이익을 적용하며, 상기 제1 경로의 중앙 부분 중 일부를 형성하는 것으로 식별되지 않은 가항 구간들에는 불이익을 적용하지 않는 단계를 포함한다. 실시예들에서, 상기 방법은 오직 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에만 불이익을 가하는 단계(예를 들어, 오직 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에만 불이익을 적용하는 단계)를 포함한다.

바람직하게는, 상기 제1 위치 및 상기 제2 위치 사이에서 상기 가항 네트워크를 통해 생성된 대안 경로는 상기 가항 네트워크의 가항 구간들을 통과하는 비용에 기초한다. 상기 방법은 상기 가항 구간 또는 각각의 가항 구간에 비용 불이익을 적용함으로써, 경로 생성을 위해 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 불이익을 가하는 단계를 포함할 수 있다. 이러한 실시예들에서, 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간은 상기 중앙 부분의 일부를 형성하는 구간의 결과로서 비용 불이익을 포함하는, 경로 생성을 위한 비용을 할당받는다. 상기 비용 불이익은, 경로(예를 들어, 대안 경로)가 상기 가항 네트워크를 통해 생성될 때, 그렇지 않은 경우보다 덜 유리한 것으로 고려되는 구간을 야기한다. 일부 실시예들에서, 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 불이익을 가하는 단계는, 상기 중앙 부분의 일부를 형성하지 않는 상기 가항 네트워크의 다른 가항 구간들에 비해 불이익이 가해지는 상기 가항 구간 또는 각각의 가항 구간을 야기한다. 상기 식별된 구간 또는 각각의 식별된 구간은 불리한 것과 연관될 수 있다. 예를 들어, 상기 식별된 구간 또는 각각의 식별된 구간은 경로 결정에 있어서, 상기 중앙 부분의 일부를 형성하지 않는 다른 구간들에 비해 불리한, 더 많은 통과비용과 연관될 수 있다. 추천된 가항 가능한 쭉 뻗은 구간(stretch)의 가항 구간(들)은 상기 중앙 부분의 일부를 형성하지 않는 상기 가항 네트워크의 임의의 다른 가항 구간보다 덜 유리하게 될 수 있다. 그러나 비용 불이익을 고려한 후에도, 식별된 가항 구간은 여전히 생성된 대안 경로의 일부를 형성할 수 있음이 예상된다. 예를 들어, 경로 생성에서 고려되는 상기 구간들의 속성 또는 속성들에 기초한 다른 요인들에 기인한 상기 구간을 통과하는 것과 연관된 비용은, 상기 구간에 적용된 비용 불이익을 고려하였는데도, 상기 구간이 다른 후보 구간들의 통과비용 보다 더 유리한 통과비용을 가질 수 있도록 하는 정도이다.

상기 방법은 상기 구간을 통과하는 비용을 변경하는, 즉 그렇지 않았을 때 상기 구간에 할당되는 비용에 비해, 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 비용 불이익을 적용하는 단계를 포함할 수 있다. 일반적으로, 가항 구간과 연관된 비용이 높을수록, 상기 구간은 경로 생성에 있어서 덜 유리할 것이다. 종종 경로 생성은 상기 가항 네트워크를 통한 최소 비용 경로를 제공하고자 한다. 실시예들에서, 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 비용 불이익을 할당함으로써 그 가항 구간에 불이익을 가하는 단계는, 상기 가항 구간 또는 각각의 가항 구간에, 그렇지 않은 경우 상기 가항 구간에 할당될 비용 보다 더 높은 비용을 할당하는 단계를 포함한다. 이런 식으로, 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 할당되는 비용은, 상기 구간이 상기 중앙 영역의 일부를 형성한다는 사실에 기인하는 성분을 포함한다. 비용 불이익은, 예를 들어 상기 중앙 부분의 일부를 형성하는 것으로 식별된 구간들에게 추가 비용 성분을 부가함으로써, 또는 상기 식별된 구간 또는 각각의 식별된 구간(들)에 대해 결정되는 비용에 대한 스케일링 인자(scaling factor)를 적용함으로써 제공될 수 있다. 본원에서 사용된 "비용 불이익(cost penalty)"이란 용어는 상기 중앙 부분의 일부를 형성하는 구간의 결과로서, 상기 구간이 상기 중앙 부분의 일부를 형성하지 않을 때 보다, 경로 생성에 대해 덜 유리하도록 조정되는 비용을 말한다. 물론, 본 발명은 더 높은 비용이 덜 유리한 구간에 대응하는 바람직한 실시예들에 관하여 설명되었지만, 상기 방법은, 더 낮은 비용이 덜 유리한 구간에 대응하는 경우들에도 동등하게 적용될 수 있다. 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 할당되는 비용은, 적절하다면, 경로 생성을 위해 상기 구간에 불이익을 가하도록 선택될 수 있으며, 이로써, 사용된 특정 라우팅 엔진의 작동을 고려하여, 상기 구간이 경로에 포함되는 것에 대해 덜 유리하도록 만들 수 있다. 상기 라우팅 엔진은, 바람직하게는 최소 비용 경로인, 경로에 대해 최적화된 경로를 제공할 수 있다.

가항 구간을 통과하는 것과 연관된 비용은 비용 함수를 사용하여 결정될 수 있다. 실시예들에서, 비용 불이익은 상기 비용 함수를 사용하여 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 적용될 수 있다. 예를 들어, 상기 방법은, 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간이 상기 중심 영역의 일부를 형성하는 것에 따른 결과로서 그 가항 구간에(예를 들어, 오직 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에만) 비용 불이익을 적용하도록 조정된 비용 함수를 사용하여 상기 가항 네트워크의 가항 구간들을 통과하는 것과 연관된 비용을 결정하는 단계를 포함할 수 있다. 물론, 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 비용 불이익을 적용하기 위한 다른 구성들도 사용될 수 있으며, 이는 상기 비용 함수를 사용하여 수행될 필요는 없다. 예를 들어, 상기 불이익은, 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 대한 비용 함수의 적용 후에, 상기 대안 경로를 생성할 때 적절히 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 대해 결정된 비용에 가중치를 줌으로써 적용된다.

실시예들에서, 상기 가항 네트워크의 각각의 가항 구간은 자신과 연관된 하나 이상의 속성들을 나타내는 속성 데이터를 갖는다. 가항 구간을 통과하는 비용은 적어도 부분적으로, 그 가항 구간과 연관된 속성 데이터에 기초한다. 상기 비용은 가항 구간과 연관된 속성 데이터 전체 또는 일부를 고려할 수 있다. 이는 사용된 특정 비용 함수에 따라 다를 수 있다. 결국, 사용된 비용 함수는 상기 라우팅 엔진의 작동, 그리고 생성된 경로들에 대해 요구되는 속성들에 따라 달라질 것이다. 비용 함수는 가항 구간들의 속성들 중 임의의 하나 이상의 속성들을 고려할 수 있으며, 경로 생성에서의 사용을 위해 상기 구간에 비용을 할당할 때, 그것들의 속성들에게, 원하는 상대적 가중치를 적용할 수 있다.

본 발명에 따라 수행되는, 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 불이익을 가하는 단계는, 그렇지 않은 경우 상기 구간과 연관된 속성(들)이 원인일 수 있는 임의의 불이익 이상이다. 상기 불이익은 상기 제1 경로의 중앙 부분의 일부를 형성하는 가항 구간(들)에 기인하며, 따라서, 오직 상기 식별된 가항 요소(들)에게만 할당된다. 실시예들에서, 상기 방법은, 예를 들어 비용 함수를 사용하여, 상기 가항 구간들과 연관된 속성 데이터에 기초하여 상기 가항 네트워크의 가항 구간들을 통과하는 것과 연관된 비용을 결정하는 단계를 포함할 수 있으며, 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 비용 불이익을 가함으로써 그 가항 구간에 불이익을 가하여, 상기 가항 구간 또는 각각의 가항 구간이, 상기 구간과 연관된 속성 데이터에 기초하여 결정된 비용과 상이한, 바람직하게는 상기 구간과 연관된 속성 데이터에 기초하여 결정된 비용보다 더 높은 비용과 연관되게 하는 단계를 포함할 수 있다. 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간을 통과하는 비용은 상기 구간의 하나 이상의 속성들에 기초한 제1 성분 및 적용된 비용 불이익을 포함하는 제2 성분을 포함할 수 있다.

일부 구성들에서, 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간은, 본 발명에 따라, 상기 구간 또는 각각의 구간과 연관된 속성 데이터를 변경함으로써 불이익이 가해질 수 있으며, 이로써, 상기 구간 또는 각각의 구간은 경로에 포함되는 것에 있어서 덜 유리하게될 수 있다는 것이 예상된다. 따라서 적절한 비용 함수를 사용하여 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 비용 불이익을 바로 적용하는 것 외에, 가항 구간을 통과하는 비용 불이익은 상기 구간에 대한 속성 데이터를 변경하는 것을 통해 간접적으로 적용될 수 있다.

상기 방법은 :

상기 제1 경로의 중앙 부분의 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 대한 변경된 속성 데이터를 결정하는 단계로서, 상기 변경된 속성 데이터는, 상기 가항 구간들과 연관된 속성 데이터를 사용하여 상기 가항 네트워크를 통해 경로가 생성될 때, 상기 구간이 덜 유리하도록 만들기 위해, 상기 가항 구간에 불이익을 가하도록 결정되는, 단계; 및

상기 변경된 속성 데이터를 사용하여 상기 제1 위치 및 상기 제2 위치 사이의 대안 경로를 생성하는 단계를 포함할 수 있다.

이러한 실시예들에서, 본 발명에 따라 변경된 속성 데이터가 결정되는 상기 구간 또는 각각의 구간과 연관된 속성 또는 속성들은, 본 발명에 따라 변경될 때, 상기 구간(들)을 포함하는 상기 가항 네트워크를 통한 경로를 생성하는 것에 관해 고려될 때 불리하게 취급되는 상기 구간 또는 각각의 구간을 야기할 것인, 상기 구간 또는 각각의 구간과 연관된 속성들 중 임의의 속성 또는 속성들일 수 있다. 따라서 상기 속성(들)은 경로 생성시 라우팅 엔진에 의해 고려되는 속성(들)이다. 일부 바람직한 실시예들에서, 구간과 연관된 오직 하나의 속성만이 변경되지만, 속성들의 임의의 조합은, 이것이 경로 생성시 덜 유리한 것으로 간주되도록 불이익이 가해지는 구간을 야기한다면, 변경될 수 있다.

변경되는 속성 또는 속성들은, 예를 들어 (내비게이션 기기 또는 서버일 수 있는) 상기 시스템의 라우팅 엔진에 의해, 가항 구간들의 네트워크를 가로지르는 최소 비용 경로를 생성할 때와 같은 라우팅을 위해 고려되는 속성(들)에 따라 달라질 것이다. 일 예시적 구성에서, 변경되는 속성 또는 상기 속성은 상기 식별된 구간 또는 각각의 식별된 구간에 대한 교통 흐름 속도(flow speed)(예를 들어, 상기 구간에 따라 주행시 예상되는 속도)일 수 있다. 경로 생성시 덜 유리하게 취급되는 구간을 야기하기 위해, 대안적으로, 또는 추가적으로 변경될 수 있는, 그리고 본 발명에 따라 변경될 수 있는 다양한 다른 속성들이 있다. 예들은 상기 구간에 대한 통과 시간, 구간 길이, 상기 구간을 통과하기 위한 CO2 배출량, 또는 상기 구간을 통과하기 위한 연료 소비량을 포함한다. 이러한 속성들 중 임의의 속성은 상기 라우팅 엔진의 설정들에 따라, 비용을 참조하여 경로(예를 들어, 최소 비용 경로)를 생성하는데 사용하기 위해, 상기 구간과 연관된 비용을 결정하는데 사용될 수 있다. 예를 들어, 사용자는 주행 시간, 길이, CO2 배출량 또는 연료 소비량, 추가적으로 또는 대안적으로 도착 예정 시간 중 하나 이상을 최소화시키는 경로들이 생성되기를 바란다는 것을 명시할 수 있을 것이다. 라우팅 엔진은, 경로를 결정할 때, 예를 들어 비용 함수를 사용하여, 서로 다른 속성들의 범위의 균형을 유지하도록 조정될 수 있으며, 이 때, 상기 속성들은 사용자가 지정한 속성들을 포함하거나 포함하지 않을 수 있다.

상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 불이익이 가해지는 방법과 무관하게, 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 불이익을 가하는 단계는, 상기 가항 네트워크를 통한 경로 생성을 위해 불이익이 가해지는 상기 가항 구간 또는 각각의 가항 구간을 야기한다. 바람직하게는, 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간은, 상기 구간이, 상기 네트워크의 가항 구간들을 가로지르는 것에 대한 정해진 비용에 기초하여 생성된, 상기 네트워크를 통한 경로에 포함되는 것에 대해 덜 유리하게 되도록 불이익이 가해진다. 그러면, 상기 대안 경로는 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 적용된 불이익을 고려하여 생성될 수 있다. 바람직하게는, 상기 방법은 각각의 구간을 통과하는 것에 대해 정해진 비용에 기초하여, 가항 구간들의 상기 네트워크를 통한 대안 경로를 생성하는 단계를 포함한다. 바람직하게는, 상기 방법은 비용에 있어서 최적화된, 그리고 바람직하게는 상기 가항 네트워크를 통한 최소 비용 경로인, 대안 경로를 생성하는 단계를 포함한다. 이렇게 생성된 대안 경로는, 상기 제1 경로의 중앙 부분을 형성하는 하나 이상의 식별된 가항 구간들에 대해 적용된 불이익을 고려하여, 경로 결정에서 사용된 주어진 비용 함수에 대해 최적화된 경로이다. 상기 시스템(예를 들어, 서버 또는 내비게이션 기기)은 설명된 실시예들 중 임의의 실시예를 따라 작동하도록 조정된 라우팅 엔진을 포함할 수 있다.

상기 가항 네트워크의 각각의 가항 구간은 경로(예를 들어, 대안 경로)를 생성할 때 고려되거나 고려되지 않을 수 있음이 이해될 것이다. 예를 들어, 라우팅 엔진은 오직 특정 가항 구간들만을, 예를 들어 라우팅 통로(routing corridor) 등의 일부를 형성하는 가항 구간들만을, 고려할 수 있다. 따라서 상기 식별된 가항 구간들 또는 각각의 식별된 가항 구간은 고려된 다른 가항 구간들과 비교하여 불이익이 가해지며, 경로를 생성하는 단계는, 상기 네트워크의 가항 구간들의 서브셋이거나 서브셋이 아닐 수 있는, 상기 가항 네트워크의 가항 구간들을 통과하는 비용에 기초할 수 있다.

본 발명의 일부 바람직한 실시예들에서, 상기 방법은 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례하는 정도까지 상기 중앙 부분의 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 불이익을 가하는 단계를 포함한다. 즉, 더 긴 제1 경로들에 대해, 상기 중앙 부분의 가항 구간들에게 불이익이 가해지는 정도는 더 짧은 제1 경로에 대한 경우보다 더 적을 것이다. 이러한 특징은, 더 짧은 경로들의 경우에, 상기 제1 경로의 중앙 부분으로부터 멀어지도록 상기 생성된 대안 경로들을 더 강하게 "미는(pushing)" 효과를 갖는다.

상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 불이익을 가하는 단계는 상기 대안 경로를 생성하는 단계 전에, 또는 상기 대안 경로를 생성하는 단계의 일부로서 발생할 수 있다.

본 발명의 양상들 또는 실시예들의 임의의 것에서 본 발명을 따르면, (제1) 대안 경로가 생성되었다면, 본 발명의 단계들은 추가 대안 경로를 획득하기 위해, 즉 처음으로 생성된 대안 경로의 대안을 획득하기 위해, 상기 제1 경로 대신에, 생성된 대안 경로를 사용하여 반복될 수 있다. 상기 추가 대안 경로 또는 각각의 추가 대안 경로는 본원에서 설명된 방식들 중 임의의 방식으로 출력되거나 저장되거나 디스플레이될 수 있다. 이러한 실시예들에서 본 발명의 단계들을 반복할 때, 상기 대안 경로의 중앙 부분의 상대적 범위는 상기 제1 위치 및 상기 제2 위치 사이의 거리를 참조하여 결정된다. 이는 상기 제1 경로를 참조하여, 또는 관련 경로에 따른 상기 (제1) 대안 경로를 참고하여 측정될 수 있으며, 또는 상기 제1 위치 및 상기 제2 위치 사이의 직선거리를 참고할 수 있다.

이에 따라 상기 방법은 :

상기 생성된 대안 경로의 중앙 부분을 한정하는 단계로서, 상기 중앙 부분은 상기 제1 위치 및 상기 제2 위치 사이의 거리를 참고하여 결정되는 상기 대안 경로를 따르는 범위를 가지며, 상기 대안 경로를 따르는 상기 중앙 부분의 상대적 범위는 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있는, 단계;

상기 대안 경로를 따르는 상기 한정된 중앙 부분을 형성하는 하나 이상의 가항 구간들을 식별하는 단계;

상기 가항 네트워크를 통한 경로 생성을 위해, 상기 가항 구간 또는 각각의 가항 구간이 상기 가항 네트워크를 통한 경로에 포함되는 것에 대해 덜 유리하도록 만듦으로써, 상기 대안 경로를 따르는 상기 중앙 부분의 상기 식별된 가항 구간 또는 식별된 각각의 가항 구간에 불이익(penalty)을 가하는 단계; 및

상기 제1 위치 및 상기 제2 위치 사이에 있는, 상기 가항 네트워크를 통한 추가 대안 경로를 생성하는 단계를 더 포함한다.

이러한 추가 실시예에서, 상기 추가 대안 경로를 제공하기 위해 상기 (제1) 대안 경로에 관하여 수행되는 단계들, 즉 상기 제1 경로에 대한 대안에 관하여 수행되는 단계들은, 상기 제1 경로에 관하여 상술한 실시예들 중 임의의 실시예를 따를 수 있다. 따라서 상기 (제1) 대안 경로를 생성하는 것에 관해 설명된 단계들 또는 특징들 중 임의의 것은 추가 대안 경로를 생성하는 것과 결부시켜 사용될 수 있다. 상기 대안 경로의 중앙 부분은 상기 제1 경로와 관련하여 상술한 방식들 중 임의의 방식으로 한정될 수 있다.

물론, 또 다른 대안 경로들이 유사한 방식으로 생성될 수 있다. 각각의 경우에, 생성된 대안 경로는, 중앙 부분이 한정되고 가항 구간들에게 불이익이 가해지고, 그리고 대안 경로가 생성되는 경로를 제공하기 위해 사용될 수 있다. 상기 중앙 부분의 범위는 직선으로서 측정되는, 또는 상기 제1 경로, 제1 대안 경로 또는 이전에 생성된 임의의 추가 대안 경로를 따라 측정되는 상기 제1 위치 및 상기 제2 위치 사이의 거리를 사용하여 결정될 수 있다.

대안 경로가 생성되면, 먼저 생성된 대안 경로에 기초하여 상술된 바와 같이 획득된 제1 대안 경로이든 또는 추가 대안 경로이든 간에, 그것은 추가 테스팅 없이 사용될 수 있다. 예를 들어, 사용자에게 출력되거나 이하에서 설명되는 바와 유사하게 사용될 수 있다. 그러나 다른 실시예들에서, 생성된 대안 경로는 그것이 허용 가능한 대안 경로로 간주되기 이전에 추가 테스팅의 대상이 되는 후보 대안 경로인 것으로 고려될 수 있다.

상기 방법은 생성된 대안 경로(제1 대안 경로이든 또는 추가 대안 경로이든 관계없이)가 허용 가능한 대안 경로인지 여부를, 상기 생성된 대안 경로의 상기 제1 경로와의 유사성을 평가함으로써 판단하는 단계를 포함할 수 있다. 바람직하게는, 상기 평가는 상기 제1 경로와 공유된, 상기 대안 경로의 비율을 참고하여 수행된다. 예를 들어, 공유된 경로 부분들의 길이 비율이 판단될 수 있다. 상기 방법은 상기 평가의 결과들을 사용하여 상기 대안 경로가 혀용 가능한지 여부를 판단하는 단계를 포함할 수 있다. 일반적으로, 대안 경로가 상기 제1 경로와 너무 유사하지 않는 것이 바람직하다. 대안 경로가 허용 가능한지 여부를 판단하는 단계는 적절하다면, 예를 들어 상기 제1 경로와 공유된 상기 경로의 비율을 임계값 혹은 유사한 것과 비교함으로써, 수행될 수 있다. 예를 들어 상기 제1 경로와 공유된 상기 대안 경로의 비율을 참고하여, 상기 대안 경로의 상기 제1 경로와의 유사성이 주어진 임계값 아래에 있을 때, 상기 대안 경로는 허용 가능한 것으로 간주될 수 있다. 이에 따라 일부 실시예들에서, 상기 방법은 상기 제1 경로와 공유된 상기 대안 경로의 비율이 미리 정해진 임계값을 초과할 때, 상기 대안 경로는 허용가능하지 않다고 판단하는 단계를 포함한다. 임계값은, 용인될 수 있는 경로 유사성의 정도에 따라, 원하는 대로 설정될 수 있다.

상기 방법은, 상기 생성된 대안 경로가 상기 제1 경로와 너무 유사하여 받아들여질 수 없는 것으로 간주된다면, 상기 식별된 가항 구간 또는 각각의 식별 가항 구간에 추가 불이익을 가하여, (상기 구간(들)에 적용된 불이익을 고려하여) 상기 가항 네트워크를 통해 경로가 생성될 때 상기 구간 또는 각각의 구간이 훨씬 더 불리하도록 만드는 단계를 포함할 수 있다. 상기 방법은 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 추가 불이익이 가해지면, 상기 제1 위치 및 상기 제2 위치 사이의 또 다른 대안 경로를 생성하는 단계를 포함할 수 있다. 이에 따라, 상기 초기 대안 경로는 제1 대안 경로로 지칭될 수 있다.

물론, 동일한 단계들은 또 다른 생성된 경로에 대해 반복될 수 있다. 따라서 생성된 또 다른 대안 경로의 상기 제1 경로와의 유사성이 평가될 수 있으며, 그것이 너무 유사하여 받아들여질 수 없는 것으로 간주된다면, 상기 식별된 구간 또는 구간들에게 추가 불이익이 가해져, 상기 구간 또는 각각의 구간이 경로 생성에 있어서 훨씬 더 불리하도록 만들 수 있으며, 또 다른 대안 경로가 생성된다. 생성된 경로의 상기 제1 경로와의 유사성을 판단하는 단계, 상기 경로가 상기 제1 경로와 너무 유사하여 받아들여질 수 없는 것으로 간주된다면 상기 제1 경로의 상기 중앙 부분의 구간들에게 추가 불이익을 가하는 단계, 그리고 또 다른 대안 경로를 생성하는 단계의 이러한 프로세스는, 허용가능한 대안 경로가 생성될 때까지, 미리 정해진 횟수의 시도들까지 반복될 수 있으며, 이 때, 상기 중앙 부분의 상기 식별된 구간(들)에 적용되는 불이익은 각각의 시도마다 더 증가된다. 그 때까지 허용 가능한 것으로 간주되는 대안 경로가 생성되지 않는다면, 적절한 대안 경로를 찾을 수 없다고 판단될 수 있다. 사용자에게 대안 경로 생성 프로세스의 실패를 알리기 위해, 즉 적절한 대안 경로를 찾을 수 없다고 명시하기 위해, 사용자에게 적절한 출력이 이루어질 수 있다.

예를 들어 상기 제1 경로와의 유사성을 참고하여, 생성된 대안 경로들이 허용가능성에 대해 평가된 경우, 경로에 대한 정보는 오직 그러한 테스트가 통과된 경우에만 출력될 수 있다. 즉, 오직 허용 가능한 경로들만이 설명된 방식들 중 임의의 방식으로 출력된다.

상기 방법은 생성된 대안 경로 또는 상기 생성된 대안 경로(예를 들어, 다수의 경로들이 생성된 경우 제1 대안 경로, 또는 실시예들에서 허용 가능한 것으로 간주된 임의의 추가 대안 경로)를 출력하는 단계를 포함할 수 있다. 바람직한 실시예들에서, 상기 방법은 사용자에게 생성된 대안 경로를 나타내는 정보를 제공하는 단계를 더 포함한다. 이는 상기 경로 또는 상기 경로를 나타내는 정보를 사용자에게 출력하는 단계를 포함할 수 있다. 상기 정보는 임의의 방식으로(예를 들어, 명령들의 세트로) 상기 경로를 나타낼 수 있으며, 이러한 정보는 음성적(audible)이거나 또는 시각적일 수 있지만, 바람직하게는, 상기 경로의 시각적 표현이다. 바람직한 실시예들에서, 상기 방법은 사용자에게 상기 경로를 디스플레이하는 단계를 포함한다. 그러나 출력의 다른 형태들이 사용될 수 있다. 예를 들어, 상기 방법은 상기 경로를 나타내는 정보를 프린팅하는 단계를 대안적으로 또는 추가적으로 포함할 수 있다. 바람직하게는, 상기 경로를 나타내는 정보는 내비게이션 기기를 통한, 사용자에 게 출력될 수 있지만, 다른 실시예들에서, 상기 정보는, 예를 들어 경로 생성 기능을 갖지만 내비게이션 기능을 가질 필요가 없는 컴퓨터 장치 등에 의해 디스플레이됨으로써, 임의의 적절한 처리 장치에 의해 출력될 수 있다. 이는 상기 경로가 서버에 의해 생성되는 경우 적절할 수 있다. 바람직한 실시예들에서, 상기 적어도 하나의 대안 경로가 PND 또는 통합 내비게이션 기기(예를 들어, 차량 내 내비게이션 기기) 같은 내비게이션 기기에 의해 생성되는지 여부와 관계없이, 상기 경로(들)를 나타내는 정보는 그러한 장치에 의해 상기 사용자에게 출력된다. 예를 들어, 경로의 생성은 원격 서버에 의해 수행될 수 있으며, 상기 경로를 나타내는 정보는 사용자에게 출력되기 위해 내비게이션 기기에게 제공될 수 있다. 바람직한 실시예들에서, 상기 경로가 생성된 경우, 상기 경로를 디스플레이하는 단계는 상기 경로 또는 각각의 경로를 상기 전자 지도 상에 중첩시키는 단계를 포함할 수 있다. 이는 사용자에게 상기 경로를 따를지의 여부를 결정할 시간을 제공한다. 상기 사용자의 현재 위치는 상기 사용자와 연관된 (예를 들어, 상기 사용자의 차량 내에 위치한) 내비게이션 기기(예를 들어, 휴대용(또는 모바일) 장치 또는 통합 장치)에 의해 결정된 현재 위치에 해당할 수 있다.

바람직하게는, 상기 방법은 사용자에게 상기 제1 경로를 나타내는 정보를 제공하는 단계를 더 포함한다. 이는 대안 경로 또는 상기 대안 경로를 참고하여 설명된 방식들 중 임의의 방식으로 수행될 수 있다. 실시예들에서, 상기 방법은 상기 사용자에게 상기 제1 경로를, 바람직하게는 상기 대안 경로도, 출력하는 단계(예를 들어, 디스플레이하는 단계)를 포함하며, 바람직하게는, 이 경우, 상기 제1 대안 경로 또는 상기 대안 경로는, 예를 들어 상기 전자 지도상에 상기 경로들을 동시에 디스플레이 함으로써, 사용자에게 동시에 출력된다(예를 들어, 디스플레이된다).

상기 방법은 대안 경로 또는 상기 대안 경로를 따라 사용자를 안내하기 위한 내비게이션 명령들의 세트를 제공하는 단계를 더 포함할 수 있다. 상기 명령들은 당업계에 공지된 바와 같이, 시각적 명령들, 청각적 명령들 또는 촉각적 명령들, 또는 이들의 조합들일 수 있다. 이는 본원의 내비게이션 명령들에 대한 모든 언급에 적용된다. 바람직하게는, 상기 경로는 사용자가 선택한 경로이다. 상기 내비게이션 명령들은 내비게이션 기기를 통해 사용자에게 제공될 수 있으며, 또는, 예를 들어 명령들을 디스플레이하거나 명령들을 프린팅하는 등 경로 생성 기능을 제공하는 컴퓨터 장치에 의해, 사용자에게 출력될 수 있다. 상기 명령들은 대안 경로에 대한 사용자 선택에 응답하여 제공될 수 있다.

실시예들에서, 상기 방법은 사용자로부터 대안 경로 또는 상기 대안 경로의 선택의 표시를 수신하는 단계를 더 포함할 수 있다. 상기 선택은 상기 사용자가 상기 선택된 경로를 따라 길 안내를 받고 싶어 한다는 것을 나타낼 수 있다. 예를 들어, 상기 사용자는, 예를 들어 내비게이션 기기의, 또는 경로 생성 기능을 제공하는 컴퓨팅 장치와 연관된, 적절한 사용자 인터페이스를 통해 대안 경로를 선택할 수 있다. 오직 하나의 대안 경로가 제공된다면, 상기 사용자는 그들이 상기 제1 경로보다 상기 대안 경로를 사용하고 싶다고 명시할 수 있다. 물론, 대안 경로(들)가 제공된 경우라도, 상기 사용자는 상기 제1 경로를 사용하기로 결정할 수 있다. 그러나 본 발명은 사용자에게, 그들이 대안 옵션들을 고려하였으며 처음 생성된 경로를 사용한다는 것에 대해 긍정적인 결정을 내렸다는 것을 재확인할 수 있는 기회를 제공한다. 사용자에게 대안 경로들을 제시하는 예시적 방법들은 위에서 언급된 WO 2012/034581에서 발견될 수 있다.

바람직하게는, 상기 대안 경로(들)는 자동적으로 생성된다. 즉, 사용자 개입 없이 생성된다.

본 발명의 양상들 또는 실시예들 중 임의의 것에서 본 발명의 방법은 상기 전자 지도에 의해 커버되는 영역 내에 있는 위치들 사이에 있는 하나 이상의 추가 경로들에 대해 반복될 수 있다는 것이 이해될 것이다. 상기 추가 경로들은 추가 입력 경로들, 즉 상기 제1 경로들에 대한 추가들이다.

길 안내되고 있는 미리 정해진 경로에 대한 언급들은, 예를 들어 내비게이션 기기에 의해, 사용자가 안내받고 있는 경로를 의미하기 위해, 바람직하게는 그와 관련하여 내비게이션 명령(들)이 제공되고 있는 경로를 의미하기 위해, 당해 분야에서의 통상적인 의미로 이해될 수 있다. 이러한 것들은 일반적으로 예를 들어 상기 경로를 따를 상기 사용자에 의해 취해질 동작(manoeuvre)들 또는 다른 액션을 나타내는 하나 이상의 명령들의 세트와 조합한, 경로의 디스플레이 형태일 수 있으며, 이는 음성적으로 그리고/또는 시각적으로 주어질 수 있다. 상기 미리 정해진 경로는 상기 대안 경로들이 생성된 시간에 주행되고 있는, 또는 적어도 사용자에게 제공되고 있는, 경로를 의미한다.

본 발명에 따른 방법들 중 임의의 방법은 적어도 부분적으로 소프트웨어(예를 들어, 컴퓨터 프로그램들)를 사용하여 구현될 수 있다. 따라서 본 발명은 본 발명의 양상들 또는 실시예들 중 일부에 따른 방법을 수행하기 위해, 또는 내비게이션 기기 및/또는 서버가 본 발명의 양상들 또는 실시예들 중 일부에 따른 방법을 수행하도록 유발하기 위해 실행 가능한 컴퓨터 판독 가능한 명령들을 포함하는 컴퓨터 프로그램까지 연장한다.

이에 부응하여, 본 발명은, 데이터 처리 수단을 포함하는 시스템 또는 장치를 작동시키기 위해 사용될 때, 상기 데이터 처리 수단과 함께, 상기 장치 또는 상기 시스템이 본 발명의 방법들의 단계들을 수행하도록 유발하는 소프트웨어를 포함하는 컴퓨터 소프트웨어 캐리어(carrier)로 연장한다. 그러한 컴퓨터 소프트웨어 캐리어는 ROM 칩, CD ROM 또는 디스크와 같은 비-일시적 물리적 저장 매체일 수 있으며, 또는 와이어들을 통한 전자 신호와 같은 신호, 광신호, 또는 위성 신호와 같은 무선 신호 등일 수 있다. 본 발명은, 기계에 의해 판독될 때, 상기 기계가 본 발명의 양상들 또는 실시예들 중 임의의 것의 방법에 따라 작동하도록 유발시키는 명령들을 포함하는 기계 판독 가능 매체를 제공한다.

구현과 무관하게, 본 발명에 따라 사용되는 내비게이션 기기는 프로세서, 메모리, 그리고 상기 메모리 내에 저장된 디지털 지도 데이터를 포함할 수 있다. 상기 프로세서 및 상기 메모리는 소프트웨어 운영 시스템이 확립될 수 있는 실행 환경을 제공하기 위해 협력한다. 하나 이상의 추가 소프트웨어 프로그램들이 제공되어, 상기 장치의 기능이 제어될 수 있게 하며, 다양한 다른 기능들을 제공할 수 있다. 바람직하게는, 본 발명의 내비게이션 기기는 GPS(Global Positioning System) 신호 수신 및 처리 기능을 포함할 수 있다. 상기 장치는 하나 이상의 출력 인터페이스들을 포함할 수 있으며, 상기 출력 인터페이스들을 이용하여, 사용자에게 정보가 전달될 수 있다. 상기 출력 인터페이스(들)는 영상 디스플레이 이외에 음성 출력을 하기 위한 스피커를 포함할 수 있다. 상기 장치는 상기 장치의 온/오프 작동 또는 다른 기능들을 제어하기 위해 하나 이상의 물리적 버튼들을 포함하는 입력 인터페이스들을 포함할 수 있다.

다른 실시예들에서, 상기 내비게이션 기기는 특정 내비게이션 기기의 일부를 형성하지 않는 처리 장치의 애플리케이션에 의해 적어도 부분적으로 구현될 수 있다. 예를 들어, 본 발명은 내비게이션 소프트웨어를 실행하도록 조정된 적절한 컴퓨터 시스템을 사용하여 구현될 수 있다. 상기 시스템은 모바일 또는 이동식 컴퓨터 시스템(예를 들어, 휴대폰 또는 랩탑)일 수 있으며, 또는 데스크탑 시스템일 수 있다.

달리 명시되지 않는다면, 본 발명의 양상들의 임의의 얏아에서 본 발명은, 서로 모순이 되지 않는 정도까지는, 본 발명의 다른 양상들 또는 실시예들에 대하여 설명된 모든 또는 임의의 특징들을 포함할 수 있다는 것이 이해될 것이다. 특히, 상기 방법에서 그리고 상기 장치에 의해 수행될 수 있는 동작들의 다양한 실시예들이 설명되었지만, 이러한 작업들 모두 또는 하나 이상은 원하는 대로, 그리고 적절하다면, 상기 방법에서 그리고 상기 장치에 의해, 임의의 조합으로 수행될 수 있다는 것이 이해될 것이다.

이러한 실시예들의 이점들은 이하에 명시되어 있으며, 이러한 실시예들 각각의 추가적인 세부사항 및 특징들은 첨부된 종속항들 및 다음의 상세한 설명에서 정의된다.

이하에서는, 본 발명의 실시예들이 첨부 도면들을 참조하여, 단지 예로서만 설명될 것이다.
도 1은 내비게이션 기기에 의해 사용가능한 위성 위치 확인 시스템(Global positioning system; GPS)의 예시적 부분의 개략도이다.
도 2는 내비게이션 기기 및 서버 간의 통신을 위한 통신 시스템의 개략도이다.
도 3은 도 2의 내비게이션 기기 또는 임의의 다른 적절한 내비게이션 기기의 전자 컴포넌트들의 개략도이다.
도 4는 내비게이션 기기를 장착시키고 그리고/또는 도킹(docking)하는 장치의 개략도이다.
도 5는 본 발명의 일실시예에 따른 방법의 단계들을 도시하는 흐름도이다.
도 6은 제1 경로의 중앙 부분이 한정될 수 있는 방법을 도시한다.

이제, 본 발명의 실시예들은 특히 PND(Portable Navigation Device)를 참조하여 설명될 것이다. 그러나 본 발명의 교시들은 PND들로 한정되는 것이 아니며, 그 대신에, 경로 계획 및 내비게이션 기능을 제공하기 위해 이동 가능한 방식으로 내비게이션 소프트웨어를 실행시키도록 구성된 임의의 유형의 처리 기기에 광범위하게 적용가능하다는 것이 기억되어야 한다. 따라서 본 출원의 맥락에서, 내비게이션 기기는, 그 기기가 PND로서 구현된 것인지, 자동차와 같은 차량으로서 구현된 것인지, 또는 실제로 경로 계획 및 내비게이션 소프트웨어를 실행하는 휴대용 컴퓨팅 리소스(예를 들어, 휴대용 개인 컴퓨터(PC), 휴대용 전화기 또는 휴대용 정보 단말기(PDA))로 구현된 것인지 여부와 관계없이, 임의 유형의 경로 계획 및 내비게이션 기기를 (한정하지 않으면서) 포함하도록 의도된 것이다.

또한, 본 발명의 실시예들은 도로 구간들(road segments)을 참조하여 설명된다. 본 발명은 길, 강, 운하, 자전거 길(cycle path), 예선로(tow path), 철도선 등의 세그먼트들과 같은, 다른 가항 세그먼트들에도 적용될 수 있다는 것이 이해되어야 한다. 편의상, 이러한 것들은 통상 도로 구간라고 한다.

또한 본 발명의 교시들은, 사용자가 한 지점에서 다른 지점으로 이동하는 방법에 대한 설명들을 필요로 하지 않지만, 주어진 위치의 뷰만은 제공받고자 하는 상황들에서 조차도 유용성을 가진다는 것도 이하에서 명백해질 것이다. 이러한 상황들에서, 상기 사용자에 의해 선택된 "목적지" 위치는 상기 사용자가 경로 찾기를 시작하고자하는 해당 시작 위치를 가질 필요는 없으며, 결과적으로, 본 명세서에서의 "목적지" 위치에 대한 언급들 또는 실제로는 "목적지" 뷰에 대한 언급들은, 경로의 생성이 필수적이라거나, 상기 "목적지"로의 주행이 일어나야만 한다거나, 또는 실제로, 목적지의 존재가 해당 시작 위치의 지정을 필요로 한다는 것을 의미하는 것으로 해석되어서는 안 된다.

상기 단서들을 기억한 채로 살피면, 도 1의 위성 위치 확인 시스템(GPS) 및 그와 유사한 것들은 다양한 목적들을 위해 사용된다. 일반적으로, GPS는 무제한 사용자들에 대한 연속적인 위치, 속도, 시간, 그리고 일부 예들에서는 방향 정보를 판단할 수 있는 위성-라디오 기반 네비게이션 시스템이다. 예전에 NAVSTAR로 알려진 GPS는 매우 정확한 궤도들로 지구를 선회하는 다수의 위성들을 포함한다. 이들의 정확한 궤도들에 기초하여, GPS 위성들은 임의의 수의 수신 유닛들에게 그들의 위치를, GPS 데이터로서, 중계할 수 있다. 그러나 GLOSNASS, 유럽의 Galileo 위치 확인 시스템, COMPASS 위치 확인 시스템 또는 IRNSS(Indian Regional Navigational Satellite System) 같은 위성 위치 확인 시스템들이 사용될 수 있음이 이해될 것이다.

GPS 시스템은, 특히 GPS 데이터를 수신하도록 구성된 기기가 GPS 위성 신호들용 무선 주파수들을 스캐닝하는 것을 시작할 때 구현된다. GPS 위성으로부터 무선 신호를 수신할 때, 상기 기기는 서로 다른 다수의 종래 방법들 중 하나를 통해 그 위성의 정확한 위치를 판단한다. 상기 기기는, 대부분의 예들에서, 적어도 3개의 상이한 위성 신호들을 취득할 때까지(그 포지션은 보통 그런 것은 아니지만, 다른 삼각측량 기술들을 사용하여 오직 두 개의 신호들만으로 판단될 수 있다는 것에 유의한다), 신호들에 대한 스캐닝을 계속할 것이다. 기하학적 삼각측량을 구현함으로써, 상기 수신기는 3 개의 알려진 위치들을 활용하여, 상기 위성들에 대한 자신의 고유의 2-차원 포지션을 판단한다. 이는 공지된 방법으로 행해질 수 있다. 추가적으로, 제4 위성 신호를 취득하는 것은, 상기 수신 기기가 알려진 방식의 동일한 기하학적 계산에 의해 자신의 3차원 포지션을 계산하는 것을 가능하게 한다. 상기 포지션 및 속도 데이터는 무제한의 사용자들에 의해 계속적으로 실시간 업데이트 될 수 있다.

도 1에 나타난 바와 같이, 상기 GPS 시스템(100)은 지구(104)에 대해 궤도를 그리며 도는 다수의 위성들(102)을 포함한다. GPS 수신기(106)는 많은 상기 다수의 위성들(102)로부터 확산 스펙트럼(spread spectrum) GPS 위성 데이터 신호들(108)로서 GPS 데이터를 수신한다. 상기 확산 스펙트럼 데이터 신호들(108)은 각각의 위성(102)으로부터 연속적으로 송신되며, 송신된 확산 스펙트럼 데이터 신호들(108) 각각은, 그 데이터 스트림이 발생한 특정 위성(102)을 식별하는 정보를 포함하는 데이터 스트림을 포함한다. 일반적으로 상기 GPS 수신기(106)는 2-차원 포지션을 계산할 수 있기 위해 적어도 3개의 위성들(102)로부터의 확산 스펙트럼 데이터 신호들(108)을 필요로 한다. 제4 확산 스펙트럼 데이터 신호는, 상기 GPS 수신기(106)가, 공지된 기법을 사용하여 3-차원 포지션을 계산할 수 있게 한다.

도 2를 참조하면, 상기 GPS 수신 기기(106)를 포함하거나 GPS 수신 기기(106)에 연결된 내비게이션 기기(200)(즉, PND)는 모바일 기기(도시되지 않음)(예를 들어, 휴대폰, PDA 및/또는 휴대폰 기술을 가진 임의의 기기)를 통해 "모바일" 또는 원격 통신 네트워크의 네트워크 하드웨어를 사용하여 데이터 세션을 구축할 수 있어서, 디지털 연결(예를 들어, 공지된 블루투스 기술을 통한 디지털 연결)을 구축한다. 그 후, 자신의 네트워크 서비스 제공자를 통해, 상기 모바일 기기는 (예를 들어, 인터넷을 통해) 서버(150)와의 네트워크 연결을 구축할 수 있다. 그에 따라, "실시간의" 또는 적어도 매우 "최신의" 정보 게이트웨이를 제공하기 위해, (상기 내비게이션 기기(200)가 단독으로 그리고/또는 차량 내에서 이동함에 따라 움직일 수 있고, 종종 움직이는) 내비게이션 기기(200) 및 상기 서버(150) 사이에 "모바일" 네트워크 연결이 구축된다.

예를 들어 인터넷을 사용한, (서비스 제공자를 경유한) 상기 모바일 기기, 그리고 상기 서버(150)와 같은 또 다른 기기 간의 네트워크 연결 설정은, 공지된 방식으로 수행될 수 있다. 이와 관련하여, 얼마든지 많은 적절한 데이터 통신 프로토콜들(예를 들어, TCP/IP 계층화된 프로토콜)이 채용될 수 있다. 뿐만 아니라, 상기 모바일 기기는 CDMA2000, GSM, IEEE 802.11 a/b/c/g/n 등과 같은 임의의 개수의 통신 표준들을 사용할 수 있다.

이런 이유로, 인터넷 연결이 사용될 수 있음을 알 수 있으며, 예를 들어, 이는 상기 내비게이션 기기(200) 내의 데이터 연결을 통해, 휴대폰 또는 휴대폰 기술을 통해 달성될 수 있다.

도시되지 않았지만, 물론 상기 내비게이션 기기(200)는 상기 내비게이션 기기(200) 그 자체 내에 자신 고유의 이동 전화 기술(mobile telephone technology)(예를 들어, 안테나 포함, 또는 옵션으로는 상기 내비게이션 기기(200)의 내부 안테나를 사용)을 포함할 수 있다. 상기 내비게이션 기기(200) 내의 이동 전화 기술은 내부 컴포넌트들을 포함할 수 있으며, 그리고/또는, 예를 들어 필요한 이동 전화 기술 및/또는 안테나가 완비된, 삽입 가능한 카드(예를 들어, 가입자 식별 모듈(Subscriber Identity Module; SIM) 카드)를 포함할 수 있다. 이와 같이, 상기 내비게이션 기기(200) 내의 이동 전화 기술은 임의의 모바일 기기의 연결 방식과 유사한 방식으로, (예를 들어, 인터넷을 통한) 상기 내비게이션 기기(200) 및 상기 서버(150) 간의 네트워크 연결을 유사하게 설정할 수 있다.

전화 설정들의 경우, 블루투스 가능 내비게이션 기기는 휴대폰 모델들, 제조사들 등의 상시 변화 스펙트럼(ever changing spectrum)에 알맞게 작동하도록 사용될 수 있고, 모델/제조사 특유의 설정들은 예를 들어 상기 내비게이션 기기(200) 상에 저장될 수 있다. 이러한 정보를 위해 저장된 상기 데이터는 업데이트될 수 있다.

도 2에서, 상기 내비게이션 기기(200)는 다수의 서로 다른 배열들 중 임의의 배열에 의해 구현될 수 있는 포괄 통신 채널(152)을 통해 상기 서버(150)와 통신하는 것으로 묘사된다. 일반적으로, 상기 통신 채널(152)은 상기 내비게이션 기기(200) 및 상기 서버(150)를 연결하는 전파 매체 또는 경로를 나타낸다. 상기 서버(150) 및 상기 내비게이션 기기(200)는 상기 서버(150) 및 상기 내비게이션 기기(200) 사이에 상기 통신 채널(152)을 통한 연결이 설정되었을 때 통신할 수 있다(이러한 연결은 모바일 기기를 통한 데이터 연결, 인터넷을 통한 개인용 컴퓨터를 통한 직접 연결 등일 수 있음을 유의).

상기 통신 채널(152)은 특정 통신 기술에 제한되지 않는다. 또한, 상기 통신 채널(152)은 단일 통신 기술에 제한되지 않는데; 즉, 상기 채널(152)은 다양한 기술을 사용하는 여러 통신 링크들을 포함할 수 있다. 예를 들어, 상기 통신 채널(152)은 전기, 광 및/또는 전자기 통신들 등을 위한 경로를 제공하도록 조정될 수 있다. 이에 따라, 상기 통신 채널(152)은 다음을 중 하나 또는 복수개의 조합을 포함하나 이에 제한되지 않는다 : 전기 회로들, 전선들(wires) 및 동축 케이블들과 같은 전기 전도체들, 광섬유 케이블들, 컨버터들, 라디오-주파수(RF) 파들, 대기(atmosphere), 빈 공간 등. 뿐만 아니라, 상기 통신 채널(152)은, 예를 들어 라우터들, 리피터들, 버퍼들, 송신기들 및 수신기들과 같은, 중계 기기들을 포함할 수 있다.

일 예시적 배열에서, 상기 통신 채널(152)은 전화 및 컴퓨터 네트워크들을 포함한다. 뿐만 아니라, 상기 통신 채널(152)은, 예를 들어 적외선 통신, (마이크로 주파수 통신 같은) 라디오 주파수 통신 등의 무선 통신을 지원할 수 있다. 또한, 상기 통신 채널(152)은 위성 통신을 지원할 수 있다.

상기 통신 채널(152)을 통해 송신된 상기 통신 신호들은, 주어진 통신 기술에 필요하거나 바람직할 수 있는 신호들을 포함하나, 이에 제한되지는 않는다. 예를 들어, 상기 신호들은 시분할 다중 접속(Time Division Multiple Access(TDMA)), 주파수 분할 다중 접속(Frequency Division Multiple Access(FDMA)), 코드 분할 다중 접속(Code Division Multiple Access(CDMA)), 유럽 이동 통신 시스템(Global System for Mobile Communications(GSM)), 범용 패킷 무선 서비스(General Packet Radio Service(GPRS)) 등 같은 셀룰러 통신 기술에 사용되도록 조정될 수 있다. 디지털 및 아날로그 신호들 모두가 상기 통신 채널(152)을 통해 송신될 수 있다. 이러한 신호들은, 상기 통신 기술에 바람직할 수 있도록, 변조되고, 암호화되고, 그리고/또는 압축된 신호들일 수 있다.

상기 서버(150)는, 도시되지 않을 수 있는 다른 컴포넌트들에 추가하여, 프로세서(154)를 포함하며, 상기 프로세서(154)는 메모리(156)에 작동적으로 연결(operatively connected)되고 나아가 유선 또는 무선 연결(158)을 통해 대용량 데이터 저장 기기(160)에 작동적으로 연결된다. 상기 대용량 저장 기기(160)는 내비게이션 데이터 및 지도 정보의 저장을 포함하며, 그리고 상기 서버(150)로부터 분리된 기기일 수 있거나, 또는 상기 서버(150) 내에 포함될 수도 있다. 또한, 상기 프로세서(154)는 송신기(162) 및 수신기(164)에 작동적으로 더 연결되어, 통신 채널(152)을 통해 내비게이션 기기(200)로부터, 그리고 내비게이션 기기(200)에게 정보를 송신하고 수신한다. 발송된 신호들 및 수신된 신호들은 데이터, 통신 및/또는 다른 전파된 신호들을 포함할 수 있다. 상기 송신기(162) 및 상기 수신기(164)는 상기 내비게이션 시스템(200)을 위한 통신 설계에 사용되는 통신 기술 및 통신 요건에 따라 선택되거나 설계될 수 있다. 또한, 상기 송신기(162) 및 상기 수신기(164)의 기능들은 단일의 송수신기로 결합될 수 있음이 유의되어야 한다.

전술한 바와 같이, 상기 내비게이션 기기(200)는 통신 채널(152)을 통해 상기 서버(150)와 통신하도록 조정될 수 있으며, 상기 송신기(166) 및 상기 수신기(168)를 사용하여, 상기 통신 채널(152)을 통해 신호들 및/또는 데이터를 발송하고 수신하도록 조정될 수 있다. 이 때, 이러한 기기들은 상기 서버(150)가 아닌 기기들과 통신하는 데에도 사용될 수 있음에 유의한다. 또한, 상기 송신기(166) 및 상기 수신기(168)는 상기 내비게이션 기기(200)의 통신 설계에 사용되는 통신 요건들 및 통신 기술에 따라 선택되거나 설계되며, 그리고 상기 송신기(166) 및 상기 수신기(168)의 기능들은 도 2와 관련하여 전술한 바와 같이 단일의 송수신기로 결합될 수 있다. 물론, 상기 내비게이션 기기(200)는 다른 하드웨어 및/또는 기능적 부분들을 포함하며, 이는 이하에서 더 자세히 설명될 것이다.

서버 메모리(156)에 저장된 소프트웨어는 상기 프로세서(154)를 위한 명령들을 제공하고, 그리고 상기 서버(150)가 상기 내비게이션 기기(200)에게 서비스들을 제공하도록 한다. 상기 서버(150)에 의해 제공된 하나의 서비스는 상기 내비게이션 기기(200)로부터의 요청들을 처리하는 것, 그리고 상기 대용량 데이터 저장소(160)로부터 상기 내비게이션 기기(200)로 내비게이션 데이터를 송신하는 것에 관여한다. 상기 서버(150)에 의해 제공될 수 있는 다른 서비스는, 원하는 적용(application)을 위해 다양한 알고리즘들을 사용하여 내비게이션 데이터를 처리하는 것, 그리고 이러한 계산들의 결과들을 상기 내비게이션 기기(200)에게 발송하는 것을 포함한다.

상기 서버(150)는 무선 채널을 통해 상기 내비게이션 기기(200)에 의해 접근 가능한 데이터의 원격 소스(remote source)를 구성한다. 상기 서버(150)는 근거리 통신망(local area network; LAN), 광역 네트워크(wide area network; WAN), 가상사설망(virtual private network; VPN) 등에 위치한 네트워크 서버를 포함할 수 있다.

상기 서버(150)는 데스크탑 또는 노트북 컴퓨터와 같은 개인용 컴퓨터를 포함할 수 있으며, 상기 통신 채널(152)은 상기 개인용 컴퓨터 및 상기 내비게이션 기기(200) 사이에 연결된 케이블일 수 있다. 대안적으로, 개인용 컴퓨터는 상기 내비게이션 기기(200) 및 상기 서버(150) 사이에 연결되어, 상기 서버(150) 및 상기 내비게이션 기기(200) 사이의 인터넷 연결을 구축할 수 있다.

상기 내비게이션 기기(200)는 정보 다운로드들을 통해 상기 서버(150)로부터 정보를 제공받을 수 있으며, 상기 정보 다운로드들은, 때때로 자동적으로, 또는 상기 내비게이션 기기(200)를 상기 서버(150)에 연결하는 사용자에 의해, 업데이트될 수 있으며, 그리고/또는 상기 정보 다운로드들은 예를 들어 무선 모바일 연결 기기 및 TCP/IP 연결을 통해 상기 서버(150)와 상기 내비게이션 기기(200) 사이에서 이루어지는 더욱 지속적인 또는 빈번한 연결로 더욱 동적으로 이루어질 수 있다. 많은 동적 계산들의 경우, 상기 서버(150) 내의 상기 프로세서(154)는 대량의 처리 요구들을 다루는데 사용될 수 있지만, 상기 내비게이션 기기(200)의 프로세서(도 2에 도시되지 않음) 또한 많은 처리 및 계산을 다룰 수 있고, 이는 종종 서버(150)로의 연결과 별개로 이루어질 수 있다.

도 3을 참조하면, 상기 내비게이션 기기(200)의 블록도는 상기 내비게이션 기기의 모든 컴포넌트들을 포함한 것은 아니고, 많은 예시적 컴포넌트들 중 일부만을 예시한 것임을 유의하여야 한다. 상기 내비게이션 기기(200)는 하우징(도시되지 않음) 내에 위치한다. 상기 내비게이션 기기(200)는, 예를 들어 상술한 참조번호 202의 프로세서를 포함하는, 처리 회로를 포함하며, 상기 프로세서(202)는 입력 기기(204) 및 디스플레이 기기(예를 들어, 디스플레이 스크린(206))에 연결된다. 본원에서는 단일의 입력 기기(204)에 대한 참조가 이루어졌지만, 당업자는 상기 입력 기기(204)가 임의의 개수의 입력 기기들(키보드 기기, 음성 입력 기기, 터치 패널 및/또는 정보를 입력하는데 활용되는 다른 공지된 입력 기기를 포함)을 나타내는 것이라고 이해해야 한다. 이와 유사하게, 상기 디스플레이 스크린(206)은, 예를 들어 LCD(Liquid Crystal Display) 같은, 임의의 유형의 디스플레이 스크린을 포함할 수 있다.

일 구성에서, 상기 입력 기기(204), 상기 터치 패널 및 상기 디스플레이 스크린(206)의 일 양상은, 터치패드 또는 터치스크린 입력(250)(도 4)을 포함하는 통합된 입력 및 디스플레이 기기를 제공하여 (직접 입력, 메뉴 선택 등을 통한) 정보 입력 및 상기 터치 패널 스크린을 통한 정보의 디스플레이 모두를 가능하게 하며, 이로써, 사용자는 다수의 디스플레이 선택들 중 하나를 선택하기 위해 또는 다수의 가상 또는 "소프트" 버튼들 중 하나를 활성화하기 위해 상기 디스플레이 스크린(206)의 일부를 터치하기만 하면 된다. 이와 관련하여, 상기 프로세서(202)는 상기 터치스크린과 함께 작동하는 그래픽 사용자 인터페이스(Graphical User Interface; GUI)를 지원한다.

상기 내비게이션 기기(200)에서, 상기 프로세서(202)는 입력 기기(204)에 작동적으로 연결되어 있으며, 상기 입력 기기(204)로부터 입력 정보를 수신할 수 있다. 그리고 상기 프로세서(202)는 상기 디스플레이 스크린(206) 및 상기 출력 기기(208) 중 적어도 하나에 작동적으로 연결되며, 각각의 출력 연결부들(212)을 통해, 그곳에 정보를 출력한다. 상기 내비게이션 기기(200)는 예를 들어 음성 출력 기기(예를 들어, 확성기)와 같은 출력 기기(208)를 포함할 수 있다. 상기 출력 기기(208)가 상기 내비게이션 기기(200)의 사용자를 위해 음성 정보를 생성할 수 있는 것과 마찬가지로, 상기 입력 기기(204) 역시 입력 음성 명령들을 수신하기 위한 마이크 및 소프트웨어를 포함할 수 있음이 이해되어야 한다. 또한, 상기 내비게이션 기기(200)는, 예를 들어 오디오 입/출력 기기들 같은, 임의의 추가 입력 기기(204) 및/또는 임의의 추가 출력 기기도 포함할 수 있다.

상기 프로세서(202)는 참조번호 216의 연결부를 통해 메모리(214)에 작동적으로 연결되며, 참조번호 220의 연결부를 통해 입/출력(I/O) 포트들(218)로부터 정보를 수신하고 그리고/또는 I/O 포트들(218)에게 정보를 발송하도록 더 조정되며, 이 경우, 상기 I/O 포트(218)는 상기 내비게이션 기기(200)의 외부에 있는 I/O 기기(222)에게 연결될 수 있다. 상기 외부 I/O 기기(222)는, 예를 들어 이어폰 같은, 외부 청취 기기를 포함할 수 있으나, 이에 제한되지 않는다. 또한, 상기 I/O 기기(222)로의 연결은, 예를 들어 이어폰 또는 헤드폰으로의 연결을 위해 그리고/또는 휴대폰으로의 연결을 위해, 예를 들어 핸즈-프리 동작을 위한 그리고/또는 음성 활성 동작을 위한 카 스테레오 유닛 같은, 임의의 다른 외부 기기로의 유선 또는 무선 연결일 수 있으며, 이 경우, 상기 휴대폰 연결은 상기 내비게이션 기기(200), 그리고 인터넷 또는 임의의 다른 네트워크 사이에서 데이터 연결을 구축하기 위해 그리고/또는, 예를 들어 인터넷 또는 다른 네트워크를 통해 서버로의 연결을 구축하기 위해 사용될 수 있다.

상기 내비게이션 기기(200)의 메모리는 (예를 들어, 프로그램 코드를 저장하기 위해) 비-휘발성 메모리의 일부 및 (예를 들어, 상기 프로그램 코드가 실행될 때 데이터를 저장하기 위해) 휘발성 메모리의 일부를 포함한다. 또한 상기 내비게이션 기기는 연결부를 통해 상기 프로세서와 통신하는 포트(228)를 포함하여, (일반적으로 카드라 불리는) 이동식 메모리 카드가 상기 기기(200)에 추가되도록 한다. 설명되고 있는 실시예에서, 상기 포트는 SD(Secure Digital) 카드가 추가될 수 있게 하도록 조정된다. 다른 실시예들에서, 상기 포트는 (CF(Compact Flash) 카드들, 메모리 스틱들, xD 메모리 카드들, USB(Universal serial Bus) 플래시 드라이브들, MMC(MultiMedia) 카드들, 스마트미디어 카드들, 마이크로드라이브들 등 같은) 다른 형태의 메모리들이 연결될 수 있게 할 수 있다.

또한, 도 3은 참조번호 226의 연결부를 통한 상기 프로세서(202) 및 안테나/수신기(224) 간의 작동적 연결(operative connection)을 도시하며, 상기 안테나/수신기(224)는 예를 들어 GPS 안테나/수신기일 수 있으며, 이로써 도 1의 GPS 수신기 같이 기능할 것이다. 참조번호 224로 표시된 안테나/수신기는 도시를 위해 개략적으로 통합되었으나, 상기 안테나 및 수신기는 별도로 위치하는 컴포넌트들일 수 있고, 그리고 상기 안테나는 예를 들어 GPS 패치 안테나(GPS patch antenna) 또는 헬리컬 안테나(helical antenna)일 수 있음이 이해되어야 한다.

또한 도 3에 도시된 전자 컴포넌트들은 하나 이상의 파워 소스들(도시되지 않음)에 의해 종래의 방법으로 전력 공급된다는 것은 당해 기술 분야의 통상의 지식을 가진 자에게 이해될 것이다. 이러한 파워 소스들은 내부 배터리 및/또는 저전압 DC 서플라이 또는 임의의 다른 적절한 구성을 위한 입력을 포함할 수 있다. 당해 기술 분야의 통상의 지식을 가진 자에게 이해되는 바와 같이, 도 3에 도시된 컴포넌트들의 서로 다른 구성들이 고려된다. 예를 들어, 도 3에 도시된 컴포넌트들은 유선 연결 및/또는 무선 연결 등을 통해 서로 통신할 수 있다. 이에 따라, 본원에 설명된 상기 내비게이션 기기(200)는 휴대용 또는 손에 들고 쓰는(handheld) 내비게이션 기기(200)일 수 있다.

또한, 도 3의 휴대용 또는 손에 들고 쓰는 내비게이션 기기(200)는, 예를 들어 자전거, 오토바이, 자동차 또는 보트 같은, 차량에 공지된 방식으로 연결되거나 "도킹(docking)"될 수 있다. 이후 이러한 내비게이션 기기(200)는 도킹된 위치에서 제거되어 휴대용 또는 손에 들고 쓰는 내비게이션으로 사용될 수 있다. 실제로, 다른 실시예들에서, 상기 기기는 사용자의 내비게이션을 가능하게 하기 위해 손에 들고 쓰이도록 조정될 수 있다.

도 4를 참조하면, 상기 내비게이션 기기(200)는 일체형 입력 및 디스플레이 기기(206) 및 도 2의 다른 컴포넌트들(내부 GPS 수신기(224), 프로세서(202), 파워 서플라이(도시되지 않음), 메모리 시스템들(214) 등을 포함하지만 이에 제한되지 않는다)을 포함하는 유닛일 수 있다.

상기 내비게이션 기기(200)는, 석션 컵(suction cup)(254)을 사용하여 차량의 대시보드/창문 등에 고정될 수 있는, 암(252) 위에 있을 수 있다. 이러한 암(252)은 상기 내비게이션 기기(200)가 도킹될 수 있는 도킹 스테이션(docking station)의 일례이다. 상기 내비게이션 기기(200)는 도킹되거나, 그렇지 않으면, 예를 들어 상기 내비게이션 기기(200)를 상기 암(252)에 스냅(snap)식으로 연결함으로써 상기 도킹 스테이션의 암(252)에 연결될 수 있다. 그 다음, 상기 내비게이션 기기(200)는 상기 암(252) 상에서 회전 가능할 수 있다. 상기 내비게이션 기기(200) 및 상기 도킹 스테이션 사이의 연결을 풀기 위해서, 예를 들어 상기 내비게이션 기기(200)상의 버튼(도시되지 않음)이 눌러질 수 있다. 상기 내비게이션 기기(200)를 도킹 스테이션에 연결 및 분리하기 위한 다른 동등한 적절한 구성들은 당해 기술 분야의 통상의 기술자들에게 잘 알려져 있다.

설명된 실시예에서, 상기 내비게이션 기기의 프로세서(202)는 안테나에 의해 수신된 GPS 데이터를 수신하도록, 그리고 때때로, 상기 내비게이션 기기의 위치의 기록을 모으기 위해, 상기 GPS 데이터가 수신되었을 때의 타임스탬프와 함께, 상기 GPS 데이터를 상기 메모리(214) 내에 저장하도록 프로그래밍된다. 이렇게 저장된 각각의 데이터 기록은 GPS 위치(fix)로 간주될 수 있다 : 즉, 이는 상기 내비게이션 기기의 위치의 정점이며, 위도, 경도, 타임스탬프 및 정확도 보고(accuracy report)를 포함한다.

일실시예에서, 상기 데이터는 주로, 예를 들어 매 5 초마다, 주기적으로 저장된다. 당업자는 다른 주기들도 가능할 것이라는 것과, 그리고 데이터 해상도 및 메모리 용량 간에 균형이 존재한다는 것을 이해할 것이다; 즉, 데이터의 해상도가 더 많은 샘플들을 취함으로써 증가됨에 따라, 그 데이터를 보유하기 위해 더 많은 메모리가 요구된다. 그러나 다른 실시예들에서, 상기 해상도는 실질적으로 : 매 1초, 매 10초, 매 15초, 매 20초, 매 30 초, 매 45초, 매 1분, 매 2.5분(또는 실제로, 이러한 기간들 사이에 있는 기간) 일 수 있다. 따라서 상기 기기의 메모리 내에서, 어떤 시점에서의 상기 기기(200)의 소재의 기록이 구축된다. 일부 실시예들에서, 캡처된 데이터의 품질은 주기가 증가할수록 감소된다는 것이 발견될 수 있으며, 반면 성능 저하의 정도는 적어도 부분적으로 상기 내비게이션 기기(200)가 움직이는 속도에 의존할 것이라는 것이 발견될 수 있다. 이 때, 약 15초의 주기는 적당한 상한을 제공할 수 있다. 상기 내비게이션 기기(200)는 일반적으로 자신의 소재의 기록을 구축하도록 조정되는 반면, 일부 실시예들은 여정의 시작 또는 끝에서 미리 정해진 기간 및/또는 거리 동안 데이터를 기록하지 않는다. 이러한 방식은, 그/그녀의 집의 위치 및 자주 찾는 다른 목적지들을 보호할 가능성이 있기 때문에, 상기 내비게이션 기기의 사용자의 개인 정보를 보호하는 데 도움이 된다. 예를 들어, 상기 내비게이션 기기(200)는 대략 여정의 처음 5 분 동안, 그리고/또는 대략 여정의 처음 1 마일동안 데이터를 저장하지 않도록 조정될 수 있다.

다른 실시예들에서, GPS는 주기적으로 저장되지 않을 수 있으며, 미리 정해진 이벤트가 발생할 때 상기 메모리 내에 저장될 수 있다. 예를 들어, 상기 프로세서(202)는 상기 기기가 도로 교차점, 도로 구간의 변경 또는 이와 유사한 이벤트를 통과할 때 상기 GPS 데이터를 저장하도록 프로그래밍될 수 있다.

추가로, 상기 프로세서(202)는, 때때로, 상기 기기(200)의 소재들(whereabouts)(즉, GPS 데이터 및 타임스탬프)의 기록을 상기 서버(150)에 업로딩하도록 조정된다. 상기 내비게이션 기기(200)가, 상기 서버(150)에 상기 내비게이션 기기(200)를 연결시키는 영구적인, 또는 적어도 일반적으로 현존하는, 통신 채널(152)을 갖는 일부 실시예들에서, 상기 데이터의 업로딩은, 예를 들어 매 24 시간마다 한번일 수 있는, 주기로 발생한다. 당업자는 다른 주기들 또한 가능하다는 것과, 다른 주기들은 주로 다음의 주기들 중 임의의 것일 수 있다는 것을 이해할 것이다 : 15분, 30분, 1 시간 마다, 2 시간 마다, 5 시간마다, 12시간마다, 2일마다, 일주일마다, 또는 이들 사이의 임의의 시간. 실제로, 이러한 실시예들에서, 상기 프로세서(202)는 사실상 실시간으로 상기 소재들의 기록을 업로드하도록 조정될 수 있지만, 이는 필연적으로, 상기 데이터가 사실상 때때로 송신되고, 그 송신들 사이의 기간은 상대적으로 짧다는 것을 의미할 수 있으며, 그리고 이는 이로써, 더 정확하게 가상(pseudo) 실시간으로 여겨질 수 있다. 이러한 가상 실시간 실시예들에서, 상기 내비게이션 기기는 상기 메모리(214) 내에 및/또는 상기 포트에 삽입된 카드 상에 GPS 위치(fix)들 버퍼링하도록 조정될 수 있으며, 그리고 미리 정해진 개수가 저장될 때 이들을 송신하도록 조정될 수 있다. 상기 미리정해진 개수는 약 20, 36, 100, 200, 또는 그 사이의 임의의 숫자일 수 있다. 당업자는 상기 미리 정해진 개수가 상기 메모리(214)의 크기 또는 상기 포트(228) 내의 카드의 크기에 의해 부분적으로 좌우된다는 것을 이해할 것이다.

일반적으로 현존하는 통신 채널(152)을 갖지 않는 다른 실시예들에서, 상기 프로세서(202)는 통신 채널(152)이 형성될 때 상기 기록을 상기 서버(152)에 업로드하도록 조정될 수 있다. 이는, 예를 들어, 상기 내비게이션 기기(200)가 사용자 컴퓨터에 연결될 때 이루어질 수 있다. 또한, 이러한 실시예들에서, 상기 내비게이션 기기는 상기 메모리(214) 내에, 또는 상기 포트(228)에 삽입된 카드 상에 상기 GPS 위치들을 버퍼링하도록 조정될 수 있다. 상기 메모리(214) 또는 상기 포트 내의 카드(228)가 GPS 위치들로 가득찬다면, 상기 내비게이션 기기는 가장 오래된 GPS 위치들을 삭제하도록 조정되며, 이로써, 이는 선입선출(First in First Out; FIFO) 버퍼로 여겨질 수 있다.

설명된 실시예에서, 상기 소재들의 기록은 하나 이상의 추적 정보(trace)들을 포함하며, 각각의 추적 정보는 24 시간 동안의 상기 내비게이션 기기(200)의 움직임을 나타낸다. 각각의 24는 역일(calendar day)과 일치하도록 조정되지만, 다른 실시예들에서는 이런 경우일 필요가 없다.

일반적으로, 내비게이션 기기(200)의 사용자는 상기 기기들의 소재들의 기록이 상기 서버(150)에 업로드되는 것을 허락한다. 만약 허락이 없다면, 상기 서버(150)에 업로드되는 기록은 없다. 상기 내비게이션 기기 그 자체, 그리고/또는 상기 내비게이션이 연결되어 있는 컴퓨터는, 사용자에게 이러한 소재 기록의 사용에 대한 허락을 요청하도록 조정될 수 있다.

상기 서버(150)는 상기 기기의 소재들의 기록을 수신하도록 조정되고, 그리고 처리를 위해 이것을 상기 대용량 데이터 저장 기기(160) 내에 저장하도록 조정된다. 따라서 시간이 흐름에 따라, 상기 대용량 데이터 저장 기기(160)는 업로드된 데이터를 갖는 내비게이션 기기들의 소재들에 대한 다수의 기록들을 축적한다.

상술한 바와 같이, 상기 대용량 데이터 저장 기기(160)는 지도 데이터를 포함한다. 이러한 지도 데이터는 도로 구간(road segment)들의 위치에 대한 정보, 관심 포인트들에 대한 정보, 그리고 일반적으로 지도에서 발견되는 이와 유사한 정보를 제공한다.

이제 도 5 및 도 6을 참조하여 본 발명의 실시예가 설명될 것이다. 이러한 방법의 단계들은 내비게이션 기기에 의해, 예를 들어 휴대용 내비게이션 기기(portable navigation device; PND), 서버, 또는 이들의 조합에 의해, 수행될 수 있다.

도 5에 설명된 본 발명의 방법의 일실시예에 따르면, 제1 위치 및 제2 위치 사이에서 연장하는 제1 경로가 획득된다(단계 300). 상기 경로는 전자 지도에 의해 커버되는 영역 내의 경로이며, 상기 전자 지도는 상기 전자 지도에 의해 커버되는 영역 내에 있는 가항 네트워크(navigable network)의 가항 구간들을 나타내는 다수의 구간들을 갖고, 각각의 구간은 자신과 연관된 하나 이상의 속성들을 나타내는 속성 데이터를 갖는다. 예를 들어, 속성 데이터는 구간의 교통 흐름 속도(flow speed), 구간 길이, 구간의 곡률, 경사도, 구간을 통과하기 위한 연료 소비량, 주어진 기간 동안 상기 구간을 통과하기 위한 예상 시간 등과 같이 해당 분야에 공지된 것들을 나타낼 수 있다. 각각의 구간은 하나 이상의 속성들을 나타내는 데이터와 연관될 수 있다.

예시적 제1 경로(400)가 도 6에 도시되어 있다. 상기 제1 경로(400)는 제1 위치(A) 및 제2 위치(B) 사이에서 연장한다. 이러한 제1 경로는 "메인" 경로이며, 메인 경로와 관련하여, 대안 경로가 발견되는 것이 바람직하다.

상기 미리 정해진 경로를 따라 길 안내를 하는 동안 대안 경로가 생성되는 일예시적 실시예에서, 상기 제1 경로는 현재 길 안내되고 있는 미리 정해진 경로의 나머지이며, 상기 제1 위치(A)는 상기 경로를 따르는 현재 위치이며, 상기 제2 위치(B)는 상기 미리 정해진 경로의 목적지이다. 따라서 상기 제1 경로를 획득하는 단계는, 길 안내되고 있는 상기 미리 정해진 경로의 나머지를 나타내는 정보를 획득하는 단계를 포함한다. 이러한 실시예들에서, "도중에(en route)" 대안 경로가 제공될 수 있다. 이 경우, 대안 경로 생성의 개시는 사용자 입력에 응답하여 이루어질 수 있거나, 또는 자동적으로 트리거링될 수 있어서, 예를 들어 사용자에게 그들의 목적지(또는 이들 보다 앞에 있는 위치)에 도달하기 위한 다른 옵션들을 제공할 수 있다.

경로를 따른 길 안내가 발생하기 전에 대안 경로가 생성되는 또 다른 예시적 실시예에서, 예를 들어 이로써 사용자는 그들이 출발하기 전에 메인 경로를 따를지 또는 대안 경로를 따를지 여부를 선택할 수 있는 예시적 실시예에서, 상기 제1 경로를 획득하는 단계는, 상기 제1 경로의 시작점인 상기 제1 위치(A) 및 상기 경로의 목적지인 상기 제2 위치(B) 사이의 상기 제1 경로(400)를 생성하는 단계를 포함한다. 상기 제1 경로는 당업계에 공지된 바와 같은 라우팅 엔진(routing engine)에 의해 생성되는 최소 비용 경로(a least cost route)일 수 있다. 상기 경로는 적절한 비용 함수를 사용하여 생성될 수 있다. 상기 경로를 제공하기 위해 최소화된 비용은, 상기 생성된 최소 비용 경로가 가장 빠른 경로, 가장 짧은 경로, 가장 환경 친화적인 경로 등일 수 있도록 적절하게 선택될 수 있다.

참조번호 302의 단계에 따르면, 상기 제1 경로(400)의 중앙 부분이 한정된다. 상기 중앙 부분은 상기 제1 위치(A) 및 상기 제2 위치(B) 사이에서 상기 제1 경로(400)의 길이를 따른 중앙 지점(D)에 대해 센터링된다. 상기 중앙 부분은 상기 제1 위치(A) 및 상기 제2 위치(B) 사이의 거리에 기초해 결정되는, 상기 제1 경로(400)를 따르는 범위(extent)를 갖는다. 상기 중앙 부분의 범위를 결정하는데 사용된 A 및 B 사이의 거리는 상기 제1 경로를 따라 측정되는 거리일 수 있지만, 대안적으로 상기 제1 위치(A) 및 상기 제2 위치(B) 사이의 직선 길이가 사용될 수 있음이 예상된다. 상기 제1 경로의 길이를 따르는 상기 중앙부의 상대적 범위는 상기 제1 위치(A) 및 상기 제2 위치(B) 사이의 거리와 반비례 관계에 있다. 이는 상기 중앙부가 연장하는 상기 제1 경로(400)의 길이의 비율을, 상기 A 및 B 사이의 거리에 반비례하도록 선택함으로써 달성될 수 있다. 이러한 반비례 관계는, A 및 B 사이의 거리가 증가함에 따라, 즉 상기 제1 경로의 길이가 증가함에 따라, 상기 제1 경로를 따르는 상기 중앙부의 상대적 범위가 감소한다는 것을 말한다. 이에 따라, 더 짧은 제1 경로들에 대한 중앙부는, 더 긴 제1 경로들에 대한 경우들 보다, 상기 제1 경로에 대해 상대적으로 더 큰 범위를 갖도록 한정될 것이다. 상기 A 및 B 사이의 거리는 (예를 들어 A 및 B 사이에서 연장하는 제1 경로의 길이의 백분율 같은) 그 거리에 대한 중앙부의 상대적 범위를 제공하기 위한 함수에 대한 입력일 수 있으며, 이 경우, 상기 함수는 상기 A 및 B 사이의 거리, 그리고 정해진 상대적 범위 간의 반비례 관계를 정의한다.

도 6은 상기 제1 경로(400)에 대해 한정된 상기 중앙 부분(403)을 도시한다. 상기 중앙 부분(403)은 상기 제1 경로(400)의 굵은 부분으로 도시되어 있다. 상기 중앙 부분(403)은 점 C 및 점 E 사이에서 한정되며, 이 때, 상기 점 C 및 점 E는 상기 제1 경로(400)의 중앙 지점(D)으로부터 등거리에 있다. 이로써, 상기 중앙 부분은 상기 중앙 지점(D)에 중심을 두게 된다. 점 C 및 점 E 사이에 있는 상기 중앙 부분(403)의 길이는, 상기 중앙 부분(403)이, 상기 A 및 B 사이의 거리를 사용하여 결정된 상기 제1 경로(400)의 비율을 따라 연장하는 것과 같으며, 상기 제1 경로를 따르는 상기 중앙 부분(403)의 상대적 범위는 상기 A 및 B 사이의 거리와 반비례 관계에 있다. A 및 B 사이의 거리가 더 길었다면, 상기 경로를 따르는 상기 중앙 부분(403)의 상대적 범위는 더 작았을 것이다.

단계 304에 따르면, 상기 제1 경로(400)의 상기 중앙 부분을 형성하는 이러한 가항 구간들(navigable segments)이 식별된다. 이는 전체가 상기 중앙 부분에 포함되는 가항 구간들을 포함할 것이며, 그리고 상기 중앙 부분에 오직 부분적으로만 포함되는 임의의 가항 구간들을 포함하거나 포함하지 않을 수 있다. 이와 관련하여, 이러한 구간들을 포함할지 또는 배제할지에 대한 선택이 이루어질 수 있으며, 이는 구간이 상기 영역 내에 포함되는 정도에 대한 고려를 포함하거나 포함하지 않을 수 있다.

단계 306에 따르면, 상기 식별된 구간들에 대해 비용 불이익(cost penalty)이 적용되며, 이로써 상기 구간들은 상기 가항 네트워크의 가항 구간들을 통과하는 비용에 기초한 최소 비용 경로 생성 과정에서, 다른 경우들 보다 불리하게 취급될 것이다. 상기 경로 생성 과정에서 가항 구간을 통과하는 것과 관련된 비용은 비용 함수를 사용하여 결정되며, 그리고 상기 구간과 연관된 속성(들) 중 적어도 일부에 기초한다. 구간 통과 비용을 결정할 때 고려되는 속성 또는 속성들의 선택은 상기 경로를 결정하는데 사용되는 상기 라우팅 엔진의 작업에 따라, 그리고 예를 들어 상기 라우팅 엔진의 설정들에 따라, 달라질 수 있다. 고려될 수 있는 속성들의 예들은 구간의 교통 흐름 속도, 구간 통과 시간, 구간을 통과하기 위한 연료 소비량, 구간의 곡률, 구간의 길이 등을 포함한다. 예를 들어, 상기 라우팅 엔진이 주행 시간을 최소화시킴으로써 가장 빠른 경로를 결정하는 경우, 상기 속성은 구간 통과 시간일 수 있다.

본 발명에 따르면, 상기 식별된 가항 구간들의 속성 데이터에 기초하여 상기 구간(들)에 대한 비용이 결정되었을 경우 보다 더 높은 비용을 상기 구간(들)에 할당함으로써, 상기 식별된 가항 구간들에 비용 불이익이 적용된다. 이런 방식으로 상기 구간(들)에 비용 불이익을 적용함으로써, 상기 가항 네트워크를 통해 최소 비용 경로가 생성될 때 상기 구간(들)은 덜 유리하게 취급될 것이다. 이는 비용 함수를 사용하여 달성될 수 있다.

단계 308에서, 상기 제1 위치(A) 및 상기 제2 위치(B) 사이에서 대안 경로가 생성된다. 이는 가항 구간들의 네트워크에 걸친 최소 비용 경로를 결정하는 비용 함수를 사용하여 대안 경로를 결정하는 (예를 들어, PND의 또는 서버의) 라우팅 엔진에 의해 수행될 수 있다. 상기 경로의 결정은 상기 네트워크의 가항 구간들을 통과하는 비용에 기초할 것이며, 또한, 상기 경로의 결정은 상기 식별된 가항 구간들이 상기 제1 경로의 중앙 부분에 포함된다는 이유로 단계 306에서 상기 식별된 가항 구간(들)에 적용된 상기 비용 불이익을 고려할 것이다.

이러한 방식으로, 상기 경로 결정은, 상기 제1 경로의 중앙 부분(403)의 일부를 형성하는 가항 구간들 보다, 상기 제1 경로의 중앙 부분(403)의 일부를 형성하지 않는 가항 구간들을 선호하는 경향이 있을 것이며, 생성되는 대안 경로가 상기 제1 경로의 중앙 부분으로부터 멀리 떨어지도록 밀어낸다. 그러나 상기 중앙 부분의 구간(들)은 그것들이 대안 경로에 포함되는 것에 대해 덜 선호되도록 만들기 위해 불이익이 가해지는 것일 뿐이다. 상기 중앙 부분의 구간(들)은 상기 경로 내에 포함되는 것이 완전히 막아지도록 차단되지 않는다. 이는 더 안정적인 라우팅 프로세스를 제공할 수 있는 것으로 밝혀졌다. 뿐만 아니라, 이와 달리 상기 구간이 (예를 들어 자신의 속성들로 인해) 더 적은 비용과 연관된다면, 심지어 비용 불이익이 적용된 후에도 더 적은 비용과 연관된다면, 식별된 가항 구간은 상기 최소 비용 대안 경로가 생성될 때 불이익이 가해지지 않았던 대안 구간보다 여전히 더 유리할 것이다. 유리하게는, 변경된 속성 데이터가 구간들에게 불이익을 가하는 정도는 상기 제1 위치(A) 및 상기 제2 위치(B) 사이의 거리와 반비례 관계에 있도록 선택되며, 이로써, 상기 중앙 부분의 구간들은 더 짧은 경로들에 대해 더 많은 불이익이 가해질 것이며, 더 긴 경로들에 대해 더 적은 불이익이 가해질 것이다.

상기 중앙 부분의 상대 범위가 A 및 B 사이의 거리(예를 들어, 상기 제1 경로(400)의 길이)에 기초함에 따라, 생성된 대안 경로는 더 긴 경로 보다 더 짧은 경로의 길이의 대부분으로부터 멀어질 것이며, 이로써, 그 결과 생성된 대안 경로는 더 긴 경로들에 대해서보다 더 짧은 경로들에 대해서 초기 제1 경로와 상대적으로 더 상이할 것이다. 이는, 운전자들이 더 짧은 메인 경로와 더 상당히 다른 대안 경로를 원할 것이라는 사실을 인식한다. 더 긴 메인 경로들에 대해, 그 대안 경로가, 자신의 길이의 대부분에 대해 상기 제1 경로와 일치하는 것이 허용될 수 있어, 예를 들어 상기 경로의 고속도로 부분들이 대안으로 유지되도록 보장할 수 있다.

대안 경로가 생성되면, 상기 대안 경로의 상기 제1 경로(400)와의 유사성은 공유된 경로 부분들의 길이 비율을 고려하여 평가될 수 있다. 공유 부분들의 비율이 주어진 임계값을 초과한다면, 생성된 대안 경로는 상기 제1 경로와 너무 유사하여 받아들여질 수 없는 것으로 간주될 수 있다. 그 후, 단계 306 및 단계 308이 반복될 수 있으며, 이 때, 상기 제1 경로(400)의 중앙 부분의 식별된 가항 요소들은, 경로 생성이 수행될 때, 그것들이 처음 불이익이 가해졌을 때의 경우 보다, 훨씬 더 불리하도록 불이익이 더 가해진다. 그 후, 다른 대안 경로가 생성될 수 있다. 상기 제1 경로의 상기 중앙 부분의 구간들에 불이익을 더 가하는 것의 효과는, 생성된 대안 경로가 상기 제1 경로의 상기 중앙 부분으로부터 멀어지도록 더 강하게 밀어야 하며, 이로써, 그 결과물인 대안 경로는 초기 생성된 대안 경로의 경우보다 상기 제1 경로와 더 많이 달라야 한다.

생성된 추가 대안 경로의 상기 제1 경로와의 유사성은 그것이 받아들여질 수 있는지 여부를 판단하기 위해 평가될 수 있다. 추가 대안 경로가 받아들여질 수 없다면, 또 다시 단계306 및 단계308이 반복될 수 있으며, 상기 중앙 부분의 구간들에게 또 다른 추가 불이익이 가해지며, 그 결과물인 대안 경로는 상기 제1 경로와의 유사성에 대해 평가받는다. 이러한 순환은, 상기 제1 경로와 필요한 정도로 상이한 허용 가능한 대안 경로가 생성될 때까지, 또는 처음에 허용 가능한 대안 경로가 발견되지 않는다면 미리 정해진 횟수의 시도들 동안, 반복될 수 있다. 후자의 경우, 사용자는 대안 경로를 찾을 수 없다고 통지받을 수 있다.

대안 경로가 발견되면, 적절하다면, 유사성 평가가 수행된 경우 "허용가능"하다고 간주된 대안 경로가 발견되면, 상기 경로는 사용자에게 출력될 수 있다. 상기 경로는, 예를 들어 PND를 통해, 사용자에게 디스플레이될 수 있다. 이는, 사용자가 상기 대안 경로를 선택할지 또는 상기 제1 경로를 계속할지 여부를 결정할 수 있게 할 수 있다. 대안 경로를 따라야하는 경우, 상기 대안 경로를 따르기 위해 내비게이션 명령들의 세트가 생성될 수 있다. 대안적으로, 또는 추가적으로, 상기 대안 경로는 저장될 수 있다.

본 발명은 하나의 대안 경로를 제공하는 것에 제한되지 않는다. 단계 308에서 대안 경로가 제공되면, 그리고 적절한 경우, 유사성 평가 후 허용가능하다고 간주된 경우, 추가 대안 경로가 생성될 수 있다. 이 방법은 단계 302 내지 단계 308을 반복하는 단계를 포함할 것이지만, 이 경우, 상기 제1 경로가 아닌 상기 대안 경로의 중앙 부분을 한정한다. 이는 상기 제1 경로에 대해 설명된 것과 동일한 방식으로 수행될 수 있으며, 이 때, 상기 중앙 부분의 범위는 다시 한번 상기 제1 위치(A) 및 제2 위치(B) 사이의 거리에 기초하며, 상기 중앙 부분의 상대적 범위는 상기 A 및 B 사이의 거리와 반비례 관계에 있다. 상기 A 및 B 사이의 거리는 직선거리로서 측정될 수 있거나, 또는 상기 제1 경로를 따라 또는 생성된 상기 제1 대안 경로를 따라 측정될 수 있다. 그 다음, 상기 대안 경로의 한정된 중앙 부분의 일부를 형성하는 가항 구간들은 상기 제1 경로와 관련하여 설명된 바와 같이, 경로 생성을 위해 불이익이 가해질 수 있다. 그 후, 적용된 불이익들(penalties)을 고려하여, 가항 구간들의 네트워크를 통해 경로(예를 들어, 최소 비용 경로)가 생성될 수 있다. 이는 추가 대안 경로가 생성되도록 야기할 것이다. 그 후, 이러한 과정은 또 다른 대안 경로를 생성하기 위해 반복될 수 있으며, 이번엔, 상기 제1 위치(A) 및 상기 제2 위치(B) 사이의 측정된 거리에 기초하여 상기 추가 대안 경로의 중앙 부분을 한정하며, 상기 또 다른 대안 경로를 생성하기 전에, 상기 경로 생성을 위해 상기 중앙 부분의 식별된 구간들에게 불이익을 추가로 가한다. 더 많은 대안 경로들이 필요한 경우, 이러한 과정은 여러번 반복될 수 있다. 생성된 대안 경로들 중 임의의 경로 또는 모든 경로들이 사용자에게 출력될 수 있다.

(임의의 첨부된 청구항들, 요약서 및 도면들을 포함한) 본 명세서에 개시된 모든 특징들, 그리고/또는 그렇게 개시된 임의의 방법 또는 과정의 모든 단계들은, 그러한 특징들 및/또는 단계들의 적어도 일부가 상호 배타적인 조합들을 제외하고, 임의의 조합으로 결합될 수 있다.

(임의의 첨부된 청구항들, 요약서 및 도면들을 포함한) 본 명세서에 개시된 각각의 특징들은, 명시적으로 달리 언급되어 있지 않은 한, 동일, 등가 또는 유사 목적을 제공하는 대안적인 특징들로 대체될 수 있다. 따라서 명시적으로 달리 언급되어 있지 않은 한, 개시된 각각의 특징은 단지 일반적인 일련의 등가 또는 유사 특징들의 일례일 뿐이다.

본 발명은 임의의 전술한 실시예들의 상세한 설명에 한정되지 않는다. 본 발명은, (임의의 첨부된 청구항들, 요약서 및 도면들을 포함한) 본 명세서에 개시된 특징들 중 임의의 신규한 특징, 또는 개시된 특징들의 임의의 신규한 조합, 또는 그와 같이 개시된 임의의 방법 또는 과정의 단계들의 임의의 신규한 단계 또는 임의의 신규한 조합까지 확장된다. 청구항들은 단지 전술한 실시예들만을 포함하는 것으로 해석되어서는 안 되고, 청구항들의 범위 내에 속하는 임의의 실시예들도 포함하는 것으로 해석되어야 한다.

Claims (20)

1. 전자 지도에 의해 커버되는 영역 내에 있는 경로들을 생성하는 방법으로서,
   상기 지도는 상기 전자 지도에 의해 커버되는 영역 내에 있는 가항 네트워크(navigable network)의 가항 구간들을 나타내는 다수의 구간들을 포함하며,
   상기 방법은 :
   상기 영역 내에서, 제1 위치 및 제2 위치 사이의 제1 경로를 획득하는 단계;
   상기 제1 경로의 중앙 부분을 한정하는 단계로서, 상기 중앙 부분은 상기 제1 위치 및 상기 제2 위치 사이의 거리에 기초하여 결정되는, 상기 제1 경로를 따르는 범위(extent)를 가지며, 상기 중앙 부분은 상기 제1 위치와 상기 제2 위치 사이에서 상기 제1 경로의 길이를 따른 중앙 지점에 대해 센터링되며, 상기 제1 경로를 따르는 상기 중앙 부분의 상대적 범위는 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있는, 단계;
   상기 제1 경로를 따르는 상기 한정된 중앙 부분을 형성하는 하나 이상의 가항 구간들을 식별하는 단계; 및
   라우팅 알고리즘을 사용하여 상기 제1 위치와 상기 제2 위치 사이의 다수의 구간들을 포함하는 대안 경로를 생성하는 단계로서, 상기 라우팅 알고리즘에서, 상기 제1 경로의 중앙 부분의 하나 이상의 식별된 구간들에 불이익이 가해져서 상기 하나 이상의 식별된 구간들 각각은 생성된 대안 경로에 포함되는 것에 대해 덜 유리하게 되며, 상기 대안 경로는 상기 제1 경로에 대한 대안 경로인, 단계를 포함하는, 경로 생성 방법.
2. 청구항 1에 있어서,
   상기 제1 경로를 획득하는 단계는 시작점 및 목적지 사이의 경로를 생성하는 단계를 포함하며,
   상기 제1 경로는 상기 생성된 경로에 해당하며,
   상기 제1 위치 및 상기 제2 위치는 각각 상기 생성된 경로의 시작점 및 목적지인, 경로 생성 방법.
3. 청구항 1에 있어서,
   상기 제1 경로는 길 안내가 되고 있는 미리 정해진 경로의 나머지에 해당하는, 경로 생성 방법.
4. 청구항 1 내지 청구항 3 중 어느 한 항에 있어서,
   상기 제1 위치 및 상기 제2 위치 사이의 거리는 상기 제1 위치 및 상기 제2 위치 사이의 상기 경로를 따라 측정되는, 경로 생성 방법.
5. 청구항 1 내지 청구항 3 중 어느 한 항에 있어서,
   상기 식별된 가항 구간 또는 각각의 식별된 가항 구간은 상기 가항 구간에 비용 불이익(cost penalty)을 적용함으로써 불이익을 받으며, 이로써, 상기 가항 구간은 상기 네트워크의 가항 구간들을 통과하는 것의 미리 정해진 비용에 기초하여 생성된, 상기 네트워크를 통한 상기 대안 경로에 포함되는 것에 대해 덜 유리하게 될 것인, 경로 생성 방법.
6. 청구항 5에 있어서,
   상기 식별된 가항 구간 또는 각각의 식별된 가항 구간은 상기 가항 구간에 비용 불이익을 적용함으로써 불이익을 받으며, 상기 비용 불이익은 상기 가항 구간을 통과하는 비용을 증가시키며, 이로써, 상기 가항 구간은 상기 네트워크를 통해 생성된 최소 비용 경로에 포함되는 것에 대해 덜 유리하게 될 것인, 경로 생성 방법.
7. 청구항 5에 있어서,
   상기 가항 네트워크의 상기 가항 구간들 각각은 자신과 연관된 하나 이상의 속성들을 나타내는 속성 데이터와 연관되며,
   가항 구간을 통과하는 비용은 상기 가항 구간과 연관된 속성 데이터에 적어도 부분적으로 기초하며,
   상기 방법은 : 상기 식별된 가항 구간 또는 각각의 식별된 가항 구간에 비용 불이익을 적용함으로써 상기 가항 구간에 불이익을 가하여, 상기 가항 구간 또는 각각의 가항 구간이, 상기 구간과 연관된 상기 속성 데이터에 기초하여 결정되었을 비용과 상이한 비용과 연관되게 하는 단계를 포함하는, 경로 생성 방법.
8. 청구항 1 내지 청구항 3 중 어느 한 항에 있어서,
   상기 방법은 :
   상기 제1 경로의 중앙 부분을 한정하는 단계 전에, 상기 제1 위치 및 상기 제2 위치 사이의 거리를, 입력 거리로 작동하는 함수에 입력하여, 그 거리에 대한 상기 제1 경로를 따르는 중앙부의 상대적 범위인 출력을 제공하는 단계를 포함하며,
   상기 함수는 제1 위치 및 제2 위치 사이의 임의의 입력 거리에 대해, 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있는 제1 경로를 따르는 상기 중앙 부분에 대한 상대적 범위 출력을 제공하도록 조정되며, 상기 제1 경로는 상기 제1 위치 및 상기 제2 위치 사이에서 연장하는, 경로 생성 방법.
9. 청구항 1 내지 청구항 3 중 어느 한 항에 있어서,
   상기 제1 경로의 중앙 부분을 한정하는 단계는 :
   상기 제1 위치 및 상기 제2 위치 사이에서 상기 제1 경로의 길이를 따른 중앙 지점을 식별하는 단계; 및
   상기 중앙 지점 주위에서 상기 중앙 부분을 한정하는 단계를 더 포함하는, 경로 생성 방법.
10. 청구항 1 내지 청구항 3 중 어느 한 항에 있어서,
    상기 방법은 상기 대안 경로를 생성한 후에 :
    상기 생성된 대안 경로의 중앙 부분을 한정함으로써 추가 대안 경로를 생성하는 단계로서, 상기 생성된 대안 경로의 중앙 부분은 상기 제1 위치 및 상기 제2 위치 사이의 거리에 기초하여 결정되는 상기 제1 경로를 따르는 범위를 가지며 상기 제1 위치 및 상기 제2 위치 사이에서 상기 대안 경로의 길이를 따른 중앙 지점에 대해 센터링되며, 상기 제1 경로를 따르는 상기 생성된 대안 경로의 상기 중앙 부분의 상대적 범위는 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있는, 단계;
    상기 대안 경로를 따르는 상기 생성된 대안 경로의 상기 한정된 중앙 부분을 형성하는 하나 이상의 가항 구간들을 식별하는 단계; 및
    라우팅 알고리즘을 사용하여 상기 제1 위치와 상기 제2 위치 사이의 다수의 구간들을 포함하는 상기 추가 대안 경로를 생성하는 단계로서, 상기 라우팅 알고리즘에서, 상기 대안 경로의 중앙 부분의 하나 이상의 식별된 구간들에 불이익이 가해져서 상기 하나 이상의 식별된 구간들 각각은 생성된 추가 대안 경로에 포함되는 것에 대해 덜 유리하게 되며, 상기 추가 대안 경로는 상기 대안 경로에 대한 대안 경로인, 단계를 포함하는, 경로 생성 방법.
11. 청구항 1 내지 청구항 3 중 어느 한 항에 있어서,
    상기 방법은 :
    상기 대안 경로를 생성한 후에, 생성된 대안 경로 또는 상기 생성된 대안 경로의 상기 제1 경로와의 유사성을 평가함으로써, 상기 생성된 대안 경로가 허용 가능한 대안 경로인지의 여부를 판단하는 단계를 더 포함하며,
    상기 평가는 상기 제1 경로와 공유된, 상기 대안 경로의 비율을 참고하여 수행되는, 경로 생성 방법.
12. 청구항 11에 있어서,
    상기 생성된 대안 경로가 허용 가능한 대안 경로인지의 여부를 판단하는 단계는 :
    상기 대안 경로의 상기 제1 경로와의 유사성이 주어진 임계값 아래에 있을 때, 상기 대안 경로가 허용가능하다고 판단하는 단계를 더 포함하는, 경로 생성 방법.
13. 청구항 11에 있어서,
    상기 생성된 대안 경로가 허용 가능한 대안 경로인지의 여부를 판단하는 단계는 :
    상기 생성된 대안 경로와 상기 제1 경로의 유사도가 특정 임계값보다 높아서 상기 대안 경로가 허용 가능하지 않은 것으로 간주된다면, 라우팅 알고리즘을 사용하여 상기 제1 위치 및 상기 제2 위치 사이의 다수의 구간들을 포함하는 또 다른 대안 경로를 생성하는 단계로서, 상기 라우팅 알고리즘에서 상기 제1 경로의 중앙 부분의 하나 이상의 식별된 구간들에 추가 불이익이 가해져서 상기 하나 이상의 식별된 구간들 각각은 생성된 대안 경로에 포함되는 것에 대해 덜 유리하게 되는, 단계를 포함하는, 경로 생성 방법.
14. 청구항 1 내지 청구항 3 중 어느 한 항에 있어서,
    상기 대안 경로를 생성하는 단계 후에, 사용자에게 출력하기 위해 대안 경로 또는 상기 대안 경로를 제공하는 단계를 더 포함하는, 경로 생성 방법.
15. 청구항 1 내지 청구항 3 중 어느 한 항에 있어서,
    상기 대안 경로를 생성하는 단계 후에, 대안 경로 또는 상기 대안 경로를 따라 사용자를 안내하기 위한 내비게이션 명령들의 세트를 제공하는 단계를 더 포함하는, 경로 생성 방법.
16. 전자 지도에 의해 커버되는 영역 내에 있는 경로들을 생성하는 시스템으로서,
    상기 지도는 상기 전자 지도에 의해 커버되는 영역 내에 있는 가항 네트워크(navigable network)의 가항 구간들을 나타내는 다수의 구간들을 포함하며,
    상기 시스템은 :
    상기 영역 내에서, 제1 위치 및 제2 위치 사이의 제1 경로를 획득하는 수단;
    상기 제1 경로의 중앙 부분을 한정하는 수단으로서, 상기 중앙 부분은 상기 제1 위치 및 상기 제2 위치 사이의 거리에 기초하여 결정되는, 상기 제1 경로를 따르는 범위를 가지며, 상기 중앙 부분은 상기 제1 위치와 상기 제2 위치 사이에서 상기 제1 경로의 길이를 따른 중앙 지점에 대해 센터링되며, 상기 제1 경로를 따르는 상기 중앙 부분의 상대적 범위는 상기 제1 위치 및 상기 제2 위치 사이의 거리와 반비례 관계에 있는, 한정 수단;
    상기 제1 경로를 따르는 상기 한정된 중앙 부분을 형성하는 하나 이상의 가항 구간들을 식별하는 수단;
    라우팅 알고리즘을 사용하여 상기 제1 위치와 상기 제2 위치 사이의 다수의 구간들을 포함하는 대안 경로를 생성하는 수단으로서, 상기 라우팅 알고리즘에서, 상기 제1 경로의 중앙 부분의 하나 이상의 식별된 구간들에 불이익이 가해져서 상기 하나 이상의 식별된 구간들 각각은 생성된 대안 경로에 포함되는 것에 대해 덜 유리하게 되며, 상기 대안 경로는 상기 제1 경로에 대한 대안 경로인, 수단을 포함하는, 경로 생성 시스템.
17. 청구항 16에 있어서,
    상기 시스템은 내비게이션 기기인, 경로 생성 시스템.
18. 청구항 16에 있어서,
    상기 시스템은 서버인, 경로 생성 시스템.
19. 컴퓨터 프로그램 제품이 저장된 컴퓨터 판독가능 매체에 있어서,
    상기 컴퓨터 프로그램 제품은 :
    기계에 의해 판독될 때, 상기 기계가 청구항 1 내지 청구항 3 중 어느 한 항의 방법에 따라 작동하도록 유발하는 명령들을 포함하는, 컴퓨터 판독가능 매체.
20. 삭제

Images