专利名称：产生和使用栅格地图路径的设备和方法
技术领域：
一个或多个实施例涉及一种路径搜索系统，更具体地讲，涉及一种产生和使用栅 格地图(grid map)中的障碍规避路径的设备和方法。
背景技术：
通常使用栅格地图来设置移动对象(诸如移动机器人)的运动路径。栅格地图将 移动对象运动的周围区域划分为更小的可限定的区域或栅格，并且可使用可限定的概率来 表现每个栅格中对象存在的可能性。为了运动到特定位置，移动对象使用栅格地图沿路径 运动到该位置，从而不与障碍碰撞。移动机器人(诸如清洁机器人)可能感兴趣的传统的 特定位置是用于自动充电的充电站或者用于特定任务的特定位置。通常，在产生将被移动目标使用的路径期间，一般期望找到从起点到终点的最短 路径，因此顺序检测从起点到终点的许多(可能不是全部)可用的路径。当栅格地图不大 时，这种路径搜索的计算量对于将被快速产生的适当路径来说不是很大。然而，栅格地图越 大，栅格数量越多。因此，需要的存储量和计算量与栅格地图的大小成比例地增加。其结果 是，具有有限存储和处理能力的设备(诸如具有嵌入式系统的设备)难以快速地找到适当 路径。

发明内容
一个或多个实施例涉及这样一种设备和方法，即，可减少使用栅格地图搜索路径 所需的存储容量以及根据搜索到路径使移动目标运动的该路径的使用。根据一个或多个实施例，提供一种产生路径的设备，包括路径产生器，基于通过 缩小地图而产生的缩小的地图，为相对于地图移动的对象产生近似路径，基于近似路径的 划分将地图划分为多个部分，并且基于近似路径在每个划分的部分中产生详细路径。根据一个或多个实施例，提供一种在地图中产生对象的路径的方法，包括在通过 缩小地图而产生的缩小的地图内产生近似路径；基于近似路径的划分将地图划分为多个部 分；基于近似路径在每个划分的部分中产生详细路径。根据一个或多个实施例，提供一种产生路径的设备，包括路径产生器，为相对于 地图移动的对象产生缩小的地图的近似路径，基于将缩小的地图的近似路径映射到地图来 将地图划分为多个部分，分别通过至少一种搜索算法在每个划分部分中产生详细路径，其 中，路径产生器还基于近似路径上的点在每个划分部分中设置开始路点和目的路点，并使 用每个设置的开始路点和目的路点基于应用于每个划分部分的路径产生算法在每个划分 部分中产生详细路径。根据一个或多个实施例，提供一种产生路径的方法，包括为相对于地图移动的对象产生缩小的地图的近似路径；基于将缩小的地图的近似路径映射到地图来将地图换分为 多个部分；分别通过至少一种搜索算法在每个划分部分中产生详细路径，其中，划分地图的 步骤还包括基于近似路径上的点在每个划分部分中设置开始路点和目的路点，并使用每 个设置的开始路点和目的路点基于应用于每个划分部分的路径产生算法在每个划分部分 中产生详细路径。在下面的描述中将部分地阐明本发明另外的方面和/或优点，通过描述部分地会 变得更加清楚，或者通过实施本发明可以了解。


通过下面结合附图对实施例进行的描述，本发明的这些和/或其他方面和优点将 会变得清楚和更易于理解，其中图1示出根据一个或多个实施例的用于产生路径的设备；图2A示出通过缩小栅格地图来产生详细路径的传统方法；图2B示出根据一个或多个实施例的缩小栅格地图以产生适当路径的方法；图3示出根据一个或多个实施例的路径产生处理的结果；图4示出根据一个或多个实施例的产生详细路径的处理；图5是根据一个或多个实施例的栅格地图的示例，其中，映射到原始栅格地图的 适当路径已被划分为多个部分以产生详细路径；图6示出根据一个或多个实施例的产生路径的处理；图7详细示出根据一个或多个实施例的诸如图6所示的路径产生方法。
具体实施例方式现在对实施例进行详细的描述，其示例示出在附图中，其中，相同的标号始终表示 相同部件。就此而言，本发明的实施例可以以许多不同形式被实现，而不应被解释为限制于 这里阐述的实施例。因此，下面仅是通过参照附图对实施例进行描述以解释本发明的各方图1是根据一个或多个实施例的用于产生路径的设备的框图。这里，贯穿以下的 描述，术语“设备”在所有实施例中应该与物理系统的部件同义地理解，不限于单个封装或 在各单个封装中实现的所有所述部件，相反，根据实施例，该术语公开为通过不同部件在不 同封装和/或位置中一起或分开实现。仅作为另一示例，各设备/系统或方法还可通过一 个或多个处理部件/装置来控制或者通过分布式网络来实现，注意，另外的和替换的实施 例同样可用。此外，在实施例中，用于产生路径的设备还是移动机器人，其另外包括用于栅格地 图产生的传感部件和使移动机器人根据产生的路径运动的运动部件。在实施例中，产生适 当栅格地图的处理还可包括使移动机器人沿该路径运动。此外，虽然这里可关于移动机器 人来讨论实施例，但是，当例如机器人周围的运动以与障碍边缘或区域无限或有限的交互 作用来实现时，实施例同样可用于固定机器人。在实施例中，移动机器人同样可以是计算机 产生的空间中的虚拟形象。因此，如图1所示，用于产生路径的设备100可包括例如路径产生器110和存储器
7120。简言之，如上所述，设备100还可以是移动机器人，并且包括用于使移动机器人根据产 生的路径运动的运动部件。为了解释的目的，这里没有另外讨论这种根据路径的运动控制， 尽管其可理解为适当的实施例。可以在题为“Method and apparatus for moving along shortest movement pathusing grid map”的第2004-0116864号美国专利公开找到至少这 种控制和运动部件的讨论，该专利公开包含于此。此外，尽管在这里针对基于栅格识别定位 系统的地图进行实施例的讨论，但是可实现基于替换的位置识别系统来区分障碍位置或障 碍区域和非障碍区域，例如，相对于地图中的移动对象和其它对象的位置。路径产生器110首先基于通过缩小原始栅格地图产生的缩小的栅格地图来产生 近似路径，将原始栅格地图的近似路径划分为多个部分，然后在各个划分部分中产生详细 路径。其后，这样的多个详细路径可被组合以产生原始栅格地图的详细路径。路径产生器 110可使用多种路径产生方法，但是为了简单起见，在实施例中，可建设使用A星(A-star) (A*)算法来产生路径。作为替换，仅作为示例，可使用D星(D-star) (D*)算法、不同算法或 不同算法的组合来产生路径。简言之，A星算法是最佳优先图形搜索算法，该算法从给定的初始节点到(一个或 多个可能目标中的)一个目标节点中搜索最小成本路径。可以以成本增加的次序顺序检 测从开始点到目的点的所有可能路径。因此，A星使用距离加成本启发函数(通常表示为 f(x))来确定搜索树中的访问节点的次序。距离加成本启发可以是两个函数的和从开始 节点到当前节点的成本的路径成本函数(通常表示为g(x))；到目标的距离的可接受“启 发估计”(通常表示为 h(x))。可以在 Hart，P. E.，Nilsson，N. J. , Raphael, B.，“A Formal Basis for the HeuristicDetermination of Minimum Cost Paths", IEEE Transactions of Systems Scienceand Cybernetics，vol. ssc_4，No. 2 中找至lj合并于此的最早的讨论 或A星算法。D星算法是A星算法的变型，当在行进期间发生近似路径中的方向改变时，允 许通过重新使用先前的搜索结果来进行快速搜索。然而，在实际实现中，使用图像金字塔 (Image Pyramid)的A星算法通常显示出比D星算法更快的处理速度。应该注意，可以在不 同的划分的栅格地图之间使用不同的算法，但效率可能更低。这里，例如，因为可将先前的 路径结果用于随后的搜索，所以先前的搜索算法和当前的搜索算法不必相同。在“Optimal and Efficient PathPlanning for Partially-Known Environments，，，Proceeding of the InternationalConference on Robotics and Automation, Stentz，Anthony (1994)中讨 论了合并于此的 D 星算法。相似地，还在 H.Choset，K. Lynch, S. Hutchinson, G. Kan tor, W.Burgard,L. Kavraki,and S.Thrun, “ Principles of Robot Motion，“ pp.527 536 中讨论了合并于此的A星算法、D星算法以及其他搜索算法。这里，应该注意“Principles of Robot Motion”(机器人运动原理)还解释了关于移动机器人跟随限定的路径的处理的 合并的讨论。因此，存储器120可存储用于路径产生的栅格地图、设备100操作所需的应用数据 等，注意，用于各个数据或组合数据的替换存储部件同样可用。这里，在实施例中，存储器 120可包括允许写入和读取在路径产生器110的路径产生操作中产生的数据的足够可用的 存储空间。路径产生器110可包括例如地图缩小器112、近似路径产生器114和详细路径产生 器 116。
8
通常，栅格地图包括指示在特定位置或区域存在障碍的概率的信息。可通过例如 距离传感器(诸如红外传感器、超声波传感器或激光传感器)来获得该信息。在这种栅格 地图中，通常不考虑移动对象的大小。因此，当移动对象使用栅格地图行进时，即使限定路 径不与障碍或障碍区域碰撞，移动对象的边缘仍可能与障碍撞击或碰撞。因此，在实施例 中，地图缩小器112通过在新产生的缩小的栅格地图中将移动对象缩小为一点，并相应地 在产生的缩小的栅格地图中增加墙壁或边缘的厚度以及障碍或障碍区域，来考虑移动对象 的大小。从而还可在缩小的栅格地图的栅格地图中同样地限定缩小的栅格地图的自由区域 (即，移动对象可不与障碍或障碍区域碰撞不受限制地运动的区域)。在实施例中，地图缩小器112可通过缩小栅格地图来产生缩小的栅格地图，例如， 通过实现抗混叠(anti-aliasing)滤波处理来包括关于确定的自由区域的信息。当限定将在产生缩小的栅格地图中实现的缩小时，可依赖另外的或替换的因素。 例如，当移动对象的大小为20cm，lcm的栅格单元可映射到1点，如果原始栅格地图的缩小 率为1/20或更小，则存在的障碍不能适当地反映在缩小的栅格地图中。因此，在这种情况 下，栅格地图的缩小率可限于移动对象的大小映射到1点的缩小率。可基于移动对象的大 小考虑栅格地图的归一化。简言之，在实施例中，在路径近似之前增加墙壁或障碍的宽度的 原因可用于移动对象必须在距离墙壁或障碍预定空间内运动的情况。此外，与增加墙壁或 障碍的宽度相反，还可减小墙壁或障碍的宽度，在这种情况下，可基于最短路径执行路径规 划，在该最短路径上，至少防止移动对象与墙壁或障碍的碰撞。因此，可通过根据缩小的栅格地图相对于原始栅格地图的缩小进行转换，来在缩 小的栅格地图中表现期望设置最终路径的任何原始开始点和目的点的坐标。例如，当原始 栅格地图线性地缩小1/N2时，各个坐标可仅乘以1/N。因此，对于开始点和目的点，它们各 自的坐标可以乘以1/N，并且可以在缩小的栅格地图内搜索与转换的坐标最近的自由区域 中的坐标，即，如果开始点和目的坐标的相乘操作导致在缩小的栅格地图的障碍区域中相 同的反映，则设置为缩小的栅格地图开始点和目的点。虽然已经讨论线性缩小，但是也可进行原始栅格地图的非线性缩小。在这种实施 例中，如果特定栅格地图已被非线性地缩小并且进行路径规划，则当为了路径搜索放大地 图时，可期望栅格地图与非线性缩小成反比地非线性放大，而不是简单地放大两倍(x2)。近似路径产生器114可在缩小的栅格地图中产生从缩小的栅格地图开始点到缩 小的栅格地图目的点的近似路径。例如，可使用A星算法搜索从相应设置的开始点到设置 的目的点的近似路径。详细路径产生器116可随后将找到的路径划分为两个或更多个部分，并在原始栅 格地图中开始搜索从每个划分部分中的各个开始点到目的点的路径，这些详细路径一起的 组合用于产生原始栅格地图的完整的详细路径。这些进行的搜索可以是映射到原始栅格地 图的近似栅格地图的细节，或者是基于近似栅格地图设置的每个划分部分的各个开始点和 终点。以下将更详细地描述产生详细路径的操作。首先，在实施例中，可以在地图缩小器112的缩小操作之前，详细路径产生器116 将近似路径中的路点(waypoint)映射到包括自由区域信息的栅格地图。在图4的栅格地图 410中可以看到示例路点31和32，路点是移动对象在开始点和目的点之间的运动点。移动 对象可使用每个路点作为各个目的点，并从一个路点运动到另一个路点。映射操作的结果是，从缩小的栅格地图映射到原始栅格地图的部分路点(或者甚至是开始点和目的点)可 能被映射到移动对象可运动的自由区域的外部，例如，障碍或障碍区域之内。因此，详细路 径产生器116检查任何映射的路点是否位于原始栅格地图的自由区域的外部。当部分路点 位于自由区域的外部时，它们被移动到例如原始栅格地图的自由区域中的最接近的位置。随后，详细路径产生器116将从缩小的栅格地图产生的近似路径划分为多个部 分，在原始栅格地图的每个相应划分的部分中设置开始点和目的点，并在每个划分部分中 重置路径，每个划分部分的组合用于产生最终的详细路径。在实施例中，详细路径产生器116可基于用于路径计算的可用存储空间的大小和 /或处理能力，将路径划分为多个部分，例如，划分为具有各自大小的确定数量的部分。例 如，当使用A星算法执行路径搜索时，一个栅格所需的存储量通常为18字节。因此，当在 栅格地图的路点中确定开始点和目的点时，可计算路径计算所需的存储量。这里，在实施 例中，还应注意，对于这种将路径划分为各个部分，可采用用于所有部分的并行路径产生处 理，从而可以在明显短于使用单个路径产生处理的传统路径产生的时间内产生整个详细路 径。例如，不是将近似路径映射回到原始栅格地图并划分原始栅格地图，而是可将原始栅格 地图划分为基于划分的近似路径的局部地图，并可对每个局部栅格地图应用适当的搜索算 法，例如，A星算法。然后，每个局部栅格地图的所得的详细路径可分别由移动对象以通过 在原始栅格地图中行进所需的完整路径的顺序使用。以下，假设近似路点从缩小的栅格地图映射到原始栅格地图，移动到自由区域的 路点由Ps、Ps+1.....Ps+N (其中N是自然数)表示，Ps是开始点，Ps+N是目的点。详细路径产生器116可限定具有路点(例如PS+1Q)作为目的点的部分，并使用包 括限定的部分的栅格地图，其中，Ps+1(l存在于位于自由区域中的原始开始点Ps和目的点Ps+N 之间的路点中，并且用于计算从开始点Ps到Ps+1(l的路径的存储器大小不超过可用的存储器 大小。其后，详细路径产生器116可相似地限定具有路点Ps+1(l作为开始点和路点(例如， Ps+2。)作为目的点的部分，并使用包括该限定部分栅格地图产生详细路径，其中，Ps+1(l是前 一部分的目的点，并且用于计算从Ps+1。到Ps+2。的路径的存储器大小不超过可用的存储器大 小。同样地，可限定从开始点到原始目的点Ps+N的最后部分，并可产生在该限定部分中的详 细路径。此时，可限定诸如彼此部分重叠的部分。例如，当第一部分的目的点是Ps+Kl时，第 二部分的开始点可能设置为Ps+9。详细路径产生器116可通过组合以这种方式设置的特定 部分的详细路径来产生最终详细路径。详细路径产生器116还可选择位于方向变化点的改变点，其中，方向变化点存在 于位于最终详细路径上的路点中。移动对象可沿使用关于开始点、目的点和选择的改变点 的信息在栅格地图中产生的路径运动。这里，移动对象可以是物理移动机器人或预定对象， 例如，游戏应用中的角色或虚拟形象，它们被设置为沿路径搜索应用搜索到的路径移动。路径产生器110或设备100还可以是各种电子装置，诸如移动电话、便携式媒体播 放器(PMP)或个人数字助理(PDA)，或者是诸如移动机器人的移动对象，其可使用一个处理 装置产生路径并移动。如上所述，当路径产生器110由移动机器人实现时，移动机器人还可 包括传感单元、行进单元等，其中，传感单元用于产生栅格地图，检测移动对象的运动量等， 行进单元用于使移动对象运动。传感单元可用于产生移动对象周围的二维或三维地图，从而可能产生移动机器人周围的原始栅格地图的全部或部分。如上所述，根据一个或多个实施例，可缩小栅格地图并在缩小的栅格地图内产生 近似路径。还可将近似路径划分为在原始栅格地图中反映的多个路径和路径部分。因此， 还可在原始栅格地图的划分部分中搜索详细路径，最终组合为原始栅格地图内的最终详细 路径。因此，与通过分析整个原始栅格地图一下搜索整个路径的方法相比，通过例如重 复使用较小的存储量，可以与栅格地图缩小的比率成比例地减少路径搜索所需的存储量。 因为在缩小的栅格地图中搜索路径或者对于整个栅格地图搜索特定部分的路径，所以与搜 索整个栅格地图的路径的传统方法相比，路径搜索花费的时间减少。图2A示出通过缩小栅格地图来产生详细路径的传统方法，图2B示出根据一个或 多个实施例的缩小栅格地图以产生各个详细路径的方法。当从原始栅格地图产生包括关于对象可不受限制地运动的区域的自由区域信息 的栅格地图时，可执行例如将栅格地图缩小1/N2的处理。图2A和图2B都示出了将栅格地 图缩小1/4的方法。图2A示出产生存储器需求和处理要求较低的路径的处理，其中，仅通过缩小原始 栅格地图来产生缩小的栅格地图220，例如，通过提取仅关于原始栅格地图210的四分之一 的信息，并且计算缩小的栅格地图220内或从缩小的栅格地图220计算适当的详细路径。然 而，根据该方法，如图2A所示，使用原始信息中仅关于A、C、I和K的信息，关于其余部分的 信息被丢弃。因此，由于关于原始栅格地图的信息的损失，很可能在这种栅格地图缩小处理 中不能产生最精确的最终详细路径。可选择地，图2B示出根据一个或多个实施例的通过抗混叠滤波来缩小栅格地图 的方法。根据实施，栅格地图230的栅格以四个为一组，计算特定组的平均值，从而产生缩 小的栅格地图240。然后，将平均值与阈值比较。当平均值满足阈值时，例如，等于阈值或大 于阈值时，可将相应的栅格的值设置为1 ；当平均值不满足阈值时，例如，小于阈值时，可将 相应的栅格的值设置为0。这里，在该示例中，栅格值1表示存在障碍，栅格值0表示没有障 碍。图3示出根据一个或多个实施例的路径产生处理的结果。栅格地图310至340中的空白区域表示移动对象可移动的区域，而阴影区域表示 障碍区域。在原始栅格地图310中，示出从开始点10到目的点20的路径30。已经通过使用图2A示出的缩小将原始栅格地图310缩小1/4，获得了栅格地图 320。因此，栅格地图320进一步解释了图2A中的路径产生过程。但是，采用这种缩小和路 径产生过程，栅格地图310中的路径30在栅格地图320中不能被重新产生，这是因为关于 原始栅格地图310的信息已经丢失。换句话说，当通过仅提取原始栅格地图310的四分之 一的信息来产生这样缩小的栅格地图320时，障碍信息丢失。因此，由于开始点和目的地之 间的必要路径需要穿过障碍或障碍区域，导致必要路径不能被实际使用，所以不可能产生 正确的最终详细路径。或者，虽然图2A中的缩小处理可采用实施例中的进一步描述的部分划分处理被 实现，但是如果通过抗混叠滤波来实现图2B中的缩小处理，则可产生缩小的栅格地图340， 而没有信息的丢失。如上所述，栅格地图330中所示的平均值与阈值比较。当平均值满足阈值时，相应栅格的值被设置为1，当平均值不满足阈值时，相应栅格的值被设置为0。然 后，产生缩小的栅格地图，诸如绘图340。由于栅格地图340比栅格地图320丢失较少的障 碍信息，所以例如原始栅格地图310中的路径40仍然可以被产生。图4示出了根据一个或多个实施例的产生最终详细路径的过程。在栅格地图410至栅格地图430中，障碍边界402外部的阴影区域401表示障碍 区域的边缘，障碍边界402内部的阴影区域403表示移动对象可无限制地移动的自由区域。如上所述，当在缩小的地图中寻找到的路径被映射回原始栅格地图上时，路点31 和32可被映射到自由区域外部，如图4的栅格地图410所示。根据实施例，可确定这样的路点是否位于自由区域的外部。当路点位于自由区域 的外部时，这些路点可分别移动到与自由区域的路点最接近的位置。栅格地图420示出了 映射到自由区域中的路点的路点31和32。然而，如栅格地图430所示，当栅格地图420的这些映射的路点被连接时，可产生 穿过一个区域的直线路径，其中，移动对象不能穿过该区域，如栅格地图430中的放大部分 435所示。这里，放大部分435示出了移动对象的直线路径潜在地超出了放大部分435的限 定的自由区域。因此，在实施例中，根据实施例，在缩小的栅格地图中产生的近似路径在原 始栅格地图中被重新设计，即，近似路径的相应部分(将被映射回原始栅格地图以用于部 分路径产生)可被重新限定为仅穿过限定的自由区域。此时，例如，当完成了缩小的栅格地图中的近似路径时，考虑到例如用于执行如上 所述的用于路径搜索的A星算法的存储器大小，近似路径被划分为多个部分，并且在原始 栅格地图的各个部分执行路径搜索，由此产生最终详细路径。当近似路径被映射回原始栅 格地图时，可在缩小的栅格地图或原始栅格地图内发生近似路径的划分。图5是根据一个或多个实施例的栅格地图的示例，在该栅格地图中，近似路径(例 如，被映射回相应的原始栅格地图的近似路径)被划分为多个部分以产生最终详细路径。当采用各个划分的栅格地图中的部分路径执行路径搜索操作时(其中，各个划分 的栅格地图从原始栅格地图被划分为前面描述的多个部分)，在限定划分时，用于执行路径 搜索算法(例如A星算法)的可用存储器空间的大小可被考虑。根据实施例，当可使用A 星算法寻找路径的最大栅格大小为Sx(X轴栅格大小)XSy(Y轴栅格大小)时，在SxXSY范 围内从开始点Ps到路点PE的部分可被确定为一个集合。这里，例如，Sx* SY可在可用存储 器大小的范围内变化。在图5中，在每个栅格地图部分512、514和516中执行路径搜索，其 中，每个栅格地图部分包括通过划分原始栅格地图510而获得的部分。例如，当可使用A星 算法寻找路径的最大栅格大小为128X 128个栅格点时，图4的绘图410至绘图430中的路 点可按照如图5所示被分类。更具体地，在图5中，路点501表示开始路点，路点504表示原始栅格地图的最终 详细路径的目的路点。路点502和503表示参考路点，路径部分通过这些参考路点被划分。 在图5中，从路点501到路点502的部分可被设置为第一部分，从路点502到路点503的部 分可被设置为第二部分，从路点503到路点504的部分可被设置为第三部分，可在每个部分 中寻找详细路径。在各个部分中寻找的路径随后可被组合，以产生最终详细路径。图6示出了根据一个或多个实施例的产生路径的过程。通过缩小栅格地图来产生缩小的栅格地图(操作610)。基于缩小的栅格地图产生近似路径(操作620)。近似路径被划分为多个部分(操作630)。此时，在实施例中，基于 可用存储器的大小来划分近似路径，在可用存储器中执行在路径产生过程中产生的数据的 写入和读取。在各个划分的部分中产生详细路径(操作640)。从这些详细路径产生最终详 细路径。图7是更详细地示出根据一个或多个实施例的路径产生方法(例如图6中示出的 路径产生方法)的流程图。考虑到从栅格地图产生的路径和移动对象的大小确定自由区域(移动对象可在 自由区域中无限制地移动)，并且通过缩小包括关于自由区域的信息的栅格地图来产生缩 小的栅格地图(操作710)。然后，可基于缩小的栅格地图寻找近似路径(操作720)。然后，在寻找到的近似路径中的路点可被映射到原始栅格地图(操作730)。当映 射的路点中的一部分路点位于自由区域外部时(操作740)，每个相应的路点可被移动到自 由区域中的最接近的位置(操作750)。通过将映射的路点分类，将映射(即，映射回原始栅格地图)的近似路径划分为多 个部分(操作760)。在每个划分的部分中设置开始点和目的点，并且可在每个部分中产生 详细路径(操作770)。然后，可通过将特定部分的详细路径组合来产生最终详细路径(操 作780)。最后，如果最终详细路径的部分不偏离先前产生的部分路径，则所述最终详细路径 的部分可被重新应用到随后的最终详细路径。除了上述实施例之外，也可通过介质(例如计算机可读介质)中/上的计算机可 读代码/指令来实现实施例，计算机可读代码/指令用于控制至少一个处理装置以实现上 述任何实施例。介质可与允许存储和/或传输计算机可读代码的任何限定的、可测量的有 形结构对应。计算机可读代码可通过各种方式被记录/传送到介质上，介质的示例包括记录 介质，诸如磁存储介质(例如ROM、软盘、硬盘等)和光学记录介质(例如⑶-ROM或DVD)； 非临时传输介质，诸如携带或包括载波的介质及例如互联网的硬件部件。因此，根据本发明 的实施例，介质是包括或携带信号或信息的限定的、可测量的非临时结构(例如，携带比特 流的装置)。介质还可以是分布的网络，从而计算机可读代码按照分布式方式被存储和执 行。此外，仅仅作为示例，处理部件可包括处理器或计算机处理器，处理部件可分布和/或 包括在单个装置中。尽管已经参照本发明的不同实施例示出和描述了本发明的各方面，但是应该理 解，这些实施例应该被仅按照描述性意义被考虑，而不是为了限制的目的。每个实施例范中 的特征或方面的描述一般应该被视为对于其它实施例中的其它类似特征或方面是可用的。因此，虽然已经出和描述了一些实施例，并且可等同地获得另外的实施例，但是本 领域技术人员应该理解，在不脱离权利要求及其等同物限定其范围的本发明的原理和精神 的情况下，可以对这些实施例进行改变。
权利要求
一种产生路径的设备，包括路径产生器，基于通过缩小地图而产生的缩小的地图，为相对于地图移动的对象产生近似路径，基于近似路径的划分将地图划分为多个部分，并且基于近似路径在每个划分的部分中产生详细路径。
2.根据权利要求1所述的设备，其中，地图包括障碍和自由区域的信息，其中，对象能 够在自由区域中无限制地移动而不与障碍碰撞。
3.根据权利要求1所述的设备，其中，路径产生器考虑移动对象的大小在地图中确定 对象能够无限制地移动而不与障碍碰撞的自由区域，并且通过缩小包括关于确定的自由区 域的信息的地图来产生缩小的地图。
4.根据权利要求3所述的设备，其中，地图是栅格地图，并且路径产生器通过对来自栅 格地图的不同栅格的信息分别进行抗混叠滤波来缩小栅格地图。
5.根据权利要求4所述的设备，其中，在划分地图之前，路径产生器将缩小的地图中产 生的近似路径中的路点映射到地图，以产生详细路径。
6.根据权利要求3所述的设备，其中，在划分地图之前，路径产生器将缩小的地图中产 生的近似路径中的路点映射到地图，以产生详细路径。
7.根据权利要求6所述的设备，其中，当映射的路点中的一个或多个路点位于地图中 的自由区域外部时，路径产生器将位于自由区域外部的所述一个或多个路点分别移动到与 自由区域中的路点最接近的位置。
8.根据权利要求6所述的设备，其中，当路径产生器基于近似路径的划分将地图划分 为划分的部分时，路径产生器根据多个划分的部分中的各个划分的部分将映射到地图的路 点分类，在每个划分的部分中分别设置开始路点和目的路点，在每个划分的部分中产生详 细路径，并且通过顺序组合每个详细路径来产生最终详细路径。
9.根据权利要求8所述的设备，其中，至少一个划分的部分的目的路点与另一划分的 部分的开始路点重叠。
10.根据权利要求1所述的设备，其中，地图是栅格地图，并且路径产生器使用栅格地 图的确定的自由区域的每个栅格来缩小栅格地图。
11.根据权利要求1所述的设备，其中，地图的缩小是地图的线性缩小。
12.根据权利要求1所述的设备，其中，地图的缩小被限制为根据对象的大小对地图进 行归一化。
13.根据权利要求1所述的设备，其中，在划分地图之前，路径产生器将从缩小的地图 中产生的近似路径中的路点映射到地图，以产生详细路径。
14.根据权利要求1所述的设备，还包括存储器，在所述存储器中执行在路径产生器 的操作中产生的数据的写入和读取。
15.根据权利要求14所述的设备，其中，路径产生器基于存储器的可用空间将近似路 径划分为划分的部分。
16.根据权利要求14所述的设备，其中，通过至少一个搜索算法分别并行执行各个划 分的部分中的每个详细路径的产生。
17.根据权利要求1所述的设备，其中，通过至少一个搜索算法分别并行执行各个划分 的部分中的每个详细路径的产生。
18.根据权利要求1所述的设备，其中，移动对象是移动机器人，所述移动机器人被控 制为沿着详细路径顺序移动。
19.根据权利要求1所述的设备，其中，移动对象是计算机产生的环境中的虚拟形象。
20.根据权利要求1所述的设备，其中，所述设备是蜂窝电话、便携式媒体播放器和个 人数字助理中的一种。
21.—种在地图中产生对象的路径的方法，包括在通过缩小地图而产生的缩小的地图内产生近似路径；基于近似路径的划分将地图划分为多个部分；基于近似路径在每个划分的部分中产生详细路径。
22.根据权利要求21所述的方法，其中，地图包括障碍和自由区域的信息，其中，对象 能够在自由区域中无限制地移动而不与障碍碰撞。
23.根据权利要求21所述的方法，还包括通过考虑移动对象的大小在地图中确定对 象能够无限制地移动而不与障碍碰撞的自由区域，并且通过缩小包括关于确定的自由区域 的信息的地图，来产生缩小的地图。
24.根据权利要求23所述的方法，其中，地图是栅格地图，并且通过对来自栅格地图的 不同栅格的信息分别进行抗混叠滤波来执行栅格地图的缩小。
25.根据权利要求21所述的方法，其中，划分近似路径的步骤包括将近似路径中的路 点映射到地图。
26.根据权利要求25所述的方法，其中，划分地图的步骤还包括当映射的路点中的一 个或多个路点位于地图的自由区域外部时，将位于自由区域外部的所述一个或多个路点分 别移动到与自由区域中的路点最接近的位置。
27.根据权利要求25所述的方法，其中，划分地图的步骤还包括根据划分的部分将映 射到地图的路点分类，产生每个详细路径的步骤包括在每个划分的部分中分别设置开始路点和目的路点， 在每个划分的部分中产生各个详细路径，并且通过顺序组合每个详细路径来产生最终详细 路径。
28.根据权利要求27所述的方法，其中，至少一个划分的部分的目的路点与另一划分 的部分的开始路点重叠。
29.根据权利要求25所述的方法，还包括通过考虑移动对象的大小在地图中确定对 象能够无限制地移动而不与障碍碰撞的自由区域，并且通过缩小包括关于确定的自由区域 的信息的地图，来产生缩小的地图。
30.根据权利要求21所述的方法，其中，地图是栅格地图，并且使用栅格地图的确定的 自由区域的每个栅格来缩小栅格地图。
31.根据权利要求21所述的方法，其中，地图的缩小是地图的线性缩小。
32.根据权利要求21所述的方法，其中，地图的缩小被限制为根据对象的大小对地图 进行归一化。
33.根据权利要求21所述的方法，还包括在划分地图之前，将从缩小的地图中产生的 近似路径中的路点映射到地图，以产生详细路径。
34.根据权利要求21所述的方法，其中，基于存储器的可用空间将地图划分为划分的部分。
35.根据权利要求34所述的方法，其中，通过至少一个搜索算法分别并行执行各个划 分的部分中的每个详细路径的产生。
36.根据权利要求21所述的方法，其中，通过至少一个搜索算法分别并行执行各个划 分的部分中的每个详细路径的产生。
37.根据权利要求21所述的方法，其中，所述对象是移动机器人，所述方法还包括控制移动机器人沿着详细路径顺序移动。
38.根据权利要求37所述的方法，还包括感测移动机器人的环境，并且使用地图中的 障碍信息和自由区域信息产生地图，其中，移动机器人能够在自由区域中无限制地移动而 不与障碍信息所表示的障碍碰撞。
39.根据权利要求21所述的方法，其中，所述对象是计算机产生的环境中的虚拟形象。
40.根据权利要求39所述的方法，还包括根据详细路径控制虚拟形象在产生环境内 移动。
41.一种产生路径的设备，包括路径产生器，为相对于地图移动的对象产生缩小的地图的近似路径，基于缩小的地图 的近似路径到地图的映射将地图划分为多个部分，并且分别通过至少一种搜索算法在每个 划分的部分中产生详细路径，其中，路径产生器还基于近似路径上的点在每个划分的部分中设置开始路点和目的路 点，并使用每个设置的开始路点和目的路点基于应用于每个划分的部分的路径产生算法在 每个划分的部分中产生详细路径。
42.根据权利要求41所述的设备，其中，路径产生算法是A星算法和D星算法中的至少 一种。
43.根据权利要求41所述的设备，其中，路径产生器考虑移动对象的大小在地图中确 定对象能够无限制地移动而不与障碍碰撞的自由区域，并且通过缩小包括关于确定的自由 区域的信息的地图来产生缩小的地图。
44.根据权利要求43所述的设备，其中，各个开始路点和目的路点在划分地图之前被 映射到地图，以产生详细路径。
45.根据权利要求43所述的设备，其中，当映射的路点中的一个或多个路点位于地图 中的自由区域外部时，路径产生器将位于自由区域外部的所述一个或多个路点分别移动到 与自由区域中的路点最接近的位置。
46.根据权利要求41所述的设备，其中，至少一个划分的部分的目的路点与另一划分 的部分的开始路点重叠。
47.一种产生路径的方法，包括为相对于地图移动的对象产生缩小的地图的近似路径，基于缩小的地图的近似路径到 地图的映射将地图划分为多个部分，并且分别通过至少一种搜索算法在每个划分的部分中 产生详细路径，其中，划分地图的步骤还包括基于近似路径上的点在每个划分的部分中设置开始路 点和目的路点，并使用每个设置的开始路点和目的路点基于应用于每个划分的部分的路径 产生算法在每个划分的部分中产生详细路径。
48.根据权利要求47所述的方法，其中，路径产生算法是A星算法和D星算法中的至少一种。
49.根据权利要求47所述的方法，还包括考虑移动对象的大小在地图中确定对象能 够无限制地移动而不与障碍碰撞的自由区域，并且通过缩小包括关于确定的自由区域的信 息的地图来产生缩小的地图。
50.根据权利要求49所述的方法，其中，各个开始路点和目的路点在划分地图之前被 映射到地图，以产生详细路径。
51.根据权利要求49所述的方法，其中，当映射的路点中的一个或多个路点位于地图 中的自由区域外部时，位于自由区域外部的所述一个或多个路点分别被移动到与自由区域 中的路点最接近的位置。
52.根据权利要求47所述的方法，其中，至少一个划分的部分的目的路点与另一划分 的部分的开始路点重叠。
53.至少一种计算机可读介质，所述介质包括用于控制至少一个处理装置执行权利要 求21所述的方法的计算机可读代码。
54.至少一种计算机可读介质，所述介质包括用于控制至少一个处理装置执行权利要 求47所述的方法的计算机可读代码。
全文摘要
提供一种使用有限的存储器大小来产生和使用栅格地图路径的设备和方法。基于通过缩小原始栅格地图而产生的缩小的栅格地图产生近似路径。然后，近似路径被映射到原始栅格地图，并且映射的路径基于用于路径计算的可用存储器大小被放大并被划分为多个部分。基于在每个划分的部分中设置的开始点和目的点，在每个部分中产生详细路径。
文档编号G01C21/34GK101900570SQ20101011010
公开日2010年12月1日 申请日期2010年2月20日 优先权日2009年2月18日
发明者李受珍, 郑尤然 申请人:三星电子株式会社