运动规划的制作方法-j9九游会真人

1.本发明涉及对机器人的运动规划，特别地但非排他性地用于对具有多个连杆(诸如机械臂)的机器人的碰撞检测和预防。


背景技术：

2.近年来，人们对机器人技术并且尤其是对柔性机器人越来越感兴趣，在柔性机器人中，机器人能够适应不断变化的环境(理想地是在实时条件下)。这在例如机器人将与人类一起工作的协作背景下尤其令人感兴趣，在协作背景下，环境可能是不可预测的。
3.机器人技术中的一个共同目标是执行运动规划，即，为机器人确定合适的路径，以便在以“工作空间”为特征的环境内从一个位置或状态运动到另一个位置或状态。
4.例如，这可能涉及使机械臂移动到包含需要分拣的物体的箱子、拾取其中一个物体、将该物体移动到另一个合适的容器、并且然后返回到箱子或某个其他位置。为了执行该过程，必须为机器人规划一条经由适当的过渡而经过这些状态(即，在基座处、在箱子处和接收容器处)中的每个状态的路径。该过程在本领域中通常被称为“运动规划”。
5.当对机器人进行运动规划时，涉及有诸多要考虑之处。优选的是，使机器人在状态之间平滑而有效地移动。如上所概述的，机器人可能需要与周围环境中的物体进行交互。然而，在许多应用中，机器人不与环境中的障碍物碰撞也是很重要的，该障碍物例如是环境中的静态物体、动态目标(诸如人、动物或其他机器人)以及其自身(“自身碰撞”)。因此，通常的目的是规划一条合适的、让机器人安全而有效地执行特定任务的路径。当然，在某些应用中，可能需要碰撞(collision)，例如在使用机器人来按下按钮或打开门的情况下。
6.运动规划中的一种常见策略是生成由数个节点(node)和边(edge)组成的“路线图”或“图形”，其中，路线图中的每个节点表示一个或更多个与机器人的状态相对应的变量，如下面的进一步细节中所概述的。图形中连接这些节点的边表示状态之间的过渡(transition)。可以使用本领域本身已知的图形搜索技术来找到期望的运动。
7.机器人的“配置”对应于关节角度，通常使用具有针对每个关节的元素(即矢量中的条目)的矢量对其进行描述，其中，每个元素对应于一个自由度，由此该矢量通常具有与关节数量相同的元素数量。
8.机器人的“姿势”对应于末端执行器的位置和方向，末端执行器可以具有例如6个自由度。可以根据配置计算姿势。给定的姿势往往可以通过数个配置来实现(如果关节的数量超过6个，则通常有无限多个配置可以实现给定的姿势)。
[0009]“配置空间”(或“c空间”)通常具有与关节数量相同数量的维度。
[0010]
本文中使用的与机器人有关的术语“状态”可以包括机器人的配置、机器人(或机器人的一部分)的速度和时间中的一者或多者。术语“过渡”是指这些不同状态之间的过渡(即位置、速度、时间等的变化)。
[0011]
工作空间(即机器人的环境的表示)通常被离散为许多“工作空间元素”，其中，这些元素可以是体素、像素、单元或类似物。本领域中已知的允许在在线运动规划期间有效地
使运动无效化的一种示例性方法是p.leven和s.hutchinson在2022年的《国际机器人研究杂志》的“变化环境中的实时路径规划框架(a framework for realtime path planning in changing environments)”一文中描述的“动态路线图”(drm)方法，其包括在离散化工作空间和路线图之间生成“映射”。该映射可以离线构建，并且包括关于哪些节点和边将导致与哪些工作空间元素的碰撞(通常是全部或部分)的信息。schumann-olsen，h.，bakken，m.，holhjem，和risholm，p.在2014年ieee在clutter举办的第三届机器人研讨会中的“用于在复杂动态场景中的实时运动规划的并行动态路线图(parallel dynamicroadmaps for real-time motion planning in complex dynamic scenes)”一文中描述了另一种方法，称为“并行drm”(pdrm)方法，其描述了如何构建和利用“结构化路线图”。
[0012]
在随后的在线规划过程中，映射可以用作查找表，并且路线图中的与工作空间中的障碍物碰撞的任何节点或边都将被无效化。静态障碍物的位置和环境的布局可能是预先已知的，而动态障碍物和环境的变化可以在在线操作期间进行检测，例如使用诸如3d传感器的传感器(例如，3d或“立体”相机)。可以在运行操作期间检测例如人、物体或其他机器人的位置和运动，和/或可以预测它们的行为。
[0013]
通常，为了针对给定任务规划路径，为具有路线图的规划器提供开始和结束状态，并使用路线图在该路线图之中寻找合适的无碰撞路径，例如，最短路径、最有效路径等，其中不考虑无效的节点和边。
[0014]
然而，遵循本领域本身已知的传统方法，对于给定的路线图、物理机器人设置和本地工作空间而言，映射是固定的。如果路线图、机器人和/或工作空间中的任何一者发生变化，则必须更改并重新制作整个映射。这还包括对机器人做出的任何物理更改，诸如添加的传感器、不同的夹爪(和夹爪状态)以及拾取的物体。这在计算上不是特别有效率的，并且导致了显著的内存需求以便在进行更改的情况下或者为了生成全新的映射来适应路线图、机器人和/或工作空间的更改而具有大量映射来覆盖“手头”部件的各种排列和组合。
[0015]
申请人已经意识到，将特别有利的是，提供更灵活的映射，使得可以改变路线图、机器人和/或机器人拾取的物体的物理范围、以及工作空间(或工作空间分辨率)，而不需要重新创建整个映射。


技术实现要素：

[0016]
当从第一方面来看时，本发明提供了一种执行对机器人的运动规划的方法，其中，机器人布置为在工作空间中的多个状态之间操作，所述工作空间由多个离散化的工作空间元素表示，其中，所述状态中的每个状态经由至少一个相应的过渡连接到至少一个其他状态，其中，该方法包括：
[0017]
生成或接收第一模型；
[0018]
确定第一集合，该第一集合包括对应于所述多个状态中的每个状态以及这些状态之间的相应过渡而与第一模型至少部分地碰撞的一个或更多个工作空间元素；
[0019]
生成第一映射，该第一映射包括关于所述第一集合以及使得第一模型与第一集合中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息；以及将所述第一映射存储在第一存储器区域中；
[0020]
生成或接收从第一模型延伸的第二模型；
[0021]
确定第二集合，该第二集合包括对应于所述多个状态中的每个状态以及这些状态之间的相应过渡而与第二模型至少部分地碰撞的、除了第一集合中的那些工作空间元素之外的一个或更多个另外的工作空间元素；以及
[0022]
生成第二映射，该第二映射包括关于所述第二集合以及使得第二模型与第二集合中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息；以及将所述第二映射存储在第二存储器区域中。
[0023]
本发明的第一方面延伸到一种运动规划器，该运动规划器布置为执行对机器人的运动规划，其中，机器人布置为在工作空间中的多个状态之间操作，所述工作空间由多个离散化的工作空间元素表示，其中，所述状态中的每个状态经由至少一个相应的过渡连接到至少一个其他状态，其中，该运动规划器布置为：
[0024]
生成或接收第一模型；
[0025]
确定第一集合，该第一集合包括对应于所述多个状态中的每个状态以及这些状态之间的相应过渡而与第一模型至少部分地碰撞的一个或更多个工作空间元素；
[0026]
生成第一映射，该第一映射包括关于所述第一集合以及使得第一模型与第一集合中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息；以及将所述第一映射存储在第一存储器区域中；
[0027]
生成或接收从第一模型延伸的第二模型；
[0028]
确定第二集合，该第二集合包括对应于所述多个状态中的每个状态以及这些状态之间的相应过渡而与第二模型至少部分地碰撞的、除了第一集合中的那些工作空间元素之外的一个或更多个另外的工作空间元素；以及
[0029]
生成第二映射，所述第二映射包括关于所述第二集合以及使得第二模型与第二集合中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息；以及将所述第二映射存储在第二存储器区域中。
[0030]
本发明的第一方面还延伸到包括上文概述的运动规划器的机器人。因此，本发明的第一方面延伸到一种机器人，该机器人布置为在工作空间中的多个状态之间操作，所述工作空间由多个离散化的工作空间元素表示，其中，所述状态中的每个状态经由至少一个相应的过渡连接到至少一个其他状态，其中，机器人还包括布置为执行对所述机器人的运动规划的运动规划器，该运动规划器被布置为：
[0031]
生成或接收第一模型；
[0032]
确定第一集合，该第一集合包括对应于所述多个状态中的每个状态以及这些状态之间的相应过渡而与第一模型至少部分地碰撞的一个或更多个工作空间元素；
[0033]
生成第一映射，该第一映射包括关于所述第一集合以及使得第一模型与第一集合中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息；以及将所述第一映射存储在第一存储器区域中；
[0034]
生成或接收从第一模型延伸的第二模型；
[0035]
确定第二集合，该第二集合包括对应于所述多个状态中的每个状态以及这些状态之间的相应过渡而与第二模型至少部分地碰撞的、除了第一集合中的那些工作空间元素之外的一个或更多个另外的工作空间元素；以及
[0036]
生成第二映射，该第二映射包括关于所述第二集合以及使得第二模型与第二集合
中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息，并且将所述第二映射存储在第二存储器区域中。
[0037]
本发明的第一方面进一步延伸到非暂时性计算机可读介质，该非暂时性计算机可读介质包括在由处理器执行时使得处理器执行进行对机器人的运动规划的方法的指令，其中，该机器人布置为在工作空间中的多个状态之间操作，所述工作空间由多个离散化的工作空间元素表示，其中，所述状态中的每个状态经由至少一个相应的过渡连接到至少一个其他状态，其中，该方法包括：
[0038]
生成或接收第一模型；
[0039]
确定第一集合，该第一集合包括对应于所述多个状态中的每个状态以及这些状态之间的相应过渡而与第一模型至少部分地碰撞的一个或更多个工作空间元素；
[0040]
生成第一映射，该第一映射包括关于所述第一集合以及使得第一模型与第一集合中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息，并且将所述第一映射存储在第一存储器区域中；
[0041]
生成或接收从第一模型延伸的第二模型；
[0042]
确定第二集合，该第二集合包括对应于所述多个状态中的每个状态以及这些状态之间的相应过渡而与第二模型至少部分地碰撞的、除了第一集合中的那些工作空间元素之外的一个或更多个另外的工作空间元素；以及
[0043]
生成第二映射，该第二映射包括关于所述第二集合以及使得第二模型与第二集合中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息，并且将所述第二映射存储在第二存储器区域中。
[0044]
本发明的第一方面还进一步延伸到一种计算机软件产品，该计算机软件产品包括在由处理器执行时使得处理器执行进行对机器人的运动规划的方法的指令，其中，机器人布置为在工作空间中的多个状态之间操作，所述工作空间由多个离散化的工作空间元素表示，其中，所述状态中的每个状态经由至少一个相应的过渡连接到至少一个其他状态，其中，该方法包括：
[0045]
生成或接收第一模型；
[0046]
确定第一集合，该第一集合包括对应于所述多个状态中的每个状态以及这些状态之间的相应过渡而与第一模型至少部分地碰撞的一个或更多个工作空间元素；
[0047]
生成第一映射，该第一映射包括关于所述第一集合以及使得第一模型与第一集合中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息，并且将所述第一映射存储在第一存储器区域中；
[0048]
生成或接收从第一模型延伸的第二模型；
[0049]
确定第二集合，该第二集合包括对应于所述多个状态中的每个状态以及这些状态之间的相应过渡而与第二模型至少部分地碰撞的、除了第一集合中的那些工作空间元素之外的一个或更多个另外的工作空间元素；以及
[0050]
生成第二映射，该第二映射包括关于所述第二集合以及使得第二模型与第二集合中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息，并且将所述第二映射存储在第二存储器区域中。
[0051]
因此，将理解的是，本发明的实施方式提供了一种改进的方法，其中，针对第一模
型(其可以是如下所概述的机器人的第一连杆)生成并存储映射，而在针对第一模型的映射的顶部上，建立针对第二模型(其可以是如下所概述的机器人的第二连杆或某个其它物体)的映射。针对机器人的各个部分和/或外部物体(例如，要由机器人操纵的物体)的映射是“模块化的”，并且可以组合在一起以提供适合于运动规划的整个机器人的映射。
[0052]
如下面进一步详细概述的，本发明可以允许改变机器人的设置，而不需要“换掉”整个映射(即，不需要替换“整个机器人”的映射)。换言之，当需要改变机器人和/或环境时，可以容易地改变所包括的部件及它们的布置，而无需重新创建整个映射或无需生成和存储大量整个机器人映射——这通常会增加系统的内存和计算需求。
[0053]
由于第二映射包含除了第一映射中的那些之外的工作空间元素“命中(hit)”(即，关于与第二模型至少部分地碰撞的工作空间元素以及导致这些碰撞的对应状态和/或过渡的信息)，当使用如下面进一步详细概述的结构化路线图时，这还可以允许在存储与给定的机器人设置(例如机器人所具有的连杆数量、连杆类型、机器人所携带的任意物体等)相关的映射所需的内存方面进行显著压缩。
[0054]
如上所概述的，在一些实施方式中，针对第一维度和第二维度-以及可选的一些或所有其他维度-的状态和过渡可以使用结构化路线图来布置。这可以使用前面提到的pdrm技术来实现。例如，考虑双连杆机器人的情况下，第二连杆可以在其对于第一连杆的所有状态的所有状态下摆出姿势。结构化路线图的使用可以有益地致使针对第一维度的唯一状态比针对第二维度等的唯一状态少，这可以通过再次使用具有用于该连杆(或其他实体)的相同“子状态”的所有状态的映射来提供显著的内存节省。虽然结构化路线图不是本发明的要求，但本发明特别适合于这种结构化路线图。
[0055]
然而，本发明的原理也适用于本领域本身已知的用于构建路线图的任何其他方法，诸如随机或概率采样技术。
[0056]
关于物理实体，在一些实施方式中，第一和/或第二模型可以用不同的物体来替换和/或可以添加一个或更多个另外的物体，其中，这些附加的或替代的实体可以各自具有它们自己的存储有由另外的模型至少部分地交叠的相应的附加元素的映射。该另外的模型可以包括附加的或替代的物理实体的表示。
[0057]
在一些实施方式中，第一模型包括机器人的第一连杆的表示。本发明特别适用于多连杆机器人，即包括诸如具有多个自由度的机械臂之类的多连杆的机器人。因此，在一组可能交叠的实施方式中，第二模型包括机器人的第二连杆的表示。
[0058]
通常，在机器人是多连杆机器人的实施方式中，每个连杆可以提供各自的运动维度(或“自由度”)。因此，确定由每个模型至少部分地交叠的工作空间元素的集合的步骤包括检查由所述模型提供的相应运动维度所允许的状态(即节点)和过渡(即边)。
[0059]
在一些可能交叠的实施方式中，确定由各个模型至少部分地交叠的工作空间元素的集合的步骤包括检查对应于与静态障碍物碰撞和/或自碰撞的状态和过渡。因此，必然会导致与环境中的已知静态障碍物和/或机器人本身发生碰撞的状态和过渡可以自动排除在考虑之外。这通常也会影响对运动学链中更远的物体(即后面的连杆、末端执行器和/或外部物体)的考虑。
[0060]
附加地或替代地，机器人可以包括末端执行器。因此，第二模型(或关于本发明的某些实施方式概述的另一模型)可以包括末端执行器的表示。本领域技术人员将理解的是，
末端执行器是通常位于机械臂末端的装置，其与机器人的环境或外部物体相互作用。因此，在一组实施方式中，第二模型包括机器人的末端执行器的表示。因此，在一组实施方式中，机器人可以是臂连杆，在臂连杆的远侧端处具有末端执行器。然而，如下面进一步详细概述的，在一些实施方式中，提供了更复杂的布置，例如，具有多个这样的臂连杆的机械臂，其中，在最后一个连杆的远侧端处串联布置有末端执行器。末端执行器还可以向机器人提供一个或更多个运动维度(即自由度)。
[0061]
有许多不同类型的末端执行器，在本领域中本身是已知的，其可以根据本发明使用。作为非限制性示例，末端执行器可以包括以下中的至少一者：手；夹爪；爪；颌；老虎钳；镊子；销钉；针；磁性装置(包括永磁体和/或电磁铁)；吸盘；焊接工具；切削工具；滚动工具；锤子；激光器；钻头；手术刀；和/或喷漆枪。
[0062]
在一组特定的实施方式中，对于一个特定的末端执行器可以使用一个以上的模型，对应于其不同的操作位置(或“末端执行器状态”)。例如，夹爪可以在打开(即非夹持)位置建模为一个模型，且在关闭(即夹持)位置建模为另一个模型。由于本发明的实施方式提供的有利的模块化方法，当执行运动规划时，可以针对末端执行器的当前或计划状态生成或接收适当的模型。当然，不同的映射可以用于路径的不同区段，诸如当朝着物体移动时的打开夹爪和当拾取物体并将其移动到目的地时的闭合夹爪。
[0063]
附加地或替代地，机器人可以包括感测装置。这样的感测布置可以包括来自以下组的一个或更多个传感器，该组包括：相机；立体摄影机；红外传感器；光探测和测距(lidar)传感器；麦克风；超声波传感器；接近传感器；加速度计；陀螺仪；磁力计；温度探针；压力传感器；烟雾探测器；气体传感器；湿度传感器；和ph探针。因此，第二模型(或关于本发明的某些实施方式概述的另一模型)可以包括感测装置的表示。
[0064]
本发明的原理延伸到机器人可以与之交互的“目标”物体。当机器人执行任务时，这些种物体可被拾取、携载、操纵、触摸、移动、推动、拉动等。因此，在一组实施方式中，至少一个模型——例如第二模型或另一模型——包括外部目标物体的表示。这例如在装配线上可以是有用的，在装配线上，目标物体可以包括用于组装成产品的零部件(例如，螺栓、螺钉、金属板、配线、马达、玻璃、电子器件、管道等)。对此的其它非限制性应用示例包括仓储和回收工厂中。
[0065]
可以理解的是，机器人的部件(例如连杆)通常可以在状态(即节点)之间沿两个方向移动，即过渡(即边)可以“向前”(即从节点a到节点b)或“向后”(即，从节点b到节点a)横穿。由于边是双向的并且总是扫过相同的体积，因此在一些实施方式中，仅对于过渡的一个方向的工作空间元素命中(即，工作空间元素至少部分地与一个或多个给定模型碰撞)进行存储。所存储的沿该方向的边称为“前向边”。沿相反方向的边(即“反向边”)的命中被隐式存储。在在线执行期间，为了检查反向边的有效性，检查相邻节点的相应前向边。
[0066]
为了避免存储冗余信息，在一些实施方式中，仅存储给定过渡的、在该过渡所连接的任何状态中均未找到的命中。这意味着，对于某些过渡或边，如果状态或节点布置得很紧密，则可能不会有任何命中。换言之，如果节点导致命中，则这可以隐式地为连接到该节点的所有边存储该命中，进而不会浪费空间存储关于对于这些边的命中的信息。
[0067]
过渡可以是机器人的数个关节(即多维边)的组合运动。然而，申请人已经意识到，对于对该组合运动作出贡献的“最低”连杆(即最内的)，该运动只不过是该连杆的简单运
动，其可能已经针对对应的简单边进行了存储，例如在使用了结构化路线图的情况下。因此，在一些实施方式中，仅针对较高连杆存储与组合运动相对应的工作空间元素命中，而针对较低连杆的简单过渡可以被重复利用。为了进一步增加灵活性，在一些实施方式中，针对每个组合过渡(即边)的映射可以单独存储，并且可以根据需要组合以供在线使用。
[0068]
参照上文，本发明不限于使用两个模型，并且还可以包括其他物体。因此，在一些实施方式中，该方法进一步包括：
[0069]
生成或接收从其他模型中的至少一个模型延伸的附加模型；
[0070]
确定附加集合，该附加集合包括对应于所述多个状态中的每个状态以及这些状态之间的相应过渡而与附加模型至少部分地碰撞的、除了其他集合中的那些工作空间元素之外的一个或更多个另外的工作空间元素；以及
[0071]
生成附加映射，并且将所述附加映射存储在附加存储器区域中，该附加映射包括关于所述附加集合以及使得附加模型与附加集合中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息。
[0072]
可以有多个这样的附加模型，并且每个附加模型可以从任意其他模型(即，对应于连杆、末端执行器或其他物体的任意模型)以任意合适的配置延伸，即，机器人的各个部件和外部物体不必相对于彼此串联延伸，并且可以有其他配置，使得各种连杆和/或物体以及由此的相应模型可以以树状结构相互“分支”、和/或形成环路。每个附加模型可以酌情地包括机器人的连杆、末端执行器或外部目标物体的表示。
[0073]
因此，应该理解的是，可以生成针对不同物理实体(即，机器人部件和/或外部目标物体)的映射库，并将其用于运动规划。可以为可从机器人延伸的每个连杆、末端执行器和/或目标物体创建和存储映射，并且可以从库中选择这些映射，以便容易地为机器人的特定布置的给定任务规划路径。该模块化方法是非常有益的，因为其避免了为机器人部件(例如连杆和末端执行器)和/或外部物体的每一种组合和排列创建完整映射的需要，从而潜在地提供了大量的内存节省。在映射需要花费大量时间才能生成的布置中，使用这样的映射库也很有用。通过预先生成映射并将其存储以备将来使用，可以在需要时从存储器中检索所需的映射选择。
[0074]
映射可以从库中选择并以模块化方式组合的布置本身是新颖且具创造性的。因此，当从第二方面来看时，本发明提供了一种执行对机器人的运动规划的方法，其中，机器人布置为在工作空间中的多个状态之间操作，所述工作空间由多个离散化的工作空间元素表示，其中，所述状态中的每个状态经由至少一个相应的过渡连接到至少一个其它状态，其中，该方法包括：
[0075]
从映射库中选择第一映射，所述第一映射包括关于第一集合的信息，该第一集合包括与第一模型至少部分地碰撞的一个或更多个工作空间元素，所述第一映射还包括关于使得第一模型与第一集合中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息；和
[0076]
从映射库中选择第二映射，所述第二映射包括关于第二集合的信息，该第二集合包括与从第一模型延伸的第二模型至少部分地碰撞的、除了第一集合中的那些工作空间元素之外的一个或更多个工作空间元素，所述第二映射还包括关于使得第二模型与第二集合中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息。
[0077]
本发明的第二方面延伸到一种运动规划器，该运动规划器布置为执行对机器人的运动规划，其中，机器人布置为在工作空间中的多个状态之间操作，所述工作空间由多个离散化的工作空间元素表示，其中，所述状态中的每个状态经由至少一个相应的过渡连接到至少一个其他状态，其中，该运动规划器布置为：
[0078]
从映射库中选择第一映射，所述第一映射包括关于第一集合的信息，该第一集合包括与第一模型至少部分地碰撞的一个或更多个工作空间元素，所述第一映射还包括关于第一模型与第一集合中的相应工作空间元素至少部分地碰撞所对应的相应多个状态和相应过渡的信息；和
[0079]
从映射库中选择第二映射，所述第二映射包括关于第二集合的信息，该第二集合包括与从第一模型延伸的第二模型至少部分地碰撞的、除了第一集合中的那些工作空间元素之外的一个或更多个工作空间元素，所述第二映射还包括关于第二模型与第二集合中的相应工作空间元素至少部分地碰撞所对应的相应多个状态和相应过渡的信息。
[0080]
本发明的第二方面还延伸到包括上文概述的运动规划器的机器人。因此，本发明的第二方面延伸到一种机器人，该机器人布置为在工作空间中的多个状态之间操作，所述工作空间由多个离散化的工作空间元素表示，其中，所述状态中的每个状态经由至少一个相应的过渡连接到至少一个其他状态，其中，该机器人还包括运动规划器，该运动规划器布置为执行对所述机器人的运动规划，该运动规划器布置为：
[0081]
从映射库中选择第一映射，所述第一映射包括关于第一集合的信息，该第一集合包括与第一模型至少部分地碰撞的一个或更多个工作空间元素，所述第一映射还包括关于第一模型与第一集合中的相应工作空间元素至少部分地碰撞所对应的相应多个状态和相应过渡的信息；和
[0082]
从映射库中选择第二映射，所述第二映射包括关于第二集合的信息，该第二集合包括与从第一模型延伸的第二模型至少部分地碰撞的、除了第一集合中的那些工作空间元素之外的一个或更多个工作空间元素，所述第二映射还包括关于第二模型与第二集合中的相应工作空间元素至少部分地碰撞所对应的相应多个状态和相应过渡的信息
[0083]
本发明的第二方面进一步延伸到一种非暂时性计算机可读介质，该非暂时性计算机可读介质包括在由处理器执行时使得该处理器执行进行对机器人的运动规划的方法的指令，其中，所述机器人布置为在工作空间中的多个状态之间操作，所述工作空间由多个离散化的工作空间元素表示，其中，所述状态中的每个状态经由至少一个相应的过渡连接到至少一个其他状态，其中，该方法包括：
[0084]
从映射库中选择第一映射，所述第一映射包括关于第一集合的信息，该第一集合包括与第一模型至少部分地碰撞的一个或更多个工作空间元素，所述第一映射还包括关于第一模型与第一集合中的相应工作空间元素至少部分地碰撞所对应的相应多个状态和相应过渡的信息；和
[0085]
从映射库中选择第二映射，所述第二映射包括关于第二集合的信息，该第二集合包括与从第一模型延伸的第二模型至少部分地碰撞的、除了第一集合中的那些工作空间元素之外的一个或更多个工作空间元素，所述第二映射还包括关于第二模型与第二集合中的相应工作空间元素至少部分地碰撞所对应的相应多个状态和相应过渡的信息。
[0086]
本发明的第二方面还进一步延伸到一种计算机软件产品，该计算机软件产品包括
在由处理器执行时使得该处理器执行进行对机器人的运动规划的方法的指令，其中，该机器人布置为在工作空间中的多个状态之间操作，所述工作空间由多个离散化的工作空间元素表示，其中，所述状态中的每个状态经由至少一个相应的过渡连接到至少一个其他状态，其中，该方法包括：
[0087]
从映射库中选择第一映射，所述第一映射包括关于第一集合的信息，该第一集合包括与第一模型至少部分地碰撞的一个或多个工作空间元素，所述第一映射还包括关于第一模型与第一集合中的相应工作空间元素至少部分地碰撞所对应的相应多个状态和相应过渡的信息；和
[0088]
从映射库中选择第二映射，所述第二映射包括关于第二集合的信息，该第二集合包括与从第一模型延伸的第二模型至少部分地碰撞的、除了第一集合中的那些工作空间元素之外的一个或更多个工作空间元素，所述第二映射还包括关于第二模型与第二集合中的相应工作空间元素至少部分地碰撞所对应的相应多个状态和相应过渡的信息。
[0089]
第一模型和第二模型中的每一者都可以是机器人的连杆、末端执行器或外部目标物体的表示，如前所概述的。
[0090]
这种对映射的模块化“库”方法允许随后在顶部添加进一步的映射。因此，在一些实施方式中，该方法还包括从映射库中选择另一映射，所述另一映射包括关于另一集合的信息，该另一集合包括与从第一模型和/或第二模型延伸的另一模型至少部分地碰撞的、除了第一集合和第二集合中的那些工作空间元素之外的一个或更多个工作空间元素，所述另一映射还包括关于使得该另一模型与该另一集合中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息。
[0091]
该方法还提供了将一个映射用另外的映射来替换。因此，在一些实施方式中，第二映射可以用包括关于第三集合的信息的第三映射来替换，该第三集合包括与从第一模型延伸的第三模型至少部分地碰撞的、除了第一集合中的那些工作空间元素之外的一个或更多个工作空间元素，所述第三映射还包括关于使得第三模型与第三集合中的相应工作空间元素至少部分地碰撞的相应多个状态和相应过渡的信息。因此，作为非限制性示例，如果当前设置对应于具有作为末端执行器的夹爪的机械臂，则第一模型和第二模型可以对应于臂连杆和夹爪。然而，如果夹爪要用切割工具替换，则第二模型可以用对应于切割工具的第三模型替换。
[0092]
当然，可以理解的是，可以进行任意数量的添加和替换，以选择与感兴趣的实际机器人设置相对应的映射。
[0093]
上文中关于本发明的上述方面所提及的各种模型无需一定涉及不同的物理实体。在一些实施方式中，至少其中两个模型各自是同一物理实体的表示。在这样的布置中，一个模型可以是另一个模型的延伸，以覆盖实体所可能具有的不同范围。这可以被视为在实体层级提供特定物理实体的模块化模型，类似于之前概述的在机器人层级可以如何以模块化方式使用模型。换言之，针对给定物理实体的多个模型充当“洋葱”的各层，其中，“外部的”模型可以部分或全部地包裹其他“内部的”模型，或者从它们延伸。这对于生成多个不同外部目标物体(即要由机器人操纵的物体)的映射会特别有益。例如，如果机器人布置为操纵一定长度的管道，则第一模型可以表示具有一定直径和长度的管道，而第二模型可以表示具有不同直径和/或长度的管道，其中，针对较大的第二管道的映射“建立在”针对较小的第
一管道的映射上。
[0094]
这种“洋葱”方法对机器人的部件(例如末端执行器)也会很有用。作为非限制性示例，考虑具有两个指部的钳状夹爪，其中，第一指部是静止的，而第二指部可以朝向以及远离第一指部移动以夹持某物。不是将该夹爪建模为单个模型(或一对模型，一个模型用于打开位置、一个模型用于关闭位置)，而是可以使用以上概述的“洋葱状”方法而使得夹爪的“静态”部件(即第一指部与指部所延伸自的“手”或“手掌”的其余部分)由一个模型表示，并且动态部件(即第二指部)由用于各种位置(例如，完全打开、完全闭合和/或一个或多个中间位置)的另外的模型表示。当然，这延伸到具有多个移动件的部件(例如，如果在之前的夹爪示例中两个指部都移动)。
[0095]
然后可以生成映射，该映射有效地存储关于哪些工作空间元素由于第一指部而被命中(即，至少部分地与之碰撞)以及哪些附加元素随后由于第二指部根据其位置而被命中的信息。这允许当夹爪的配置改变(或计划改变)时将正用于第二指部的模型容易地换掉，而无需更换用于整个夹爪的模型或在传统方法的情况下用于包括夹爪在内的整个机器人的模型。
[0096]
用于存储映射的“存储器区域”可以是用于存储数据的任何合适的装置。在一些实施方式中，第一存储器区域和第二存储器区域各自在存储器内，其中，它们可以在同一存储器内。任何附加的存储器区域也可以酌情地位于相同的存储器或不同的存储器内。存储器可以是以下中的至少一者：只读存储器(rom)；随机存取存储器(ram)；固态器件(ssd)；硬盘驱动器(hdd)；闪存；专用视频ram(vram)；或其他合适的存储器装置。
[0097]
优选地，存储器是本地的，即，其位于用于执行运动规划的相同装置、系统或设备内。本发明的实施方式在运动规划过程至少部分地在并行处理单元(例如gpu)上执行的情况下是特别有益的，因为其中的一个或更多个映射至少在一些实施方式中可以在本地存储在并行处理单元的存储器中。这可以允许在需要时快速“切换出”映射，而不依赖于与外部实体的任何连接(例如通过网络)。在一些布置中，可以将并行处理单元(例如gpu)与中央处理单元(cpu)一起使用，其中，可以将使用映射的计算发送到并行处理单元。
[0098]
然而，在一组可能交叠的实施方式中，一个或更多个映射可以存储在远程存储器或芯片外存储器中。应该理解的是，术语“远程”或“芯片外”在本文中是指在装置外部或装置的特定部件(诸如特定处理器)外部，其执行运动规划(例如运动规划器)。例如，如果运动规划是由特定处理器执行的，则映射可以存储在该处理器和任何相关联的芯片上存储器的外部。在这样的布置中，映射可以存储在外部(例如，芯片外存储器、外部服务器、另一装置上或云中)，并流式传输到执行运动规划的装置。应当理解的是，在“远程”存储器布置中，数据(例如，路线图和/或映射)通常从芯片外存储器(或一些其他外部存储装置)发送到运动规划器。然后可以在使用后丢弃数据(或者在该任务不再需要存储器时立即丢弃，或者在某个预定时间后丢弃，或者一旦另一个任务需要存储器时丢弃)。模块化映射会是有利的，例如，当在这样一种布置中时：其中，可以仅针对需要映射的那些部件，而不是针对整个机器人，将较小映射从芯片外存储器转移到处理器。仅作为示例，这可以允许使用较少的带宽或较不可靠的网络连接。进一步有利的是，这在映射可能需要花费大量时间来生成的情况下会是有用的，因此，能够在需要时从外部存储器下载所需的特定映射会是特别有益的。
[0099]
可以使用这些本地存储器和流式传输方法的混合，使得一些映射在本地存储(例
如，那些频繁使用的映射，或者与当前使用的映射密切相关的映射)，而其他映射可以被远程存储并在需要时流式传输。
[0100]
如前所概述的，后面的集合(例如，第二集合)包括一个或更多个除前面的集合(例如第一集合)中的工作空间元素之外的工作空间元素。因此，使用由于与后面的集合相关联的对应模型的碰撞而被命中的工作空间元素来生成适当的映射，而不需要存储被“前面的”模型“命中”的工作空间元素。在一些实施方式中，这些“附加的”工作空间元素可以直接确定，例如，通过使用借助所考虑的新模型而仅查找工作空间元素的“新”命中的检测过程来确定。然而，在一些其他实施方式中，该方法包括从第二集合中移除第一集合中的一个或更多个工作空间元素。换言之，第二集合的确定可以包括：最初也确定由其他前面的模型命中的工作空间元素，但是随后移除已经在前面的集合中的一个或更多个(并且在某些情况下是所有)工作空间元素以避免冗余地存储它们。
[0101]
虽然与给定模型至少部分地碰撞的工作空间元素可以被添加到适当的集合中，并因此被包括在所得映射中，但这并不一定意味着被该模型所至少部分地交叠的所有这些工作空间元素都被添加到该集合和映射中。
[0102]
应当理解的是，在连杆和/或物体彼此物理接触的情况下，例如在关节或接合部处，将存在与模型中的一个以上模型至少部分地碰撞的一些工作空间元素。在一些实施方式中，这些工作空间元素包括在与每个模型相对应的集合中。然而，在一些可能交叠的实施方式中，这些“共享的”工作空间元素中的一些或全部可以仅包含在其中的一个集合中。可以选择合适的约定，例如，工作空间元素可以包括在最早的集合中，即与最接近机器人基座的连杆或物体相对应的集合中。通过仅在其中一个集合中包括具有共享占用的这种工作空间元素，可以进一步减少所需的内存总量，这可以增强以上概述的优点。然而，可以存在受益于与冗余地存储在每个相关集合中的关节和/或接合部相关的占用信息的某些布置。
[0103]
附加地或可替换地，可以存在一个或更多个与特定物体(例如，连杆)至少部分地碰撞的工作空间元素，该特定物体也至少部分地与机器人的静态部件交叠，所述静态部件例如为机器人基座，连杆和/或物体中的一个或多个-以及由此相对应的模型-从该机器人基座延伸。这些“静态”工作空间元素可以包括在最“内”的集合(即第一集合的集合)中，或者可以存储在单独的“基本”映射中，该“基本”映射包含了与由于被机器人的静态基座命中而一直都至少部分地被占用的工作空间元素相关的信息。因此，在一些实施方式中，该方法包括生成基本映射，该基本映射包括关于与机器人的静态部件至少部分地碰撞的一个或更多个工作空间元素的信息。
[0104]
如上所概述的，映射存储关于至少部分地被占用的工作空间元素的信息。在一些实施方式中，这可意味着整个集合被存储为映射。然而，申请人已经意识到，可以存在存储关于相关工作空间元素的信息的更具存储效率的方式。在一些实施方式中，为映射中的一个或更多个映射存储的信息可以包括多个兴趣点，例如角点和/或中心点。本领域技术人员将理解的是，部分占用的工作空间元素可以形成一个或更多个阵列、区域、表面和/或体积，这些阵列、区域、表面和/或体积可以由选定数量的“兴趣点”(诸如“角点”和/或“中心点”)重建。例如，考虑与立方体形状的物体相关的模型。与该物体至少部分地碰撞的工作空间元素也可以形成立方体。虽然可以存储包括所有这些元素的集合，但两个相对的角(例如，左下后角和右上前角)足以能够重建整个立方体。类似地，可以使用对中心点的认知来重建物
体，例如，如果与对物体从该中心点延伸多远的认知相结合，则可以酌情与中心点一起存储该范围(或不同方向上的多个这样的范围)。
[0105]
工作空间元素本身不必全部具有相同的形状和/或大小，也不一定必须是“正方形/矩形”像素或“立方体/长方体”体素。在一些实施方式中，工作空间被离散化为具有不同形状和/或大小的工作空间元素。这可以允许在显著感兴趣的区域中具有较高的分辨率(即，较小的工作空间元素，进而较高的工作空间元素密度)，同时允许在不太感兴趣的区域中具有较低的分辨率(即，较大的工作空间元素，进而较低的工作空间元素密度)。在机器人将与人类操作员一起在环境中工作的特定示例中，可以在人通常将占据的区域以及机器人将执行大多数任务的区域中使用较高的分辨率，而可以在机器人后面或在人或机器人都不可能花费太多时间的区域的极限外周使用较低的分辨率。类似地，不同形状的工作空间元素可以在不同的区域中使用——例如，元素可以在一个区域中具有弯曲的横截面，而在另一个区域具有四边形横截面，这取决于针对环境的特定部分的最合适形状。
[0106]
工作空间的大小和分辨率上的灵活性是非常有益的，因为从零开始创建映射比从高分辨率映射重新创建映射在计算上成本要高得多。通过这种方式，只需要存储一个预先生成的高分辨率映射，而不需要存储众多具有一系列分辨率和大小的映射，然后可以根据需要以及可用的计算资源，针对不同应用的需要重新使用该单个高分辨率映射。
[0107]
在前述任一方面的一些实施方式中，然后可以使用映射来生成用于机器人遵循的路径。换言之，为了为机器人生成适当的计划来执行给定任务，可以以与用于整个机器人的单个映射通常相同的方式使用适当映射的组合。
[0108]
由上文提到的各种模型表示的物理实体可以能够在机器人的环境内横向移动。然而，这些实体中的一个或更多个可以附加地或替代地能够围绕一个或更多个轴线旋转。例如，末端执行器(诸如夹爪)可以能够绕其主轴线旋转，类似于在手腕处扭曲的人手。每次旋转可以形成机器人的另一“状态”(例如配置)，其方式与机器人的不同横向位置的相同。通常，旋转状态可以以某种方式离散化，其中，可以为这些离散化状态生成映射。然而，申请人已经意识到，实体或实体的一部分可以具有大于1的轴向对称度。例如，诸如具有两个对称螺旋桨叶片的螺旋桨之类的旋转工具位于轴的端部，其中，轴(以及由此螺旋桨)围绕其主(即纵向)轴线旋转。在螺旋桨的所有旋转状态下，由轴命中的工作空间元素可以是相同的。类似地，在给定旋转中由螺旋桨叶片命中的工作空间元素可以是与180
°
(即半旋转)状态相同的状态。
[0109]
在这种情况下，当该实体旋转时至少部分地被占用的工作空间元素可以在多个旋转位置上是相同的。因此，在一些实施方式中，对于旋转对称模型的多个状态相同地部分占用的工作空间元素可以仅被存储一次，并且其他状态然后可以简单地参照第一旋转相同状态，这导致那些工作空间元素被添加到用于映射的集合中。
[0110]
在一些布置中，一个以上的机器人可以一起使用或者彼此非常接近地使用。前述方面的原理同样适用于对第二机器人(或任意数量的其他机器人，酌情而定)的运动规划。
[0111]
映射可以包括针对映射中的每个工作空间元素的状态标识符和过渡标识符。换言之，使用图形术语，本发明的实施方式可以存储针对每个工作空间元素或体素的节点和边标识符(或“id”)。因此，每个工作空间元素(例如体素)可以具有表示与该元素部分或完全地碰撞的所有节点和边的列表，即“命中”列表。通过存储针对每个工作空间元素的状态和
过渡id，可以在内存和计算的优化方面进行改进。当然，在这样的布置中，一些工作空间元素(或体素)可以具有空列表(由于该元素没有被任何节点或边命中)。
[0112]
然而，在另一些实施方式中，针对每个边和/或每个节点存储工作空间元素(例如体素)id。
[0113]
应当理解的是，上文中关于本发明的任何特定方面所描述的可选特征酌情同样适用于本发明的其他方面。
[0114]
类似地，关于与本发明的特定方面相关联的方法、运动规划器、机器人、非暂时性计算机可读介质和计算机软件产品的实施方式所描述的任何以及所有可选特征在必要的修改后同样适用于所述方法、运动规划器、机器人、非暂时性计算机可读介质和计算机软件产品的与该方面相关联的的其他者。
[0115]
在关于方法步骤描述可选特征的情况下，这延伸到布置为执行相同方法步骤的装置、设备或系统(例如，如上所概述的运动规划器或机器人)。类似地，在关于装置、设备或系统的一方面描述可选特征的情况下，这延伸到对应的方法步骤或者作用于这样的装置、设备或系统的方法步骤。
附图说明
[0116]
现在将参照附图，仅通过示例的方式描述本发明的某些实施方式，在附图中：
[0117]
图1是机器人在一环境中需要的运动规划的典型布置的示意图；
[0118]
图2a和图2b是示出由第一机器人连杆命中的工作空间元素的示意图；
[0119]
图3是示出由第二机器人连杆命中的附加工作空间元素的示意图；
[0120]
图4是示出由另一机器人连杆命中的另一附加工作空间元素的示意图；
[0121]
图5是示出由夹爪手掌命中的工作空间元素的示意图；
[0122]
图6是示出由在打开位置的图5的夹爪的指部命中的工作空间元素的示意图；
[0123]
图7是示出由在如图6所示的打开位置的夹爪的指部命中的唯一映射的工作空间元素的示意图；
[0124]
图8是示出由在闭合位置的图5的夹爪的指部命中的工作空间元素的示意图；
[0125]
图9是示出由在如图8所示的闭合位置的夹爪的指部命中的唯一映射的工作空间元素的示意图；
[0126]
图10是示出由小物体命中的工作空间元素的示意图；
[0127]
图11是示出由作为附加“洋葱”层的中等物体命中的工作空间元素的示意图；
[0128]
图12是示出由作为另一附加“洋葱”层的大物体命中的工作空间元素的示意图；以及
[0129]
图13是示出由具有轴对称性的机器人连杆命中的工作空间元素的示意图。
具体实施方式
[0130]
图1是在环境4中操作的机械臂2所需的运动规划的典型布置的示意图。机械臂2包括在关节12处相互连接的基座6、一对连杆8a、8b和末端执行器10。机械臂2的任务是将物品从一个箱14移动到另一个箱16，例如用于在装配线上分拣零部件。然而，机械臂2必须避开多个静态障碍物18、动态障碍物20和人22。
[0131]
工作空间4被离散化(即“分解”)为多个不同的工作空间元素24，为了便于说明，图1中只标记了从这些工作空间元素中选择的一小部分。这些工作空间元素24中的每一个工作空间元素都是体素，使得工作空间4被划分成立方体的三维网格。然而，可以理解的是，尽管图1中的工作空间元素24都具有相同的大小和形状，但情况不一定如此，在另一些示例中，工作空间4的某些区域相较于其他区域可以使用不同的分辨率和/或形状。类似地，如果处理二维问题，则工作空间可以被适当地划分成二维工作空间元素(例如像素或方形)的网格。
[0132]
可以随着检测到或捕捉到环境的变化而对工作空间4进行更新。例如，可以使用诸如3d相机之类的传感器来检测环境和动态障碍物的变化。然后可以相应地更新离散化的工作空间4。附加地或替代地，可以响应于所预测的空间中的实体(例如，在环境内运动的动态障碍物或人)的运动而对工作空间4进行更新。仅作为示例，对工作空间4的更新可以例如关于物体的物理放置、到物体的距离、物体的类型或所预测的物体的运动来执行。
[0133]
如本领域中众所周知的，当执行运动规划时，可以使用路线图来描述机器人可用的运动范围，其中，路线图的节点是机器人的可能状态，而连接节点的边是这些状态之间的过渡。虽然路线图用于运动规划，但机器人当然也可以移动到路线图之外。
[0134]
在下面描述的特定但非限制性的示例中，“状态”与机器人2的配置有关。然而，应当理解的是，如上所概述的，另外的参数可以(附加地或替代地)形成状态的一部分，诸如速度、角度、时间、温度等。换言之，可以将(在特定时刻)相同地定位但具有第一速度的机器人以与当该机器人具有不同的第二速度时不同的状态表示。
[0135]
为了执行对机器人2的运动规划，生成描述机器人2的操作空间的路线图，其中，为每个关节12提供一个维度。然而，代替像现有技术方法中那样为整个路线图和整个机器人2创建单个映射，本发明的实施方式如下所概述地将连杆(以及末端执行器和任何其他相关的目标物体)分离开。
[0136]
根据本发明的实施方式生成映射的第一步骤是分离针对每个连杆(8a、8b)、末端执行器10、以及目标物体(例如，被从一个箱14移动到另一个箱16的物品)的映射。
[0137]
首先，创建针对第一连杆8a的映射，其中，机器人2被视为1-dof(一个自由度)机器人，如图2a所示。这是通过在所有配置下(即，在所有可能的状态下)摆出第一连杆8a的模型的姿势并检查路线图中的第一维度所允许的所有边(即，过渡)(即，由第一连杆8a提供的自由度)来执行的。
[0138]
将在各种状态和过渡中由第一连杆8a部分地或全部地占用的工作空间元素26添加到元素集合中，然后将该元素集合用于生成针对第一连杆8a的映射。该映射有效地提供了关于在各个不同状态和过渡中与第一连杆8a至少部分地碰撞的工作空间元素26(出自所有工作空间元素24)的集合的信息。
[0139]
虽然图2a示出了这些用于单个配置的元素26，但在图2b中可以看到由不同状态和过渡命中的元素26的集合，图2b示出了第一状态100与第二状态102之间的过渡。在此，集合中的元素26被划分成在两个状态(节点)100、102中由第一连杆8a的模型命中的那些元素26a、以及在这些状态之间的过渡(边)期间所命中的那些元素26b。
[0140]
将针对第一连杆8a的映射作为单独的“连杆1映射”存储在存储器中。与按照现有技术的方法的用于整个机器人2的映射相比，该映射将非常小。
[0141]
接下来，如图3所示，添加第二连杆8b的模型，进而现在考虑前两个维度。在所有配置下摆出新的二自由度机器人的姿势，并检查路线图中的所有边。如图3所示，存在一些在第一连杆8a与第二连杆8b之间的关节周围被命中的工作空间元素27。这些元素27已经存储在针对第一连杆8a的映射中，并且因此在生成针对第二连杆8b的第二映射时可以被忽略。因此，只有由第二连杆8b唯一地命中的工作空间元素28被用于生成第二映射(即“连杆2映射”)，其与“连杆1映射”分离地存储在存储器中。
[0142]
因此，由第一连杆8a和第二连杆8b两者产生的所有的工作空间元素命中被压缩，并且仅存储在针对“较低”连杆(即，第一连杆8a)的映射中。通过在已产生的针对较低连杆的映射中查找，可以出于唯一性而有效地检查命中，而无需对该连杆执行碰撞检查。
[0143]
然而，在一些布置中，与这些元素27相关的信息可用于生成第二映射，使得在两个映射中包括“交叠的”元素27。
[0144]
如图4所示，该例行过程由另外的物体9继续并考虑相应的自由度，其中，针对每个附加连杆生成映射，直到针对所有自由度映射出整个机器人2。虽然另一连杆在图4中示出为物体9，但该过程可以针对任何末端执行器和目标物体执行，如下进一步详细概述的。
[0145]
该过程还可以针对当前不在机器人2上的替代和/或附加物体(例如，连杆、末端执行器或目标物体)来执行。例如，在有多个不同的工具可以作为末端执行器附接到第二连杆8b的情况下，可以为每个末端执行器生成映射并将该映射存储在存储器中。在某些情况下，给定的物体可以具有一个以上存储的与该物体的不同操作状态有关的映射。例如，可以打开或闭合的夹爪可能在存储器中具有针对打开条件和闭合条件中的每个条件存储了单独的映射。因此，可以以相同的方式添加新的装备，例如，传感器和夹爪。装备所连接到的连杆规定了对于映射需要考虑的维度。来自所考虑的装备的所有唯一的命中都映射在单独的“部件x映射”中。
[0146]
特定的物体也可以由一个以上的映射来表示。例如，夹爪可以被划分为一个针对“手掌”部分的映射和针对朝向及远离手掌移动的“可移动指部”部分的另外一对映射，其中，为处于打开位置的指部存储一个映射，为处于闭合位置的指部存储另一个映射。
[0147]
这方面的一个示例如图5至图9所示。图5是夹爪手掌30的示意图，其中，该手掌30形成可定位在机器人2的远侧端处的夹爪末端执行器的一部分。具体而言，图5示出了在特定状态下由夹爪的手掌30命中的工作空间元素32。
[0148]
夹爪还具有两个指部34，它们可以在打开位置与闭合位置之间操作，在打开位置中，指部通过间隙彼此分隔开，在闭合位置中，指部34被一起拉近——相对于手掌30横向移动——从而减小它们之间的间隙，以便夹持物体。
[0149]
图6是示出了当在打开位置中操作时由指部34命中的工作空间元素36的示意图，图7示出了由在打开位置中的指部34命中的、被唯一地映射出的工作空间元素38，即那些仅由于指部34的存在而被命中的元素38，而不是那些由于手掌30的存在而已经被命中的“交叠的”元素40。因此，只有与这些附加的工作空间元素38的集合相关的信息才需要存储在映射中，因为否则的话已经存储在针对手掌30的映射中的元素38是冗余的。
[0150]
图8是示出了当在闭合位置操作时由指部34命中的工作空间元素42的另一示意图，并且图9示出了由在闭合位置中的指部34命中的、被唯一地映射出的工作空间元素44，即那些仅由于指部34的存在而被命中的元素44，而不是那些由于手掌30的存在而已经被命
中的“交叠的”元素46。如前所述，仅与这些附加的工作空间元素44的集合相关的信息需要存储在针对闭合的指部34的映射中。
[0151]
然后可以将针对在打开位置及闭合位置中的指部34的映射作为用于该部件(即夹爪)的“(part maps)部件映射”，与“(link map)连杆映射”一起存储在存储器的库中。然后，可以根据针对给定任务的夹爪的当前或计划状态，从库中酌情地选择这些映射。有利地，这避免了在工作空间元素命中的差异仅仅是由于指部34的位置所致，而所有其他工作空间元素命中(即，由于机器人2的手掌和其他连杆所致的)对于两个位置而言是重复的情况下存储针对整个机器人的两个完整映射。
[0152]
边可以是数个关节12的组合运动。然而，对于为组合运动作出贡献的最低连杆而言，该运动只是该连杆的已针对相对应的简单边存储的简单运动。因此，用于对应于组合运动的边的映射仅被存储用于较高连杆，而用于较低连杆的简单边的映射被重复使用。对于某些应用，可能只需要简单的边，而对于其他更高级的应用，则可能需要组合边。此外，所需的高级边的集合可能因应用而异。为了进一步提高灵活性，针对每个组合边的link map可以被单独存储，并且也可以根据需要进行组合以供在线使用。
[0153]
当组合时，所有映射的大小将与一个组合机器人映射的大小大致相同。虽然针对给定机器人设置的映射的组合可能由于任意所存储的交叠工作空间元素而略大于针对整个机器人的单个映射(例如，在关节处的那些元素针对该关节任一侧的两个连杆而被存储在映射中的情况下)，但是当考虑在现有技术的方法中将需要为每个可能的机器人设置和所操纵或携载的物体而存储整个机器人映射时，提供了显著的整体内存节省。因此，使用本发明的原理，与存储路线图和连杆/部件的所有不同组合所需的总存储空间的显著减少相比，用于任意单个机器人设置的映射的存储器需求的轻微折衷可以忽略不计。
[0154]
从前面的映射延伸而来的所有映射对于用来生成它们的特定较低连杆(以及在使用情况下的子路线图)都是有效的。然而，子路线图对于所有维度都应该是相同的，因为这规定了所映射的连杆最终的位置。底层(或“内部”)连杆的运动学可不改变，因为这样做也会改变“外部”的一个连杆或多个连杆最终的位置。
[0155]
换言之，考虑了一种机器人，在其设置中，在由两个连杆构造成的机械臂的末端提供有夹爪型末端执行器(即相当于上臂“第一连杆”、下臂“第二连杆”和手“末端执行器”)。“link map 1”和“link map 2”覆盖了这两个连杆。针对末端执行器的映射对于该特定设置是有效的，然而，如果第二连杆(下臂)以由“link map 3”覆盖的不同的第三连杆(即，不同的下臂，即具有不同的形状或物理范围)代替，将需要针对夹爪型末端执行器的不同映射，这是因为被部分地占用的工作空间元素的集合可由于运动学链中之前的变化而不同。但是，因为映射不受运动学链中进一步发生的事情的影响，所以最外的连杆、部件和维度(例如，前述示例中的末端执行器)可以自由地改变。
[0156]
这种映射在路线图维度方面的灵活性非常有用，因为不同的应用具有不同的分辨率需求。有些可能需要高分辨率，而另一些则可能不需要。例如，机器人可具有能够提供末端执行器的旋转运动的“手腕”。视应用不同而可能需要精确的旋转运动，但在另一些应用中，可能只需要非常“粗糙”的旋转(例如，在两个不同的位置之间，相隔180
°
，诸如“手掌向上”和“手掌向下”)。
[0157]
在这种情况下，对于例如6-dof机器人，使用该系统的两个不同使用者针对他们的
不同应用可以对前三个连杆使用相同的映射，而仅对三个外部连杆使用不同的映射。
[0158]
由于使用本发明可以预先计算大量不同的映射，这将因为可以将映射重复用于不同的连杆而节省大量的存储空间和计算时间。此外，所选择的夹爪(将有很大变化)不会影响用于机器人的映射并且可以单独地生成。
[0159]
由于机器人2可以在运行期间拾取不同的物体，因此机器人2的范围(包括由机器人2操纵的物体)通常也将在线改变，即在机器人2的操作期间改变。本发明的模块化映射方法使得在操作期间的每个给定时间能够灵活地使用已经存在的适当连杆和部件的映射，而无需改变对于整个机器人2的映射。
[0160]
经常地，在机器人应用中，机器人可能需要处理不同大小和形状的大量物体。例如，在仓库中，机器人可能需要拾取许多不同的部件进行分配(例如，将交付给消费者的来源于网上商店的商品)，其中，这些部件中的每个部件具有不同的形状或大小(即，它们具有不同的物理范围)。类似地，在回收工厂中，机器人可能需要对具有不同物理范围的不同类型的物体(例如，玻璃瓶、铝罐、纸板等)进行分拣。
[0161]
在针对机器人2的所有部件(包括那些由机器人2携载或操纵的部件在内)的映射的情况下，管理针对大量物体的映射的集合很快变得不易实行。一种j9九游会真人的解决方案是将所有物体均视为等同于机器人将需要操纵的、具有最大物理范围的物体。然而，这通常由于其可能例如导致机器人2走更长的路径而是无效率的，这是因为其假设了其所携载的物体将会命中障碍物，但实际上所操纵的物体要小得多并且如果遵循了较小物体所允许的更优选(例如更短)的路径，障碍物实际上并不会被命中。此外，采取这种保守的方法(即，通过将物体都视为与最大的可能的物体一样大)可能会导致本应可行的目标由于错误碰撞的“检测”而被视为不可行。
[0162]
此外，为机器人设置和所操纵物体的所有不同组合生成所有必要的映射会需要大量时间。这种现有技术的方法还使得系统对该设置中的变化以及对新任务的灵活性降低。为了解决这个问题，本发明的实施方式引入了“layered map(分层映射)”方法，如下面参照图10至图12所概述的。
[0163]
图10是示出由小物体50命中的工作空间元素48(即与该小物体50至少部分地碰撞的元素48)的示意图。对于较大的物体，这些物体可以从小物体“生长”出来，如图11和图12所示，其中，只存储命中的附加工作空间元素。
[0164]
具体而言，图11是示出了作为附加的“洋葱”层、由从小物体50扩展的中等物体54命中的工作空间元素52的示意图。图12示出了添加作为另一附加的“洋葱”层的、由从中等物体54扩展而来的大物体58命中的工作空间元素56。
[0165]
因此，类似于如何由不同的层构建洋葱，部件可以由适当的层模块化构建。因此，代替为每个部件整体地制作一个单独的映射，分层映射方法针对各层构建多个映射，这些映射一起映射整个部件。因此，如果对于路径规划过程要考虑中等物体54，则可以从针对小物体50的映射加上针对由中等物体54在那些由小物体50命中的元素48“之上和上面”命中的额外工作空间元素52的“附加”映射来构造适当的映射。类似地，可以通过组合对于所有三个物体50、54、58的映射来考虑大物体58。
[0166]
通过这种策略，可以映射大范围的部件，而不会在冗余信息上浪费存储装置。
[0167]
每次为单个层创建映射。每个层都以与前面描述的相同的方式(即关于连杆和/或
末端执行器的链路)创建，其中，每个在外工作的层都从紧挨着的前一内层延伸。每个映射只存储对该给定层而言唯一的命中，即不存储针对任何内层的任何命中。因此，对于单个配置，针对组成部件的所有层的命中的数量可以与用于整个部件作为整体的一个单个映射的命中的数量完全相同。由于每个层可以比单个体素小或薄，因此给定的节点或边可能不会产生唯一的命中。
[0168]
由于对于每层的映射只存储唯一的命中，因此每个“层映射”只能与下层的层映射结合使用。因此，在构建过程中(即，为各个部件设计映射库时)，必须就如何“生长”部件做出设计决策。应该理解的是，这将取决于特定的应用和针对该特定实现的设计要求，因此这里不进一步对此进行讨论。
[0169]
如果层之间的分离距离大于工作空间元素的最大对角线长度，则不会存在两个层同时接触的任何工作空间元素(例如体素)，因此它们永远不会具有共享命中，并且针对任何层的所有命中相对于其他层都是唯一的。
[0170]
因此，本发明提供了一种有利的布置，其中，数个部件的分层映射可以被加载到本地存储器，例如，诸如gpu之类的并行处理单元的存储器，其中，存储器需求相比于通过传统方法的存储器需求更为优化，在传统方法中，针对整个机器人的每个部件进行单独的映射。本发明的j9九游会真人的解决方案提供了一种灵活的方法，其中，可以拾取不同的部件，并且可以使用不同的末端执行器(例如夹爪)。
[0171]
本发明的另一个优点是，在生成映射时不需要知道要拾取的确切部件。可以通过很少的开销存储器创建一大组形状，并在线将其组合以捕获正在(或计划)操纵的当前部件。例如，传感器可以确定待操纵的未知物体比小物体50大，但适合于中等物体54的边界内，进而可以使用针对中等物体的适当映射。
[0172]
路线图的无效化或标记(例如，以抛弃导致与障碍物16、18、20、22碰撞的节点和/或边)可以以与本领域本身已知的传统方法类似的方式执行，然而，本文所描述的模块化映射方法使得无效化过程对于由并行处理单元(例如gpu)执行而言更具存储器效率。
[0173]
节点和边的标记可以以“标记阵列”或一些其他合适的存储格式存储，其可以存储在并行处理单元(例如gpu)的存储器中。所使用的标记可以简单到对应于工作空间元素(例如体素)是被占用还是空闲(即二进制标记)，或者可以使用更复杂的标记(例如，可以使用占用的“风险”数或可能性、到物体的距离和/或预期物体存在的时间作为标记)。
[0174]
在该阵列中，可以基于引起与工作空间元素(体素)相交的机器人连杆来分层存储标记，这在使用结构化路线图时特别有用。利用这样的分层结构，当靠近基座的连杆与针对给定节点或边的标记工作空间元素(体素)相交时，这意味着直到该连杆的所有配置和具有相同配置的边都隐式地被赋予相同的标记。对基本节点/边的任何标记都隐式地标记了所有臂节点/边。
[0175]
利用本文所描述的模块化映射方法，可以在启动时将与特定路线图、机器人设置和物理范围、运动学以及工作空间相对应的所有映射加载到gpu(或其他并行处理单元)。
[0176]
检查工作空间元素的标记(即，它们是否被标记为已占用、空闲或某些其他状态)，并且基于该标记，可以相应地标记相应的节点/边(以及在结构化路线图的情况下，所有隐式地存储的节点/边)。然后可以使用无效化的或标记的路线图来执行图形搜索，以获得避免无效节点和边的路径。例如，可以使用其他标记(即，非二元标记)来调整运动通过该边或
节点的成本，并且图形搜索可以使用成本函数来找到“最优”路径(其中，成本可能与例如风险、能耗、速度限制等有关)。
[0177]
如图13所示，可以布置特定的关节，使得无论关节角度如何，连杆的大部分都会命中相同的区域。这些命中可以仅存储一次，潜在地用于所有关节角度，以提供进一步的内存节省。当使用结构化的路线图时，这可以通过考虑将这些命中作为较低连杆的一部分来实现。由于映射是模块化的，因此这仍然隐式地存储在针对当前连杆的映射中，而且其是针对引起命中的“较低”或“内”连杆的映射的一部分。
[0178]
在这个特定的示例中，连杆60在一端围绕一关节的轴线旋转，如图13中呈虚线的不同旋转状态所示。在此情况下，由该关节命中的工作空间元素62在连杆60的所有旋转状态下都是相同的。如此，这些元素62只需要被存储一次，并且被确定为针对该连杆60的所有旋转状态的命中。
[0179]
因此，可以看出，本发明的实施方式提供了一种执行对机器人的运动规划的改进方法，其中，用于不同物体(例如，机器人连杆、末端执行器和/或要由机器人操纵的外部物体)的映射被分解为“模块化”映射，所述“模块化”映射可以酌情进行组合。与需要生成整个机器人的映射的传统方法相比，这种方法可以提供对执行运动规划的存储器和/或计算要求的显著的改进。
[0180]
本领域技术人员将理解，这里描述的具体实施方式仅仅是示例性的，并且可设想本发明范围内的许多变型。