专利名称：使用路径id在客户端和服务器端之间传送路径的制作方法
技术领域：
本发明总体上涉及对导航系统提供路径功能。具体地说，本发明涉及对导航路 径的更有效的说明。
背景技术：
用于司机和步行者的导航系统在市场上变得日益受欢迎。直到最近，大多数 导航系统还是完备设备计算路径并且对于借助于完全发生在设备上的计算搜索关注的 点。一些具有较小内存、速度较慢的处理器的导航系统主要是基于服务器的将导航请 求发送给服务器，计算路径并且将其传送至客户端设备，并且随后客户端设备仅监视沿 着路径的行进。现在，随着更便宜、更快速的处理器出现在客户端设备，以及客户端和服务器 之间的连接提供了更大的带宽和更稳定的连接性，出现了新的导航模式。在该模式中， 其可以称为“已连接的导航”，客户端设备可以执行大部分导航系统的工作，但是另 外，一些其它功能可以委托给服务器。当委托给服务器的功能所需要的计算功率大于客 户端设备可用的功率或者数据量过大而难以有效地传送给客户端时，该模式是最为有利 的。这种功能的一个实例是路径选择考虑了当前和预测的交通状况。一些现代自动 交通信息馈电系统提供了主要城市区域的所有主要道路的当前交通信息以及对下周每隔 15分钟的每条主要道路的预测交通信息。这是非常大量的信息，实际上使用其非常小的 一部分以计算任何给定路径。因而，对于将所有数据传送给该区域的每个客户端设备而
言，效率非常差。

发明内容
本发明允许了一种技术，用于将路径描述从发送器传送至接收器，其需要的空 间大大小于链路ID的完整列表，其需要的用于覆盖整个路径描述的计算时间大大减少。 为了简化，或者使路径“脱水(dehydrate)”，使用一系列“面包屑(breadcrumb)”，并 且在一些实施例中伴随着由“线索(hint)”来解决潜在的错误。面包屑包括点的坐标， 路径到达面包屑处的航向(heading)以及路径离开面包屑处的航向。第一和最后面包屑 标记了路径的开始和结束，并且特殊情况是，因为第一面包屑不包括到达航向，而最后 面包屑不包括离开航向。为了使路径脱水，脱水模块在标记路径开始的位置处放置面包 屑，并且具有离开航向，所述航向标识原始路径中的链路。检查原始路径中每个链路的 结尾处的节点。如果离开节点的链路是与到达节点的链路最平行的链路，那么对已脱水的路径不增加任何内容。如果离开节点的链路不是与到达节点的链路最平行的链路，那 么对已脱水的路径增加面包屑，从而指明点的坐标、面包屑的到达航向以及面包屑的离 开航向。在路径结束之处，放置结束面包屑。为了使路径“再水化(rehydrate)”，再水化模块标记由起始面包屑标识的点处 的路径的开始。选择最接近起始面包屑的离开航向的链路作为再水化路径中的链路。如 果不存在标识该链路结束处节点的面包屑，那么对再水化路径添加最平行于到达节点的 链路的离开该节点的链路。针对随后的节点和链路重复该过程。当遇到存在面包屑的节 点时，对已脱水路径增加最接近平行于由面包屑指定的航向的离开节点的链路。结束面 包屑标识了再水化路径结束处的点。为了防止在水化和脱水模块不使用相同地图、或者执行略有不同的计算的情况 下发生错误，用面包屑提供线索或将线索提供至面包屑内。一些实施例中的线索指定了 限制区域，其中残留有一些或所有原始路径。如果路径再水化而超出限制区域，那么会 发生错误并且可以报告错误。


图1是根据本发明一个实施例的与服务器116通信的移动设备102的图。图2是示出根据本发明一个实施例的一种用于简化路径描述的方法的流程图。图3是示出根据本发明一个实施例的一种用于从已简化路径恢复原始路径的方 法的流程图。附图仅针对说明的目的而描述了本发明的优选实施例。本领域技术人员从下列 讨论中将易于认识到，可以采用本文所述的结构和方法的备选实施例，而不脱离本文所 描述的本发明的原理。
具体实施例方式图1是根据本发明一个实施例的系统100的图，其中移动设备102与服务器116 通信。移动设备102包括客户端选路引擎104、数据库106和用户界面(UI)模块108。 服务器116包括服务器选路引擎110和数据库112。客户端选路引擎104和服务器端选 路引擎110各自分别包括脱水模块122、118以及再水化模块124、120。客户端选路引 擎104和服务器端选路引擎110均另外包括用于提供导航功能的特征；本文未描述的内 容与本说明书无密切关系。移动设备102和服务器116经由通信网络114而彼此通信， 所述通信网络114可以包括蜂窝、Wi-MAX、WAN或任何其它合适的网络。移动设备 102和服务器116各自包括附加的硬件和软件，用于执行本领域中已知的或者与本说明书 无密切关系的附加功能，因而在此未对其进行描述。在各个实施例中，可以在移动设备 和/或服务器中包括更多或更少模块。而且，在整个说明书中，基本上参考系统100以 描述执行各个步骤的部件的集合。实践中，系统100的各个元件自身是系统；例如，在 一个实施例中，移动设备102是与服务器116分别出售的完备系统，其自身可以整体或局 部地、与其它已标识的部件分离地可用。为了充分利用诸如本文所述的已连接的导航时机，有利地是能够在移动设备102 和服务器116之间尽可能有效地交换路径信息。系统100提供了这样的一种方法。
4
在一些情况下，客户端设备可能希望将路径发送给服务器。例如，客户端设备 可能希望沿着路径搜索关注的点(POI)。因为POI信息改变非常频繁，尤其是诸如汽油 价格的增强POI信息，可能并不合理的是持续地将更新的POI信息发送给所有客户端设 备。作为代替，客户端设备可以将沿着其进行搜索的路径发送给服务器，从而服务器可 以标识客户端的相关POI。另一应用可以包括移动设备和服务器，交换关于沿着所推荐 的行进路径的实施交通状况的信息。对于诸如上述的用途，需要将对路径的描述从发送器传送至接收器，各自可以 是客户端设备或服务器，这取决于当时的情况。描述路径的一种方法是发送路径的每个 部分的列表。例如，在许多路径计算系统中，每个可能的道路链路具有链路ID，并且可 以通过发送整个路径的链路ID的列表而传送路径描述。对于长的路径，这可以是相当长 的列表。描述路径的另一种方法是通过发送起点和终点以及足够的中间航路点而传送路 径的描述，从而接收器可以重新计算路径。这需要更短的传送，但是需要接收器部件上 更多的计算以重建路径。出于路径计算的目的，导航系统通常将数字地图中的道路网络表示为节点和链 路的集合，如我们针对该说明书的目的一样。节点是诸如道路交叉或分岔的点，在节点 处可以在备选路径之间做出决定。链路是从一个节点到另一节点的可能路径。数字地 图(其可以位于客户端数据库106、服务器数据库112或两者之中)存储了每个节点的坐 标(纬度和经度)、以及链路几何形状的表示(其通常作为起始节点和结束节点之间的一 系列点(所谓的形状点(shapepoint))的坐标(纬度和经度))，选择使得从起始节点通过 连续形状点至结束节点的线段的序列遵循实际道路的形状，其表示了所期望级别的精确 性。路径的起始和结束点可以是节点，或者是沿着链路的中间点。在后者情况下，它们 可能是链路的形状点，或者可以在形状点之间。系统100允许使用对路径的简化描述，可互换地称其为“路径ID”或“脱水路 径”，以在移动设备102和服务器116之间通信。简化的描述包括对路径上临界决定点 的描述，本文称其为“面包屑”，以及关于面包屑之间的路径的线索的描述。每个面包 屑包括随着其路径到达和离开面包屑的点坐标的描述和对路径航向的描述。在一个实施 例中，表示起点的面包屑不具有对到达航向的描述，而表示结束点的面包屑不具有对离 开航向的描述。选择面包屑，使得可以通过以指定航向离开第一面包屑，而后在每个节 点采用最靠近到达链路(incoming link)的同一方向的链路，直到到达下一面包屑，来重 建从每个面包屑至下一面包屑的路径。在一个实施例中，由描述路径的脱水模块来执行面包屑的放置。在一些情况 下，将由客户端脱水模块122描述路径；在其它时候，将由服务器脱水模块118描述路 径。在一个实施例中并且参考图2，如下确定面包屑的放置在202，将面包屑放置在路 径的起点，所述起点可以是或者也可以不是节点。随后顺序地逐一检查路径中的链路的 序列。在204，跟随路径中的第一链路至在终点处的节点。在206，检查离开该节点的 链路。在208，如果路径的下一链路是以最接近等于路径中的到达链路(“最接近平行 于下一链路”)的航向离开节点的链路，那么在210，在节点处不放置面包屑。然而，在 208，如果路径的下一链路并不是最接近平行于下一链路，则在212，在节点处放置面包 屑。在任一情况下，在214，跟随路径的下一链路至其终点，所述终点是下一节点或者是路径的终点。在216，如果链路在路径终点处结束，那么在218，在终点处放置面包屑。 在216，如果链路在另一节点处结束，处理返回步骤208，并且核查下一链路以查看是否 其最接近平行链路。该处理重复，直到到达路径的终点。存储在数据库106或数据库112中的数据的改变可以使得整个路径的重建、也 称为“再水化”失败，因为可能从未发现下一面包屑。(类似地，称路径的简化为“脱 水”。)因此，为了使得这种故障不出现，在本发明的一些实施例中，随着用于描述 连续面包屑之间的路径通路以及描述包含通路的区域的脱水路径，包括了称为“线索 (hint)”的额外信息。在一些实施例中，包含区域是包含通路的限制矩形(bounding rectangle)。在一个实施例中，通过使用包含或描述预定空间发报系统(predetermined spatial keying system)中矩形的键(key)数量，编码了限制矩形的描述，正如在美国专利 5,963,956中所述的，通过引用将其全文并入本文。在一些实施例中，线索包含对包括连 续面包屑之间的通路的椭圆形的描述。选择椭圆形从而其焦距是两个面包屑，从而仅需 要再一个参数以描述椭圆。在一些这种实施例中，附加参数是椭圆的离心率；在其它实 施例中，附加参数是从椭圆上任意点到两个焦点的距离和；作为选择，附加参数是距离 之和与两个焦点之间的直接距离或欧几里得距离或大圆(great-circle)距离的比率。在各种实施例中，线索包括对两个面包屑之间的通路的总长度的指示。在一个 这种实施例中，长度表示为沿着路径的通路的长度与两个面包屑之间的直接距离或欧几 里得距离或大圆距离的比率。在一个实施例中，对在线索中描述的包含区域或限制距离的表示稍大于实际包 含区域，以便于使得原始路径的重建更为可靠。根据面包屑和线索，创建对路径的编码描述。对每个面包屑的描述包含对面包 屑坐标以及到达和离开面包屑的链路的航向的表示。如上所述，第一面包屑不具有到达 航向(incoming heading)，而最后的面包屑不具有离开航向(exiting heading)。在一些实 施例中，为了最小化将传送的数据量，对于不同的面包屑，对坐标和/或航向的表示的 精确性不同，以允许区分面包屑与另一附近节点和/或区分实际到达或离开来自附近另 一个链路的链路所需的精确性，同时在不需要这种区分时允许较低精确性。在这种实施 例中，对面包屑的编码包含对它们精确性的表示。在一个实施例中，这由编码了在每个 坐标中所用的比特数量的小数量的比特所表示，其后是表示坐标本身的比特。类似地， 每个线索包含了对限制区域或区域或面包屑之间的通路的长度的表示。已脱水路径(其可以简称为“路径标识符”或“路径ID” )的描述，其经由通 信网络114在移动设备102和服务器116之间传送。随后位于接收器处的再水化模块使用路径ID以重建原始路径。在一个实施例中 并且参考图3，如下进行重建在302，在重建的路径中确定最接近起始面包屑的链路， 其中，该链路具有最接近面包屑的离开航向的航向；在304，在重建的路径中放置该链 路。在306，跟随该链路至其结束节点。在308，如果节点不在面包屑精确度内的下一 面包屑处，或者如果链路的结束航向不等于面包屑精确度内的下一面包屑的到达航向， 那么在310，在重建的路径中选择和放置最接近平行的下一链路。在308，如果节点在下 一面包屑处，并且链路的结束航向等于下一面包屑的到达航向，两者都在面包屑精确度
6内，那么在312，在重建路径中选择离开节点的链路，其中，所述链路的航向几乎最匹配 面包屑的离开航向，并且在重建路线中放置该链路。在任一情况下，在314，跟随所选链 路至其终点节点，并且重复该处理，直到选择的链路在最终面包屑处结束或者包含最终 面包屑316，在面包屑精确度内，并且其以面包屑的到达航向到达该点，其也在面包屑精 确度内。然后完成了路径的重建。在一些实施例中，在上述处理中，使用线索以核查不可能成为原始通路的一部 分的偏差。在重建从一个面包屑至下一面包屑的路径中，对于路径的该部分将所选链路 的通路与线索中所描述的限制区域进行比较。如果链路的通路超出区域或线索中所描述 的区域，那么再水化模块确定已经发生错误，并且以错误指示终止处理。如果存储在移动设备数据库106和服务器数据库112中的地图不同，那么选择作 为最接近点的链路可能不是正确的选择，而不同的链路可能是正确的选择。在一些实施 例中，使用回溯方法以允许更可靠地(robust)重建路径，而具有更少的错误。(回溯作为 一种通用搜索方法，是本领域已知的)。该方法通过以下列方式进行而允许重建在一个面 包屑和随后的下一个面包屑之间的路径在重建的每个步骤，可以标识一个以上的可能 下一链路。例如，如果其它链路在航向上靠近最接近平行下一链路，也可以认为它们是 可能的下一链路。如果路径重建失败，例如，因为下一链路超出限制区域外侧，再水化 模块返回最新的节点，在该节点处有未尝试的可能的下一链路，使用该链路代替先前在 该节点做的选择，并且向前进行。如果重建再次失败，再水化模块再次返回到最近出现 的节点，在该节点处有未尝试的可能的下一链路，等等，直到重建到达下一面包屑或者 直到由于自从先前的面包屑之后不再有更多未尝试的可能的下一链路而导致重建失败为 止。上述的实施例使用单一标准，以确定所选的下一链路，即最接近笔直的下一链 路。事实上，在各个实施例中可以对该选择使用其它标准。在一些实施例中，基于包括 航向的多个标准，选择已选为下一链路的链路。例如，可以使用记分(scoring)系统，其 中基于航向匹配的程度、道路名称匹配的程度以及道路是否为同一类型(例如，坡道还 是非坡道)，而对可能的下一链路指派分数(score)，并且选择具有最优分数的可能下一 链路，而不是仅选择最接近笔直的下一链路。这利用了如下观察，例如最优路径倾向于 在已经行进的方向上以及它们所在的街道上继续行进。本领域普通技术人员将理解，可以对上述方法进行大量改变。尤其步骤的次序在所述方法中并不重要。如上所述，放置了所有面包屑，并且随后 发射路径ID。如果放置面包屑和发射路径ID中的步骤彼此交错，那么该方案同样有效。已发射的路径ID中的面包屑和线索的次序并不重要。可以在所有线索的列表之 前，发射面包屑列表，或者线索可以与面包屑之间交错。就从起点到终点的前向上通过路径而言，描述了放置面包屑位置的选择。同样 可以在相反的方向上从终点至原点通过路径。就寻找在一些方面(航向、名称和/或道路类型)最紧密对应于给定链路的可能 的下一链路而言，描述了对面包屑的选择。同样可以通过比较可能的在先链路或者通过 选择双向标准而选择面包屑。例如，可以将面包屑放置在节点的离开链路不是最接近笔 直的下一链路或者节点的到达链路不是最接近笔直的前一链路之处。
在一个实施例中，仅在一个方向上，从移动设备102至服务器116或者从服务器 106至移动设备102，提供脱水路径。在这种情况下，脱水路径的发送器不需要包括再水 化模块，而脱水路径的接收器无需包括脱水模块。本发明允许的路径选择的形式，所述形式可以称为“基于服务器的建议的交通 路径选择。在该用途中，在移动客户端设备102上执行路径计算，其不具有交通信息或 者具有有限的交通信息。随后，将对路径的描述(其可能是如上所述的脱水路径ID，或 者是以常规方式描述的路径)发送至服务器116，所述服务器具有大量交通信息，例如， 在地理区域中许多道路上的当前的和/或预测的和/或历史的交通状况。随后，服务器 116对于客户端102发射的路径计算预期驾驶时间，并且重新计算从客户端发送的路径起 点到该路径的终点的一条或多条备选路径。如果该路径(或那些路径)与客户发送的路 径不同，将备选路径(或者多条备选路径)发送回客户端设备102 (再次通过发射一个或 多个路径ID)。在一个实施例中，如果将发送回移动客户端设备102的备选路径以与原 始路径相同的一系列路径选择步骤开始和/或结束，那么服务器116仅发射路径的已改变 部分，以及一系列数字或其它指示，以指示需要改变原始路径ID的哪些部分。在另一实施例，(任选地除了发送在诸如已评估的驾驶时间的其它描述性信息之 外)还通过将备选路径的图像(诸如GIF、JPEG或PNG图像)发送至客户端设备，并且 仅当客户端设备的用户选择一条备选路径时，发送路径ID，来完成对客户端设备的更简 洁的发射。在2009年4月1日提交的美国专利申请12/416,812中进一步描述了基于服务器 建议的交通的路径选择，通用引用全文将其并入本文。虽然上文已经特别详细地参考有限数量的实施例描述本发明，其它实施例也是 可行的。部件的特定命名以及它们的编程或结构方面并非强制性或重要的，而实施本发 明或其特征的机制可以具有不同的名称、格式或协议。此外，系统可以经由如上所述的 硬件或软件的组合或者完全以硬件元件实施。此外，本文所述的各个系统部件之间的功 能性的特定划分仅是示例性的，而非强制性的；单一系统部件执行的功能可以作为代替 地由多个部件执行。例如，脱水模块122和再水化模块124的特定功能可以由多个或一 个模块提供。如上所述的操作虽然进行了功能性或逻辑性的描述，但是可以实施为存储在一 个或多个计算机可读介质上并且由处理器执行的计算机程序。例如，计算机可读存储介 质包括任何类型的盘，例如软盘、光盘、CD-ROM、磁光盘、只读存储器(ROM)、随机 存取存储器(RAM)、EPROM> EEPROM、磁或光卡、专用集成电路(ASIC)或适于存储 电子指令的任何类型的介质，并且均耦合至计算机系统总线。此外，本说明书中所引用 的计算机可以包括单个计算机，或者可以是采用多个处理器涉及用于增强计算能力的结 构。在整个说明书中，使用诸如“处理”或“计算处理”或“计算”或“确定” 或“显示”等的术语进行的讨论，指得是特定计算机系统或类似电子计算设备的步骤或 处理，所述设备将表示或建模物理特征的数据操作和转换为表示了计算机系统存储器或 寄存器或其它这种信息存储、发射或显示设备中的物理(电子)量。上述的算法和显示器并非固有地涉及任何特定计算机或其它装置。通过使用本文的教导，还可以修改各种通用系统，或者其可以证明是便于构建更专用的装置以执行 所述的方法步骤。根据上述说明书，将出现各种这些系统的所需结构。此外，并未参考 任何特定的编程语言描述本发明，可以由实施者选择任何合适的编程语言。
最后，应当注意到，原则上处于可读性和指导性目的而选择本说明书中使用的 语言，并且并未选择以限定或限制本发明的主题。因此，本发明的公开内容意欲是说明 性的，而非限制本发明的范围。
权利要求
1.一种用于简化原始导航路径的方法，所述导航路径具有起点和终点，并且由多个 链路表示，每个链路连接多个节点，该方法包括对于原始路径的每个节点确定沿着到达该节点的路径的第一链路的航向；确定沿着离开所述节点的路径的第二链路的航向；响应于离开所述节点并且不在所述原始路径上的链路，在简化路径上放置面包屑， 所述面包屑包括对所述节点的坐标的表示以及当所述路径到达和离开所述面包屑时所述 路径的航向的表示，其中，所述原始路径具有的航向更平行于所述第一链路而不是所述 第二链路；以及在所述路径的结束处放置面包屑，所述路径的结束处的面包屑具有所述路径的终点 的位置坐标以及当所述路径到达所述面包屑时所述路径的航向。
2.根据权利要求1所述的方法，还包括在所述简化路径的开始处放置面包屑，所述面 包屑具有所述起点的位置坐标以及当所述路径离开所述面包屑时所述路径的航向。
3.一种用于根据简化的路径描述确定原始导航路径的方法，所述简化的描述包括多 个面包屑，每个面包屑包括沿着所述路径的位置坐标、以及到达航向和离开航向中的至 少一个，所述方法包括确定所述原始路径的起点作为所述简化路径中通过面包屑的坐标所标识的点，并且 所标识的点被标注为表示所述起点；选择最接近平行于由表示所述起点的面包屑指定的离开航向的链路作为所述原始路 径中的链路；对于选择作为所述原始路径中链路的链路的终点处的每个节点 将所选择的链路的终点处的节点插入所述原始路径中；响应于在具有标识所述节点的坐标的简化路径中没有面包屑，选择最平行于到达所 述节点的链路的离开该节点的链路作为所述原始路径中的下一链路；响应于具有标识所述节点的坐标的简化路径中的面包屑中的一个，选择最平行于匹 配面包屑的离开航向的离开所述节点的链路作为所述原始路径中的下一链路；以及 在导航设备的用户界面中显示所述原始路径。
4.一种用于简化原始导航路径的计算机程序产品，所述导航路径具有起点和终点， 并且由多个链路表示，每个链路连接多个节点，所述计算机程序产品存储在计算机可读 介质上，并且包括指令，所述指令被配置为使得计算机执行如下步骤对于原始路径的每个节点 确定沿着到达节点的路径的第一链路的航向； 确定沿着离开所述节点的路径的第二链路的航向；响应于离开所述节点并且不在所述原始路径上的链路，在简化路径上放置面包屑， 所述面包屑包括对所述节点的坐标的表示以及当所述路径到达和离开所述面包屑时所述 路径的航向的表示，其中，所述原始路径具有的航向更平行于所述第一链路而不是所述 第二链路；以及在所述路径的结束处放置面包屑，所述路径的结束处的面包屑具有所述路径的终点 的位置坐标以及当所述路径到达所述面包屑时所述路径的航向。
全文摘要
路径脱水允许发射路径的描述，与路径的完整描述相比，其需要更少空间。一系列“面包屑”和线索用于脱水。面包屑包括点坐标、路径到达面包屑处的航向以及路径离开面包屑处的航向。脱水模块在标记路径起点的位置放置面包屑，并且具有标识原始路径中链路的离开航向。检查原始路径中每个链路终点处的节点。如果离开节点的链路是与到达节点的链路最平行的链路，对已脱水路径未增加任何内容。如果不是，对脱水路径增加面包屑，从而指定点的坐标、面包屑的到达航向以及面包屑的离开航向。
文档编号G01C21/34GK102016508SQ200980115975
公开日2011年4月13日 申请日期2009年4月1日 优先权日2008年4月1日
发明者R·F·波彭 申请人:德卡尔塔公司