导航系统的路径搜索方法和导航系统转让专利
申请号 : CN200580001328.4
文献号 : CN1898531B
文献日 : 2010-06-09
发明人 : 佐野克己 , 当摩和弘
申请人 : 株式会社查纳位资讯情报
摘要 :
可以缩短从设置目的地开始到展现推荐路径为止的时限的导航系统。车载导航系统配备有存储链接信息的存储设备(3)和处理器(1)。使得处理器(1)执行以下处理：检测车辆的停止；检测车辆的当前位置，如果检测到车辆停止或者如果导航系统本身启动的话；通过使用链接信息，搜索从检测的当前位置到预定距离范围内的交叉口的路径；接受设置的目的地；以及通过使用链接信息，搜索从该交叉口到该目的地的路径，如果接受设置的目的地的话，并且指定搜索的从当前位置到该交叉口的路径和搜索的从该交叉口到该目的地的路径组成的路径作为推荐路径。
权利要求 :
1.通过使用链接信息搜索到达目的地的推荐路径的车载导航系统中的路径搜索方法，其特征在于该导航系统执行以下步骤：从存储装置获取网格大小列表，并将该网格大小列表存储在RAM中；
检测车辆的停止；
在导航系统本身启动的情况下，检测车辆的当前位置；
确定当前位置的预定距离范围内包含的网格；
通过参阅所存储的网格大小列表，获取所确定的网格的链接信息；
通过使用所述链接信息，搜索从检测到的当前位置到预定距离范围内的交叉口的路径；
接受设置的目的地；以及
在接受设置的目的地的情况下，通过使用链接信息，搜索从该交叉口到该目的地的路径，并且指定搜索的从当前位置到该交叉口的路径和搜索的从该交叉口到该目的地的路径组成的路径作为推荐路径。
2.通过使用链接信息搜索到达目的地的推荐路径的车载导航系统中的路径搜索方法，其中将显示设备和该导航系统连接起来；并且其中该导航系统执行以下步骤：
从存储装置获取网格大小列表，并将该网格大小列表存储在RAM中；
检测车辆的当前位置；
确定当前位置的预定距离范围内包含的网格；
通过参阅所存储的网格大小列表，获取所确定的网格的链接信息；
接受来自用户的目的地的输入；
在该显示设备上显示一个画面以接受来自用户的用于证实接受的目的地是否有错的确认；
在接受来自该用户的表示目的地正确的数据的情况下，设置目的地；
在接受该目的地的输入的情况下，在设置该目的地之前，通过使用链接信息，搜索从检测的当前位置到接受的目的地的路径；以及在设置目的地的情况下，指定搜索的路径作为推荐路径。
3.通过使用链接信息搜索到达目的地的推荐路径的车载导航系统，包括：从存储装置获取网格大小列表，并将该网格大小列表存储在RAM中的装置；
检测车辆停止的装置；
在导航系统本身启动的情况下，检测车辆的当前位置的装置；
确定当前位置的预定距离范围内包含的网格的装置；
通过参阅所存储的网格大小列表，获取所确定的网格的链接信息的装置；
通过使用链接信息，搜索从检测的当前位置到预定距离范围内的交叉口的路径的装置；
接受设置的目的地的装置；以及
在接受设置的目的地的情况下，通过使用链接信息，搜索从该交叉口到该目的地的路径，并且指定搜索的从当前位置到该交叉口的路径和搜索的从该交叉口到该目的地的路径组成的路径作为推荐路径的装置。
4.通过使用链接信息搜索到达目的地的推荐路径的车载导航系统，包括：从存储装置获取网格大小列表，并将该网格大小列表存储在RAM中的装置；
检测车辆的当前位置的装置；
确定当前位置的预定距离范围内包含的网格的装置；
通过参阅所存储的网格大小列表，获取所确定的网格的链接信息的装置；
接受来自用户的目的地的输入的装置；
显示信息以接受来自用户的用于证实接受的目的地是否有错的确认的装置；
在接受来自该用户的表示该目的地正确的数据的情况下，设置目的地的装置；
在接受目的地的输入的情况下，在设置目的地之前，通过使用链接信息搜索从检测的当前位置到接受的目的地的路径的装置；以及在设置目的地的情况下，指定搜索的路径作为推荐路径的装置。
说明书 :
技术领域
本发明涉及导航系统，更具体地，涉及车载导航系统的路径搜索技术。
背景技术
已知的导航系统是这样的，它通过使用链接信息(例如，专利文献1)搜索从当前位置到目的地的推荐路径集合。正如专利文献1描述的那样，导航系统接受用户设置的目的地，然后开始搜索到达所设置的目的地的推荐路径。
专利文献1：日本专利公开出版号：H6-331379
专利文献1：日本专利公开出版号：H6-331379
发明内容
本发明要解决的问题
通过使用Dijkstra算法或类似算法，导航系统执行操作以搜索能够以最低成本到达目的地的路径。大部分的路径搜索操作通常需要很长的时间。另一方面，用户希望在设置目的地之后的短时间内展现推荐的路径。
然而，专利文献1已经考虑了简化用户设置目的地的操作，但是并未特别考虑在短时限内向用户展现到达设置的目的地的搜索的路径。
本发明是在考虑到上述背景下构思的，目的是提供能够缩短从设置目的地到展现推荐路径的时限的导航系统。
解决该问题的手段
为了解决上述问题，把本发明的一种方式应用于通过使用链接信息搜索到达目的地的推荐路径的车载导航系统中。该导航系统执行以下步骤：检测车辆的停止；检测车辆的当前位置，如果检测到车辆停止或如果导航系统本身启动的话；通过使用链接信息，搜索从检测的当前位置到预定距离范围内的交叉口的路径；接受设置的目的地；以及通过使用链接信息，搜索从该交叉口到该目的地的路径，如果接受设置的目的地的话；并且指定搜索的从当前位置到该交叉口的路径和搜索的从该交叉口到该目的地的路径组成的路径作为推荐路径。
为了解决上述问题，把本发明的另一种方式应用于通过使用链接信息搜索到达目的地的推荐路径的车载导航系统中。这里，将显示设备和该导航系统连接起来。
此外，该导航系统执行以下步骤：检测车辆的当前位置；接受来自用户的目的地的输入；在该显示设备上显示一个画面以接受来自用户的用于证实接受的目的地是否有错的确认；设置目的地，如果接受来自该用户的表示目的地正确的数据的话；在设置该目的地之前，通过使用链接信息，搜索从检测的当前位置到接受的目的地的路径，如果接受该目的地的输入的话；以及指定搜索的路径作为推荐路径，如果设置目的地的话。
本发明的效果
因此，根据本发明，导航系统检测车辆的当前位置，如果它检测到车辆停止或者如果导航系统本身启动的话，目的是确定所检测的当前位置的预定距离范围内的交叉口，从而搜索从当前位置到确定的交叉口的路径。而且，如果该导航系统接受设置的目的地，则它通过使用从所搜索的当前位置到该交叉口的路径，搜索到达该目的地的推荐路径。
因此，如果接受设置的目的地，则可以省略从当前位置到预定距离范围内的交叉口的路径的搜索操作，从而可以缩短用于搜索到达目的地的推荐路径的时限。
另一方面，按照本发明的另一种方式，如果接受来自用户的目的地的输入，则设置目的地，如果接受用于表示该目的地没有错误的该用户的确认数据的话。此外，根据本发明的另一种方式，在设置目的地之前，在接受目的地的输入时开始搜索到达该目的地的路径。
因此，假使设置目的地，则到达该目的地的推荐路径的搜索已经开始，所以可以缩短从最后设置目的地开始的搜索时限。
通过使用Dijkstra算法或类似算法，导航系统执行操作以搜索能够以最低成本到达目的地的路径。大部分的路径搜索操作通常需要很长的时间。另一方面，用户希望在设置目的地之后的短时间内展现推荐的路径。
然而，专利文献1已经考虑了简化用户设置目的地的操作，但是并未特别考虑在短时限内向用户展现到达设置的目的地的搜索的路径。
本发明是在考虑到上述背景下构思的，目的是提供能够缩短从设置目的地到展现推荐路径的时限的导航系统。
解决该问题的手段
为了解决上述问题，把本发明的一种方式应用于通过使用链接信息搜索到达目的地的推荐路径的车载导航系统中。该导航系统执行以下步骤：检测车辆的停止；检测车辆的当前位置，如果检测到车辆停止或如果导航系统本身启动的话；通过使用链接信息，搜索从检测的当前位置到预定距离范围内的交叉口的路径；接受设置的目的地；以及通过使用链接信息，搜索从该交叉口到该目的地的路径，如果接受设置的目的地的话；并且指定搜索的从当前位置到该交叉口的路径和搜索的从该交叉口到该目的地的路径组成的路径作为推荐路径。
为了解决上述问题，把本发明的另一种方式应用于通过使用链接信息搜索到达目的地的推荐路径的车载导航系统中。这里，将显示设备和该导航系统连接起来。
此外，该导航系统执行以下步骤：检测车辆的当前位置；接受来自用户的目的地的输入；在该显示设备上显示一个画面以接受来自用户的用于证实接受的目的地是否有错的确认；设置目的地，如果接受来自该用户的表示目的地正确的数据的话；在设置该目的地之前，通过使用链接信息，搜索从检测的当前位置到接受的目的地的路径，如果接受该目的地的输入的话；以及指定搜索的路径作为推荐路径，如果设置目的地的话。
本发明的效果
因此，根据本发明，导航系统检测车辆的当前位置，如果它检测到车辆停止或者如果导航系统本身启动的话，目的是确定所检测的当前位置的预定距离范围内的交叉口，从而搜索从当前位置到确定的交叉口的路径。而且，如果该导航系统接受设置的目的地，则它通过使用从所搜索的当前位置到该交叉口的路径，搜索到达该目的地的推荐路径。
因此，如果接受设置的目的地，则可以省略从当前位置到预定距离范围内的交叉口的路径的搜索操作，从而可以缩短用于搜索到达目的地的推荐路径的时限。
另一方面，按照本发明的另一种方式，如果接受来自用户的目的地的输入，则设置目的地，如果接受用于表示该目的地没有错误的该用户的确认数据的话。此外，根据本发明的另一种方式，在设置目的地之前，在接受目的地的输入时开始搜索到达该目的地的路径。
因此，假使设置目的地，则到达该目的地的推荐路径的搜索已经开始，所以可以缩短从最后设置目的地开始的搜索时限。
附图说明
图1是应用于本发明之某一实施方式的车载导航系统的示意配置图；
图2是用于模拟本发明之实施方式的存储设备中存储的地图数据的数据结构的示图；
图3是用于说明本发明之实施方式的处理器的功能配置的示图；
图4是用于表示本发明之实施方式的处理器的硬件配置的示图；
图5是用于说明启动本发明的实施方式的导航系统时执行的路径搜索过程的流程的示图；以及
图6是用于说明本发明的实施方式的导航系统检测到车辆停止时执行的路径搜索过程的示图。
参考号数和符号的说明
1-处理器，2-显示器，3-存储设备，4-语音输入/输出设备，5-输入设备，6-车轮速度传感器，7-地磁传感器，8-陀螺，9-GPS接收机，10-设置部件，11-当前位置检测部件，12-数据读取部件，13-地图匹配处理部件，14-路径搜索部件，15-路径导航部件，16-地图显示处理部件，17-图形处理部件，21-CPU，22-RAM，23-ROM，24-DMA，25-绘图控制器，26-VRAM，27-调色板，28-A/D转换器，29-SCI，30-PIO，以及31-计数器。
图2是用于模拟本发明之实施方式的存储设备中存储的地图数据的数据结构的示图；
图3是用于说明本发明之实施方式的处理器的功能配置的示图；
图4是用于表示本发明之实施方式的处理器的硬件配置的示图；
图5是用于说明启动本发明的实施方式的导航系统时执行的路径搜索过程的流程的示图；以及
图6是用于说明本发明的实施方式的导航系统检测到车辆停止时执行的路径搜索过程的示图。
参考号数和符号的说明
1-处理器，2-显示器，3-存储设备，4-语音输入/输出设备，5-输入设备，6-车轮速度传感器，7-地磁传感器，8-陀螺，9-GPS接收机，10-设置部件，11-当前位置检测部件，12-数据读取部件，13-地图匹配处理部件，14-路径搜索部件，15-路径导航部件，16-地图显示处理部件，17-图形处理部件，21-CPU，22-RAM，23-ROM，24-DMA，25-绘图控制器，26-VRAM，27-调色板，28-A/D转换器，29-SCI，30-PIO，以及31-计数器。
具体实施方式
以下参照附图描述本发明的实施方式。
首先，参照图1描述可以应用该实施方式的车载导航系统的示意配置。
图1是应用于本发明之实施方式的车载导航系统(以下简称为“导航系统”)的示意配置图。
如图所示，所配置的导航系统包括，处理器1，显示屏2，存储地图数据等的存储设备3，语音输入/输出设备4，输入设备5，车轮速度传感器6，地磁传感器7，陀螺8和GPS(全球定位系统)接收机9。
处理器1是一个主要部件，它处理为导航系统的用户提供的各种信息。例如，处理器1以各种传感器6-8以及GPS接收机9输出的信息为基础检测当前位置。处理器1从存储设备3中读取所检测的当前位置周围的地图数据，在显示屏2上用图形方式展现读取的地图数据并显示地图数据和表示当前位置的标记。
另一方面，在接受设置的目的地之前，处理器1预先搜索连接以下两点的路径：车辆的当前位置以及距离当前位置预定距离范围内的交叉口。此外，如果设置目的地，则处理器1通过使用到达预先搜索的预定范围内的交叉口的路径，搜索到达该目的地的推荐路径。以下详细描述用来搜索到达该目的地的推荐路径的过程。
显示屏2是用来显示处理器1创建的图形数据的一个部件，其配置可以是CRT、液晶显示器等。处理器1和显示屏2通常是用诸如RGB信号或NTSC(全国电视标准委员会)信号的信号S1连接的。
存储设备3是存储地图数据的部件，地图数据包括从日本岛的全图到日本国的城市、城镇和乡村的详细地图的众多比例的地图。例如，也可以使用DVD设备或硬盘设备作为存储设备3。
以下描述地图数据的配置。
图2是用于模拟存储设备3中存储的地图数据的数据结构的示图。
如图所示，把地图数据310分成网格区域，这是通过把地图分成许多块得到的。地图数据310包含用于标识网格区域的网格ID 311以及由该网格区域内的公路组成的各个链接的链接数据312。此外，在地图数据310中，每个网格ID 311均包含一个网格大小列表330，其中利用该网格ID定义的网格区域的链接数据312的数据量(即，网格大小)彼此相对应。
链接数据312包括：标识该链接的链接ID 3121；作为该链接的两个节点(起始节点和结束节点)的坐标信息3122；用来表示链接的公路是“收费公路”还是“普通公路”的公路种类3123；用于表示该链接的长度的链接长度信息3124；该链接的运行时间(或移动时间)信息3125；以及连接两个节点(即，起始节点和结束节点)的链接的链接ID(即，相连链接ID)3126。
当处理器1执行路径搜索时，使用网格大小列表330来确认要从存储设备3中读取的地图数据的数据量。具体地，当导航系统启动时，处理器1从存储设备3中读取并保存网格大小列表312。地图数据310还包含除公路之外的对应网格区域内包含的地图部分的信息(例如，名称、种类或坐标信息)。
以下回到图1继续该描述。语音输入/输出设备4把处理器1为用户创建的信息转换成语音信号并输出，识别用户发出的话音，并且向处理器1传送识别的内容。
输入设备5是用来接受用户的指令的部件，用户指令如选择各种功能或设置导航系统的目的地，其配置为硬件开关，如滚动键或比例变更键，操纵杆或粘贴在显示屏2上的触板。
导航系统使用传感器6-8以及GPS接收机9来检测当前位置。车轮速度传感器6测量与车轮的圆周的距离以及与测量的车轮转数的距离，并且根据成对车轮的转数测量车辆的转角。地磁传感器7检测地球的磁性，由此获得车辆的方位角。陀螺8是由光纤陀螺或振动陀螺组成的，目的是检测车辆转动的角度。GPS接收机9接收GPS卫星的信号，以测量车辆和三颗或更多颗GPS卫星之间的距离以及这些距离的变化率，由此检测车辆的当前位置，行使方向和行使方位。
随后，参照图3解释迄今描述的导航系统的处理器1的功能。
图3是用于解释该实施方式的处理器1的功能配置的示图。
如图所示，处理器1的配置包括，设置部件10，当前位置检测部件11，数据读取部件12，地图匹配处理部件13，路径搜索部件14，路径导航部件15，地图显示处理部件16，图形处理部件17和网格大小列表获取部件。
设置部件10接受用户输入到输入设备5或语音输入/输出设备4的需求，并且控制处理器1，所以可以执行与所需内容相对应的处理。例如，需要路径搜索部件14进行处理以搜索从当前位置到目的地的推荐路径，如果用户需要通过输入设备5搜索到达目的地的推荐路径的话。
当前位置检测部件11相对于时间轴计算距离数据和角度数据的积分，从而周期计算距离初始值(X，Y)的当前位置(X’，Y’)或行使一段后的位置，其中距离数据和角度数据是通过分别计算车轮速度传感器6测量的距离脉冲数据S5的积分和陀螺传感器8测量的角速度数据S7的积分得到的。当前位置检测部件11向地图显示处理部件16输出所计算的当前位置，并且向地图匹配处理部件13输出在每个预定计算时刻计算的当前位置。此外，当前位置检测部件11向地图显示处理部件16输出当前位置的校正数据，如果它从后面描述的地图匹配处理部件13那里获得当前位置的校正数据的话。再者，当前位置检测部件11向路径导航部件15输出当前位置(或其校正数据)，如果需要的话。
为了使主动轮的推进装置的转角与行使方向一致，当前位置检测部件11引用从地磁传感器7那里获得的方位数据S6以及从陀螺8那里获得的角速度数据S7的角数据的积分，由此估计车辆行使方向的绝对方位。如果车轮速度传感器6的数据S5和陀螺8的数据S7的积分是分别计算的，其误差会累积。因此，当前位置检测部件11消除以在预定期限内从GPS接收机9那里获得的位置数据S8为基础累积的误差，由此确定当前位置的数据。
数据读取部件12从存储设备3中读取要在显示屏2上显示的所需区域内的或路径搜索所需区域内(包含当前位置和目的地)的地图数据31。
地图匹配处理部件13处理数据读取部件12读取的当前位置以及当前位置检测部件11周期检测的当前位置周围的地图数据之间的地图匹配。地图匹配处理部件13周期校正当前位置，并且向当前位置检测部件11输出用于表示经过校正的当前位置的数据。
通过使用Dijkstra算法或其它算法，路径搜索部件14利用链接数据312(参阅图2)搜索以最低成本到达目的地的连接两点(例如，当前位置和目的地)的路径。路径搜索部件14向地图显示处理部件16输出用来表示推荐路径的数据，从而在显示屏2上显示作为搜索结果的路径，该路径作为推荐路径。此外，路径搜索部件14向路径导航部件15输出用于表示搜索的推荐路径的数据。
此外，当导航系统启动时，该实施方式的路径搜索部件14通过数据读取部件12，获取存储设备3中存储的地图数据310中的网格大小列表310。接着，路径搜索部件14把获取的网格大小列表310存储到RAM 22(参阅图4)的预定区域中。关于RAM 22的预定区域中存储的网格大小列表310，路径搜索部件14在执行路径搜索时确认能够在RAM 22上展现路径搜索所用的网格的链接数据312。在确认可以在RAM 22上展现路径搜索所用的网格的链接数据312之后，路径搜索部件14通过数据读取部件12获取该链接数据312。
正如在该实施方式中说明的那样，当导航系统启动时，路径搜索部件14从存储设备3中读取网格大小列表330，并且把它存储到RAM22的预定区域中。接着，当路径搜索部件14获取链接数据312时，它会查阅RAM 22中存储的网格大小列表330，由此确认能否在RAM22上展现链接数据312。换句话说，当需要获取链接数据312时，该实施方式无需访问存储设备3就能实现，不论是否能在RAM 22上展现链接数据312。简言之，该实施方式可以缩短处理路径搜索时用于获取链接数据312的时限。
此外，该实施方式的路径搜索部件14在设置部件10接受来自用户的目的地设置之前，预先搜索连接两点(即，车辆的当前位置和当前位置的预定范围内的交叉口)的路径。如果设置目的地，则路径搜索部件14利用到达该交叉口的路径，因为该路径是预先搜索的并且包含在预定范围内，由此搜索到达目的地的推荐路径。因此，在该实施方式中，在接受目的地的设置之前，搜索车辆的当前位置周围的路径。因此，如果设置目的地，可以缩短用于搜索到达目的地的推荐路径的搜索时限。
路径导航部件15引导用户经由搜索的推荐路径到达目的地。具体地，路径导航部件15从当前位置检测部件11中周期获取当前位置。此外，路径导航部件15通过使用获取的当前位置，用于表示从路径搜索部件14中获取的推荐路径的数据，以及通过数据读取部件12从存储设备3中读取的地图数据，引导用户到达目的地。这里，该实施方式不对路径导航部件15引导用户到达目的地的具体方法施加特殊限制。例如，路径导航部件15在显示屏2上显示一个画面，其中把路径搜索部件14搜索的推荐路径叠加到地图上，从而可以通过语音输入/输出设备4通知用户车辆在推荐路径上行使时所需的信息(例如，车辆是否在下一个交叉口转弯的信息)。
地图显示处理部件16通过数据读取部件12从存储设备3那里接收需要在显示屏2上显示的区域中的地图数据3。地图显示处理部件16从路径搜索部件14那里接收搜索的推荐路径，并且从当前位置检测部件11那里接收有关当前位置的信息。此外，地图显示处理部件16创建绘图命令，以便在显示屏2的屏幕上绘制诸如公路、其它地图成分、当前位置、目的地和导航箭头之类的标记，并且向图形处理部件17输出绘图命令。
图形处理部件17利用地图显示处理部件16创建的绘图命令在显示屏2的屏幕上显示图形数据。
以下描述该实施方式的处理器1的硬件配置。
图4是用于表示处理器1的硬件配置的示图。
如图所示，处理器1的配置包括：CPU(中央处理器)21；用于临时存储CPU 21执行的程序或数据的RAM(随机存取存储器)22；用于存储程序的ROM(只读存储器)23，其中该程序执行上面提及的各部件(即，设置部件10，当前位置检测部件11，数据读取部件12，地图匹配处理部件13，路径搜索部件14，路径导航部件15，地图显示处理部件16和图形处理部件17)的功能；在存储器之间并且在存储器和各设备之间传送数据的DMA(直接存储器存取)24；执行图形绘制并控制显示的绘图控制器25；存储图形图像数据的VRAM(视频随机存取存储器)26；把图像数据转换成RGB信号的调色板27；把模拟信号转换成数字信号的A/D转换器28；把串行信号转换成与总线同步的并行信号的SCI(串行通信接口)29；以与总线同步的方式把并行信号叠加到总线上的PIO(并行输入/输出)30；以及计算脉冲信号的积分的计数器31。实现上面提及的各部件(即，设置部件10，当前位置检测部件11，数据读取部件12，地图匹配处理部件13，路径搜索部件14，路径导航部件15，地图显示处理部件16和图形处理部件17)的功能，以至CPU 21把ROM 23中存储的用于执行各部件之功能的程序加载到RAM 22中，并执行这些程序。
以下描述该实施方式的导航系统为搜索推荐路径而执行的处理。首先描述导航系统启动时执行的路径搜索处理。
图5是用来说明该实施方式的导航系统启动时执行的路径搜索过程的流程的示图。
当导航系统启动时(S100)，处理器1的路径搜索部件14开始以下操作。
首先，路径搜索部件14通过数据读取部件12获取存储设备3中存储的网格大小列表330，并把它存储到RAM 22的预定区域中(S101)。每当路径搜索部件14通过数据读取部件12获取路径搜索所需的网格的链接数据312时，都要利用网格大小列表330。
随后，路径搜索部件14从当前位置检测部件11那里获取车辆的当前位置，并且确定当前位置周围的预定距离范围内是否存在交叉口。接着，路径搜索部件14搜索从当前位置到所检测的交叉口的路径(S102)。
具体地，路径搜索部件14确定当前位置的预定距离范围内包含的网格。路径搜索部件14通过数据读取部件12从存储设备3中获取所确定的网格的链接数据312。这里，在路径搜索部件14获取指定网格的链接数据312时，它会参阅在RAM 22的预定区域中存储的网格大小列表330。通过确认与网格大小列表330相对应的指定网格的链接数据312的数据量和RAM 22的容量，路径搜索部件14顺序获取可以在RAM 22上展现的链接数据312。
接着，路径搜索部件14使用获取的链接数据312来确定距离当前位置预定距离范围内的交叉口。借助于该获取的链接数据312，路径搜索部件14搜索从当前位置到上面提及的确定交叉口的路径。如果距离当前位置的预定距离范围内有多个交叉口，则路径搜索部件14搜索从当前位置到众多交叉口的每个交叉口的路径。接着，路径搜索部件14保存从当前位置到交叉口的搜索路径。
随后，路径搜索部件14前进到S104，如果它通过设置部件10接受来自用户的目的地输入的话(S103)。
在S104中，路径搜索部件14在显示屏2上显示一个画面(即，确认画面)，用于接受来自用户的证实输入的目的地是否有错的确认。此外，在路径搜索部件14接受来自用户的表示该目的地没有错误(目的地确定数据)的数据(目的地确定数据)之前，开始搜索到达在S103中接受的目的地的推荐路径。
具体地，通过使用当前位置和接受的目的地，路径搜索部件14指定该路径搜索使用的网格。通过参阅RAM 22中存储的网格大小列表330，路径搜索部件14确认与网格大小列表330相对应的指定网格的链接数据的数据量以及可以在RAM上展现的数据量。作为该确认的结果，路径搜索部件14通过数据读取部件12顺序获取可在RAM 22上展现的链接数据312。通过使用获取的链接数据312，路径搜索部件14搜索从交叉口到目的地的路径，正如在S102中确定的那样。此外，路径搜索部件14获得的路径是由在S102中确定的从当前位置到交叉口的路径以及从交叉口到目的地的路径组成的。
随后，路径搜索部件14前进到S106的操作，如果它接受来自用户的“目的地确定数据”的话。如果在S104中开始的路径搜索尚未结束，则路径搜索部件14继续搜索操作。另一方面，路径搜索部件14退出在S104中开始的路径搜索过程，如果它接受来自用户的表示目的地错误的数据的话，清除(即，删除)搜索的路径，如果路径搜索处理已经结束的话，并且该处理返回到S103的操作。
在S106中，路径搜索部件14指定作为在S104中开始的路径搜索处理之结果而获得的路径作为推荐路径，并且在显示屏2上显示指定的推荐路径。接着，路径搜索部件14向路径导航部件15输出指定的推荐路径，并且该处理结束。
这里，迄今为止所做的描述是基于以下情况的，用户向导航系统输入表示目的地的数据，但本发明并不限于此。例如，设置部件10接受诸如“地址”或“电话号码”之类的检索条件，并且导航系统配备有根据接受的检索条件检索目的地的检索功能。如果目的地是用检索功能检索的，则设置部件10向路径搜索部件14输出检索的目的地。此外，当接受来自设置部件10的目的地时，在设置部件10接受来自用户的对检索的目的地的确认之前，路径搜索部件14开始到达该目的地的路径搜索。
以下说明当该实施方式的导航系统检测到车辆停止时的路径搜索过程。
图6是用于说明该实施方式的导航系统检测到车辆停止时执行的路径搜索过程的示图。
此时，导航系统的路径搜索部件14周期获取来自车轮速度传感器(未示出)的信息，由此检测车辆是否已停止(S200)。路径搜索部件14前进到S102的操作，如果它检测到车辆停止的话。另一方面，如果路径搜索部件14没有检测到车辆停止，则它重复S200的操作。
此后，路径搜索部件14执行与参照图5描述的S102到S106的操作相同的操作。
因此，根据该实施方式，在导航系统启动时，路径搜索部件14从存储设备3中读取网格大小列表330，并把它存储在RAM 22的预定区域中。因此，在路径搜索时，路径搜索部件14可以实现以下操作，在不访问存储设备3的情况下，确认能否在RAM 22上展现搜索所需的网格的链接数据。因此，在该实施方式中，最终可以缩短路径搜索的时限。
此外，在设置部件10接受来自用户的目的地的设置之前，该实施方式的路径搜索部件14预先搜索连接以下两点的路径：车辆的当前位置以及当前位置的预定距离范围的交叉口。接着，在设置目的地时，路径搜索部件14通过使用到达预先搜索的预定范围内的交叉口的路径，搜索到达目的地的路径。换句话说，在该实施方式中，车辆的当前位置周围的路径是在接受目的地的设置之前搜索的。因此，在设置目的地时，可以省略从当前位置到交叉口的路径搜索，从而可以缩短用于搜索到达目的地的推荐路径所需的搜索时限。
此外，在该实施方式中，当导航系统接受设置的目的地时，并且在接受来自用户的用于证实输入的目的地是否有错的确认之前，开始到达目的地的路径搜索。因此，在接受来自用户的目的地确认时，到达该目的地的推荐路径的搜索已经开始。因此，根据该实施方式，可以缩短从最后设置目的地开始的搜索时限。
因此，根据该实施方式，导航系统可以缩短从设置目的地开始到向用户展现推荐路径为止的时限。
这里，本发明并不限于迄今为止描述的各种实施方式，而是可以在其范围内用各种方式进行修改。例如，在该实施方式中，在设置目的地的情况下，通过使用在设置目的地之前预先搜索的从当前位置到交叉口的路径进行路径搜索，但是本发明并不限于那种路径搜索。例如，路径搜索部件14保存在搜索到达目的地的推荐路径时尚未选定的候选路径，即使在启动最终选定的推荐路径的导航以后。此外，在检测到车辆偏移的情况下，路径搜索部件14可以使用保存的候选路径再次搜索到达目的地的路径。通过再次使用先前搜索的候选路径，可以缩短自动改线的搜索时限。
此外，在该实施方式中，从当前位置到预定位置范围内的交叉口的路径是在设置目的地之前搜索的，但是路径搜索并不限于此。例如，也可以搜索从当前位置到干线的路径。
首先，参照图1描述可以应用该实施方式的车载导航系统的示意配置。
图1是应用于本发明之实施方式的车载导航系统(以下简称为“导航系统”)的示意配置图。
如图所示，所配置的导航系统包括，处理器1，显示屏2，存储地图数据等的存储设备3，语音输入/输出设备4，输入设备5，车轮速度传感器6，地磁传感器7，陀螺8和GPS(全球定位系统)接收机9。
处理器1是一个主要部件，它处理为导航系统的用户提供的各种信息。例如，处理器1以各种传感器6-8以及GPS接收机9输出的信息为基础检测当前位置。处理器1从存储设备3中读取所检测的当前位置周围的地图数据，在显示屏2上用图形方式展现读取的地图数据并显示地图数据和表示当前位置的标记。
另一方面，在接受设置的目的地之前，处理器1预先搜索连接以下两点的路径：车辆的当前位置以及距离当前位置预定距离范围内的交叉口。此外，如果设置目的地，则处理器1通过使用到达预先搜索的预定范围内的交叉口的路径，搜索到达该目的地的推荐路径。以下详细描述用来搜索到达该目的地的推荐路径的过程。
显示屏2是用来显示处理器1创建的图形数据的一个部件，其配置可以是CRT、液晶显示器等。处理器1和显示屏2通常是用诸如RGB信号或NTSC(全国电视标准委员会)信号的信号S1连接的。
存储设备3是存储地图数据的部件，地图数据包括从日本岛的全图到日本国的城市、城镇和乡村的详细地图的众多比例的地图。例如，也可以使用DVD设备或硬盘设备作为存储设备3。
以下描述地图数据的配置。
图2是用于模拟存储设备3中存储的地图数据的数据结构的示图。
如图所示，把地图数据310分成网格区域，这是通过把地图分成许多块得到的。地图数据310包含用于标识网格区域的网格ID 311以及由该网格区域内的公路组成的各个链接的链接数据312。此外，在地图数据310中，每个网格ID 311均包含一个网格大小列表330，其中利用该网格ID定义的网格区域的链接数据312的数据量(即，网格大小)彼此相对应。
链接数据312包括：标识该链接的链接ID 3121；作为该链接的两个节点(起始节点和结束节点)的坐标信息3122；用来表示链接的公路是“收费公路”还是“普通公路”的公路种类3123；用于表示该链接的长度的链接长度信息3124；该链接的运行时间(或移动时间)信息3125；以及连接两个节点(即，起始节点和结束节点)的链接的链接ID(即，相连链接ID)3126。
当处理器1执行路径搜索时，使用网格大小列表330来确认要从存储设备3中读取的地图数据的数据量。具体地，当导航系统启动时，处理器1从存储设备3中读取并保存网格大小列表312。地图数据310还包含除公路之外的对应网格区域内包含的地图部分的信息(例如，名称、种类或坐标信息)。
以下回到图1继续该描述。语音输入/输出设备4把处理器1为用户创建的信息转换成语音信号并输出，识别用户发出的话音，并且向处理器1传送识别的内容。
输入设备5是用来接受用户的指令的部件，用户指令如选择各种功能或设置导航系统的目的地，其配置为硬件开关，如滚动键或比例变更键，操纵杆或粘贴在显示屏2上的触板。
导航系统使用传感器6-8以及GPS接收机9来检测当前位置。车轮速度传感器6测量与车轮的圆周的距离以及与测量的车轮转数的距离，并且根据成对车轮的转数测量车辆的转角。地磁传感器7检测地球的磁性，由此获得车辆的方位角。陀螺8是由光纤陀螺或振动陀螺组成的，目的是检测车辆转动的角度。GPS接收机9接收GPS卫星的信号，以测量车辆和三颗或更多颗GPS卫星之间的距离以及这些距离的变化率，由此检测车辆的当前位置，行使方向和行使方位。
随后，参照图3解释迄今描述的导航系统的处理器1的功能。
图3是用于解释该实施方式的处理器1的功能配置的示图。
如图所示，处理器1的配置包括，设置部件10，当前位置检测部件11，数据读取部件12，地图匹配处理部件13，路径搜索部件14，路径导航部件15，地图显示处理部件16，图形处理部件17和网格大小列表获取部件。
设置部件10接受用户输入到输入设备5或语音输入/输出设备4的需求，并且控制处理器1，所以可以执行与所需内容相对应的处理。例如，需要路径搜索部件14进行处理以搜索从当前位置到目的地的推荐路径，如果用户需要通过输入设备5搜索到达目的地的推荐路径的话。
当前位置检测部件11相对于时间轴计算距离数据和角度数据的积分，从而周期计算距离初始值(X，Y)的当前位置(X’，Y’)或行使一段后的位置，其中距离数据和角度数据是通过分别计算车轮速度传感器6测量的距离脉冲数据S5的积分和陀螺传感器8测量的角速度数据S7的积分得到的。当前位置检测部件11向地图显示处理部件16输出所计算的当前位置，并且向地图匹配处理部件13输出在每个预定计算时刻计算的当前位置。此外，当前位置检测部件11向地图显示处理部件16输出当前位置的校正数据，如果它从后面描述的地图匹配处理部件13那里获得当前位置的校正数据的话。再者，当前位置检测部件11向路径导航部件15输出当前位置(或其校正数据)，如果需要的话。
为了使主动轮的推进装置的转角与行使方向一致，当前位置检测部件11引用从地磁传感器7那里获得的方位数据S6以及从陀螺8那里获得的角速度数据S7的角数据的积分，由此估计车辆行使方向的绝对方位。如果车轮速度传感器6的数据S5和陀螺8的数据S7的积分是分别计算的，其误差会累积。因此，当前位置检测部件11消除以在预定期限内从GPS接收机9那里获得的位置数据S8为基础累积的误差，由此确定当前位置的数据。
数据读取部件12从存储设备3中读取要在显示屏2上显示的所需区域内的或路径搜索所需区域内(包含当前位置和目的地)的地图数据31。
地图匹配处理部件13处理数据读取部件12读取的当前位置以及当前位置检测部件11周期检测的当前位置周围的地图数据之间的地图匹配。地图匹配处理部件13周期校正当前位置，并且向当前位置检测部件11输出用于表示经过校正的当前位置的数据。
通过使用Dijkstra算法或其它算法，路径搜索部件14利用链接数据312(参阅图2)搜索以最低成本到达目的地的连接两点(例如，当前位置和目的地)的路径。路径搜索部件14向地图显示处理部件16输出用来表示推荐路径的数据，从而在显示屏2上显示作为搜索结果的路径，该路径作为推荐路径。此外，路径搜索部件14向路径导航部件15输出用于表示搜索的推荐路径的数据。
此外，当导航系统启动时，该实施方式的路径搜索部件14通过数据读取部件12，获取存储设备3中存储的地图数据310中的网格大小列表310。接着，路径搜索部件14把获取的网格大小列表310存储到RAM 22(参阅图4)的预定区域中。关于RAM 22的预定区域中存储的网格大小列表310，路径搜索部件14在执行路径搜索时确认能够在RAM 22上展现路径搜索所用的网格的链接数据312。在确认可以在RAM 22上展现路径搜索所用的网格的链接数据312之后，路径搜索部件14通过数据读取部件12获取该链接数据312。
正如在该实施方式中说明的那样，当导航系统启动时，路径搜索部件14从存储设备3中读取网格大小列表330，并且把它存储到RAM22的预定区域中。接着，当路径搜索部件14获取链接数据312时，它会查阅RAM 22中存储的网格大小列表330，由此确认能否在RAM22上展现链接数据312。换句话说，当需要获取链接数据312时，该实施方式无需访问存储设备3就能实现，不论是否能在RAM 22上展现链接数据312。简言之，该实施方式可以缩短处理路径搜索时用于获取链接数据312的时限。
此外，该实施方式的路径搜索部件14在设置部件10接受来自用户的目的地设置之前，预先搜索连接两点(即，车辆的当前位置和当前位置的预定范围内的交叉口)的路径。如果设置目的地，则路径搜索部件14利用到达该交叉口的路径，因为该路径是预先搜索的并且包含在预定范围内，由此搜索到达目的地的推荐路径。因此，在该实施方式中，在接受目的地的设置之前，搜索车辆的当前位置周围的路径。因此，如果设置目的地，可以缩短用于搜索到达目的地的推荐路径的搜索时限。
路径导航部件15引导用户经由搜索的推荐路径到达目的地。具体地，路径导航部件15从当前位置检测部件11中周期获取当前位置。此外，路径导航部件15通过使用获取的当前位置，用于表示从路径搜索部件14中获取的推荐路径的数据，以及通过数据读取部件12从存储设备3中读取的地图数据，引导用户到达目的地。这里，该实施方式不对路径导航部件15引导用户到达目的地的具体方法施加特殊限制。例如，路径导航部件15在显示屏2上显示一个画面，其中把路径搜索部件14搜索的推荐路径叠加到地图上，从而可以通过语音输入/输出设备4通知用户车辆在推荐路径上行使时所需的信息(例如，车辆是否在下一个交叉口转弯的信息)。
地图显示处理部件16通过数据读取部件12从存储设备3那里接收需要在显示屏2上显示的区域中的地图数据3。地图显示处理部件16从路径搜索部件14那里接收搜索的推荐路径，并且从当前位置检测部件11那里接收有关当前位置的信息。此外，地图显示处理部件16创建绘图命令，以便在显示屏2的屏幕上绘制诸如公路、其它地图成分、当前位置、目的地和导航箭头之类的标记，并且向图形处理部件17输出绘图命令。
图形处理部件17利用地图显示处理部件16创建的绘图命令在显示屏2的屏幕上显示图形数据。
以下描述该实施方式的处理器1的硬件配置。
图4是用于表示处理器1的硬件配置的示图。
如图所示，处理器1的配置包括：CPU(中央处理器)21；用于临时存储CPU 21执行的程序或数据的RAM(随机存取存储器)22；用于存储程序的ROM(只读存储器)23，其中该程序执行上面提及的各部件(即，设置部件10，当前位置检测部件11，数据读取部件12，地图匹配处理部件13，路径搜索部件14，路径导航部件15，地图显示处理部件16和图形处理部件17)的功能；在存储器之间并且在存储器和各设备之间传送数据的DMA(直接存储器存取)24；执行图形绘制并控制显示的绘图控制器25；存储图形图像数据的VRAM(视频随机存取存储器)26；把图像数据转换成RGB信号的调色板27；把模拟信号转换成数字信号的A/D转换器28；把串行信号转换成与总线同步的并行信号的SCI(串行通信接口)29；以与总线同步的方式把并行信号叠加到总线上的PIO(并行输入/输出)30；以及计算脉冲信号的积分的计数器31。实现上面提及的各部件(即，设置部件10，当前位置检测部件11，数据读取部件12，地图匹配处理部件13，路径搜索部件14，路径导航部件15，地图显示处理部件16和图形处理部件17)的功能，以至CPU 21把ROM 23中存储的用于执行各部件之功能的程序加载到RAM 22中，并执行这些程序。
以下描述该实施方式的导航系统为搜索推荐路径而执行的处理。首先描述导航系统启动时执行的路径搜索处理。
图5是用来说明该实施方式的导航系统启动时执行的路径搜索过程的流程的示图。
当导航系统启动时(S100)，处理器1的路径搜索部件14开始以下操作。
首先，路径搜索部件14通过数据读取部件12获取存储设备3中存储的网格大小列表330，并把它存储到RAM 22的预定区域中(S101)。每当路径搜索部件14通过数据读取部件12获取路径搜索所需的网格的链接数据312时，都要利用网格大小列表330。
随后，路径搜索部件14从当前位置检测部件11那里获取车辆的当前位置，并且确定当前位置周围的预定距离范围内是否存在交叉口。接着，路径搜索部件14搜索从当前位置到所检测的交叉口的路径(S102)。
具体地，路径搜索部件14确定当前位置的预定距离范围内包含的网格。路径搜索部件14通过数据读取部件12从存储设备3中获取所确定的网格的链接数据312。这里，在路径搜索部件14获取指定网格的链接数据312时，它会参阅在RAM 22的预定区域中存储的网格大小列表330。通过确认与网格大小列表330相对应的指定网格的链接数据312的数据量和RAM 22的容量，路径搜索部件14顺序获取可以在RAM 22上展现的链接数据312。
接着，路径搜索部件14使用获取的链接数据312来确定距离当前位置预定距离范围内的交叉口。借助于该获取的链接数据312，路径搜索部件14搜索从当前位置到上面提及的确定交叉口的路径。如果距离当前位置的预定距离范围内有多个交叉口，则路径搜索部件14搜索从当前位置到众多交叉口的每个交叉口的路径。接着，路径搜索部件14保存从当前位置到交叉口的搜索路径。
随后，路径搜索部件14前进到S104，如果它通过设置部件10接受来自用户的目的地输入的话(S103)。
在S104中，路径搜索部件14在显示屏2上显示一个画面(即，确认画面)，用于接受来自用户的证实输入的目的地是否有错的确认。此外，在路径搜索部件14接受来自用户的表示该目的地没有错误(目的地确定数据)的数据(目的地确定数据)之前，开始搜索到达在S103中接受的目的地的推荐路径。
具体地，通过使用当前位置和接受的目的地，路径搜索部件14指定该路径搜索使用的网格。通过参阅RAM 22中存储的网格大小列表330，路径搜索部件14确认与网格大小列表330相对应的指定网格的链接数据的数据量以及可以在RAM上展现的数据量。作为该确认的结果，路径搜索部件14通过数据读取部件12顺序获取可在RAM 22上展现的链接数据312。通过使用获取的链接数据312，路径搜索部件14搜索从交叉口到目的地的路径，正如在S102中确定的那样。此外，路径搜索部件14获得的路径是由在S102中确定的从当前位置到交叉口的路径以及从交叉口到目的地的路径组成的。
随后，路径搜索部件14前进到S106的操作，如果它接受来自用户的“目的地确定数据”的话。如果在S104中开始的路径搜索尚未结束，则路径搜索部件14继续搜索操作。另一方面，路径搜索部件14退出在S104中开始的路径搜索过程，如果它接受来自用户的表示目的地错误的数据的话，清除(即，删除)搜索的路径，如果路径搜索处理已经结束的话，并且该处理返回到S103的操作。
在S106中，路径搜索部件14指定作为在S104中开始的路径搜索处理之结果而获得的路径作为推荐路径，并且在显示屏2上显示指定的推荐路径。接着，路径搜索部件14向路径导航部件15输出指定的推荐路径，并且该处理结束。
这里，迄今为止所做的描述是基于以下情况的，用户向导航系统输入表示目的地的数据，但本发明并不限于此。例如，设置部件10接受诸如“地址”或“电话号码”之类的检索条件，并且导航系统配备有根据接受的检索条件检索目的地的检索功能。如果目的地是用检索功能检索的，则设置部件10向路径搜索部件14输出检索的目的地。此外，当接受来自设置部件10的目的地时，在设置部件10接受来自用户的对检索的目的地的确认之前，路径搜索部件14开始到达该目的地的路径搜索。
以下说明当该实施方式的导航系统检测到车辆停止时的路径搜索过程。
图6是用于说明该实施方式的导航系统检测到车辆停止时执行的路径搜索过程的示图。
此时，导航系统的路径搜索部件14周期获取来自车轮速度传感器(未示出)的信息，由此检测车辆是否已停止(S200)。路径搜索部件14前进到S102的操作，如果它检测到车辆停止的话。另一方面，如果路径搜索部件14没有检测到车辆停止，则它重复S200的操作。
此后，路径搜索部件14执行与参照图5描述的S102到S106的操作相同的操作。
因此，根据该实施方式，在导航系统启动时，路径搜索部件14从存储设备3中读取网格大小列表330，并把它存储在RAM 22的预定区域中。因此，在路径搜索时，路径搜索部件14可以实现以下操作，在不访问存储设备3的情况下，确认能否在RAM 22上展现搜索所需的网格的链接数据。因此，在该实施方式中，最终可以缩短路径搜索的时限。
此外，在设置部件10接受来自用户的目的地的设置之前，该实施方式的路径搜索部件14预先搜索连接以下两点的路径：车辆的当前位置以及当前位置的预定距离范围的交叉口。接着，在设置目的地时，路径搜索部件14通过使用到达预先搜索的预定范围内的交叉口的路径，搜索到达目的地的路径。换句话说，在该实施方式中，车辆的当前位置周围的路径是在接受目的地的设置之前搜索的。因此，在设置目的地时，可以省略从当前位置到交叉口的路径搜索，从而可以缩短用于搜索到达目的地的推荐路径所需的搜索时限。
此外，在该实施方式中，当导航系统接受设置的目的地时，并且在接受来自用户的用于证实输入的目的地是否有错的确认之前，开始到达目的地的路径搜索。因此，在接受来自用户的目的地确认时，到达该目的地的推荐路径的搜索已经开始。因此，根据该实施方式，可以缩短从最后设置目的地开始的搜索时限。
因此，根据该实施方式，导航系统可以缩短从设置目的地开始到向用户展现推荐路径为止的时限。
这里，本发明并不限于迄今为止描述的各种实施方式，而是可以在其范围内用各种方式进行修改。例如，在该实施方式中，在设置目的地的情况下，通过使用在设置目的地之前预先搜索的从当前位置到交叉口的路径进行路径搜索，但是本发明并不限于那种路径搜索。例如，路径搜索部件14保存在搜索到达目的地的推荐路径时尚未选定的候选路径，即使在启动最终选定的推荐路径的导航以后。此外，在检测到车辆偏移的情况下，路径搜索部件14可以使用保存的候选路径再次搜索到达目的地的路径。通过再次使用先前搜索的候选路径，可以缩短自动改线的搜索时限。
此外，在该实施方式中，从当前位置到预定位置范围内的交叉口的路径是在设置目的地之前搜索的，但是路径搜索并不限于此。例如，也可以搜索从当前位置到干线的路径。