在具有动态对象环境中促进运动规划的设备、方法和物体

摘要

主要主体，例如，自动驾驶车辆，的计算机系统的运动规划器，在执行运动规划前先使用可重新配置的碰撞检测体系结构硬件对主要主体的规划图进行碰撞评估。系统至少部分的基于碰撞评估，针对表示主要主体的状态间的转换的规划图上的边缘，设置与环境中的另一主体(例如，动态对象)碰撞的概率。根据主要主体的目标是避免与环境中的特定动态对象碰撞还是与环境中的特定动态对象碰撞，系统然后执行优化以在所得规划图中识别一条路径，在该路径中，与特定的动态对象碰撞的可能性相对低或相对高。所述系统随后使主要主体的制动器系统至少部分基于优化用可应用的识别的路径来实现运动规划。

说明书

技术领域

本公开总体涉及运动规划，尤其涉及在具有动态对象的环境中促进主体(例如，自动驾驶车辆)或其它机器人主体的运动规划的系统和方法。

背景技术

运动规划是机器人中的一个基本问题。运动规划可用于控制自动驾驶车辆的运动或控制其他类型的机器人或机器人的部分(例如，附件)的运动。例如，运动规划指定一条衔接第一配置状态(例如，起始姿态)和目标状态(例如，终点姿态)的路径，自动驾驶车辆或机器人或机器人的部分可沿着这条路径运动，通常不会与操作环境中的任何障碍发生碰撞或与操作环境中的任何物体发生碰撞的可能性降低。但是，在某些情况下，例如在游戏中，可能需要与操作环境中的对象进行交互，例如检查对象，收集来自对象的信息，与对象交换信息，甚至与对象碰撞。创建运动规划通常涉及四个主要部分：感知，路线图(本文中也称为运动规划图)构造，碰撞检测和路径搜索。在包括静态对象，特别是在该环境中运动的动态对象的自动驾驶车辆或机器人周围的环境中，上述四个部分中的每个部分都产生了需要克服的挑战。动态障碍物的接下来的运动也可能是未知的或不确定的。这种动态对象可能沿着与自动驾驶车辆或其它类型的机器人的目标的方向相反的方向运动。因此，自动驾驶车辆或其它类型的机器人进行运动规划以实时跟上那些变化是有利的，可以避免碰撞或拦截此类对象以达到目标状态。

发明内容

运动规划器系统可以接收表示主要主体(例如，自动驾驶车辆，其他类型的机器人)所操作的环境的感知信息。所述运动规划器系统在执行运动规划之前，要针对主要主体的规划图执行碰撞评估，其中要考虑的有环境中其他主体的动作，包括那些其他主体如何对主要主体所采取的动作做出反应。

规划图的每个边缘代表主要主体在主要主体的配置空间中从一种状态转换到另一种状态，并具有与之相关的固有或运营成本。固有或运营成本可能反映出主要主体的各种运营参数，例如燃料和/或能源使用和/或时间。每个边缘可具有对应于各自固有或运营成本的初始权重。对于代表主要主体状态转换的规划图上的边缘，系统至少部分基于碰撞评估来确定与环境中的动态对象碰撞的概率，然后基于与动态对象碰撞的概率来修改或调整边缘的初始权重。例如，系统可以将成本函数应用于每个边缘以基于该边缘的初始权重(即，与固有成本相对应的权重)进行数学运算以获得修改后的权重。通过基于碰撞概率将附加权重添加到初始分配的权重，通过将初始分配的权重乘以碰撞因子的概率或通过应用涉及碰撞概率和与固有成本对应的初始权重的一些其它方程或公式来实现上述这一点。如本文所述，碰撞评估有利地解决了环境中其他主体对主要主体的动作产生的反应，以及彼此之间的反应。除了碰撞概率，系统还可以分配与碰撞概率无关的特定于对象的成本，例如反映对象相对重要性的成本。例如，与人碰撞的成本可以指定为为明显高于与树木碰撞的成本。

例如，在主要主体的目标是避免与其环境中的动态对象发生碰撞的情况下，如果各个边缘与一个或多个动态对象碰撞的概率相对较高，则系统可以为规划图的边缘分配具有相对较大的正值的权重。如果相应边缘与环境中的一个或多个动态对象发生碰撞的概率相对较低，则系统可以为规划图的边缘分配具有相对较小的正值的权重。然后，系统执行优化，以在最终的规划图中标识出一条路径，在这条路径中，与主要主体操作的环境中的一个或多个动态对象碰撞的概率相对较低。然后，系统至少部分地基于优化，可选地使主要主体的致动器系统实现运动规划，其中与这种动态对象碰撞的可能性相对较低。

又例如，在主要主体的目标是要与其环境中的动态对象发生碰撞的情况下，如果相应的边缘与一个或多个动态对象碰撞的概率相对较高，则系统可以为规划图的边缘分配具有相对较小的正值的权重，如果相应边缘与环境中的一个或多个动态对象发生碰撞的概率相对较低，则系统可以为规划图的边缘分配具有相对较高的正值的权重。然后，系统执行优化，以在最终的规划图中标识出一条路径，在这条路径中，与主要主体操作的环境中的一个或多个动态对象碰撞的概率相对较高。然后，系统至少部分地基于优化，可选地使主要主体的致动器系统实现运动规划，其中与这种动态对象碰撞的可能性相对较高。

在公开的实施方式中，存在一种计算策略，其中将晶格中的每个边缘初始化为“无碰撞”。采样其他主体(例如动态对象)的意图。例如，可以开发每个主体的行为模型，该模型将主体意图视为对潜在策略或目标，而不是对简单的轨迹进行建模。潜在策略或目标可以采用可以被采样以确定主体对其他主体轨迹如何反应的形式。每个主体的意图都会提供一条轨迹t，从而产生一组轨迹S。对于S中的每个样本未来轨迹t：确定与t碰撞的晶格中的边缘(可以同时执行)；并且增加了边缘的成本以反映碰撞概率(例如，如果10％的轨迹与边缘E碰撞，则E的碰撞概率为10％)。运行最小成本路径搜索(在应用一个或多个成本函数(包括概率碰撞的成本项)之后)以找到规划。边缘的成本不必是边缘碰撞概率的线性函数。

在主要主体的目标是避免与特定动态对象发生碰撞的情况下，运动规划器执行优化以识别得到的规划图中的路径，该路径为主要主体提供运动规划(例如行进路线)，在主要主体运行的环境中，主要主体与此类动态对象发生碰撞的可能性相对较低。然后，所述系统至少部分地基于优化，使得主要主体(例如，自动驾驶车辆)的致动器系统实现一种运动规划，其中与一个或多个对象碰撞的可能性相对较低。

在主要主体的目标是与特定动态对象发生碰撞的情况下，运动规划器执行优化以识别得到的规划图中的路径，该路径为主要主体提供运动规划(例如行进路线)，在主要主体运行的环境中，主要主体与此类动态对象发生碰撞的可能性相对较高。然后，所述系统至少部分地基于所述优化，使得主要主体(例如，自动驾驶车辆)的致动器系统实现一种运动规划，其中与一个或多个对象碰撞的可能性相对较高。

描述了一种在基于处理器的系统中通过规划图执行运动规划的操作的运动规划方法，其中每个规划图分别包括多个节点和边缘，每个节点隐式或显式表示时间和表征主要主体的特征的变量，所述主要主体在包括一个或多个其他主体的环境中运行，并且每个边缘代表相应的一对节点之间的过渡。

该方法可以总结为包括以下几点：对于第一规划图中的当前节点，在分别代表一个或多个其他主体中的至少一个主体的实际或预期轨迹的一组轨迹中的每个轨迹中，在任何边缘与相应的轨迹碰撞的情况下，确定第一规划图的哪一边缘与相应的轨迹碰撞；将成本函数应用于各个边缘中的一个或多个边缘以反映确定的碰撞和不存在碰撞中的其中一种；

对于第一规划图中的多个候选节点中的每一个候选节点，所述候选节点是第一规划图中的任何节点，该节点通过第一规划图的各个单个边缘直接连接到第一规划图中的当前节点，在所述第一规划图中找到从当前节点到目标节点的一条最小成本路径，该最小成本路径从当前节点直接传递到各自的候选节点，然后传递到所述目标节点，在相应的候选节点和目标节点之间连续有或没有沿着相应路径的多个中间节点；在针对轨迹集合的轨迹找到每个候选节点的最小成本路径之后，至少部分地基于与所有路径上的相应候选节点的每个最小成本路径相关联的各个成本计算每个候选节点的相应值；以及部分基于计算得出的相应值来选择其中一个候选节点。

将成本函数应用于各个边缘中的一个或多个边缘上以反映确定的碰撞或不存在碰撞中的其中一种可以包括：对于确定为与至少一个轨迹碰撞的任何边缘，增加各个边缘的成本至相对高的幅度反映了明确发生了碰撞，其中相对高的幅度相对高于反应至少一个其他边缘不存在碰撞的相对低的幅度。

将成本函数应用于各个边缘中的一个或多个边缘上以反映反映确定的碰撞或不存在碰撞中的其中一种可以包括：对于确定为未与至少一个轨迹碰撞的任何边缘，增加各个边缘的成本至相对高的幅度反映了不存在碰撞，其中相对高的幅度相对高于反应至少一个其他边缘存在碰撞的相对低的幅度。

该方法还可以包括针对环境中的至少一个其他主体，进行采样以确定其他主体的各自预期轨迹；以及根据确定的每个其他主体的相应实际或预期轨迹形成轨迹集。

该方法还可以包括基于候选节点从第一规划图的其他节点中在第一规划图中选择候选节点，所述候选节点是第一规划图中的任何节点，这一任何节点通过第一规划图中的各个单个边缘直接连接至第一规划图中的当前节点。

至少部分地基于与所有轨迹上的各个候选节点的每个最小成本路径相关联的各个成本来计算各个值，这种计算可以包括计算与每个最小成本路径相关联的各个成本的平均值，所述每个最小成本路径通过相应的候选节点以及通过所有的中间节点(如果存在中间节点)从所述候选节点一直延伸至所述目标节点。

至少部分地基于所计算的各个值来选择候选节点之一可以包括：选择具有相应计算得出的值的其中一个候选节点，其中相应计算得出的值为所有计算得出的值中的最小值。

该方法还可以包括基于所选择的候选节点之一来更新主要主体的轨迹。

该方法还可以包括在将成本函数应用于各个边缘以反映确定发生碰撞之前，初始化所述第一规划图。初始化所述第一规划图可以包括：对于所述第一规划图中的每个边缘，相对于环境中的多个静态对象中的每一个静态对象对边缘执行碰撞评估，以识别相应边缘和静态对象之间的碰撞(如果发生了碰撞)。初始化所述第一规划图可以包括：对于被评估为与至少一个静态对象碰撞的每个边缘，将成本函数应用于相应的边缘以反映所评估的碰撞或从第一规划图移除边缘。初始化所述第一规划图可以包括：对于第一规划图中的每个节点，计算从该节点到目标节点的成本；以及将所计算的成本与各个节点进行逻辑关联。

该方法还可以包括：在第一规划图中将所选择的候选节点之一分配为新的当前节点；以及对于第一规划图中的新当前节点，针对分别代表一个或多个其他主体中至少一个的实际或预期轨迹的一组轨迹中的每个轨迹，如果任何边缘与相应的轨迹碰撞，确定第一规划图的哪个边缘与所述相应的轨迹碰撞；将成本函数应用于一个或多个相应的边缘，以反应确定的碰撞或不存在碰撞中的其中一种；针对第一规划图中多个新的候选节点中的每一个候选节点，所述候选节点是第一规划图中的任何节点，该节点通过第一规划图的各个单个边缘直接连接到第一规划图中的新的当前节点，在所述第一规划图中找到从当前新的节点到目标节点的一条最小成本路径，该最小成本路径从新的当前节点直接传递到各自新的候选节点，然后传递到所述目标节点，在相应的新的候选节点和目标节点之间连续有或没有沿着相应路径的多个中间节点；在针对轨迹集合的轨迹找到每个新的候选节点的最小成本路径之后，至少部分地基于与所有路径上的相应的新的候选节点的每个最小成本路径相关联的各个成本计算每个新的候选节点的相应值；以及部分基于计算得出的相应值来选择其中一个新的候选节点。

描述了一种用于通过规划图执行运动规划的基于处理器的系统，其中每个规划图分别包括多个节点和边缘，每个节点隐式或显式表示时间和表征主要主体状态的变量，主要主体在包括一个或多个其他主体的环境中操作，并且每个边缘代表相应的一对节点之间的过渡。所述系统可以概括为包括：至少一个处理器；以及以及至少一种非暂时性处理器可读介质，其存储处理器可执行指令或或数据中的其中至少一个，其中在处理器可执行指令或或数据由所述至少一个处理器执行时，会导致所述至少一个处理器执行上述总结的任何方法。

描述了一种在运动规划系统中操作的方法，该方法采用具有表示状态的节点和表示状态之间的转换的边缘的图。该方法可以概括为包括：对于第一图中的相对于当前节点的每个可用的下一节点，经由所述至少一个处理器计算相应的相关联的代表性成本，以经由相应的下一个节点从当前节点开始到达目标节点，根据基于环境中一个或多个主体的非确定性行为来评估与环境中的一个或多个主体的碰撞概率，所述相应的相关联的代表性成本反应了与从当前节点经由相应的下一个节点到达目标节点的每条可用路径相关联的相应代表性成本，其中上述主体可不断改变位置、速度、轨迹、行进路径或形状；基于每个可用的下一个节点的计算得出的相应的相关联的代表性成本，由所述至少一个处理器选择下一个节点；以及至少部分基于所选择的下一个节点，由所述至少一个处理器发出运动指令。

计算从当前节点经由相应的下一个节点到达目标节点的各个相关联的代表成本，可以包括：对于当前节点经由相应的下一个节点到达目标节点之间的每个预期路径，对于沿着所述相应的代表路径的当前节点与目标节点之间的每个边缘，确定相应的相关联的代表成本；将确定的每个边缘的相应的相关联的代表成本分配给沿相应预期路径的当前节点和目标节点之间的每个边缘的相应边缘；

至少部分地基于所分配的所确定的相应相关联的代表成本，从当前节点与目标节点之间的各个预期路径经由各个下一节点来确定相应下一节点的最小成本路径；并将代表所确定的最小成本路径的值分配给相应的一个节点。

至少部分地基于所分配的所确定的相应的相关联的代表成本，经由相应的下一个节点确定从当前节点到目标节点之间的各个预期路径的所述相应的下一个节点的最小成本路径，包括：确定包括从当前节点到相应的下一个节点的成本的最小成本路径。

为沿着相应的预期路径的当前节点和目标节点之间的每个边缘确定相应的相关联的代表成本可以包括：对于沿着相应的预期路径的当前目标与目标节点之间的每个边缘，以及基于分别表示环境中一个或多个主体中的每个主体的不确定性行为的一个或多个概率函数，评估与环境中的一种或多种主体发生碰撞的风险。

基于分别表示环境中一个或多个主体中的每个主体的不确定性行为的一个或多个概率函数，评估与环境中的一种或多种主体发生碰撞的风险可以包括：鉴于一系列行为，对分别表示环境中一个或多个主体中的每个主体的不确定性行为的概率函数进行采样，其中所述一系列行为由沿着相应的预期路径的相应的下一个节点和每个连续的节点之间的每个边缘的相应一个所表示。

基于分别表示环境中一个或多个主体中的每个主体的不确定性行为的一个或多个概率函数，评估与环境中的一种或多种主体发生碰撞的风险可以包括：鉴于一系列行为，对分别表示环境中一个或多个主体中的每个主体的不确定性行为的概率函数进行采样，其中所述一系列行为由沿着相应的预期路径的相应的下一个节点和每个连续的节点之间的每个边缘的相应一个所表示，所述当前节点是在评估碰撞风险期间到达的沿着相应的预期路径的另一节点。

基于分别表示环境中一个或多个主体中的每个主体的不确定性行为的一个或多个概率函数，评估与环境中的一种或多种主体发生碰撞的风险可以包括：针对每个主体，对分别表示相应的主体的不确定性行为的相应的概率函数进行重复采样。对分别表示相应的主体的不确定性行为的相应的概率函数进行重复采样可包括：至少部分地基于命令必须发生之前的可用时间，针对多个迭代，全部的迭代对相应的概率函数进行重复采样。

基于分别表示环境中一个或多个主体中的每个主体的不确定性行为的一个或多个概率函数，评估与环境中的一种或多种主体发生碰撞的风险可以包括：鉴于一系列行为，对分别表示环境中一个或多个主体中的每个主体的不确定性行为的概率函数进行重复采样，其中所述一系列行为由沿着相应的预期路径的相应的下一个节点和每个连续的节点之间的每个边缘的相应一个所表示。

基于分别表示环境中一个或多个主体中的每个主体的不确定性行为的一个或多个概率函数，评估与环境中的一种或多种主体发生碰撞的风险可以包括：鉴于一系列行为，对分别表示环境中一个或多个主体中的每个主体的不确定性行为的概率函数进行采样，其中所述一系列行为由沿着相应的预期路径的相应的下一个节点和每个连续的节点之间的每个边缘的相应一个所表示，所述当前节点是在评估碰撞风险期间到达的沿着相应的预期路径的另一节点。

碰撞风险的评估包括模拟走遍各个预期路径。

基于分别表示环境中一个或多个主体中的每个主体的不确定性行为的一个或多个概率函数，评估与环境中的一种或多种主体发生碰撞的风险可以包括：至少基于环境中一个或多个主体中的每个主体的通过概率确定相应的轨迹，通过专门的风险评估硬件来评估碰撞风险，其中所述相应的相关联的代表成本至少部分基于所述评估得出的碰撞风险。

基于分别表示环境中一个或多个主体中的每个主体的不确定性行为的一个或多个概率函数，评估与环境中的一种或多种主体发生碰撞的风险可以包括：基于分别表示环境中主体的至少一个次要主体的不确定性行为的一个或多个概率函数，评估与环境中的一种或多种主体发生碰撞的风险，主体的主要主体是正在执行运动规划的那一个主体。

所述方法还可以包括：在计算经由相应的下一个节点从当前节点到达目标节点的相应的相关联的代表成本之前，初始化第一图形，可以包括：执行静态碰撞评估以识别与环境中的一个或读个主体的任何碰撞；对于第一图中的每个节点，计算经由相应的节点从相应的节点到达目标节点的各个成本；对于第一图中的每个节点，将到达目标节点的相应的计算得到的成本与相应的节点逻辑关联。

描述了用于执行运动规划的基于处理器的系统，该系统采用具有表示状态的节点和表示状态之间的转换的边缘的图。该系统可以概括为包括：至少一个处理器；以及至少一种非暂时性处理器可读介质，其存储处理器可执行指令或数据中的至少一个，当可执行指令或数据由至少一个处理器执行时，使至少一个处理器执行任何上述方法。

描述了运动规划系统中的一种操作方法，该方法采用具有表示状态的节点和表示状态之间的转换的边缘的图来生成主要主体的运动规划。该方法可以总结为包括：将步数计数器T初始化为初始值(T＝0)；初始化第一张图；运行模拟，该模拟包括：从第一张图中的当前节点N开始而不是从第一图中的目标节点G开始：对于一个或多个采样迭代，针对环境中一个或多个二级主体中的每个二级主体，根据概率函数使步进计数器递增(T+1，即下一步)时对相应二级主体采取的动作进行采样，该概率函数表示主要主体采取的动作以及一个或多个二级主体采取的动作，这些动作为从步进计数器的初始值至目标值；确定与下一个动作相碰撞的第一张图的任何边缘；对于与下一个动作发生碰撞的任何边缘，将相应的成本函数应用于边缘以反映碰撞条件的存在；对于直接连接到当前节点的一组节点的第一张图中的每个节点，计算表示最小成本路径的值，以通过一条或多条预期路径遍历经由相应的节点的从当前节点到目标节点的一个或多个路径，其中相应的节点直接连接到当前节点；确定是否执行另一个采样迭代；在确定不执行另一采样迭代时，从直接连接到当前节点的节点集合中选择成本最小的节点集合中的一个节点；递增步数计数器(T＝T+1)；确定模拟是否在目标节点处，在确定模拟不在目标节点处时，在不命令主要主体的情况下将所选节点设置为新的当前节点，并继续进行模拟；在确定模拟在目标节点处时，从直接连接到当前节点的节点集合中选择成本最小的节点；提供对所选择的具有最小成本的节点的标识，以命令主要主体的行动。

当步数计数器根据表示由一个或多个二级主体和主要主体从步数计数器的起始值到当前值所采取的动作的概率函数递增时，对相应的二级主体将采取的动作进行采样可以包括：鉴于主要主体所采取的一系列动作，对表示环境中的一个或多个二级主体的每个二级主体的不确定性行为的概率函数进行采样，其由直接连接至当前节点的相应节点和沿着路线至目标节点的每个连续节点之间的每个边缘的其中相应一个所表示。

基于每个边缘各自所代表的一系列动作，分别对表示环境中一个或多个主体中每个主体的不确定性行为的概率函数进行采样可以包括：对于每个主体，重复对分别表示相应主体的不确定性行为的概率函数进行采样。

所述主要主体可以是主要的自动驾驶车辆。该方法还可以包括：接收表示主要自动驾驶车辆在其中运行的环境的感知信息；并由主要的自动驾驶车辆实施最终的运动规划。接收感知信息可包括接收表示环境中至少一个动态对象的位置和轨迹的感知信息。接收知觉信息可包括在运动规划器处接收感知信息，通过一个或多个传感器收集所述感知信息，而这一个或多个传感器由主要的自动驾驶车辆

所携带，所述感知信息表示环境中的至少一辆其他车辆的位置或轨迹。

所述方法还可以包括由对象检测器根据经由一个或多个传感器收集的感知信息识别环境中的至少第一动态对象。

描述了一种运动规划系统，该系统采用具有表示状态的节点和表示状态之间的转换的边缘的图来生成主要主体的运动规划。可以将运动规划系统概括为包括：至少一个处理器；至少一个非暂时性处理器可读介质，其存储处理器可执行指令，当可执行指令由至少一个处理器执行时，使至少一个处理器执行任何上述方法。

附图说明

在附图中，相同的附图标记表示相似的元素或动作。附图中元件的尺寸和相对位置不必按比例绘制。例如，未按比例绘制各种元素的形状和角度，并且其中一些元素被任意放大并设置以提高图形的可读性。此外，所绘出的元素的特定形状并不旨在传达关于特定元素的实际形状的任何信息，并且仅是为了易于在附图中识别而选择的特定形状。

图1是根据一个示出的实施例的环境的示意图，其中主要主体(例如，自动驾驶车辆，具有或不具有附件的机器人等)可以在该环境中操作。

图2是根据一个示出的实施例的与可以在图1的环境中操作的与主要主体(例如，自动驾驶车辆，具有或没有可移动的附件的机器人等)相关联的计算机系统的功能框图。

图3是示出根据一个示出的实施例的在图2的计算机系统中的各个组件之间的示例数据流的框图。

图4A是根据一个示出的实施例的图1的主要主体的示例性运动规划图，在这种情况下，主要主体的目标是与图1中可能试图避开主要主体的动态对象碰撞。

图4B是根据一个示出的实施例的图1的主要主体的示例性运动规划图，在这种情况下，主要主体的目标是与图1中可能试图避开主要主体的动态对象碰撞，同时图4B是在主要主体的规划图中识别处的示例性路径，以与动态对象碰撞。

图5A是根据一个示出的实施例的图1的主要主体的示例性运动规划图，在这种情况下，主要主体的目标是避免与图1中接近主要主体的动态对象碰撞。

图5B是根据一个示出的实施例的图1的主要主体的示例性运动规划图，在这种情况下，主要主体的目标是避免与图1中接近主要主体的动态对象碰撞。，同时图5B是在主要主体的规划图中识别处的示例性路径，以避免与动态对象碰撞。

图6是根据一个示出的实施例的环境的示意图，主要主体(例如，自动驾驶车辆，具有或不具有附件的机器人等)可以在该环境中操作，并且其他主体人在该环境中具有已知的轨迹。

图7是根据一个示出的实施例的图6的主要主体的示例运动规划图，其示出了通过两个候选节点中的每一个候选节点的最小成本路径的示例，其中成本基于其他主体的已知轨迹来确定。

图8A是示出了根据一个示出的实施例的，经由规划图来标识主要主体的路径的方法的流程图，其中通过候选节点的路径具有最低的平均成本，其中该最低平均成本考虑了其他主体的已知轨迹。

图8B是示出根据一个示出的实施例的，用于计算在图8A的方法中的一组已知轨迹上平均的每个候选节点的成本的方法的流程图。

图9是根据一个示出的实施例的一种环境的示意图，主要主体(例如，自动驾驶驾驶汽车，具有或不带有附件的机器人等)可以在该环境中操作，且主要主体和其他主体在该环境中具有互相依存的轨迹。

图10是根据一个示出的实施例的图9的主要主体的示例运动规划图，其中示出了第一最小成本路径和第二最小成本路径的示例，基于其他主体的轨迹来确定第一最小成本路径和第二最小成本路径，在沿着当前节点到候选节点的第一最小成本路径来规划主要主体的运动之后根据概率模型来计算得出其他主体的轨迹。

图11A是示出一种通过规划图来识别主要主体的路径的流程图，路径通过具有最小平均成本的候选节点，其中考虑到了主要主体到目标的规划的路径和使用概率模型确定的其它主体的路径。

图11B是根据一个示出的实施例示出在图11A的方法中有用的方法的流程图，该方法基于主要主体到目标的规划路径以及根据概率模型确定的其他主体人的路径来计算每个候选节点的值。

图11C是根据一个示出的实施例示出在图11B的方法中有用的方法的流程图，该方法基于概率模型基于来自其他主体的采样的下一步骤的边缘碰撞成本来确定下一时间步骤的每个候选节点的值。

具体实施方式

在以下描述中，阐述了某些特定细节以便完全理解各种公开的实施例。但是，相关领域的技术人员将认识到，可以在没有一个或多个这些具体细节的情况下，或者利用其它方法、组件、材料等来实现实施例。在其他情况下，为了避免不必要地混淆实施例的描述，未详细示出和/或描述与计算机系统、致动器系统和/或通信网络关联的已知结构。在其他情况下，为了避免不必要地混淆实施例的描述，未详细描述用于生成一个或多个对象的感知数据和体积表示以及占用网格的构造的公知的计算机视觉方法和技术。

除非上下文另有要求，否则在整个在随后的说明书和权利要求书中，词语“包括”及其变体例如“包含”应理解为开放式的意义，即“包括但不限于”。

在整个说明书中，对“一种实施方式”或“一个实施例”的引用是指结合该实施例描述的特定特征、结构或特性包括在至少一种实施方式或至少一个实施例中。因此，在整个说明书中各处出现的短语“一种实施方式”或“一个实施例”不一定全部是指相同的实施方式或相同的实施例。此外，可以在一个或多个实施方式或实施例中以任何合适的方式来组合特定特征、结构或特性。

如本说明书和所附权利要求书中所使用的，除非内容中另有明确规定，否则单数形式“一”，“一个”和“该”包括复数指示对象。还应该注意的是，除非内容中另有明确规定，否则术语“或”通常以其包括“和/或”的含义使用。

在整个说明书中，对“主要主体”或“一个主要主体”的引用是指为其制定或生成相应的运动规划的主体(例如，半自动或全自动车辆，具有或不具有可移动附件的机器人)。在整个说明书中，对“其他主体”或“另一主体”或“二级主体”或“二级主体”的引用是指除为其制定或生成相应的运动规划的主体(例如，半自动或全自动车辆，具有或不具有可移动附件的机器人)之外的主体。在一些情况下，可能会对这些其他或二级主体指定运动规划的情况，但是那些运动规划并不是为主要主体制定的。

本文提供的本公开的标题和摘要仅是为了方便起见，并且不解释实施例的范围或含义。

图1示出了根据一个示出的实施例的动态操作环境100，主要主体(例如，自动驾驶车辆，具有或不具有可移动附件的机器人)102可以在该动态操作环境中进行操作。为了简洁起见，动态操作环境100在本文中被称为环境。尽管通常以自动驾驶车辆的方式进行描述，但是本文描述的各种实施方式适用于机器人或其部分，例如可操作来导航环境的机器人和/或具有一个或多个可移动附件的机器人。

该环境表示主要主体(例如，自动驾驶车辆)102可以在其中运行和移动的二维或三维空间。主要主体102可以是汽车、飞机、轮船、无人驾驶飞机或任何其他车辆，或者可以是另一种类型的机器人，其可以自主地或半自主地(即，至少部分地自主地)操作并沿着由环境100表示的空间中的路线或路径移动。

环境100是车辆在其中进行操作的二维或三维空间，与参照图4A至5B的运动规划图所引用的车辆的“配置空间”(通常称为“C空间”)不同，正如以下两个国际专利申请所述，其中一个申请为于2017年6月9日提交，题为“MOTION PLANNING FOR AUTONOMOUS VEHICLESAND RECONFIGURABLE MOTION PLANNING PROCESSORS”的国际专利申请No.PCT/US2017/036880，其全部内容通过引用并入本文，另一个申请为于2016年1月5日提交，题为“SPECIALIZED ROBOT MOTION PLANNING HARDWARE AND METHODS OF MAKING AND USINGSAME”的国际专利申请No.W/0 2016/122840，其全部内容通过引用并入本文。配置空间通常是多个二维的(即，大于3维)。参照图1，环境100可以包括障碍物碰撞区域。这些障碍物碰撞区域可能是由于静态对象(例如，建筑物、树木、岩石等)或动态对象(例如，其他基于空中或地面的车辆，人，动物，滚动的岩石，鸟类等)引起的，可以在环境100中将这些对象统称为“主体”或“其他主体”。例如，静态对象C 108表示在环境100中不移动并在环境100中创建碰撞区域的对象，如果这些静态对象试图同时占据环境100内的相同空间，则车辆102可能与静止对象C 108碰撞。在各种实施例中，可能有比图1所示更少或更多的静态对象。

除了静态对象之外，还可以存在动态对象，动态对象包括那些代表以已知/特定轨迹运动的对象(例如，跌落的砖块、滚动的罐子)，那些由有意识的人控制的对象(例如，骑自行车的人、行人、驾驶员、飞行员、鸟类等)以及由其他自主系统控制的对象，例如其他自动驾驶车辆或机器人。由于这些动态对象而使运动规划面临的挑战包括以非常快的速度执行运动规划的能力以及分析动态对象可能如何运动的不确定性的能力。车辆102周围的环境100可以快速变化，并且车辆102执行运动规划以跟上那些变化是有利的。例如，如图1所示，例如动态对象A 104的主体当前正在沿着轨迹110移动离开车辆102。但是，在某些情况下，可能需要车辆102跟随或拦截动态对象A 104，例如在游戏中，检查动态对象A 104，从动态对象A 104收集信息，与动态对象A 104交换信息，甚至与动态对象A 104碰撞。

相反，如图1所示，动态对象B 112当前正在沿着轨迹106向车辆102移动。在某些情况下，可能需要车辆102避免与动态对象B 112碰撞或避免靠近动态对象B 112，例如不出现碰撞的情况下到达目标位置，避免此类碰撞造成的损坏，或避免例如在游戏中与动态对象B112接触。在一实施例中，车辆102的目标是在不与动态对象B 112碰撞的情况下最大化时间，以使得例如动态对象B 112在与车辆102碰撞之前耗尽燃料。在一个示例实施例中，车辆102的目标是在当前时间和车辆达到目的地之间或实现特定目标之间，或在当前时间和动态对象B 112燃料用尽之间，尽可能地减少与动态对象B 112碰撞的可能性。环境100中可能存在图1中所示更少或更多的动态对象。此外，在某些情况下，环境可能具有与车辆102的范围相对应的边界，该边界可能至少部分取决于车辆102可用的当前的燃料或能源。

尽管图1示出了代表性环境100，但是典型的环境可以包括许多额外的主体，包括与其他有人驾驶和自动驾驶车辆相对应的对象以及各种其他天然或人工的静态和动态对象以及障碍物。本文所教导的概念可按照类似的方式用在比示出的环境的人口更稠密的环境中。

图2和下面的讨论以计算机系统200的形式提供了合适的控制器的简要概述，其中可以实现各种示出的运动规划系统和方法。

尽管不是必需的，但是将在计算机可执行指令的一般上下文中描述许多实施例，所述计算机可执行指令例如是存储在计算机或处理器可读介质上并由计算机或处理器和专用车辆运动规划硬件执行的程序应用模块，对象或宏，计算机或处理器和专用车辆运动规划硬件可以评估碰撞和执行运动规划操作。这样的运动规划操作可以包括在规划图的边缘上执行碰撞评估，确定和设置碰撞的可能性，执行优化以识别规划图中的路径，通过在规划图中找到最小成本路径并实现这样的运动规划来避免碰撞或引起与环境中的物体的碰撞。

通过运动规划器执行的运动规划通常包括碰撞检测和找到最小成本路径。例如，可以在一个或多个现场可编程门阵列(FPGA)上实现碰撞检测和/或找到最小成本路径，从而有利于实现轻松的可重新配置性。例如，可以在一个或多个专用集成电路(ASIC)上实现碰撞检测和/或找到最小成本路径，从而有利地允许快速处理，同时仍然允许某些可重新配置性。

当代表主体，例如车辆(例如，自动驾驶车辆或机器人)或环境中的物体(例如，静态或动态障碍物))时，可以将车辆或环境中的物体的表面表示为体素(3D像素)或多边形网格(通常是三角形)。每个离散的空间区域都称为“体素”，体素相当于3D(体积)像素。在某些情况下，将对象表示为框(矩形棱镜)是有利的。由于对象不是随机成形的，因此体素的组织方式可能存在大量结构；一个对象中的许多体素在3D空间中彼此相邻。因此，将对象表示为框可能需要少得多的比特(即，可能仅需要框的两个相对角的x，y，z坐标)。同样，对框进行相交检测的复杂性同对像素进行相交检测的复杂性相当。各种其他数据结构可用于表示对象的3D表面，例如，欧几里得距离场，二进制空间分区树等。

在一个实施例中，通过首先在所有动态对象体素(或框)中流式传输到处理器(例如，FPGA，ASIC)上来执行碰撞评估。然后，从专用于路线图的存储器中流送车辆102的路线图的每个边缘的边缘信息。当在路线图中从一个状态转换到由边缘表示的另一状态时，每个边缘具有相同数量的体素(或框)，这与车辆102扫过的3D空间中的体积相对应。当在路线图中从一个状态转换到由该边缘表示的另一状态时，由车辆102扫过的那些体素或框存储在存储器中，用于该路线图的每个边缘。对于每个边缘体素(或框)，当每个边缘体素(或框)从边缘的波及体积中流进来时，如果其与任何障碍物体素(或框)发生碰撞，则系统200确定与路线图中的该边缘的碰撞。例如，从路线图的边缘x的波及体积中流入边缘体素时，如果它与任何障碍物(或框)相撞，则系统会记录与边缘x的碰撞。此实现改进了碰撞评估技术，因为与在规划图中的所有边缘上并行执行碰撞评估的其他设计相比，这种实现使得可以在碰撞评估中用到大得多的路线图。这尤其有助于克服其他设计的缺点，即，可以存储在芯片电路上的路线图信息非常有限。

但是，使用本文所述的碰撞评估方法，片上存储通常足以存储所有障碍物箱(尽管使用体素时可能更少)。这提供了将大型路线图和/或多个路线图存储在较便宜的片外存储中的能力，片外存储例如为动态随机存取存储器(DRAM)。

在各种实施方式中，这样的操作可完全在硬件电路中执行，或者这样的操作可作为软件为存储在存储器(例如，系统存储器214)中，并由一个或多个硬件处理器212a执行，例如，一个或多个微处理器，数字信号处理器(DSP)，现场可编程门阵列(FPGA)，专用集成电路(ASIC)，图形处理单元(GPU)处理器，可编程逻辑控制器(PLC)，电可编程只读存储器(EEPROM)，或作为硬件电路和存储在存储器中的软件。例如，可以通过优化器292执行优化以通过在规划图中找到最小成本路径来识别规划图中的路径，从而避免与环境中的对象发生碰撞或引起与物体的碰撞。在一个示例实施例中，当路径优化器292是用硬件实现的，规划图的拓扑也可以映射到硬件单元的可重新配置的结构上，以快速确定最小成本路径。这种映射涉及使用其逻辑邻居的地址和边缘权重对每个物理节点进行编程。这允许将体系结构重新配置为不同的规划图拓扑。其他实施方式可以使用在FPGA上实现的微型处理器。

在替代实施例中，可以通过专用运动规划硬件在车辆102的所得规划图的每个边缘上并行执行碰撞评估，这里所述的专用运动规划硬件例如可重新配置的碰撞检测体系结构和以下专利申请中所述的其他实施例，于2017年6月9日提交，题为“MOTION PLANNINGFOR AUTONOMOUS VEHICLES AND RECONFIGURABLE MOTION PLANNING PROCESSORS”的国际专利申请PCT/US2017/036880，另一个申请为于2016年1月5日提交，题为“SPECIALIZEDROBOT MOTION PLANNING HARDWARE AND METHODS OF MAKING AND USING SAME”的国际专利申请W/0 2016/122840。例如，这些专用运动规划硬件的全部或部分可以被合并到运动规划器280和碰撞评估器288中或形成运动规划器280和碰撞评估器288的一部分。此外，以下国际专利申请中也描述了感知，规划图构造、碰撞检测和路径搜索的各种相关方面的实现，所述国际专利申请为于2017年6月9日提交，题为“MOTION PLANNING FOR AUTONOMOUSVEHICLES AND RECONFIGURABLE MOTION PLANNING PROCESSORS”的国际专利申请PCT/US2017/036880，另一个申请为于2016年1月5日提交，题为“SPECIALIZED ROBOT MOTIONPLANNING HARDWARE AND METHODS OF MAKING AND USING SAME”的国际专利申请W/02016/122840。相关领域的技术人员将理解，可以利用其他系统配置和/或其他计算系统配置来实现示出的实施例和其它实施方式，所述的其他系统配置和/或其它计算系统配置包括：机器人，手持设备，多处理器系统，基于微处理器或可编程的消费者电子产品，个人计算机(“PC”)，联网的PC，小型计算机，大型计算机等。可以在分布式计算环境中实践实现或其部分(例如，在设计时，配置时，运行前)，在分布式计算环境中，任务或模块由通过通信网络链接的远程处理设备执行。在分布式计算环境中，程序模块可以位于本地和远程存储设备或媒体中。但是，具有用于车辆102的有效计算能力对于允许车辆102实时地对变化的环境做出响应是重要的。该问题的普遍部署的解决方案未能解决性能和电源问题。它们太慢，以至于无法让高自由度的车辆和机器人对环境做出实时响应，并给多个CPU或GPU供电给系统造成负担。为了解决这个问题，图2的示例实施方式中示出的计算机系统200包括运动规划器280，该运动规划器280在车辆102上具有碰撞评估器288，该碰撞评估器288使用完全可重新定向的碰撞检测微体系结构，例如FPGA 290。但是，包括可编程逻辑块的阵列和可重配置互连的层次结构的其它可编程碰撞检测微体系结构可用于诸如ASIC体系结构的各种替代实施例中。通过编程阶段，碰撞检测微体系结构可以应用于任何车辆规划问题。碰撞评估器288可以实现避免与特定对象碰撞和/或寻求与其他对象的碰撞。使用可重配置处理器作为碰撞评估器288，有效地消除了设计专门针对单个车辆/路线图对的限制。最小成本路径模块允许例如使用分布式Bellman-Ford策略来快速计算最小成本路径。

如上所述，一些预处理活动可以在运行时间之前执行，因此，在一些实施例中，这些操作可以由远程处理设备执行，这些远程处理设备通过通信网络经由网络接口280链接到车辆200。例如，编程阶段允许针对感兴趣的问题配置处理器。在这样的实施例中，利用广泛的预处理来避免运行时计算。将预计算的3D空间中的体积的数据发送至运动规划器280的碰撞评估器288，其中当在路线图中从由路线图中的边缘所表示第一个状态转换到另一状态时，车辆102扫过3D空间中的体积。还可以将路线图的拓扑映射到诸如FPGA 290之类的计算单元的可重配置结构上，以实现对最小成本路径的快速确定。映射步骤包括用其逻辑邻居的地址和边缘权重对计算单元的可重配置结构的每个物理节点进行编程。这使体系结构可以针对不同的路线图拓扑。在运行时间阶段期间，传感器282将感知数据发送到运动规划器280。感知数据是当前环境中存在其体素或框(在下面更详细描述)的流。碰撞评估器288计算哪些运动可能涉及碰撞而哪些运动不涉及碰撞，并且在完成这些碰撞评估时，规划优化器292使用评估结果来确定最小成本路径。这可以有利地发生而无需与传感器282或其他外部组件进一步通信。运动规划器280根据车辆102的目标，在运行期间基于环境相应地修改与路线图相关联的成本，以避免或寻求与环境中的特定物体碰撞。运动规划器280然后运行并将所得路径返回至致动器系统286。图2示出了计算机系统200，例如用于自动驾驶车辆102的计算机系统，其包括运动规划器280和一个或多个相关联的非暂时性机器可读存储介质，诸如与磁盘驱动器224相关联的系统存储器214和计算机可读介质226。包括系统存储器214和与磁盘驱动器224相关联的计算机可读介质226的相关的非暂时性计算机或处理器可读存储介质经由一个或多个通信通道，例如系统总线216，通信地连接至运动规划器280。系统总线216可以采用任何已知的总线结构或体系结构，包括具有存储器控制器的存储器总线，外围总线和/或本地总线。一个或多个传感器282，对象检测器284，对象行为预测器286和致动器系统266也经由系统总线216通信地连接到运动规划器280。这些组件中的一个或多个组件可以或替代地通过一个或多个其他通信通道彼此通信，这些通信通道例如：一个或多个并行电缆，串行电缆或能够进行高速通信的无线网络通道，例如通用串行总线(“USB”)3.0，外围组件互连Express(PCIe)或雷电

计算机系统200还可以可通信地连接到远程系统，例如台式计算机、膝上型计算机、超便携式计算机、平板计算机、智能手机、可穿戴计算机(未示出)，这些远程系统通过网络接口260直接可通信地连接或间接地可通信地连接至计算机系统200的不同组件上。在实施方式中，计算机系统200本身或其部分可以是远程的。这样的远程系统可以用于对计算机系统200和计算机系统200内的各种组件进行编程，配置，控制或以其他方式与计算机系统200和计算机系统200内的各种组件进行接口，或向其输入数据。这种连接可以通过一个或多个通信信道，例如一个或多个广域网(WAN)，例如使用互联网协议的互联网进行。如上所述，可以通过与车辆102或其他类型的机器人分离的系统来执行运行前计算(例如，初始路线图生成)，同时可以在车辆102上进行运行计算，因为系统能够更新或改变车辆速度以实时或接近实时(微秒)作出反应，以及对变化的操作环境100作出反应是很重要的。

以下国际专利申请中描述了图2中示出的不同框的结构和操作的一些方面，于2017年6月9日提交，题为“MOTION PLANNING FOR AUTONOMOUS VEHICLES ANDRECONFIGURABLE MOTION PLANNING PROCESSORS”的国际专利申请PCT/US2017/036880，另一个申请为于2016年1月5日提交，题为“SPECIALIZED ROBOT MOTION PLANNING HARDWAREAND METHODS OF MAKING AND USING SAME”的国际专利申请W/0 2016/122840。因此，正如相关领域技术根据本文通过引用的并入的参考文献来理解的那样，不会对这些框进行详细描述。

计算机系统200可以包括一个或多个处理单元212a、212b(统称为212)，系统存储器214和系统总线216，该系统总线216将包括系统存储器214的各种系统组件连接到处理单元212。处理单元212可以是任何逻辑处理单元，例如一个或多个中央处理单元(CPU)212a，数字信号处理器(DSP)212b，专用集成电路(ASIC)，现场可编程门阵列(FPGA)等。此类ASIC和FPGA可以代替碰撞评估器288的FPGA 290或在碰撞评估器288的FPGA 290的FPGA 290的基础上使用此类ASIC和FPGA，在车辆102的规划图的边缘上进行碰撞评估。系统存储器214可以包括只读存储器(“ROM”)218和随机存取存储器(“RAM”)220。可以形成ROM 218的一部分的基本输入/输出系统(“BIOS”)222包含基本例程，基本例程例如在启动期间有助于在计算机系统200中的各个元素之间传递信息。

计算机系统200可以包括磁盘驱动器224，磁盘驱动器224可以是例如用于从硬盘读取和写入到硬盘的硬盘驱动器，用于从闪存设备读取和写入到闪存设备的闪存驱动器，用于从可移动光盘读取和写入可移动光盘的光盘驱动器，或用于从磁盘读取和写入磁盘的磁盘驱动器。在各种不同的实施例中，计算机系统200还可以包括这种磁盘驱动器的任何组合。磁盘驱动器224可以经由系统总线216与处理单元212通信。正如本领域技术人员所知，磁盘驱动器224可以包括连接在这样的驱动器和系统总线216之间的接口或控制器(未示出)。磁盘驱动器224及其关联的计算机可读介质226为计算机系统200提供了计算机可读指令，数据结构，程序模块和其他数据的非易失性存储。相关领域的技术人员将理解，可以使用可存储可通过计算机访问的数据的其他类型的计算机可读介质，例如WORM驱动器、RAID驱动器、盒式磁带、数字视频磁盘(“DVD”)、Bernoulli盒式磁带、RAM、ROM、智能卡等。

程序模块可以存储在系统存储器214中，例如操作系统238，一个或多个应用程序238，其他程序或模块240和程序数据242。应用程序238可以包括使处理器212执行以下操作的指令：在对应于环境100的规划图的边缘上执行碰撞评估，确定和设置规划图的每个边缘的碰撞概率，执行优化以识别规划图上的路径以避免或引起与环境100中的主体(例如，动态对象B 112)碰撞。识别规划图中的路径的优化可以包括在规划图中找到最小成本路径。应用程序238可以包括多个指令，这些指令然后使处理器212向致动器系统288发送信号，以使车辆102根据本文所述的运动规划来运动。应用程序238可以另外包括一个或多个机器可读指令，这些机器可读指令使一个或多个处理器212(通过传感器282)执行其他感知操作，规划图构造，碰撞检测和路径搜索，如本文和通过引用并入本文的参考文献所述。

应用程序238可以另外包括一个或多个机器可读指令，这些机器可读指令使一个或多个处理器212从传感器282接收表示车辆102在其中运行的环境100的感知信息；这些机器可读指令使运动规划器280使用碰撞评估器288的可重新配置的碰撞检测体系结构硬件来对车辆102的所得规划图的两个或更多个边缘中的每一个边缘进行碰撞评估；对于所得的规划图的两个或更多边缘中的每一个边缘，至少部分基于碰撞评估来设置碰撞概率；执行优化以在所得的规划图中识别一条路径，其中与车辆102在其中运行的环境100中的一个或多个其他主体(例如，动态对象A 104)碰撞的概率相对较高；并使致动器系统266至少部分地基于优化来实现运动规划，其中与车辆102在其中运行的环境100中的一个或多个其他主体(例如，动态对象A 104)碰撞的概率相对较高。可重配置碰撞检测体系结构硬件可以是例如FPGA290。但是，在各种替代实施例中可以使用包括可编程逻辑块阵列和可重配置互连的层次结构的其他可编程碰撞检测微体系结构，例如ASIC体系结构。

应用程序238可以另外包括一个或多个机器可读指令，这些指令对于一个规划图使一个或多个处理器212至少部分地基于与环境中与一个或多个动态对象(104、112)的碰撞概率的评估来进行以下操作，其中车辆102在环境中运行：如果相应的边缘与环境100中的一个或多个动态对象(104、112)碰撞的概率相对较低，则将值等于或大于0的权重分配给规划图的每个边缘；如果相应的边缘与环境100中的一个或多个动态对象(104、112)碰撞的概率相对较高，则将值小于0的权重分配给规划图的每个边缘；并执行优化，以在所得的规划图中识别一条路径，其中与车辆102在其中运行的环境100中的一个或多个动态对象(104、112)碰撞的可能性相对较高。

应用程序238可以另外包括一个或多个机器可读指令，一个或多个机器可读指令使一个或多个处理器212经由代表车辆102在其中运行的环境100的传感器282来接收感知信息；使运动规划器280使用碰撞评估器288的可重新配置的碰撞检测体系结构硬件来对规划图的两个或多个边缘中的每一个边缘进行碰撞评估；对于规划图的两个或更多边缘中的每一个边缘，至少部分基于碰撞评估来设置碰撞概率；执行优化以在所得规划图中识别一条路径，其提供了车辆102在路径指定的二维或三维空间中的最长行驶路线，其中与车辆102在其中运行的环境100中的一个或多个动态对象(例如，动态对象B 112)的碰撞可能性相对较低；并至少部分基于优化来实现一种运动规划，其中与车辆102在其中运行的环境100中的一个或多个动态对象(例如，动态对象B 112)的碰撞可能性相对较低。

应用程序238可以另外包括一个或多个机器可读指令，这些一个或多个机器可读指令使一个或多个处理器212执行本文所述的各种其他方法，包括但不限于图6至图13所示的那些方法。

尽管在图2中被示为存储在系统存储器214中，但是操作系统236、应用程序238、其他程序/模块240和程序数据242可以存储在磁盘驱动器224的关联计算机可读介质226上。

一个或多个处理器212可以是任何逻辑处理单元，例如一个或多个中央处理单元(CPU)，数字信号处理器(DSP)，专用集成电路(ASIC)，现场可编程门阵列(FPGA)等。可商购获得的计算机系统的非限制性示例包括但不限于：美国英特尔公司提供的Celeron，Core，Core 2，Itanium和Xeon系列微处理器；美国超威半导体公司提供的K8，K10，Bulldozer和Bobcat系列微处理器；美国苹果计算机公司提供的A5，A6和A7系列微处理器；美国高通公司提供的Snapdragon系列微处理器；以及美国甲骨文公司提供的SPARC系列微处理器。除非另有说明，图2中所示的各个块的结构和操作是常规设计的。因此，如相关领域的技术人员将理解的那样，本文不需要进一步详细描述这样的框。运动规划器280的碰撞评估器288的可重新配置的碰撞检测体系结构硬件可以是于2017年6月9日提交，题为“MOTION PLANNINGFOR AUTONOMOUS VEHICLES AND RECONFIGURABLE MOTION PLANNING PROCESSORS”的国际专利申请PCT/US2017/036880中所述的其中一种体系结构，例如为每个边缘提供“边缘模块”阵列的体系结构，该“边缘模块”具有与逻辑门并联连接的存储机制和比较器，以对并行线的输出执行“OR”(或)操作，以产生碰撞结果。

图3是示出根据一个示出的实施例的在图2的计算机系统中的各个组件之间的示例数据流300的框图。一个或多个传感器282，例如照相机、激光传感器设备、音频传感器等，被并入主要主体102中或与主要主体102可操作地通信，收集感知信息302并将感知信息传达给对象检测器284以产生环境100的模型。对象检测器284提取与检测到的主体(例如环境100中的动态对象A 104和动态对象B 112)有关的轨迹信息，并将这种轨迹信息308传达给对象行为预测器286。如轨迹信息308所指示，至少部分地基于环境100中当前检测到的动态对象(104、112)的轨迹，对象行为预测器286生成动态对象(104、112)的一个或多个预测轨迹，并且将该信息作为预测轨迹信息306的一部分传达给运动规划器280。例如，如果轨迹信息308指示动态对象A 104目前在沿着特定方向前进的轨迹上，则对象行为预测器286可预测动态对象A 104继续在其当前轨迹上的概率为40％，而它作出其它动作的概率为60％。

各种因素可以影响对环境100中的动态对象(104、112)的预测轨迹的对象行为预测器286的确定。例如，在一些实施方式中，可以指示或确定动态对象(104、112)具有将影响其在环境100内的未来移动的目标。作为一个示例，可以指示或确定检测到当前处于直接远离主要主体102的轨迹上的动态对象A 104具有远离(以及保持远离)主要主体102的目标。因此，对象行为预测器286在预测动态对象A 104的运动时可以考虑这一点。另一方面，可以指示或确定检测到当前处于朝向主要主体102的轨迹上的动态对象B 112具有与主要主体102碰撞的目标。因此，对象行为预测器286在预测动态对象B 112的运动时可以考虑这一点。

此外，其他主体(例如，动态对象(104、112))的运动可能会受到主要主体102的轨迹变化的影响。因此，对象行为预测286在确定动态对象(104、112)的预测轨迹时可将计划的，但未实现的或执行的主要主体102的当前轨迹变化考虑入内，并将这种数据包含在提供给运动规划器280中的预测轨迹信息306中。例如，如果指示或确定检测到当前正直接朝向主要主体102的轨迹上的动态对象B 112具有与主要主体102碰撞的目标，可以预测，如果主要主体102改变其轨迹，则动态对象B 112可以在其轨迹上进行相应的更改以追赶主要主体102。因此，如果主要主体102的目标是到达环境100内的目的地而不与动态对象发生碰撞B112(动态对象正想要与主要主体102发生碰撞)，则运动规划器280可以规划到目的地的路径，以避免与动态对象B 112发生碰撞，同时考虑到在主要主体102改变其轨迹以到达目的地时，动态对象B 112可以对其轨迹作出相应改变以追逐主要主体102。

总体上，该系统通过使用传感器282以及由对象检测器284和对象行为预测器288执行的处理的组合来执行感知，以产生环境100的模型。在一种实施方式中，传感器282产生占用网格。占用网格是一种数据结构，表示在离散化的环境(例如环境100)中，哪些空间和时间区域包含障碍物。每个离散化的空间区域都称为“体素”，相当于3D(体积)像素。在某些情况下，将对象表示为框(矩形棱柱)是有利的。由环境中的对象(包括动态对象A 104，动态对象B 112和静态物体C 108)定义的空间区域由这种体积表示来表示。将一个或多个动态对象(例如，动态对象A 104和动态对象B 112)的体积表示以及相关静态对象的体积表示从对象检测器284传达到运动规划器280。在计算机视觉和感测领域的普通技术人员可获得的和已知的大量公开文献中描述了占用网格的构造。

运动规划器280接收感知数据，包括来自对象检测器284的动态和静态对象的体积表示以及来自对象行为预测器的预测轨迹信息。然后，运动规划器280调整规划图中沿每个边缘的碰撞概率，以导致与感知数据中的障碍物发生碰撞，以说明预测的轨迹，确定考虑了成本和碰撞概率的路径，并将该路径输出至计算系统。

运动规划器可以包括硬件处理器和存储器，作为运动规划器280内的碰撞评估器288的一部分。例如，FPGA 290或其他可编程逻辑块阵列可以存储规划图，在此也称为“路线图”(例如，参见图4A至5B)。在一些实施方式中，运动规划器280包括硬件碰撞检测电路，例如FPGA 290，以执行碰撞检测。在一些实施方式中，运动规划器280包括可重新配置的碰撞检测加速度。当在路线图中由路线图中的边缘表示的一个状态转换到另一个状态时，有关由主要主体102扫过的2D或3D空间中的体积的数据可以存储在运动规划器280的碰撞评估器288的存储器中，使得在运动规划期间，当接收到包括预测的轨迹信息的感知数据时，碰撞评估器288的硬件处理器将感知数据与碰撞评估器288的存储器(或计算机系统200的本地系统存储器214)中存储的数据进行比较，以确定碰撞。在运行期间，可以基于一个或多个变量为规划图的边缘分配信息。例如，在主要主体102的目标是与动态对象A 104碰撞的情况下，基于根据预测的轨迹信息306对动态对象A 104的前进方向的预测，运动规划器280将生成主要主体102与动态对象A 104碰撞的运动规划。为此，碰撞评估器288针对与动态对象A 104碰撞的可能性评估规划图中的所有边缘。请注意，环境100是主要主体102在其中运行的二维或三维空间，并且与参考图4A至图5B中所示的运动规划图引出的主要主体的“配置空间”不同。主要主体的配置空间是表征主要主体的状态的主要主体102的所有配置的空间，通常是多维空间，例如，具有三个以上的维度。图4A至图5B中表示的规划图400和500中的边缘表示主要主体102的配置之间的转换。规划图400的边缘不一定表示笛卡尔坐标中的实际移动，但是在某些实施例中它们可以表示笛卡尔坐标中的实际移动。规划图400的边缘还可以包括速度变化等。

规划图400和500的每个边缘表示主要主体从一个状态到另一状态的转换，并且具有与之相关的固有或运营成本。例如，固有或运营成本可以与燃料使用，执行相关联的动作的时间，与该动作相关联的磨损和/或其他因素有关。为每个边缘分配一个初始权重，该权重对应于固有成本或运营成本。

该系统在运行时间期间调整边缘的成本，以至少部分地基于碰撞评估来表示与环境中的动态对象(104、112)碰撞的概率。该系统可以通过基于碰撞的概率修改每个边缘的初始分配的权重来执行成本的调整。例如，系统可以将成本函数应用于每个边缘，以基于该边缘的初始权重(即，与固有成本相对应的权重)执行数学运算以获得修改后的权重。这可以通过基于碰撞概率将附加权重添加到初始分配的权重，通过将初始分配的权重乘以碰撞因子的概率，或通过应用涉及碰撞概率和与固有成本相一致的初始权重的一些函数或公式来实现这一点。

还可以在运行时间期间调整分配给边缘的固有或运营成本，以反映特定于对象的成本，这些特定于对象的成本表示避免与对象发生碰撞或实现于对象的碰撞的相对重要性和/或严重性。这些特定于对象的成本与固有或运营成本无关，并且与碰撞的可能性无关。例如，可以将与人的碰撞相关联的特定于对象的成本设置为明显高于与无生命的物体碰撞相关联的特定于对象的成本。

为了简化图4A至5B中的图示，已经将与每个边缘的固有成本相对应的所有初始权重设置为零，并且通过添加指示碰撞概率的附加成本来进行调整。

因此，在一种主要主体102的目标是与环境中的动态对象(例如动态对象A 104)碰撞的实施方式中，初始权重0加上碰撞概率为零会导致边缘权重为0，而碰撞概率更大会导致边缘权重具有更大负值(即，具有较大绝对值的负数)。在一种主要主体102的目标是避免与环境中的动态对象(例如动态对象B112)碰撞的实施方式中，碰撞概率更大大致调整的边缘权重具有较大的正值。

一旦调整了规划图的所有边缘权重，路径优化器292就根据从规划图中指示的主要主体102的当前位置到主要主体102用尽燃料/动力的所有可能终点处执行最小成本路径算法。然后，运动规划器280选择规划图中的最小(最负)路径。

一旦路径优化器292识别了规划图中的路径，运动规划器便立即将此识别的路径310实时传达给主要主体102的致动器系统266，以生成相应的信号给主要主体102的各种电机或运动系统，以使主要主体102的物理运动发生，以实现运动规划。

图4A是根据一个示出的实施例，在主要主体102的目标是与可能试图避开主要主体102的图1的动态对象A 104碰撞的情况下，图1的主要主体102的示例运动规划图400。规划图400包括通过边缘连接的多个节点。例如，节点408b和节点408c通过边缘410a连接。每个节点隐式地或显式地表示时间和变量，这些时间和变量表征了在主要主体配置空间中的主要主体102的状态。

在本示例中，主要主体的配置空间(通常称为C-空间)是在规划图400中表示的主要主体的配置空间，这些空间表征了主要主体的状态。规划图400中的边缘代表主要主体102的这些配置之间的转换。规划图400的边缘不代表笛卡尔坐标中的实际运动。例如，每个节点可以代表主要主体的配置，其可以包括但不限于主要主体102的当前位置，姿势，速度和前进方向。在一些实施例中，主要主体102的加速度也由规划图400中的节点表示。

规划图400的每个边缘表示对象102在相应的一对节点之间的过渡。例如，边缘410a表示对象(例如，主要主体102)在两个节点之间的过渡。特别地，边缘410a表示在与节点408b相关联的特定配置下主要主体102的状态与节点408c相关联的主要主体102的状态之间的转换。例如，主要主体102当前可以处于与节点408a相关联的特定配置中。尽管示出的节点彼此之间相距各种距离，但这仅出于说明目的，并且与任何物理距离无关，并且对规划图400中的节点数量没有限制。但是，规划图400中用到的节点越多，运动规划器280就可以根据主要主体102的目标更准确和精确地确定优化路径，因为可从更多的路径中选择最小成本路径。

在某些情况下，可能需要主要主体102跟随或拦截动态对象A 104，例如检查动态对象A 104，从动态对象A 104收集信息，与动态对象A 104交换信息，甚至与游戏中的动态对象A 104碰撞。图4A示出了在主要主体102的目标是与动态对象A 104碰撞的情况下，运动规划器280如何使用规划图来标识主要主体102的路径。此时，运动规划器280已接收感知信息，该感知信息表示主要主体102在其中运行的环境100。如上所述，碰撞检测可以使用体素或框向运动规划器280表示环境中的对象，包括主要主体102和动态对象A104，但是，应当理解，可以使用其他对象表示。

在一种实施方式中，将环境离散为体素或框的3D区域。然后，预先计算环境100中的主要主体102的每个动作的波及体积与离散空间中的体素或框之间的所有可能的碰撞。这种碰撞评估的示例示出在以下国际专利申请中，于2017年6月9日提交，题为“MOTIONPLANNING FOR AUTONOMOUS VEHICLES AND RECONFIGURABLE MOTION PLANNINGPROCESSORS”的国际专利申请PCT/US2017/036880，另一个申请为于2016年1月5日提交，题为“SPECIALIZED ROBOT MOTION PLANNING HARDWARE AND METHODS OF MAKING AND USINGSAME”的国际专利申请W/0 2016/122840。

由于动态对象A 104在环境100中移动，运动规划器280还基于预测动态对象A104将朝着哪一个位置前进来确定规划图400中两个或更多边缘的主要主体102与动态对象A104的碰撞评估。对于规划图400的这些边缘中的每一个边缘，运动规划器280至少部分地基于碰撞评估来设置主要主体102在特定的未来时间与动态对象A 104碰撞的概率。例如，根据感知信息，动态对象A 104被检测为处于环境100中的特定位置。基于动态对象A 104的当前轨迹110，运动规划器280确定动态对象A 104将在环境100中的特定位置。对于规划图400中的节点，节点之间的直接移动可能会导致与动态对象A 104发生碰撞，运动规划器将权重分配给在那些节点之间过渡的规划图400的边缘(边缘410b，410c，410d，410e，410f、410g，410h，410i、410j，410k)，指示与动态对象A 104发生碰撞的可能性。在图4A所示的示例中，这表示为曲线图部分414，但不对应于物理区域。

例如，运动规划器280可以向规划图400的多个边缘中的每个边缘分配一个等于或大于0的值的权重，其中每个边缘具有与动态对象A 104碰撞的相应概率，这概率低于碰撞的阈值概率。在本实施例中，运动规划器280分配了值为0的权重给规划图400中的那些边缘，根据动态对象A104的当前轨迹，那些边缘不具有与动态对象A104碰撞的任何概率(或几乎不存在这种碰撞概率)。

例如，如规划图400所示，运动规划器280已为边缘410a分配了零权重，因为根据动态对象A 104的当前轨迹110，与边缘410a上的动态对象A 104碰撞的可能性没有(或很小)。然后运动规划器280向规划图400的多个边缘中的每个边缘分配一个值小于0的权重，其中每个边缘具有与动态对象A 104碰撞的相应概率，这概率高于碰撞的阈值概率。在本示例中，运动规划器280已为规划图400中的那些边缘分配了小于零的权重，根据动态对象A 104的当前轨迹，这些边缘与动态对象A 104碰撞的概率很高。用于碰撞概率的特定阈值可以变化。例如，阈值可以是40％，50％，80％或更低或更高的碰撞概率。而且，运动规划器280分配值小于0的权重可以包括分配具有与碰撞的相应概率相对应的大小的负权重。例如，如规划图400所示，运动规划器向边缘410b，410c，410d和410e分配权重3，但是向边缘410f分配了具有-2的较低幅值的负权重，且向边缘410g分配了具有-5的较高幅值的权重。这些分配了的权重不需要为整数。

图4B是根据一个示出的实施例，在主要主体102的目标是与图1中可能想要避开主要主体102的动态对象A104碰撞的情况下，图1的主要主体102的示例规划图400，以及是规划图400中识别的主要主体102的示例路径(包括连接节点408a至408d的图400的粗体边缘)，以使主要主体102与动态对象A 104碰撞。在运动规划器280至少部分地基于碰撞评估来设置主要主体102与动态对象A 104的碰撞概率之后，运动规划器280执行优化以在所得的规划图400中标识路径412，在这条路径中，与动态对象A 104发生碰撞的可能性较高。

例如，一旦如图4A和图4B所示已经分配了规划图400的所有边缘权重，则运动规划器280可以执行从规划图400中的主要主体102的当前状态到主要主体102燃料耗尽的所有可能重点的最小成本路径算法。然后，运动规划器280选择规划图400中的最小(最负)路径。在本示例中，规划图中的主要主体102的当前状态在节点408a处，并且该最小成本路径(最负值路径)在规划图中示出为路径412。尽管一条路径在规划图400中示为具有许多急转弯，但是这些转弯并不表示路线中的相应物理转弯，而是代表主要主体102的状态之间的逻辑转换。所标识的路径412中的每个节点可以表示相对于环境100中的主要主体102的物理配置的状态改变，但不一定表示主要主体102的前进方向相对于图4B中所示的路径412的角度的变化。

可以使用各种用于确定最低成本路径的方法，包括那些实现Bellman-Ford算法的方法，但是可以使用其他方法，包括但不限于将最小成本路径确定为规划图400中两个节点之间的路径，从而将其组成边缘的权重之和最小化的任何这种方法。该方法通过使用规划图和碰撞检测来提高效率和响应时间以找到与理想的对象碰撞的最佳路线，从而提高主要主体(例如，自动驾驶车辆)与动态对象(104、112)碰撞的运动规划的技术。另外，一些实施方式使用相同的方法来识别主要主体102的路径，该主要主体在主要主体102所操作的环境中与一个或多个静态对象发生碰撞的可能性相对较高。在寻求与这样的静态对象发生碰撞的情况下，运动规划器280可以为具有相对于环境100中的静态对象发生碰撞的概率的规划图400的边缘分配具有大的负值的权重。通过这种方式，当运动规划器在优化过程中选择最低成本路径时，这样的路径将更有可能被选择。但是，在此类实现中，不需要考虑静态对象的速度、轨迹或加速度。

在一些实施方式中，在主要主体102试图与动态对象A 104碰撞时，还存在主要主体102应该要避免与之碰撞的静态对象。在这种情况下，基于碰撞评估来设置规划图400的边缘的碰撞概率包括(例如通过修改/调整初始权重)分配权重来避免与这种静态对象的碰撞。例如，运动规划器280为规划图400的多个边缘中的每个边缘分配值为无穷大的权重，其中每个边缘具有与环境100中的静态对象碰撞的相应概率。通过这种方式，运动规划器在优化过程中选择了成本最低的路径，因此避免了将边缘权重设置为无穷大的路径，因为如果经过这些路径会导致与静态对象发生碰撞。

运动规划器280可以执行优化以识别所得规划图400中沿着主要主体102的整个路线与动态对象A104碰撞的概率最高的路径。在一些实施方式中，路线的长度可以至少部分地由主要主体102何时用尽燃料/动力来定义。可以由计算机系统200存储指示主要主体102的“剩余燃料”的变量。在一些实施方式中，运动规划器280执行优化，以在所得规划图中识别出一条在最短的相对时间内与主要主体102所操作的环境中的一个或多个对象碰撞的可能性相对较高的路径。或者，在一些实施方式中，运动规划器280可以执行优化以在所得的规划图400中识别出行驶时间最长的一条路径，其中行驶时间由所述路径指定，在该路径中，与动态对象A104碰撞的可能性相对较高。

还可以基于动态对象A的轨迹的变化或动态对象A可能出现的轨迹变化来识别处规划图400中的路径。每次动态对象A的轨迹发生变化或每次预测动态对象A的轨迹会发生变化时，就会再次实时或几乎实时开始碰撞评估和优化过程。而且，所得的规划图400可以具有或存储表示主要主体102和/或动态对象(104、112)的物理或性能约束，主要主体的加速度，俯仰，侧倾和偏航的关联数据，以及在一些实施方式中，还包括动态对象A104的物理或性能约束。然后可以基于这样的变量来对路径进行优化。例如，如果主要主体动态对象A104的俯仰，侧倾和/或偏航发生变化，则这可以指示动态对象A104的轨迹发生变化(或可能发生变化)。

图5A是根据一个示例性实施例，在主要主体102的目标是避免与正在接近主要主体102的图1的动态对象B 112碰撞的情况下图1的主要主体102的示例运动规划图500。类似于规划图400，规划图500分别包括通过边缘连接的多个节点。每个节点隐式地或显式地表示表征主要主体102的状态的时间和变量。

例如，每个节点可以表示主要主体的配置，配置可以包括但不限于主要主体102的当前位置、姿、速度和前进方向。在一些实施例中，主要主体102的加速度还由规划图500中的节点表示。

在某些情况下，可能需要主要主体102避免动态对象B 112，例如避免与动态对象B112发生碰撞。图5A示出了在主要主体102的目标是避免与视图想要与主要主体102(例如在游戏中)碰撞的动态对象B 112碰撞或躲避动态对象B112的情况下，运动规划器280如何使用规划图来识别主要主体102的一条路径。此时，运动规划器280已经接收到表示主要主体102在其中进行操作的环境100的感知信息。如上所述，碰撞检测可以使用体素或框来表示环境中的对象，包括动态对象B112。体素或框也可以用于表示运动规划器280的主要主体102。然而，应当理解，可以使用其他对象表示。在一种实施方式中，将环境离散为体素或框的3D区域。然后，预先计算环境100中的主要主体102在规划图500中的每个运动的波及体积与离散空间中的体素或框之间的所有可能的碰撞。

由于动态对象B 112在环境100中移动这一事实，运动规划器280还基于对动态对象B112的前进方向的预测，确定了规划图500中两个或更多边边缘的主要主体102与动态对象B 112的碰撞评估。对于规划图500的这些边缘中的每一个边缘，运动规划器280至少部分地基于碰撞评估来设置主要主体102在特定的未来时间与动态对象B 112碰撞的概率。例如，根据感知信息检测到动态对象B 112处于环境100中的特定位置处。基于动态对象B 112的当前轨迹108，运动规划器280确定动态对象B 112将位于环境100中的特定位置。

对于规划图500中的节点，节点之间的直接移动可能会导致与动态对象B 112发生碰撞，因此运动规划器将权重分配给在这些节点之间过渡的边缘(边缘510a，510b，510c，510d，510e，510f，510g，510h，5101、510j，510k，5101、510m，510n，510o和510p)，表明了与动态对象B112碰撞的可能性。

在图5A所示的示例中，这表示为图形部分514，但是不对应于物理区域。

例如，运动规划器280可以将值大于零的权重分配给规划图500的多个边缘中的每个边缘，每个边缘具有与动态对象B 112发生碰撞概率，该概率高于限定的阈值碰撞概率。在本示例中，运动规划器280分配为0的权重给规划图500中的那些边缘，根据动态对象B112的当前轨迹，那些边缘与动态对象B112碰撞的概率为0(或者几乎不会碰撞)。然后运动规划器280可以将值大于零的权重分配给规划图500的多个边缘中的每个边缘，每个边缘具有与动态对象B 112发生碰撞的相应概率，该相应概率高于限定的阈值碰撞概率。在本示例中，运动规划器280分配大于0的权重给规划图500中的那些边缘，根据动态对象B112的当前轨迹，那些边缘与动态对象B112碰撞的概率较高。碰撞概率的特定阈值可以变化。例如，阈值可以比碰撞高或低40％，50％，60％。而且，运动规划器280分配具有大于零的值的权重可以包括分配具有大于零的大小的权重，该权重与对应的碰撞概率相对应。例如，如规划图500所示，运动规划器已将值为5的权重分配给碰撞概率较高的边缘510f和510i，同时将具有较小幅度为1的权重分配给运动规划器280确定发生碰撞概率低得多的边缘510p和510g。

图5B是根据一个示出的实施例，在主要主体102的目标是与图1中接近主要主体的动态对象B112碰撞的情况下，图1的主要主体102的示例规划图500，以及是规划图500中识别的主要主体102的示例路径512(包括连接节点508a至508b的图500的粗体边缘)，以使主要主体102与动态对象B112碰撞。在运动规划器280至少部分地基于碰撞评估来设置主要主体102与动态对象B112的碰撞概率之后，运动规划器280执行优化以在所得的规划图500中标识路径512，该规划图500提供了如路径指定的主要主体102的最长的行驶路线，其中与动态对象B112碰撞的可能性相对较低。

在一种实施方式中，一旦如图5A和5B所示分配了规划图500的所有边缘权重，运动规划器280就可以执行计算以确定最长的行驶路线，使得动态对象B 1 12在于主要主体102碰撞之前会耗尽燃料。例如，一旦如图5A和5B所示分配了规划图500的所有边缘权重，运动规划器280就可以从主要主体102的当前状态到主要主体102燃料耗尽的所有可能终点器件执行最小成本路径算法。然后，运动规划器280选择规划图500中成本最小(最接近零)路径的最长路径(例如，时间或距离)。但是，规划图500中最长路线和最小成本(接近0)路径之间往往存在竞争关系。在需要一条最长路线的情况下，与在规划图500中找到最小成本路径相比，最优先考虑的是先选择一条碰撞概率最低的一条路径。在本示例中，主要主体102的当前节点在规划图中位于节点508a处，且该路径在规划图500中示出为路径512。

在一些实施方式中，主要主体102可能具有到达特定目的地的次要目标(同时避免与动态对象B 112碰撞)。在这种情况下，优化可以包括从规划图500中的主要主体102的当前状态到期望目的地期间执行最小成本路径算法。

在一个实施例中，主要主体102的目标是在不与动态对象B 112碰撞的情况下将时间尽可能拉长，以使得例如动态对象B 112在与主要主体102碰撞之前耗尽燃料。在一个示例实施例中，主要主体102的目标是在当前时间和主要主体102到达目的地之间或实现特定目标的时间之间，或在当前时间和动态对象B 112燃料用尽之间，使与动态对象B 112碰撞的概率最大化。通过使用规划图和碰撞概率来提高效率和反应时间以找到最佳路线以避免与视图与自主主要主体碰撞的动态对象(104、112)，该方法改进了避免与动态对象(104、112)碰撞的运动规划技术。

另外，一些实施方式使用相同的方法来识别主要主体102的路径，该路径中与主要主体102在其中运行的环境中的一个或多个静态对象发生碰撞的可能性为零。在要避免与此类静态对象发生碰撞的情况下，运动规划器280为规划图500的多个边缘中的每个边缘分配一个值为无穷大的权重，边缘具有与环境100中的静态对象发生碰撞的相应概率。通过这种方式，当运动规划者在优化过程中选择最小成本路径时，将避免将这些边缘权重设置为无穷大的路径，因为将确定如果经过边缘就会与静态对象发生碰撞。在这样的实施方式中，不需要考虑静态物体的速度或轨迹。

在一些实施方式中，可以存在多个其他主体，例如动态对象(104、112)，其中一些主要主体102具有避免与动态对象(104、112)的目标，而其他一些主要主体102具有拦截或碰撞动态对象(104、112)的目标。在这样的实施方式中，本文中描述的用于主要主体102与动态对象(104、112)碰撞的方法和本文中描述的用于主要主体102避免与动态对象(104、112)碰撞的方法可以同时实现或可以彼此结合来实现。例如，一些对象可以被识别为与之碰撞的对象，而其他对象可以被识别为避免与之碰撞的对象。然后，运动规划器280如本文所述进行优化，优化期间也考虑了与动态和静态对象相对应的轨迹和感知信息以及是否这些对象碰撞或避免与这些对象碰撞。在这种情况下，基于碰撞评估来设置规划图的边缘的碰撞概率包括(例如，通过修改/调整初始权重)分配权重来相应地碰撞或避免碰撞。

运动规划器280可以执行优化以识别沿着主要主体102的整个路线具有与动态对象B112的碰撞的最低可能性的结果规划图500中的路径。在一些实施方式中，路线的长度可以至少部分地由主要主体102何时用尽燃料/动力来定义。可以由计算机系统200存储指示主要主体102的剩余燃料或动力的变量。在一些实施方式中，运动规划器280可以执行优化以在得到的规划图500中标识出行驶时间最长的路径，该路径中，与动态对象B 112发生碰撞的可能性相对较低。还可以基于动态对象B112的轨迹的变化或动态对象B112可能出现的轨迹变化来识别路径。每次动态对象B 112的轨迹发生变化或每次预测动态对象B112的轨迹会发生变化时，就会再次实时或几乎实时开始碰撞评估和优化过程。而且，所得的规划图500可以具有或存储表示主要主体和/或动态对象的物理或性能约束，主要主体102的加速度，俯仰，侧倾和偏航的数据，以及在一些实施方式中，还包括动态对象B112的物理或性能约束。然后可以基于这样的变量来对路径进行优化。例如，如果动态对象B 112的俯仰，侧倾和/或偏航发生变化，则这可以指示动态对象B 112的轨迹发生变化(或可能发生变化)。

可以对运动规划器280进行编程以用于各种各样的自动驾驶车辆和机器人(带有或不带有附件)和预期的任务场景。运动规划器280可以重复使用，或者再次编程，以用于不同车辆或机器人，或者运动规划器可设计用于特定的车辆或机器人。一种类型的机器人是自动驾驶车辆，例如本文所述的自动驾驶车辆。

图6是根据一个示出的实施例的环境100的示意图，其中主要主体102(例如，自动驾驶车辆，具有或不具有附件的机器人等)可以在环境100中操作并且其他主体，例如动态对象A 104和动态对象B112具有已知的路径(例如，分别为t

图7是图6的主要主体102的示例性运动规划图700。在实施例中，基于与主要主体102的节点和目标(即，最后的状态)之间的晶格的边缘相关的成本，晶格中的每个节点(例如，n0，n1，n2...)具有相关联的值(即，成本)。

通过执行静态背景碰撞检测以找到与静态对象(例如，静态对象C 108)碰撞的边缘来初始化晶格。在这种情况下，可以将成本分配(或应用成本函数)给已确定会导致与静态对象发生碰撞的边缘(例如，n14和n15之间的边缘)，从而导致成本比较高。例如，可以将成本设置为无穷大，从而有效地防止主要主体102的轨迹包括识别为与静态物体碰撞的边缘。在晶格初始化的第二方面，例如，基于从当前讨论中的节点到目标节点(例如n15)之间的最小成本路径来确定每个节点到目标的成本。例如，节点n13的成本可以由n16与n15之间的边缘的成本(c13,16)和n16与n15之间的边缘的成本(c16,15)来确定。

可以在时间T＝i开始在表示为n(例如，n0)的节点处执行使用图7中描绘的图700的用于主要主体102的运动规划。如上所述，运动规划考虑了主要主体102的环境100中其他主体(例如动态对象(104、112))的意图。例如，使用基于概率函数的行为模型来对意图进行采样，从而为每个主体A

对于S中的每个轨迹t，确定运动规划图700中的哪些边缘(如果有的话)与该轨迹碰撞，即，哪些边缘将导致主要主体102与对应于该轨迹t的另一主体碰撞。例如通过应用确定与碰撞相关联的成本的成本函数来修改这些边缘的成本值，将例如产生高值的函数分配给碰撞中的边缘。

在基于轨迹t修改图700的边缘的成本之后，计算每个候选节点n’的成本，即，候选节点n’是可在单个时间步骤(即，时间T＝i+1)中从当前的节点n(例如，n0)处获得的节点。通过找到一条从当前节点n(例如，n0)到通过候选节点n’的目标(例如，n15)的最小成本路径来计算候选节点n’(例如，n3,n4,n5和n1)的成本。图7示出了从节点n0到通过候选节点n4的目标(节点n15)的第一最小成本路径710和从节点n0到通过候选节点n5的目标的第二最小成本路径720。在这些示例中，节点n4对于轨迹t的成本将会使沿着第一路径(例如，c0,4,c4,9,c9,13,c13,16,c16,15)的边缘的总和。

按照上述方式对轨迹集合S中的每个轨迹(t

图8A是示出了根据一个示出的实施例的，经由规划图来识别主要主体的路径的方法800的流程图，其中，通过候选节点的路径具有最低的平均成本，其中该最低平均成本考虑了其他主体的已知轨迹。在805处，系统执行静态背景碰撞检测。在810处，计算每个节点到目标的成本。如以上参照图7所讨论的，基于节点和主要主体102的目标(即，最终状态)之间的晶格的边缘相关联的成本(例如，c

图8B是示出了根据一个示出的实施例的方法850的流程图，该方法850可用于计算在图8A的方法中的一组已知轨迹上平均的每个候选节点的成本(参见框820)。在855处，启动循环以考虑对于t＝1至m的轨迹集合S中的每个轨迹t，其中m是轨迹的数量。在860处，系统确定运动规划图700的哪些边缘与轨迹t(如果有的话)碰撞。在865处，系统将成本函数应用于确定为与轨迹t(如果有的话)发生碰撞的边缘的值。在870处，系统基于从节点n到经过各个候选节点n’的目标的最小成本路径来确定每个候选节点n’的成本。在875处，增加识别轨迹的索引t，并且重复方法850，直到处理完所有轨迹为止。

图9是根据一个示出的实施例的环境100的示意图，其中主要主体(例如，自动驾驶车辆，具有或不具有附件的机器人等)可在环境100中操作，同时其他主体(例如，动态对象A104和动态对象B1112)具有互相依存的轨迹。动态对象(104、112)的轨迹可以通过概率来建模(例如，X

因此，开发了每个主体的行为模型，该行为模型将主体的意图视为对潜在策略或目标，而不是简单的轨迹进行建模。潜在策略或目标可为可进行采样的形式，以确定主体如何对其它主体轨迹作出反应。当主要主体102在当前时间T位于节点n时，系统试图确定其他主体在将来位于什么位置。首先根据主要主体从其起始节点到节点n的路径，向前模拟其他主体的策略，直到当前时间T为止，并考虑二级主体对主要主体的动作以及动作作出的反应以及所有二级主体的动作。因此，给定二级主体的概率函数代表直到当前时间为止的主要主体和二级主体的至少一些动作。这产生了指示其他主体在当前时间T占据的空间的结果。之所以如此，是因为在当前时间T另一个主体的位置取决于所有其他主体和主要主体102直到当前时间所遵循的轨迹。

图10是图9的主要主体102的示例运动规划图1000，其示出了第一最小成本路径1010和第二最小成本路径1020的示例。第二最小成本路径1020基于概率来确定。根据一个示出的实施例，在主要主体102沿着第一最小成本路径1010从当前节点(例如，n

在实施例中，晶格中的每个节点(例如，n

在实施例中，对其他主体A

可以在时间T＝0开始在表示为n(例如，n

为了进行规划，假设主要主体102移动到最小值候选节点n’，在图10所示的示例中该候选节点n’是节点n

如概率模型所确定的，主要主体102到节点n

在以这种方式映射了主要主体102的规划运动之后，运动规划图1000将具有边缘，基于规划的路径针对边缘确定了成本，又基于用于对主要主体的环境中的其他主体建模的概率函数来确定规划路径。确定了具有最低值(即，成本)的候选节点n’，同时主要主体102从当前节点n

图11A是示出了根据一个示出的实施例的经由规划图来识别主要主体102的路径的方法1100的流程图，其中通过候选节点的路径具有最低的平均成本，其中考虑了主要主体102到目标的规划路径和其他主体通过概率确定的路径。在1105处，如上所述，系统执行静态背景碰撞检测。在1110处，计算运动规划图1000的每个节点到目标的成本。在1115处，系统为每个主体A

图11B是根据一个示出的实施例的示出在图11A的方法1100中有用的方法1135的流程图(框1120)，该方法1135基于主要主体102到目标的规划路径和其它主体的通过概率确定的路径来计算每个候选节点的值。在1140处，系统基于模型集合S，基于其他主体A

图11C是根据一个示出的实施例的示出了方法1150的流程图，该方法1150可用于图11B的方法1135中(框1140)，用于基于概率模型S的集合，基于根据其它主体A

如上所述，在实施方式中，主体A

前述具体实施方式已经通过使用框图、示意图和示例阐述了设备和/或方法的各种实施例，只要这样的框图，示意图和示例包含一个或多个功能和/或操作，本领域技术人员就应当理解，可以通过广泛的硬件、软件、固件或其实际上的任何组合来单独地和/或共同地实现这样的框图、流程图或示例内的每个功能和/或操作。在一个实施例中，本主题可以是通过专用集成电路(ASIC)和/或FPGA实现。然而，本领域技术人员将认识到，本文公开的实施例可以全部或部分地以各种不同的方式在标准集成电路中实现，作为在一个或多个计算机上运行的一个或多个计算机程序(例如，作为在一个或多个计算机系统上运行的一个或多个程序)，作为在一个或多个控制器(例如，微控制器)上运行的一个或多个程序，作为在一个或多个处理器(例如，微处理器)上运行的一个或多个程序，作为固件或实际上是它们的任何组合，并且设计电路和/或编写软件和/或固件的代码将在本公开领域中的技术人员的知识范围内。

本领域技术人员将认识到，本文阐述的许多方法或算法可以采用附加动作，可以省略某些动作和/或可以以与指定顺序不同的顺序执行动作。

另外，本领域技术人员将意识到，本文所教导的机制能够以各种形式作为程序产品来分发，并且示例性实施例同样适用，这与用于实际进行分发的特定类型的信号承载媒介无关。信号承载媒介的示例包括但不限于以下内容：可记录类型的媒介，例如硬盘驱动器、CD ROM和计算机内存。

可以将上述各种实施例组合以提供其他实施例。本说明书中提到的和/或申请数据表中列出的所有公共转让的美国专利申请公开，美国申请，国外专利和国外专利申请的全部内容均通过引用并入本文，其中申请数据表包括但不限于：于2018年12月4日提交，题为“APPARATUS,METHOD,AND ARTICLE TO FACILITATE MOTION PLANNING IN ANENVIRONMENT HAVING DYNAMIC OBJECTS”的美国专利申请No.62/775,257；于2018年1月12日提交，题为“AAAPRATUS,METHODS,AND ARTICLE TO FACILITATE MOTION PLANNING OF ANAUTONOMOUS VEHICLE IN AN ENVIRONMENT HAVING DYNAMIC OBJECTS”的美国专利申请No.62/616,783；于2017年6月9日提交，题为“MOTION PLANNING FOR AUTONOMOUS VEHICLESAND RECONFIGURABLE MOTION PLANNING PROCESSORS”的国际专利申请No.PCT/US2017/036880；以及于2016年1月5日提交，题为“SOECILIZED ROBOT MOTION PLANNING HARDWAREAND METHODS OF MAKING AND USING SAME”的国际专利申请No.WO 016/122840。可以根据上述具体实施方式对实施例进行这些和其他改变。一般而言，在所附权利要求中，不应将所使用的术语解释为将权利要求限制为说明书和权利要求书中公开的特定实施例，而是应将权利要求解释为包括所有可能的实施例以及这些权利要求所享有的等同物的全部范围。因此，权利要求不受公开内容的限制。