[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN114206698B - 在具有动态障碍物的环境中促进运动规划的装置、方法和物品 - Google Patents

在具有动态障碍物的环境中促进运动规划的装置、方法和物品 Download PDF

Info

Publication number
CN114206698B
CN114206698B CN202080055382.1A CN202080055382A CN114206698B CN 114206698 B CN114206698 B CN 114206698B CN 202080055382 A CN202080055382 A CN 202080055382A CN 114206698 B CN114206698 B CN 114206698B
Authority
CN
China
Prior art keywords
processor
collision
obstacle
primary vehicle
planning
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN202080055382.1A
Other languages
English (en)
Other versions
CN114206698A (zh
Inventor
威廉·弗洛伊德-琼斯
布赖斯·威利
乔治·科尼达里斯
龙先超
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Real Time Robots Ltd
Original Assignee
Real Time Robots Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Real Time Robots Ltd filed Critical Real Time Robots Ltd
Publication of CN114206698A publication Critical patent/CN114206698A/zh
Application granted granted Critical
Publication of CN114206698B publication Critical patent/CN114206698B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60W—CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
    • B60W30/00—Purposes of road vehicle drive control systems not related to the control of a particular sub-unit, e.g. of systems using conjoint control of vehicle sub-units
    • B60W30/08—Active safety systems predicting or avoiding probable or impending collision or attempting to minimise its consequences
    • B60W30/09—Taking automatic action to avoid collision, e.g. braking and steering
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60W—CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
    • B60W30/00—Purposes of road vehicle drive control systems not related to the control of a particular sub-unit, e.g. of systems using conjoint control of vehicle sub-units
    • B60W30/08—Active safety systems predicting or avoiding probable or impending collision or attempting to minimise its consequences
    • B60W30/095—Predicting travel path or likelihood of collision
    • B60W30/0956—Predicting travel path or likelihood of collision the prediction being responsive to traffic or environmental parameters
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60W—CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
    • B60W30/00—Purposes of road vehicle drive control systems not related to the control of a particular sub-unit, e.g. of systems using conjoint control of vehicle sub-units
    • B60W30/10—Path keeping
    • B60W30/12—Lane keeping
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60W—CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
    • B60W60/00—Drive control systems specially adapted for autonomous road vehicles
    • B60W60/001—Planning or execution of driving tasks
    • B60W60/0011—Planning or execution of driving tasks involving control alternatives for a single driving scenario, e.g. planning several paths to avoid obstacles
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60W—CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
    • B60W60/00—Drive control systems specially adapted for autonomous road vehicles
    • B60W60/001—Planning or execution of driving tasks
    • B60W60/0015—Planning or execution of driving tasks specially adapted for safety
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60W—CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
    • B60W60/00—Drive control systems specially adapted for autonomous road vehicles
    • B60W60/001—Planning or execution of driving tasks
    • B60W60/0015—Planning or execution of driving tasks specially adapted for safety
    • B60W60/0017—Planning or execution of driving tasks specially adapted for safety of other traffic participants
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60W—CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
    • B60W60/00—Drive control systems specially adapted for autonomous road vehicles
    • B60W60/001—Planning or execution of driving tasks
    • B60W60/0027—Planning or execution of driving tasks using trajectory prediction for other traffic participants
    • B60W60/00274—Planning or execution of driving tasks using trajectory prediction for other traffic participants considering possible movement changes
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60W—CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
    • B60W60/00—Drive control systems specially adapted for autonomous road vehicles
    • B60W60/001—Planning or execution of driving tasks
    • B60W60/0027—Planning or execution of driving tasks using trajectory prediction for other traffic participants
    • B60W60/00276—Planning or execution of driving tasks using trajectory prediction for other traffic participants for two or more other traffic participants
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60W—CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
    • B60W2552/00—Input parameters relating to infrastructure
    • B60W2552/30—Road curve radius
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60W—CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
    • B60W2552/00—Input parameters relating to infrastructure
    • B60W2552/50—Barriers
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60W—CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
    • B60W2552/00—Input parameters relating to infrastructure
    • B60W2552/53—Road markings, e.g. lane marker or crosswalk
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60W—CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
    • B60W2554/00—Input parameters relating to objects
    • B60W2554/40—Dynamic objects, e.g. animals, windblown objects
    • B60W2554/404—Characteristics
    • B60W2554/4045—Intention, e.g. lane change or imminent movement
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60W—CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
    • B60W2554/00—Input parameters relating to objects
    • B60W2554/80—Spatial relation or speed relative to objects
    • B60W2554/805—Azimuth angle

Landscapes

  • Engineering & Computer Science (AREA)
  • Automation & Control Theory (AREA)
  • Transportation (AREA)
  • Mechanical Engineering (AREA)
  • Human Computer Interaction (AREA)
  • Traffic Control Systems (AREA)
  • Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
  • Control Of Driving Devices And Active Controlling Of Vehicle (AREA)

Abstract

一种运动规划器使用运动规划栅格来执行具有碰撞评估的运动规划，该运动规划栅格将主行为者(例如，自主车辆)的构形状态表示为节点，并将状态之间的转换表示为边。系统可以向边分配代价值，代价值表示对应的转换的碰撞概率或可能性。代价值可以附加地或替代地表示碰撞严重性，例如经由具有两个或更多个参数和一个或更多个权重的参数函数生成。主行为者和/或动态障碍物可以表示为相应的定向边界框。一些障碍物(例如，道路标记、道路边缘)可以表示为曲线。主行为者和/或动态障碍物的轨迹可以由相应的一组拟合多项式函数表示，规划图上的边表示所述主行为者的状态转换，该系统设置表示碰撞概率以及可选地表示碰撞的严重性的值。然后，该系统使主行为者的致动器系统利用至少部分地基于优化的适用的识别的路径来实施运动规划。

Description

在具有动态障碍物的环境中促进运动规划的装置、方法和 物品
技术领域
本公开总体涉及使用具有碰撞评估的运动规划栅格的运动规划，尤其涉及在具有动态障碍物(例如，其它自主车辆、其它车辆、人、动物、礼貌区域)和静态障碍物(例如，树木、建筑物、树木、岩石、墙壁、路障、车道标记、中心线、其它道路标记、道路边缘)的环境中促进主行为者(例如，自主车辆)的运动规划的系统和方法。
背景技术
运动规划是机器人技术中的一个基本问题。运动规划可用于控制自主车辆的运动或控制其它类型机器人或机器人的部分(例如，机器人附属物、末端执行器、手臂工具末端)的运动。运动规划可以指定自主车辆或机器人或其部分可以遵循的从第一状态(例如，起始构形或起始姿态)到目标状态(例如，结束构形或结束姿态)的一系列转换或“路径”，通常不与操作环境中的任何障碍物碰撞，或者与操作环境中的任何障碍物发生碰撞的可能性低。障碍物可以采取多种形式中的任何一种或更多种，包括静态物理障碍物(例如，树木、建筑物、树木、岩石、墙壁、路障、车道标记、中心线、其它道路标记、道路边缘)、静态概念化障碍物(例如，围绕静态物理障碍的“礼貌”区域)、动态物理障碍物(例如，其它自主车辆、其它车辆、人、动物)和动态概念化障碍物(例如，围绕动态物理障碍的礼貌区域和/或关于动态物理障碍物的其它逻辑构念)。
创建运动规划通常涉及四个主要构成部分：感知、栅格构造、碰撞评估(通常也称为碰撞检测)和路径搜索。每个构成部分都提供了在自主车辆经过或其它类型机器人移动的操作环境中需要克服的挑战，该操作环境包括静态障碍物，特别是包括在操作环境中移动的动态障碍物。动态障碍物的将来的移动可能是已知的，也可能是未知的或不确定的。有利的是，自主车辆(或其它类型机器人)进行运动规划以实时跟上操作环境的变化，以避免与动态和静态障碍物发生碰撞，从而达到目标状态。
发明内容
运动规划器使用运动规划栅格来执行运动规划，该栅格将主行为者(例如，自主车辆)的构形状态表示为节点，将状态之间的转换表示为边。运动规划器优选地执行碰撞评估，确定主行为者在两个状态或构形之间转换时是否会与障碍物碰撞或与障碍物碰撞的可能性或概率。运动规划器可以将代价值分配给运动规划栅格的边，代价值表示对应转换碰撞的可能性或概率。分配的代价值可以附加地或替代地表示碰撞的严重程度，例如通过具有两个或更多个参数和一个或更多个权重的参数函数生成的碰撞的严重程度。运动规划器可以对运动规划栅格执行最小代价分析以确定从一个状态或构形到另一个状态或构形的一组转换或“路径”。运动规划器可以使主行为者的致动器或传动装置实施具有一组识别的转换或路径的运动规划。
主行为者和/或动态障碍物可以有利地表示为相应的定向边界框。一些障碍物(例如，道路标记、道路边缘)可以有利地表示为曲线。主行为者和/或动态障碍物的轨迹可以有利地由相应的一组拟合函数(例如，拟合多项式函数)表示，例如代替运动方程。与运动方程相比，拟合函数在执行碰撞评估时可以有利地需要更少的计算开销，例如通过避免对评估三角函数的需求。
各种方面：
方面1.描述了一种在基于处理器的系统中操作的用于经由规划栅格来执行运动规划的运动规划方法，其中，每个规划栅格分别包括多个节点和边，每个节点表示在包括一个或更多个其它车辆和其它障碍物的环境中操作的主要车辆的状态，每个边表示在相应的一对节点之间的转换。该方法可以总结为包括：通过基于处理器的系统将主要车辆表示为相应的定向边界框；以及针对规划栅格的多个边中的至少一个边，通过基于处理器的系统执行定向边界框碰撞检测，以确定由定向边界框表示的主要车辆在一对状态之间转换时是否将与其它车辆或其它障碍物的表示碰撞，该对状态由通过规划栅格的相应边连接的一对节点的相应节点表示；以及通过基于处理器的系统设置规划栅格的相应边的代价，以反映检测到的碰撞或不存在碰撞中的至少一者。
方面2.方面1的运动规划方法还包括：通过基于处理器的系统，将其它车辆中的至少一个车辆表示为相应的定向边界框，并且其中，执行定向边界框碰撞检测包括：执行定向边界框-定向边界框碰撞检测，以确定表示主要车辆的相应的定向边界框在由通过规划栅格的相应边连接的相应节点表示的一对状态之间转换时是否将与表示其它车辆中的至少一个车辆的相应的定向边界框碰撞。
方面3.方面1的运动规划方法还包括：通过基于处理器的系统，将其它障碍物中的至少一个障碍物表示为相应的定向边界框，并且其中，执行定向边界框碰撞检测包括：执行定向边界框-定向边界框碰撞检测，以确定表示主要车辆的相应的定向边界框在由通过规划栅格的相应边连接的相应节点表示的一对状态之间转换时是否将与表示其它障碍物中的至少一个障碍物的相应的定向边界框碰撞。
方面4.方面1的运动规划方法还包括：通过基于处理器的系统，将至少一个其它障碍物表示为曲线的表示，并且其中，执行定向边界框碰撞检测以确定由相应的定向边界框表示的主要车辆是否与其它车辆或其它障碍物碰撞包括：执行定向边界框-曲线碰撞检测，以确定表示主要车辆的相应的定向边界框在由通过规划栅格的相应边连接的相应的节点表示的一对状态之间转换时是否将与表示其它障碍物中的至少一个障碍物的曲线碰撞。
方面5.根据方面4的运动规划方法，其中，将至少一个其它障碍物表示为曲线的表示包括：将道路的中心线、道路的边缘、或道路的至少一个车道标记中的至少一个表示为样条表示。
方面6.根据方面1至5中任一方面的运动规划方法，其中，执行定向边界框碰撞检测包括：通过使用一组拟合函数表示与规划栅格的相应边对应的主要车辆的相应轨迹，来在沿着主要车辆的相应轨迹的至少一个点中的每个点处执行定向边界框碰撞检测。
方面7.根据方面1至5中任一方面的运动规划方法，其中，执行定向边界框碰撞检测包括：经由多个不同的硬件电路执行定向边界框碰撞检测。
方面8.根据方面1至5中任一方面的运动规划方法，其中，设置规划栅格的相应边的代价以反映检测到的碰撞或不存在碰撞中的至少一者包括：根据参数化代价函数，设置规划栅格的相应边中的一个或更多个边的代价，以反映碰撞的检测和反映表示检测到的碰撞的严重性的至少一个参数。
方面9.方面1至5中任一方面的运动规划方法还包括：通过基于处理器的系统，执行规划栅格的最小代价分析；以及通过基于处理器的系统至少部分地基于该最小代价分析，通过主要车辆来实施所生成的运动规划。
方面10.描述了一种用于经由规划栅格执行运动规划的基于处理器的系统，其中，每个规划栅格分别包括多个节点和边，每个节点表示在包括一个或更多个其它车辆和其它障碍物的环境中操作的主要车辆的状态，每个边表示在相应的一对节点之间的转换。该基于处理器的系统可以总结为包括：至少一个处理器；至少一个非暂时性处理器可读介质，其通信地耦接到该至少一个处理器并存储处理器可执行指令，所述处理器可执行指令在由该至少一个处理器执行时，使该至少一个处理器配置为：将主要车辆表示为相应的定向边界框；以及针对规划栅格的多个边中的至少一个边，执行定向边界框碰撞检测以确定由定向边界框表示的主要车辆在一对状态之间转换时是否将与其它车辆或其它障碍物的表示碰撞，该对状态由通过规划栅格的相应边连接的一对节点的相应节点表示；以及设置规划栅格的相应边的代价，以反映检测到的碰撞或不存在碰撞中的至少一者。
方面11.根据方面10的基于处理器的系统，其中，处理器可执行指令在由至少一个处理器执行时，使该至少一个处理器还配置为：将其它车辆中的至少一个车辆表示为相应的定向边界框，并且其中，执行定向边界框碰撞检测包括：执行定向边界框-定向边界框碰撞检测，以确定表示主要车辆的相应的定向边界框在由通过规划栅格的相应边连接的相应节点表示的一对状态之间转换时是否将与表示其它车辆中的至少一个车辆的相应的定向边界框碰撞。
方面12.根据方面10的基于处理器的系统，其中，处理器可执行指令在由至少一个处理器执行时，使该至少一个处理器还配置为：将其它障碍物中至少一个障碍物表示为相应的定向边界框，并且将定向边界框碰撞检测执行为定向边界框-定向边界框碰撞检测，以确定表示主要车辆的相应的定向边界框在由通过规划栅格的相应边连接的相应节点表示的一对状态之间转换时是否将与表示其它障碍物中的至少一个障碍物的相应的定向边界框碰撞。
方面13.根据方面10的基于处理器的系统，其中，处理器可执行指令在由至少一个处理器执行时，使该至少一个处理器还配置为：将至少一个其它障碍物表示为曲线的表示，并且将定向边界框碰撞检测执行为定向边界框-曲线碰撞检测，以确定表示主要车辆的相应的定向边界框在由通过规划栅格的相应边连接的相应节点表示的一对状态对之间转换时是否将与表示其它障碍物中的至少一个障碍物的曲线碰撞。
方面14.根据方面13的基于处理器的系统，其中，处理器可执行指令在由至少一个处理器执行时，使该至少一个处理器还配置为：将至少一个障碍物表示为曲线的表示包括：将道路的中心线、道路的边缘，或道路的至少一个车道标记中的至少一个表示为样条表示。
方面15.根据方面10至14中任一方面的基于处理器的系统，其中，处理器可执行指令在由至少一个处理器执行时，使该至少一个处理器，通过经由一组拟合函数表示与规划栅格的相应边对应的主要车辆的相应轨迹来在沿着主要车辆的相应轨迹的至少一个点中的每个点处执行定向边界框碰撞检测。
方面16.根据方面10至14中任一方面的基于处理器的系统，其中，执行定向边界框碰撞检测包括：经由多个不同的硬件电路执行定向边界框碰撞检测。
方面17.根据方面10至14中任一方面的基于处理器的系统，其中，处理器可执行指令在由至少一个处理器执行时使该至少一个处理器基于参数化代价函数设置规划栅格的相应边的代价，以反映碰撞的检测和反映检测到的碰撞的严重性。
方面18.根据方面9至14中任一方面的基于处理器的系统，其中，处理器可执行指令在由至少一个处理器执行时，使该至少一个处理器还配置为：执行规划栅格的最小代价分析；以及至少部分地基于该最小代价分析，通过主要车辆实施所生成的运动规划。
方面19.描述了一种在基于处理器的系统中操作的用于经由规划栅格执行运动规划的运动规划方法，其中，每个规划栅格分别包括多个节点和边，每个节点表征在包括一个或更多个其它车辆和其它障碍物的环境中操作的主要车辆的状态，每个边表示由相应的一对节点的表示的状态之间的主要车辆的轨迹。该方法可以总结为包括：在运行期间，针对规划栅格的多个边中的每个边，通过基于处理器的系统，将与相应边对应的轨迹表示为一组拟合函数，通过基于处理器的系统，使用该组拟合函数执行碰撞检测，以确定主要车辆的表示是否与其它车辆或其它障碍物的一个或更多个表示碰撞；以及通过基于处理器的系统，设置规划栅格的相应边的代价，以反映在由通过规划栅格的相应边连接的相应节点表示的一对状态之间转换时，确定的碰撞或不存在碰撞中的至少一者。拟合函数可以有利地避免使用三角函数。
方面20.方面19的运动规划方法还包括：通过基于处理器的系统，在主要车辆的基于处理器的系统处，从远离主要车辆定位的配置系统接收一组拟合函数，该组拟合函数由配置系统在运行之前拟合。
方面21.根据方面19的运动规划方法，其中，使用一组拟合函数执行碰撞检测，以确定主要车辆是否与其它车辆或其它障碍物碰撞包括：使用一对拟合多项式函数来执行碰撞检测，这一对拟合多项式函数中的一个拟合多项式函数表示相对于时间的第一维度中的位置，这一对拟合多项式函数中的另一拟合多项式函数表示相对于时间的第二维度中的位置，第二维度不同于第一维度。
方面22.根据方面19的运动规划方法，其中，使用一组拟合函数执行碰撞检测，以确定主要车辆是否与其它车辆或其它障碍物碰撞包括：使用一对拟合时间参数函数来执行碰撞检测，以确定主要车辆是否与其它车辆或其它障碍物碰撞。
方面23.根据方面19的运动规划方法，其中，使用一组拟合函数执行碰撞检测，以确定主要车辆是否与其它车辆或其它障碍物碰撞包括：使用一对拟合时间参数五次函数来执行碰撞检测，以确定主要车辆是否与其它车辆或其它障碍物碰撞。
方面24.根据方面19的运动规划方法，其中，使用一组拟合函数执行碰撞检测，以确定主要车辆是否与其它车辆或其它障碍物碰撞包括：使用由主要车辆的原始设备制造商提供的专用于主要车辆的品牌和型号的一对拟合函数来执行碰撞检测。
方面25.根据方面19的运动规划方法，其中，使用一组拟合函数执行碰撞检测，以确定主要车辆是否与其它车辆或其它障碍物碰撞包括：使用具有专用于主要车辆的品牌和型号的且由主要车辆的原始设备制造商提供的参数的一对拟合多项式函数来执行碰撞检测。
方面26.根据方面19至25中任一方面的运动规划方法，其中，使用一组拟合函数执行碰撞检测，以确定主要车辆是否与其它车辆或其它障碍物碰撞包括：在沿着主要车辆的相应轨迹的一个或更多个点处执行碰撞检测，该相应轨迹经由一组拟合函数指定以表示对应于规划栅格的相应边的主要车辆的相应轨迹。
方面27.根据方面19至25中任一方面的运动规划方法，其中，使用一组拟合函数执行碰撞检测，以确定主要车辆是否与其它车辆或其它障碍物碰撞包括：经由多个不同的硬件电路来执行碰撞检测。
方面28.根据方面19至25中任一方面的运动规划方法，其中，设置规划栅格的相应边的代价，以反映检测到的碰撞或不存在碰撞中的至少一者包括：根据参数化代价函数设置规划栅格的相应的边中的一个或更多个边的代价，以反映碰撞的检测以及反映检测到的碰撞的严重性。
方面29.方面19至25中任一方面的运动规划方法还包括：通过基于处理器的系统执行规划栅格的最小代价分析；以及通过基于处理器的系统至少部分地基于该最小代价分析，通过主要车辆来实施所生成的运动规划。
方面30.方面19至25中任一方面的运动规划方法还包括：在发生于运行之前的离线配置期间，针对多个边中的每个边，将相应的一组多项式函数拟合到由该边表示的轨迹所表示的运动。
方面31.描述了一种用于经由规划栅格来执行运动规划的基于处理器的系统，其中，每个规划栅格分别包括多个节点和边，每个节点表征在包括一个或更多个其它车辆和其它障碍物的环境中操作的主要车辆的状态，每个边表示由相应的一对节点表示的状态之间的主要车辆的轨迹。该基于处理器的系统可以总结为包括：至少一个处理器；至少一个非暂时性处理器可读介质，其通信地耦接到该至少一个处理器并存储处理器可执行指令，处理器可执行指令在被该至少一个处理器执行时，使该至少一个处理器配置为：在运行期间，针对规划栅格的多个边中的每个边，将对应于相应边的轨迹表示为一组拟合函数，使用该一组拟合函数执行碰撞检测，以确定主要车辆的表示是否与其它车辆或其它障碍物的一个或更多个表示碰撞；以及设置规划栅格的相应边的代价，以反映在由通过规划栅格的相应边连接的相应节点表示的一对状态之间转换时所确定的碰撞或不存在碰撞中的至少一者。拟合函数可以有利地避免使用三角函数。
方面32.根据方面31的基于处理器的系统，其中，处理器可执行指令在被至少一个处理器执行时，使该至少一个处理器还配置为：在主要车辆的基于处理器的系统处，从远离主要车辆定位的配置系统接收一组拟合函数，该一组拟合函数是由配置系统在运行之前拟合的。
方面33.根据方面31的基于处理器的系统，其中，处理器可执行指令在被至少一个处理器执行时，使该至少一个处理器利用一对拟合多项式函数来执行碰撞检测，该一对拟合多项式函数中的一个拟合多项式函数表示相对于时间的第一维度中的位置，该一对拟合多项式函数中的另一拟合多项式函数表示相对于时间的第二维度中的位置，第二维度不同于第一维度。
方面34.根据方面31的基于处理器的系统，其中，处理器可执行指令在被至少一个处理器执行时，使该至少一个处理器利用一对拟合时间参数来执行碰撞检测，以确定主要车辆是否与其它车辆或其它障碍物碰撞。
方面35.根据方面31的基于处理器的系统，其中，处理器可执行指令在被至少一个处理器执行时，使该至少一个处理器利用一对拟合时间参数五次函数来执行碰撞检测，以确定主要车辆是否与其它车辆或其它障碍物碰撞。
方面36.根据方面31的基于处理器的系统，其中，处理器可执行指令在被至少一个处理器执行时，使该至少一个处理器利用由主要车辆的原始设备制造商提供的专用于主要车辆的品牌和型号的一对拟合函数来执行碰撞检测。
方面37.根据方面31的基于处理器的系统，其中，处理器可执行指令在被至少一个处理器执行时，使该至少一个处理器利用具有专用于主要车辆的品牌和型号的且由主要车辆的原始设备制造商提供的参数的一对拟合多项式函数来执行碰撞检测。
方面38.根据方面31至37中任一方面的基于处理器的系统，其中，处理器可执行指令在被至少一个处理器执行时，使该至少一个处理器在沿着主要车辆的相应轨迹的一个或更多个点处执行碰撞检测，其中，相应轨迹经由一组拟合函数指定以表示对应于规划栅格的相应边的主要车辆的相应轨迹。
方面39.根据方面31至37中任一方面的基于处理器的系统，其中，处理器可执行指令在被至少一个处理器执行时，使该至少一个处理器经由多个不同的硬件电路来执行碰撞检测。
方面40.根据方面31至37中任一方面的基于处理器的系统，其中，处理器可执行指令在被至少一个处理器执行时，使该至少一个处理器经由参数化代价函数设置规划栅格的相应边的代价，以反映检测到的碰撞或不存在碰撞中的至少一者，以反映碰撞的检测以及反映检测到的碰撞的严重性。
方面41.根据方面31至37中任一方面的基于处理器的系统，其中，处理器可执行指令在被至少一个处理器执行时，使该至少一个处理器还配置为：执行规划栅格的最小代价分析；以及至少部分地基于该最小代价分析，通过主要车辆来实施所生成的运动规划。
方面42.根据方面31至37中任一方面的基于处理器的系统，其中，处理器可执行指令在被至少一个处理器执行时，使该至少一个处理器还配置为：在发生于运行之前的离线配置期间，针对多个边中的每个边，将相应的一组函数拟合到由该边表示的轨迹所表示的运动。
方面43.描述了一种在基于处理器的系统中操作的用于经由规划栅格来执行运动规划的运动规划方法，其中，每个规划栅格分别包括多个节点和边，每个节点表征主要车辆的状态，其中，主要车辆在包括一个或更多个其它车辆和其它障碍物的环境中操作，每个边表示由相应的一对节点表示的状态之间的主要车辆的轨迹。该方法可以总结为包括：在发生于运行之前的离线配置期间，针对规划栅格的多个边中的每个边，确定拟合到由该边表示的轨迹所表示的运动的一组拟合函数；以及提供该一组拟合函数以用于由主要车辆的基于处理器的系统进行的运动规划。
方面44.根据方面43的运动规划方法，其中，确定拟合到由该边表示的轨迹所表示的运动的一组拟合函数包括：将一组拟合函数拟合到由轨迹表示的运动。
方面45.根据方面43的运动规划方法，其中，确定拟合到由该边表示的轨迹所表示的运动的一组拟合函数包括：确定一对拟合多项式函数，该一对拟合多项式函数中的一个拟合多项式函数表示相对于时间的第一维度中的沿着轨迹的位置，该一对拟合多项式函数中的另一拟合多项式函数表示相对于时间的第二维度中的沿着轨迹的位置，第二维度不同于第一维度。
方面46.根据方面43的运动规划方法，其中，确定拟合到由该边表示的轨迹所表示的运动的一组拟合函数包括：确定表示轨迹的一对拟合时间参数函数。
方面47.根据方面43的运动规划方法，其中，确定拟合到由该边表示的轨迹所表示的运动的一组拟合函数包括：确定表示轨迹的一对拟合时间参数五次函数。
方面48.根据方面43的运动规划方法，其中，确定拟合到由该边表示的轨迹所表示的运动的一组拟合函数包括：确定由主要车辆的原始设备制造商指定的专用于主要车辆的品牌和型号的一对拟合函数。
方面49.根据方面43的运动规划方法，其中，确定拟合到由该边表示的轨迹所表示的运动的一组拟合函数包括：确定具有由通过主要车辆的原始设备制造商的专用于主要车辆的品牌和型号的参数的一对拟合多项式函数，以及将所确定的具有专用于主要车辆的品牌和型号的参数的一对拟合多项式函数提供给主要车辆的基于处理器的控制系统，其中，主要车辆是自主车辆。
方面50.描述了一种在基于处理器的系统中操作的用于经由规划栅格来执行运动规划的运动规划方法，其中，每个规划栅格分别包括多个节点和边，每个节点表征在包括一个或更多个障碍物的环境中操作的主要车辆的状态，每个边表示一对相应节点之间的转换。该方法可以总结为包括：针对规划栅格的多个边中的至少一个边中的每个边，通过基于处理器的系统执行碰撞检测，以确定主要车辆的表示在一对状态之间转换时是否将与障碍物的表示碰撞，该一对状态由通过规划栅格的相应边连接的一对节点的相应节点表示；以及通过基于处理器的系统，至少部分地基于以下项来设置与规划栅格的相应边关联的代价：i)碰撞检测，和ii)表示以下项中的至少两项或更多项的参数化代价函数：障碍物类型，碰撞类型，车辆速度，或对将在碰撞期间耗散的耗散能量的至少估计，障碍物类型表示可能与之发生碰撞的障碍物的类型，碰撞类型表示可能发生的碰撞的类型，车辆速度表示在即将发生预测的碰撞之前至少主要车辆的速度。
方面51.根据方面50的运动规划方法，其中，障碍物类型表示障碍物是有生命的障碍物还是无生命的障碍物，并且设置与相应边关联的代价包括：至少部分地基于障碍物是有生命的障碍物还是无生命的障碍物来设置代价。
方面52.根据方面50的运动规划方法，其中，碰撞类型表示碰撞是与将对物理障碍物或主要车辆造成损害的物理障碍物的碰撞，还是与不直接对主要车辆造成损害的间距要求或道路标记的碰撞，并且设置与相应边关联的代价包括：至少部分地基于碰撞是与将对物理障碍物或主要车辆造成损害的物理障碍物的碰撞还是与不对道路标记造成损害的道路标记的碰撞来设置代价。
方面53.根据方面50的运动规划方法，其中，车辆速度表示主要车辆在现实世界参考系中的速度，并且设置与相应边关联的代价包括：至少部分地基于主要车辆在现实世界参考系中的速度来设置代价。
方面54.根据方面50的运动规划方法，其中，车辆速度表示主要车辆相对于障碍物的速度的速度，并且设置与相应边关联的代价包括：至少部分地基于主要车辆相对于障碍物的速度的速度来设置代价。
方面55.根据方面50的运动规划方法，其中，车辆速度表示主要车辆的速度和障碍物的速度两者，并且设置与相应边关联的代价包括：至少部分地基于主要车辆的速度和障碍物的速度两者来设置代价。
方面56.根据方面50的运动规划方法，其中，参数化代价函数还表示基于车辆速度的碰撞的严重性水平，并且设置与相应边关联的代价包括：至少部分地基于根据主要车辆和障碍物中至少一个或两者的车辆速度的严重性水平来设置代价。
方面57.根据方面50至56中任一方面的运动规划方法，其中，执行碰撞检测包括经由多个不同的硬件电路来执行碰撞检测。
方面58.方面50至56中任一方面的运动规划方法还包括：通过基于处理器的系统执行规划栅格的最小代价分析；以及通过基于处理器的系统至少部分地基于该最小代价分析，通过主要车辆来实施所生成的运动规划。
方面59.描述了一种用于经由规划栅格来执行运动规划的基于处理器的系统，其中，每个规划栅格分别包括多个节点和边，每个节点表征在包括一个或更多个障碍物的环境中操作的主要车辆的状态，每个边表示在相应的一对节点之间的转换。该基于处理器的系统可以总结为包括：至少一个处理器；至少一个非暂时性处理器可读介质，其通信地耦接到该至少一个处理器并存储处理器可执行指令，处理器可执行指令在被该至少一个处理器执行时，使该至少一个处理器配置为：针对规划栅格的多个边中的每个边，执行碰撞检测，以确定主要车辆的表示在一对状态之间转换时是否会与障碍物的表示碰撞，该一对状态由通过规划栅格的相应边连接的一对节点的相应节点表示；以及至少部分地基于以下项来设置与规划栅格的相应边关联的代价：i)碰撞检测，和ii)表示以下项中的至少两项或更多项的参数化代价函数：障碍物类型，碰撞类型，车辆速度，或对将在碰撞期间耗散的耗散能量的至少估计，障碍物类型表示可能与之发生碰撞的障碍物的类型，碰撞类型表示可能发生的碰撞的类型，车辆速度表示在即将发生预测的碰撞之前至少主要车辆的速度。
方面60.根据方面59的运动规划方法，其中，障碍物类型表示障碍物是有生命的障碍物还是无生命的障碍物，并且处理器可执行指令在被该至少一个处理器执行时，使该至少一个处理器配置为：至少部分地基于障碍物是有生命的障碍物还是无生命的障碍物来设置代价。
方面61.根据方面59的运动规划方法，其中，碰撞类型表示碰撞是与将对物理障碍物或主要车辆造成损害的物理障碍物的碰撞，还是与不直接对主要车辆造成损害的间距要求或道路标记的碰撞，并且处理器可执行指令在被该至少一个处理器执行时，使该至少一个处理器配置为：至少部分地基于碰撞是与将对物理障碍物或主要车辆造成损害的物理障碍物的碰撞还是与不对道路标记造成损害的道路标记的碰撞来设置代价。
方面62.根据方面59的运动规划方法，其中，车辆速度表示主要车辆在现实世界参考系中的速度，并且处理器可执行指令在被该至少一个处理器执行时，使该至少一个处理器配置为：至少部分地基于主要车辆在现实世界参考系中的速度来设置代价。
方面63.根据方面59的运动规划方法，其中，车辆速度表示主要车辆相对于障碍物的速度的速度，并且处理器可执行指令在被该至少一个处理器执行时，使该至少一个处理器配置为：设置与相应边关联的代价包括至少部分地基于所述主要车辆相对于所述障碍物的速度的速度来设置代价。
方面64.根据方面59的运动规划方法，其中，车辆速度表示主要车辆的速度和障碍物的速度两者，并且处理器可执行指令在被该至少一个处理器执行时，使该至少一个处理器配置为：设置与相应边关联的代价包括至少部分地基于主要车辆的速度和障碍物的速度两者来设置代价。
方面65.根据方面59的运动规划方法，其中，参数化代价函数还表示基于车辆速度的碰撞的严重性水平，并且处理器可执行指令在被该至少一个处理器执行时，使该至少一个处理器配置为：至少部分地基于根据主要车辆和障碍物中至少一个或两者的车辆速度的严重性水平来设置与相应边关联的代价。
方面66.根据方面59至65中任一方面的运动规划方法，其中，处理器可执行指令在被该至少一个处理器执行时，使该至少一个处理器配置为：经由多个不同的硬件电路来执行碰撞检测。
方面67.根据方面59至65中任一方面的运动规划方法，其中，处理器可执行指令在被该至少一个处理器执行时，使该至少一个处理器还配置为：执行规划栅格的最小代价分析；以及至少部分地基于该最小代价分析，通过主要车辆来实施所生成的运动规划。
附图说明
在附图中，相同的附图标记指示相似的元件或动作。元件在附图中的尺寸和相对位置不一定按比例尺绘制。例如，各个元件的形状和角度没有按比例尺绘制，并且这些元件中的一些被任意放大和布置以改善附图可读性。而且，所绘制的元件的具体形状不旨在传达关于具体元件的实际形状的任何信息，并且仅是为了方便在附图中识别而选择的。
图1是根据一个所示实施方式的操作环境的示意图，主行为者(例如，自主车辆)可以在该操作环境中操作，基于针对操作环境中的动态障碍物和静态障碍物的碰撞评估来执行运动规划。
图2是根据一个所示实施方式的基于处理器的系统的功能框图，其中该基于处理器的系统可以促进运动规划，以在图1的操作环境中操作主行为者(例如，车辆)。
图3是示出根据一个所示实施方式的主行为者(例如，车辆)搭载的基于处理器的系统的各个部件与远程的基于处理器的系统之间的示例数据流的框图，其中该远程的基于处理器的系统可以促进运动规划，以在图1的操作环境中操作主行为者(例如，车辆)。
图4是根据一个所示实施方式的示例运动规划栅格，在主行为者的目的在于从一个状态转换到另一个状态同时避免与操作环境中的动态障碍物和静态障碍物碰撞的情况下用于主行为者(例如，图1的自主车辆)。
图5是根据一个所示实施方式的用于主行为者(例如，自主车辆)的示例运动规划栅格，其示出了经过两个候选节点中每个候选节点的最小代价路径的示例，针对多个边中的每个边设置或调整的代价表示基于环境中的其它行为者(例如，其它车辆)以及其它障碍物的已知或预测轨迹确定的碰撞评估，也表示基于参数化代价函数的碰撞严重性。
图6是根据至少一个所示实施方式的流程图，其示出了在基于处理器的系统中操作的用于实施运动规划的方法600。
图7是根据至少一个所示实施方式的流程图，其示出了在基于处理器的系统中操作的用于实施运动规划的方法700。
图8是根据至少一个所示实施方式的流程图，其示出了在基于处理器的系统中操作的用于实施运动规划的方法800。
图9是根据至少一个所示实施方式的流程图，其示出了在基于处理器的系统中操作的用于实施运动规划的方法900。
具体实施方式
在以下说明中，阐述了某些具体细节以提供对各个公开实施方式或实施例的透彻理解。然而，相关领域的技术人员应认识到，可以在没有这些具体细节中的一个或更多个的情况下，或者利用其它方法、部件、材料等来实践这些实施方式或实施例。在其它情况下，与基于处理器的系统、计算机系统、致动器系统和/或通信网络相关联的众所周知的结构未详细示出或描述，以避免不必要地妨碍对实施方式或实施例的说明。在其它情况下，用于生成一个或更多个主要车辆、静态障碍物和/或动态障碍物的感知数据和表示以及构建其数字表示(例如，定向边界框、曲线、占用网格等)的众所周知的计算机视觉方法和技术未详细描述，以避免不必要地妨碍对实施方式或实施例的说明。
除非上下文另有要求，否则在整个本说明书和随后的权利要求书中，“包括”这个词及其变体，例如“包含”和“含有”，应被解释为开放的、包容性的意义，即“包括，但不限于”。
整个本说明书中对“一个实施方式”或“实施方式”或“一个实施例”或“实施例”的引用，指结合该实施例描述的具体特性、结构或特征包括在至少一个实施方式或至少一个实施例中。由此，在整个本说明书各处出现的短语“一个实施方式”或“实施方式”或“在一个实施例中”或“在实施例中”不一定都指代相同的实施方式或相同的实施例。此外，特定特性、结构或特征可以在一个或更多个实施方式或实施例中以任何合适的方式组合。
如在本说明书和所附权利要求书中所使用的，单数形式“一”、“一个”和“该”包括复数所指对象，除非内容另有明确规定。还应注意，术语“或”通常以其包括“和/或”的含义使用，除非内容另有明确规定。
在整个说明书和所附权利要求中，对“主行为者”或“一个主行为者”的提及，意指针对其制定或生成相应运动规划的行为者(例如，半自主或全自主车辆、具有或不具有可移动附属物的其它机器人)。在整个说明书中对“其它行为者”或“另一行为者”或“次行为者”或“一个次行为者”的引用，意指针对其制定或生成相应运动规划的主行为者以外的行为者(例如，半自主或全自主车辆、具有或不具有可移动附属物的其它机器人、手动操作的车辆、人或动物)。在某些情况下，对于这些其它或次行为者，可能正在发生运动规划的其它实例，但这些运动规划并不表示主行为者的运动或状态。
在整个说明书和所附权利要求中，对一个或更多个障碍物的提及，意指静态障碍物和动态障碍物。静态障碍包括在执行运动规划的时间段内保持静态的物理对象和逻辑概念。静态障碍物的示例的非限制性集合包括：桥台、路缘石、建筑物、树木、岩石、墙壁、路障、屏障、中间带、车道标记、中心线、其它道路标记、道路边缘(无论是否标记)、对于静态物理障碍物的“礼貌”区域(例如，与其它车辆的最小期望间距)和/或对于静态物理障碍物的其它逻辑间距概念(例如，偏移或区域)。动态障碍物包括在执行运动规划的时间段内移动或改变位置的物理对象和逻辑间距概念。动态障碍物的示例的非限制性集合包括：其它自主车辆、其它车辆、人、动物、关于动态物理障碍的礼貌区域和/或关于动态物理障碍的其它逻辑间距概念。
如本文中和权利要求中所使用的，“礼貌区域”或“礼貌区”指从障碍物向外限定的空间体积或面积或距离偏移，其在障碍物周围提供缓冲。例如，可以在车辆周围限定礼貌区域以提供缓冲，该缓冲容纳运动规划系统和/或车辆的容差、容纳采取规避动作的延迟，以及为乘客提供舒适感。又例如，可以限定与车道标记或道路边缘的偏移。礼貌区域可以围绕车辆对称地设置，但通常不会是对称的。例如，与位于车辆侧面的礼貌区域相比，在车辆前方或后方设置更大的礼貌区域以考虑停车距离可能是有益的。围绕其它类型的动态障碍物(例如，行人)或甚至围绕静态障碍物，可能存在类似的缓冲。这些中的每个都构成了逻辑间距概念，这是因为它们提供对于其它障碍物的非物理缓冲区。
在整个说明书和所附权利要求中，术语栅格与术语规划栅格、规划路线图和运动规划图可互换使用。栅格由节点集合和边集合构成，通常在构形空间(即，C空间)中，节点集合表示主行为者的相应状态，边集合表示由节点表示的相应状态之间的相应转换。需要注意的是，栅格有别于操作环境的现实世界二维或三维表示。
在整个说明书和所附权利要求中，术语碰撞检测指如果一个或更多表示沿着轨迹移动，预测或检测车辆或其它机器人的表示与模型中的障碍物之间的碰撞。因此，术语碰撞检测和碰撞评估可互换使用。
本公开的标题和摘要在此仅为方便起见而提供，并不解释实施例的范围或含义。
图1示出了根据一个所示实施方式的动态操作环境100，示例性主行为者(例如，主要自主车辆)102可以在该动态操作环境中操作。为了简要，本文将操作环境100称作环境100。虽然基于自主车辆来一般性地描述，但本文所述的各种实施方式适用于其它类型的机器人或其部分，例如可操作以导航环境的机器人和/或具有一个或更多个可移动附属物的机器人。
环境100表示主行为者(例如，主要自主车辆)102可在其中操作和移动的二维或三维空间(即，二度空间；三度空间)。主行为者102可以是机动车辆、飞机、船只、直升机、无人机，或任何其它车辆，也可以是可自主或半自主(即，至少部分自主)操作并沿着环境100所表示的空间中的路线或路径移动的其它类型的机器人。环境100是车辆在其中操作的二维或三维空间，它不同于主行为者或车辆的“构形空间”(通常称作“C空间”)，该构形空间在下文中会相对于运动规划栅格来提及，如在2017年6月9日提交的题为《自主驾驶车辆的运动规划和可重构运动规划处理器(MOTION PLANNING FOR AUTONOMOUS VEHICLES ANDRECONFIGURABLE MOTION PLANNING PROCESSORS)》的国际专利申No.PCT/US2017/036880和2016年1月5日提交的题为《专用机器人运动规划硬件及制造和使用方法(SPECIALIZEDROBOT MOTION PLANNING HARDWARE AND METHODS OF MAKING AND USING SAME)》的国际专利申请公开No.WO 2016/122840中所解释的。构形空间通常是多维的(即，大于3维)。
为了便于说明，按照在二维环境中的导航来描述各个实施方式。本领域的普通技术人员应理解，本文描述的结构和动作可以扩展到三维环境中的导航。
参照图1，环境100可以包括障碍物碰撞区域。这些障碍物碰撞区域可以是由于静态障碍物(例如，桥台、路缘石、建筑物、树木、岩石、墙壁、路障、屏障、中间带、车道标记、中心线、其它道路标记、道路边缘、相对于静态物理障碍物的“礼貌”区域和/或相对于静态物理障碍物的其它逻辑概念)造成的。这些障碍物碰撞区域可以是由于动态物理障碍物(例如，其它自主车辆、其它车辆、人、动物、相对于动态物理障碍物的“礼貌”区域和/或相对于动态物理障碍物的其它逻辑概念)造成的。静态障碍物和动态障碍物可以统称为障碍物。其它车辆(例如，其它自主车辆、手动操作车辆)可以统称为环境100中的“行为者”或“其它行为者”，尽管“行为者”不限于车辆，而是可以包括人或动物。
静态障碍物C 108表示在主行为者102(例如，主要自主车辆)将穿过或以其它方式在环境100中操作的时间段内，不在环境100中移动的障碍物，其在环境100中创建静态碰撞区域，使得如果主行为者102(例如，主要自主车辆)试图占据环境100中的与静态障碍物C108相同的空间，则主行为者102可能会与静态障碍物C 108碰撞。在各实施例中，可能存在比图1中所示更少的静态障碍物或附加的静态障碍物。
除静态障碍物以外，还可以存在动态障碍物104、112，包括表示在已知/确定轨迹中移动的障碍物(例如，收费站的转臂、车库门)、由有意识的生物(例如，骑自行车的人、行人、驾驶员、飞行员)控制的障碍物，和由其它自主系统控制的障碍物，例如在其它自主车辆或其它自主机器人的情况中。由于这些动态障碍物104、112带来的对运动规划的挑战涉及以非常快的速度执行运动规划的能力和分析动态障碍物104、112可能会如何移动的不确定性的能力。围绕主行为者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的接触，例如在游戏中。在一个实施方式中，主行为者102的目标是最大化不与动态障碍物B 112发生碰撞的时间，以使得例如主行为者102在不与动态障碍物B 112碰撞的情况下到达目标状态。在一个实施例中，主行为者102的目标是在状态之间转换，同时使与动态障碍物B 112发生碰撞的概率最小化。在环境100中可能存在比图1所示的更少的动态障碍物或附加的动态障碍物。而且，在一些情况下，环境100可能具有与主行为者102的航程相对应的边界，其可以至少部分地取决于车辆102当前的可用燃料或能量，或乘员舒适度。
虽然图1示出了代表性环境100，但典型环境可以包括许多附加的行为者，包括对应于其它载人和自主车辆的障碍物和各种其它天然或人工的静态和动态对象和障碍物。本文教导的构思可以以类似的方式应用于比所示更多行为者的环境。
图2和以下讨论提供了对基于处理器的计算机系统200的形式的合适的运动规划器或运动规划控制器的简要的一般性描述，在该基于处理器的计算机系统中可以实施各种所示运动规划系统和方法。
虽然不是必需的，但实施方式或实施例中的许多将在计算机或处理器可执行指令的一般性背景下进行描述，可执行指令例如存储在非暂时性计算机或处理器可读介质上或由非暂时性计算机或处理器可读介质存储的，并由一个或更多个计算机或处理器(即电路)和可以执行碰撞评估和运动规划操作的专用车辆运动规划硬件执行的程序应用程序模块、对象或宏。这样的运动规划操作可以包括在规划栅格或规划图或路线图的边上执行碰撞评估、确定碰撞概率、基于碰撞评估和可选地基于表示碰撞严重性或碰撞的相对偏好排序的参数化代价函数来设置或调整与每个转换或边相关联的代价、执行优化以识别规划栅格、规划图或路线图中的路径，以在状态之间转换并同时避免与静态障碍物和动态障碍物碰撞、最小化碰撞概率、或最小化与环境中的静态障碍物和动态障碍物碰撞的代价，例如通过在规划栅格、规划图或路线图中寻找状态之间的最小代价路径来进行最小化，以及可选地将其应用为可由主行为者(例如，主要自主车辆)执行的运动规划的一部分。
如本文所述，经由运动规划器的运动规划通常包括碰撞评估或检测以及寻找最小代价路径。例如，可以在一个或更多个微处理器或现场可编程门阵列(FPGA)上执行碰撞评估或检测、最小代价路径寻找，或两者，有利地允许容易的可重新配置。例如，可以在一个或更多个专用集成电路(ASIC)上执行碰撞评估或检测、最小代价路径寻找，或两者，有利地允许快速处理并同时仍然允许一定的可重新配置。任一实施方式都可以有利地实施或配置相应的硬件电路，以使用主行为者的计算有效表示以及使用障碍物的计算有效表示来执行碰撞评估，其中主行为者的计算有效表示例如表示为定向边界框的主行为者，障碍物的计算有效表示例如表示为边界框、定向边界框，或曲线的障碍物。可以预先计算主行为者的轨迹，并且有利地将其表示为拟合函数，例如拟合到常规地由运动方程表示的运动的多项式函数。这种方法可以有利地减少碰撞评估的计算负担，并且可以将一部分计算工作从运行时转移到运行之前。
当表示环境中的主行为者(例如，自主车辆或其它类型的机器人)或障碍物(例如，其它车辆、人或动物形式的动态障碍物)时，可以将环境表示为点云，并将相应的行为者或障碍物表示为像素或几何对象(例如，边界框、定向边界框、曲线、多边形网格)。如本文所述，发明人已经意识到，可以在计算上有利的是，将主行为者(例如，主要自主车辆)和/或可选地一个或更多个障碍物表示为框(例如，矩形棱柱、平行六面体)，例如表示为二维定向边界框，例如通过大小、位置和取向(例如，正面、前进方向)指定。由于车辆通常不是随机形状的，并且沿可以容易地表示为二维世界中的方向的方向行进，因此采用二维定向边界框来表示主行为者(例如，主要自主车辆)可以具有显著的优势。类似地，某些障碍物(例如，其它自主车辆或其它车辆)通常不是随机形状的，并且沿可以容易地表示为二维世界中的方向的方向行进，因此采用二维定向边界框来表示至少某些类型的障碍物可以具有显著的计算优势。值得注意的是，将障碍物(例如，车辆、物理障碍物、逻辑间距概念)表示为框，可能需要更少得多的比特(例如，仅二维边界框的两个对角的x、y坐标)。而且，与使用其它表示(例如，体素表示)相比，对二维边界框执行相交测试的计算强度可能较低，由此增强了处理系统的操作。附加地或备选地，对于某些障碍物(例如，中心线、车道标记、道路边缘)，采用曲线来表示至少某些类型的障碍物可以具有显著的计算优势。这样的曲线表示可以采取多种形式，例如b样条表示。相同的构思可以扩展到三维世界。可以使用各种数据结构来表示对象(例如，车辆、物理障碍物、逻辑间距概念)的二维和三维表面，例如欧几里得距离场(Euclidian distance field)、二元空间划分树等。
在至少一个实施方式中，使用轨迹的相对简单的表示，例如表示为拟合函数(例如，拟合多项式函数)，在主行为者和障碍物的相对简单的几何表示(例如，边界框、定向边界框、曲线)上执行碰撞评估。碰撞评估可以经由一个或更多个处理器(例如，微处理器、FPGA、ASIC)来执行。
在各个实施方式中，这样的操作可以完全在硬件电路中执行或作为存储在诸如系统存储器214之类的存储器存储中的软件来执行，并由一个或更多个硬件处理器212a(例如一个或更多个微处理器、数字信号处理器(DSP)、现场可编程门阵列(FPGA)、专用集成电路(ASIC)、图形处理单元(GPU)处理器、可编程逻辑控制器(PLC)、电可编程只读存储器(EEPROM))来执行，或作为硬件电路和存储在存储器存储中的软件的组合来执行。例如，可以通过最小代价路径优化器292执行优化来通过寻找规划栅格内的最短路径来识别规划栅格中的路径以避免碰撞或引起与环境中的物体的碰撞。在一个示例中，当最小代价路径优化器292是通过硬件实现时，规划图的拓扑结构也可以被映射到硬件单元的可重新配置的结构上，以使得能够快速确定最短路径。可以使用各种求解器。该映射涉及利用物理节点的逻辑邻居的地址和边权重来对每个物理节点进行编程。这允许架构能够被重构为不同的规划图拓扑。其它实施方式可以使用在FPGA上实现的微型处理器。
在备选实施方式中，可以通过专用运动规划硬件，在车辆102的生成的规划栅格的每条边上并行执行碰撞评估，该专用运动规划硬件例如是在2017年6月9日提交的题为《自主驾驶车辆的运动规划和可重构运动规划处理器》的国际专利申请No.PCT/US2017/036880和2016年1月5日提交的题为《专用机器人运动规划硬件及制造和使用方法》的国际专利申请公开No.WO 2016/122840中所述的可重构碰撞检测架构和其它实施方式。例如，这样的专用运动规划硬件的全部或一部分可以结合在运动规划器280和/或碰撞评估器288中或形成它们的一部分。而且，感知、规划栅格构造、碰撞检测、设置或调整与每个边或转换关联的代价，以及路径搜索的各个相关方面的实施方式还在2017年6月9日提交的题为《自主驾驶车辆的运动规划和可重构运动规划处理器》的国际专利申请No.PCT/US2017/036880和2018年8月23日提交的题为《在机器人运动规划中有效的碰撞检测(COLLISION DETECTION USEFULIN MOTION PLANNING FOR ROBOTICS)》的美国专利申请62/722,067和2016年1月5日提交的题为《专用机器人运动规划硬件及制造和使用方法(SPECIALIZED ROBOT MOTION PLANNINGHARDWARE AND METHODS OF MAKING AND USING SAME)》的国际专利申请公开No.WO 2016/122840中描述。相关领域的技术人员应理解，所示实施例以及其它实施方式可以利用其它系统配置和/或其它计算系统配置来实践，包括机器人、手持设备、多处理器系统、基于微处理器或可编程的消费电子产品、个人计算机(“PC”)、联网PC、小型计算机、大型计算机等。实施方式或其部分(例如，在设计时、配置时、运行之前)可以在分布式计算环境中实践，其中任务或模块由通过通信网络链接的远程处理设备来执行。在分布式计算环境中，程序模块可以位于本地和远程存储器存储设备或介质两者中。然而，使主行为者102(例如，主要自主车辆)具有有效的计算能力对于允许主行为者102实时响应变化的环境是重要的。针对此问题的通常采用的解决方案在性能和功率方面都失败了。它们可能太慢而无法允许高自由度的车辆和其它机器人实时响应环境，并为多个CPU或GPU供电给系统带来负担。为了解决这个问题，图2的示例实施方式中示出的计算机系统200包括运动规划器280，该运动规划器具有主行为者102(例如，主要自主车辆)搭载的碰撞评估器288，该碰撞评估器使用主行为者和障碍物的相对简单的几何表示，并且可选地采用表示为拟合函数的轨迹，该拟合函数可以有利地在配置或运行之前的时间期间确定或计算，并从外部源提供给主行为者。可以使用完全可重定向的碰撞检测微架构(例如FPGA 290)执行碰撞检测。然而，在各种备选实施方式中，可以使用包括可编程逻辑电路或块的阵列和可重新配置互连的层级结构在内的其它可编程碰撞检测微架构，例如ASIC架构，或具有一个或更多个核的一个或更多个微处理器。通过编程阶段，可以应用表示为拟合函数的轨迹。碰撞评估器288可以寻求避免与特定对象的碰撞和/或寻求实现与特定对象的碰撞。使用可重新配置的处理器作为碰撞评估器288，有效地消除了设计完全专门用于单个车辆/栅格对的限制。最小代价路径优化器292允许快速计算最小代价路径，例如使用分布式贝尔曼-福特(Bellman-Ford)策略。运动规划器280还可以包括严重性代价调整器289，其基于与相应边相关联的潜在碰撞的严重性或感知的严重性来设置或调整与相应边相关联的值(例如，代价)。如本文中详述的，严重性代价调整器289可以采用参数方程，以基于若干碰撞严重性表示参数和这些参数的权重来确定表示碰撞严重性的值(例如，代价)。例如，参数可以表示障碍物类型、碰撞类型、碰撞速度和/或会通过碰撞耗散的能量。
如上所述，一些预处理活动(例如，确定轨迹的拟合函数，否则轨迹会由在计算上相对难求解的运动方程来描述)可以在运行之前执行，由此，在一些实施方式中，这些操作可以由经由网络接口260通过通信网络链接到系统200的远程处理设备执行。例如，编程阶段允许针对感兴趣的问题(例如，对于给定自主车辆的栅格的每个边的转换)配置处理器。在这样的实施方式中，利用大量的预处理来避免运行时计算。当在栅格中进行从由栅格中的边表示的一个状态到另一状态的转换时，将关于主行为者102的轨迹的预计算数据(例如，拟合函数而没有三角函数)发送到运动规划器280的碰撞评估器288。也可以将栅格的拓扑结构映射到计算电路或单元(例如FPGA 290)的可重新配置结构上，以实现最小代价路径的快速确定。该映射包括利用物理节点的逻辑邻居的地址和边权重对计算电路的可重新配置结构的每个物理节点进行编程。这允许架构针对不同的栅格拓扑。在运行期间，传感器282将感知数据(例如，点云)发送到运动规划器280。感知数据可以被转换为表示存在于当前环境中的行为者和/或障碍物的简化几何表示(例如，边界框、定向边界框、曲线)。碰撞评估器288计算哪些运动可能涉及碰撞，哪些可能不涉及碰撞、更新或设置与多个边中的每个边相关联的代价，并且在完成时，由最小代价路径优化器292使用结果来确定最小代价路径。这可以有利地在不与传感器282或其它外部部件进一步通信的情况下发生。
在运行期间，运动规划器280基于环境相应地修改与栅格的边相关联的代价，取决于车辆102的目标是避免还是寻求与环境中的特定障碍物的碰撞。如本文所解释的，代价还可以反映碰撞的严重性。然后，运动规划器280运行并将生成的路径返回给致动器系统或传动装置(例如，电动机和传动系统、推进机构、发动机)266。
图2示出了例如用于主行为者102(例如，自主车辆)的计算机系统200，其包括运动规划器280和一个或更多个相关联的非暂时性机器可读存储介质，例如系统存储器214和与盘驱动器224关联的计算机可读介质226。相关联的非暂时性计算机或处理器可读存储介质(包括系统存储器214和与盘驱动器224相关联的计算机可读介质226)经由一个或更多个通信通道(例如系统总线216)通信地耦接到运动规划器280。系统总线216可以采用任何已知的总线结构或架构，包括具有存储器控制器的存储器总线、外围总线和/或本地总线。一个或更多个传感器282、对象检测器284、对象行为预测器286和致动器系统266也经由系统总线216通信地耦接到运动规划器280。这种部件中的一个或更多个也可以或替代地经由一个或更多个其它通信通道(例如，一个或更多个并行电缆、串行电缆，或能够进行高速通信的无线网络信道，例如通用串行总线(“USB”)3.0、高速外围组件互连(PCIe)或)相互通信。
计算机系统200还可以通信地耦接到远程系统(例如，台式计算机、膝上型计算机、超便携式计算机、平板计算机、智能手机、可穿戴计算机(未示出))，它们经由网络接口260直接通信地耦接或间接通信地耦接到计算机系统200的各个部件。在一些实施方式中，计算机系统200本身或其一部分可以是远程的。这种远程系统可以用于编程、配置、控制计算机系统200和计算机系统200内的各个部件或以其它方式与计算机系统200和计算机系统200内的各个部件交互数据或向其输入数据。这种连接可以通过使用互联网协议的一个或更多个通信通道，例如互联网之类的一个或更多个广域网(WAN)。如上所述，运行之前的计算(例如，初始栅格生成)可以由独立于主行为者102或其它类型机器人的系统执行，而运行时计算可以在主行为者102上执行，这是因为系统能够更新或改变车辆速度以实时或接近实时(微秒)地对不断变化的操作环境100做出反应是重要的。
在2017年6月9日提交的题为《自主驾驶车辆的运动规划和可重构运动规划处理器》的国际专利申请No.PCT/US2017/036880、2018年8月23日提交的题为《在机器人运动规划中有效的碰撞检测》的美国专利申请62/722,067，和/或2016年1月5日提交的题为《专用机器人运动规划硬件及制造和使用方法》的国际专利申请公开No.WO 2016/122840中描述了图2所示的各个模块的构造和操作的一些方面。因此，无需更详细地描述这些模块，因为鉴于通过引用并入本文的参考文献，它们会被相关领域的技术人员理解。
计算机系统200可以包括一个或更多个处理器212a、212b(统称为212)、系统存储器214，和将包括系统存储器214在内的各个系统部件耦接到处理器212的系统总线216。处理器212可以是任何逻辑处理单元，例如一个或更多个中央处理单元(CPU)212a、数字信号处理器(DSP)212b、图形处理单元(GPU)、专用集成电路(ASIC)、现场可编程门阵列(FPGA)、可编程逻辑控制器(PLC)等。这些ASIC和FPGA可以代替碰撞评估器288的FPGA 290或除了碰撞评估器288的FPGA 290以外也可以使用这些ASIC和FPGA，以对主行为者102的规划图的边执行碰撞评估。可重新配置的碰撞检测架构硬件可以例如是FPGA 290。然而，可以在各种替代实施例中使用包括可编程逻辑块阵列和可重新配置交互的层级结构在内的其它可编程碰撞检测微架构，例如ASIC架构。
系统存储器214可以包括只读存储器(“ROM”)218和随机存取存储器(“RAM”)220。可以形成ROM 218的一部分的基本输入/输出系统(“BIOS”)222包含(例如在启动期间)帮助在计算机系统200内的元件之间传输信息的基本例程。
计算机系统200可以包括盘驱动器224，其可以是例如用于读取和写入硬盘的硬盘驱动器、用于读取和写入闪存设备的闪存驱动器、用于读取和写入可移动光盘的光盘驱动器，或用于读取和写入磁盘的磁盘驱动器。在各种不同实施例中，计算机系统200还可以包括这种盘驱动器的任何组合。盘驱动器224可以经由系统总线216与处理单元212通信。如相关领域的技术人员所知的，盘驱动器224可以包括耦接在这种驱动器与系统总线216之间的接口或控制器(未示出)。盘驱动器224及其相关联的计算机可读介质226为计算机系统200提供计算机可读指令、数据结构、程序模块和其它数据的非易失性存储。相关领域的技术人员应理解，可以使用能够存储可由计算机访问的数据的其它类型的计算机可读介质，例如WORM驱动器、RAID驱动器、磁带、数字视频光盘(DVD)、伯努利(Bernoulli)盒带、RAM、ROM、智能卡等。
程序模块可以存储在系统存储器214中，例如操作系统236、一个或更多个应用程序238、其它程序或模块240和程序数据242。应用程序238可以包括使一个或多个处理器212对与环境100相对应的规划栅格的边执行碰撞评估的指令。例如，应用程序238可以包括一个或更多个机器可读指令，其使运动规划器280使用碰撞评估器288来对车辆102的所生成的规划栅格的边中的一个或更多个边执行碰撞评估。
应用程序238可以包括使一个或多个处理器212确定和设置或调整与每个边相关联的代价的指令。代价可以表示规划栅格的每个边的碰撞概率，和/或表示例如通过参数化代价函数(例如，参数化严重性代价函数)确定的碰撞的严重性或碰撞的偏好排序代价，并且可选地表示固有代价(例如，燃料、航程、乘客舒适度)。指令可以使一个或更多个处理器212确定碰撞概率并且为每个边分配或设置相应代价。指令可以使一个或更多个处理器212例如基于参数化代价函数来确定表示碰撞严重性或排序的碰撞偏好的代价，并相应地调整每个边的代价。应用程序238可以例如包括一个或更多个机器可读指令，该机器可读指令使一个或更多个处理器212至少部分地基于与主行为者102在其中操作的环境100中的一个或更多个动态障碍物(104、112)碰撞的概率的评估，针对规划栅格：为每个边确定或设置至少部分地反映碰撞评估，和/或至少部分地反映与由规划栅格的每个边表示的转换相关联的任何给定潜在碰撞相关联的参数化代价的权重或代价。
应用程序238可以包括使一个或更多个处理器212执行优化以识别规划栅格中的路径来避免或导致与环境100中的障碍物(例如，动态对象B112)发生碰撞的指令。执行优化以识别规划栅格中的路径可以包括寻找规划栅格内的最小代价路径。
应用程序238可以包括以下指令，该指令使一个或更多个处理器212将信号发送到致动器系统266，以使车辆102执行运动规划，从而使致动器(例如，电动机、螺线管、发动机)根据如本文所述的运动规划移动。
应用程序238还可以包括一个或更多个机器可读指令，其使一个或更多个处理器212从传感器282接收表示主行为者102(例如，主要自主车辆)在其中操作的环境100的感知信息。应用程序238还可以包括一个或更多个机器可读指令，其使一个或更多个处理器212选择或确定用于各个行为者和/或障碍物的表示的类型，例如为一些障碍物选择定向边界框表示并为其它障碍物选择曲线。应用程序238还可以包括一个或更多个机器可读指令，其使一个或更多个处理器212根据所选择或确定的表示类型来表示主行为者(例如，自主车辆)和障碍物。
应用程序238还可以包括一个或更多个机器可读指令，其使一个或更多个处理器212执行如本文中和在通过引用并入本文的参考文献中所述的其它感知操作(通过传感器282)、规划栅格构建、碰撞检测、代价确定、代价设置或调整，和路径搜索。
例如，应用程序238可以包括一个或更多个处理器可执行指令，其使一个或更多个处理器212通过传感器282接收表示主行为者102(例如，主要自主车辆)在其中操作的环境100的感知信息；使运动规划器280使用碰撞评估器288，对规划栅格的一个或更多个边中的每个边执行碰撞评估；针对规划栅格的一个或更多个边中的每个边，部分地基于碰撞概率，并且部分地基于表示可能的碰撞的严重性的参数化代价函数来设置代价值，其中所述碰撞概率至少部分地基于碰撞评估；执行优化以识别所生成的规划栅格中的路径，该路径提供了车辆102的最长行驶路线，该路线由与主行为者102在其中操作的环境100中的一个或更多个动态障碍物(例如，动态对象B 112)发生严重碰撞的可能性相对低的路径所指定；以及至少部分地基于该优化实施与主行为者102在其中操作的环境100中的一个或更多个动态对象(例如，动态对象B 112)发生碰撞的可能性相对低的运动规划。
应用程序238还可以包括一个或更多个机器可读指令，其使一个或更多个处理器212执行本文所述的各种其它方法，包括但不限于图6到图9中所示的那些。
虽然在图2中示出为存储在系统存储器214中，但操作系统236、应用程序238、其它程序/模块240和程序数据242可以存储在盘驱动器224的相关联的计算机可读介质226上。
一个或更多个处理器212可以是任何逻辑处理单元，例如一个或更多个中央处理单元(CPU)、数字信号处理器(DSP)、专用集成电路(ASIC)、现场可编程门阵列(FPGA)等。市售计算机系统的非限制性示例包括但不限于，由美国Corporation提供的Celeron、Core、Core 2、Itanium和Xeon系列微处理器；由美国Advanced Micro Devices提供的K8、K10、Bulldozer和Bobcat系列微处理器；由美国Apple Computer提供的A5、A6和A7系列微处理器；由美国Qualcomm,Inc.提供的Snapdragon系列微处理器；和由美国Oracle Corp.提供的SPARC系列微处理器。
图3示出了根据一个所示实施方式的系统300中的在主行为者(例如，主要自主车辆)搭载的基于处理器的系统300a的各个部件与远程的基于处理器的系统300b之间的示例数据流，该远程的基于处理器的系统可以促进运动规划，以在图1的操作环境中操作主行为者(例如，主要自主车辆)。主行为者(例如，主要自主车辆)搭载的基于处理器的系统300a可以类似于或包含基于处理器的系统200(图2)的实例。远程的基于处理器的系统300b可以类似于或包含基于处理器的系统200(图2)的实例。
远程的基于处理器的系统300b可以生成或确定表示多个边中的每个边的轨迹的拟合函数，边表示车辆状态之间的转换，其中，状态表示为规划栅格中的节点。虽然转换常规地通过运动方程表示，但使用运动方程评估碰撞的计算强度高(例如，采用三角函数)。在至少一个实施方式中，基于处理器的系统可以针对多个轨迹中的每个轨迹，基于运动方程生成一组拟合函数。拟合函数可以将轨迹表示为曲线，并且可以有利地避免包含三角函数。例如，在运行之前进行配置期间，基于处理器的设备可以离线确定拟合函数(例如，拟合多项式函数)。例如，基于处理器的设备可以基于原始设备制造商(OEM)提供的信息(例如，轴距、转弯半径)，确定拟合函数，并且拟合函数甚至可以由OEM确定或生成。与使用常规运动方程相比，使用拟合函数可以提供在计算上效率更高的碰撞评估方法。
结合在主行为者102内或与主行为者102可操作地通信的一个或更多个传感器282(例如摄像机、激光传感器设备、音频传感器等)收集感知信息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％的概率做别的事情。
各种因素可能影响对象行为预测器286对环境100中的动态障碍物(104、112)的预测轨迹的确定。例如，在一些实施方式中，可以指示或确定动态障碍物(104、112)的目标会影响其在环境100内的未来移动。作为一个示例，可以指示或确定被检测到当前在直接远离主行为者102的轨迹上的动态障碍物A 104的目标是远离(并保持远离)主行为者102。因此，对象行为预测器286可以在预测动态障碍物A 104的移动时考虑到这一点。另一方面，可以指示或确定被检测到当前在直接朝向主行为者102的轨迹上的动态障碍物B 112的目标是与主行为者102碰撞。因此，对象行为预测器286可以在预测动态障碍物B 112的移动时考虑到这一点。
另外，其它障碍物(例如，其它行为者或其它自主车辆、人、动物)的移动可能会受到主行为者102的轨迹的变化的影响。因此，在确定动态障碍物的预测轨迹时，对象行为预测器286可以考虑主行为者102的当前轨迹的规划的但尚未实施或执行的变化，并将此类数据包括在提供给运动规划器280的预测轨迹信息306中。例如，如果指示或确定被检测到当前在直接朝向主行为者102的轨迹上的动态障碍物B 112的目标是与主行为者102碰撞，则可以预测，如果主行为者102改变其轨迹，则动态障碍物B 112可能会在其轨迹中做出相应的改变，以追赶主行为者102。由此，如果主行为者102的目标是在不与(正在试图与主行为者102碰撞的)动态障碍物B 112碰撞的情况下到达环境100内的目的地，则运动规划器280可以通过考虑到动态障碍物B 112可能会在主行为者102改变其轨迹以到达目的地时在其轨迹中做出相应的改变以追赶主行为者102，来规划到目的地的路径，以避免与动态障碍物B 112碰撞。
总体而言，系统可以通过使用传感器282的组合和由对象检测器284和对象行为预测器286执行的处理来执行感知，以生成环境100的模型。在一个实施方式中，传感器282生成数字表示，例如定向边界框、占用网格或曲线。定向边界框是具有方向和尺寸(例如，正好相对的对角上的两个点)的平行六面体。点云或占用网格是表示环境(例如环境100)的离散化视图中哪些空间和时间区域包含障碍物的数据结构。如果是二维的，每个离散化空间区域都被称为“像素”。在三维世界中的转移可以有效地视为二维转移的情况中(例如，常规街道、道路和/或高速公路上的地面车辆)，将对象表示为二维边界框可能是有利的，例如二维定向边界框。在三维转移的情况中，将对象表示为三维框(矩形棱柱)而不是二维框可能是有利的。曲线可以被表示为例如样条、b样条，或曲线的任何其它参数表示。
环境中的障碍物(包括动态障碍物A 104、动态障碍物B 112和静态障碍物C 108(图1))所占据的空间区域或区，由数字表示来表示，例如由二维边界框、二维定向边界框、曲线表示来表示。一个或更多个动态障碍物(例如，动态障碍物A 104和动态障碍物B 112)的数字表示，以及相关静态障碍物的体积表示从对象检测器284传递到运动规划器280。障碍物或对象的数字表示的构建在可获得的大量已发表的文献中做出了说明，并且对计算机视觉和感测领域的技术人员是已知的。
运动规划器280从对象检测器284接收包括动态障碍物和静态障碍物的表示的感知数据，并从对象行为预测器接收预测的轨迹信息。然后，运动规划器280基于碰撞评估，调整沿着规划栅格中的每条边的代价值，例如以考虑预测轨迹，并且可选地基于表示碰撞严重性或排序的碰撞偏好的参数化代价函数，通过考虑代价和碰撞概率来确定路径，并将路径输出到计算系统。
运动规划器可以包括作为运动规划器280内的碰撞评估器288的一部分的硬件处理器和存储器存储。例如，FPGA 290或其它可编程逻辑块阵列可以存储规划栅格，其在本文中也称为“路线图”(例如参见图4)。在一些实施方式中，运动规划器280包括硬件碰撞检测电路，例如FPGA 290，以执行碰撞检测。在一些实施方式中，运动规划器280包括可重新配置的碰撞检测加速装置。关于主行为者102在其中操作的环境的数据可以存储在运动规划器280的碰撞评估器288的存储器存储处，以使得在运动规划期间，随着接收可能包括关于动态障碍物的预测轨迹的信息的感知数据，由碰撞评估器288的硬件处理器比较感知数据，以评估碰撞。在运行操作期间，可以基于一个或更多个变量，为规划图的边分配信息(例如，代价值)。例如，在不仅考虑到碰撞概率或可能性，而且还考虑到指定碰撞严重性的参数化代价函数的至少一些实施方式中，在主行为者102的目标是避免与动态障碍物A 104碰撞的情况中，基于根据预测轨迹信息306对动态障碍物A 104向何处前进的预测，运动规划器280将为主行为者102生成运动规划，以避免或最小化与动态障碍物A 104碰撞的风险(例如，与无生命对象碰撞优先于与有生命对象碰撞，与逻辑空间概念(例如礼貌区域)碰撞优先于与物理对象碰撞，以较低速度碰撞优先于以较高速度碰撞，某些方向的碰撞优先于其它方向的碰撞)。参数化代价函数可以有利地允许OEM、运营商或终端用户指定参数和每个参数的权重。
为此，碰撞评估器288评估规划图的边中的至少一个边与动态障碍物A 104碰撞的可能性。要注意的是，环境100是主行为者102在其中操作的二维或三维空间，不同于在下文中参考图4中所示的运动规划栅格提及的主行为者的“构形空间”。主行为者的构形空间是表征主行为者的状态的主行为者102的所有构形的空间，通常是多维空间，例如具有三个以上的维度。图4中所示的规划栅格400中的边表示主行为者102的构形之间的转换。规划栅格400的边不一定表示笛卡尔坐标中的实际移动。规划栅格400的边还可以包括速度变化等。
规划栅格400的每个边表示主行为者从一个状态到另一个状态的转换，并且具有与其相关联的固有或操作代价。例如，固有或操作代价可能与燃料使用、执行相关联动作的时间、与动作相关联的磨损和/或其它因素有关。在至少一些实施方式中，可以为每个边分配对应于固有或操作代价的初始权重。
在运行期间，系统至少部分地基于碰撞评估，设置或调整边的代价，以表示与环境中的动态障碍物(104、112)碰撞的概率。系统可以通过至少部分地基于碰撞概率修改每个边的初始分配权重来执行代价的调整。例如，系统可以对每个边应用代价函数，以基于该边的初始权重(即，对应于固有代价的权重)来执行数学运算，以获得修改的权重。这可以通过基于碰撞概率向初始分配权重添加附加权重，通过将初始分配权重乘以碰撞概率因子，或通过应用一些涉及碰撞概率和对应于固有代价的初始权重的其它函数或公式来完成。
分配给边的固有或操作代价也可以在运行期间进行调整，以反映特定于对象的代价，这些代价表示避免与对象碰撞或实现与对象碰撞的相对重要性和/或严重性。这些特定于对象的代价独立于固有或操作代价，并独立于碰撞概率。例如，与和人碰撞相关联的特定于对象的代价可以被设置为显著高于与和无生命对象碰撞相关联的特定于对象的代价。
在至少一些实施方式中，运动规划器可以有利地采用参数化代价函数来为每个边生成代价值。参数化代价函数可以包括各种参数和相关联的权重。代价函数的参数可以例如表示与碰撞严重性相关的参数或按偏好对碰撞排序的参数，包括例如：特定于障碍物或对象的代价(例如，对象类型，例如人类与无生命的对象)、特定于碰撞的代价(例如，碰撞类型，例如将导致损坏的与物理对象的碰撞与可能不会导致损坏的与道路标记或礼貌区域的碰撞)、速度的指示或速度对于碰撞严重性的影响(例如，主要车辆绝对速度、主要车辆与障碍物之间的相对速度)，和/或耗散能量的表示(即，会通过碰撞耗散的能量)。在至少一些实施方式中，参数和/或权重是通过OEM选择或分配的。在至少一些实施方式中，参数和/或权重是通过车主或负责自主车辆操作的人或者甚至由政府部门或保险行业标准组织来选择或分配的。
为了简化图4中的图示，对应于每个边的固有代价的所有初始权重都已设置为零，并通过添加附加代价来进行调整，附加代价指示碰撞概率以及指示由参数化代价函数生成的用来表示由所分配的权重加权的特定于障碍物或对象的代价、特定于碰撞的代价和速度的代价值。由此，在其中主行为者102的目标是避免与环境中的动态对象(例如动态对象B112)碰撞的一个实施方式中，较大的碰撞概率可能会导致调整后的边权重具有较大的正值。与表示人的障碍物的碰撞可能会导致分配给对应边的正值比与无生命对象的碰撞更大。与表示可能会导致损坏的物理对象(例如，墙壁)的障碍物的碰撞可能会导致分配给对应边的正值比与车道标记或礼貌区域或其它间距偏移的碰撞更大。例如，由于车辆能够沿某些部分(例如，可塌陷区域或皱缩区域)吸收或耗散能量而不会对乘员或货物造成伤害，因此某些方向的碰撞可能优先于其它方向。类似地，以较高的绝对速度或较高的相对速度发生的碰撞导致的损坏可能更显著，可能会导致分配给对应边的正值比分配给以较低的绝对速度或较低的相对速度发生的其中导致显著损坏的可能性相对更低的碰撞的值更大。类似地，耗散较少能量的碰撞可能优选于耗散相对较多能量的碰撞，这是因为在所有其它参数相同的情况下，这些碰撞可能会导致较少的损坏。在一些实施方式中，OEM可以提供一些或所有参数和权重的值，例如基于对具体车辆类型(即品牌和型号和年份)的测试。
一旦已经调整了规划栅格的所有边的权重，路径优化器292就执行从在规划栅格中指示的主行为者102的当前位置到主行为者102的可能的下一个状态或目标状态的最小代价路径算法。然后，通常由运动规划器280选择规划栅格中的最小代价路径。
一旦路径优化器292识别出规划栅格内的路径，运动规划器立即将这个识别出的路径310实时传递到主行为者102的致动器系统266，以生成到主行为者102的各个马达或移动系统的对应信号，以使主行为者102发生物理移动，以实施运动规划。
图4是根据一个所示实施方式的用于图1的主行为者102的在主行为者102的目标是避免与接近主行为者的图1的动态障碍物B 112发生碰撞的情况下的示例运动规划栅格400以及在规划栅格400中识别的为避免与动态障碍物B 112发生碰撞的示例路径412(包括连接节点408a到408i的栅格400的粗体边)。
规划栅格400分别包括由边连接的多个节点。每个节点隐式地或显式地表示表征主行为者102在主行为者构形空间中的状态的时间和变量。在本示例中，主行为者的构形空间(通常称为C空间)是在规划栅格400中表示的表征主行为者102的状态的主行为者的构形的空间。例如，每个节点可以表示主行为者102的构形，其可以包括但不限于主行为者102的当前位置、姿态、速度和前进方向。在一些实施方式中，主行为者102的加速度也由规划栅格400中的节点表示。
规划栅格400中的边表示主行为者102在这些构形之间的转换。规划栅格400的边不表示笛卡尔坐标中的实际移动，而是表示C空间中的状态之间的转换。例如，每个节点可以表示主行为者102的构形，其可以包括但不限于主行为者102的当前位置、姿态、速度和前进方向，以及可选地主行为者的加速度。边表示这些构形之间的转换。规划栅格400的每个边表示主行为者102在相应的一对节点之间的转换。例如，边410a表示主行为者102在两个节点之间的转换。特别地，边410a表示处于与节点408b相关联的特定构形中的主行为者102的状态与处于与节点408c相关联的特定构形中的主行为者102的状态之间的转换。例如，主行为者102当前可能处于与节点408a相关联的特定构形中。尽管节点示出为彼此相距不同的距离，但这仅用于说明目的，这与任何物理距离无关，并且对规划栅格400中的节点数量没有限制。然而，在规划栅格400中使用的边和节点越多，运动规划器280就可以越准确和精确地根据主行为者102的目标确定优化路径，这是因为存在更多路径用于从中选择最小代价路径。
可能会存在希望主行为者102避开动态障碍物B 112的情况，例如为了避免与动态障碍物B 112碰撞。图4示出了在主行为者102的目标是避免与动态障碍物B 112碰撞或躲开动态障碍物的情况中，运动规划器280如何使用规划栅格400来为主行为者102识别路径。此时，运动规划器280已经接收到表示主行为者102在其中操作的环境100的感知信息。
在一个实施方式中，环境100离散化成像素或框的二维区域。障碍物可以数字化表示，例如表示为边界框、定向边界框，或曲线(例如，样条)，哪种数字表示最适合于将要执行的障碍物类型和碰撞检测类型，本身可以取决于所采用的具体硬件电路。在一些实施方式中，预先计算主行为者102的栅格中的轨迹。在2017年6月9日提交的题为《自主驾驶车辆的运动规划和可重构运动规划处理器》的国际专利申请No.PCT/US2017/036880、2018年8月23日提交的题为《在机器人运动规划中有效的碰撞检测》的美国专利申请62/722,067和2016年1月5日提交的题为《专用机器人运动规划硬件及制造和使用方法》的国际专利申请公开No.WO 2016/122840中对碰撞评估的示例进行了描述。
如上所述，对于二维转换的碰撞检测，可以使用像素或二维几何形状(例如，二维框、二维定向边界框)或其它数字表示(例如，曲线)来表示环境中的障碍物，包括动态障碍物B 112。运动规划器280可以使用像素或框来表示主行为者102，优选地，可以采用定向边界框来表示车辆。然而，应理解的是，可以使用其它对象表示。在一个实施方式中，环境离散化成点云，并且主行为者和障碍物被表示为几何对象(例如，定向边界框、曲线)或其它数字表示。然后，评估与边相关联的轨迹与障碍物表示的碰撞。沿轨迹的单个点处的碰撞可以足以识别整个轨迹，从而识别出处于碰撞状态或具有相对较高碰撞可能性的对应边。
由于动态障碍物B 112在环境100中移动，因此运动规划器280还基于对动态障碍物B 112去往何处的预测，针对规划栅格400中的两个或更多个边确定主行为者102与动态障碍物B 112的碰撞评估。对于规划栅格400的这些边中的每个边，运动规划器280至少部分地基于碰撞评估，设置主行为者102在特定的未来时间与动态障碍物B 112碰撞的概率。例如，根据感知信息，检测动态障碍物B 112在环境100中的特定位置。基于动态障碍物B 112的当前轨迹106，运动规划器280确定动态障碍物B 112将位于的环境100中的特定位置。对于规划栅格400中的在节点之间的直接转换将导致存在与动态障碍物B 112碰撞的可能的节点，运动规划器为在这些节点之间转换的规划栅格400的边(边410a、410b、410c、410d、410e、410g、410h、410i、410j、410k、410j、410m、410n、410o和410p)分配指示与动态障碍物B112碰撞的概率的权重。在图4所示的示例中，这标记为图示部分414，但不对应于物理区域。
例如，运动规划器280可以为与动态障碍物B 112的相应碰撞概率高于定义的碰撞概率阈值的规划栅格400的多条边中的每条边分配值大于零的权重。在本示例中，运动规划器280已经向规划栅格400中根据动态障碍物B 112的当前轨迹不具有(或具有非常小的)与动态障碍物B 112碰撞的可能性的那些边分配为零的权重。然后，运动规划器280为与环境100中的动态障碍物B 112的相应碰撞概率高于定义的碰撞概率阈值的规划栅格400的多条边中的每条边分配值大于零的权重。在本示例中，运动规划器280已经为规划栅格400中根据动态障碍物B 112的当前轨迹具有与动态障碍物B 112碰撞的较高可能性的那些边分配了大于零的权重。用于碰撞概率的特定阈值可以变化。例如，阈值可以是40％、50％、60％或更低或更高的碰撞概率。而且，分配值大于零的权重可以包括分配大小大于零的权重，对应于相应碰撞概率。例如，如在规划栅格400中所示，运动规划器已经向具有较碰撞可能性的边410f和410i分配了权重5，而向运动规划器280确定其具有非常低的碰撞可能性的边410p和410g分配了大小更小的权重1。
运动规划器280可以基于例如表示碰撞严重性或感知严重性的参数化代价函数来分配、设置或调整每个边的权重。参数化代价函数可以由具有相关联的权重的多个参数构成。参数可以例如包括障碍物类型、碰撞类型和速度。参数可以具有布尔值、二进制值、整数值、实数值，和/或其它类型的值。例如，障碍物类型可以表示障碍物类型(例如，人、动物、载有人的车辆、未载人的自主车辆，无生命对象)或映射到障碍物类型的相应值。表示人或存在人的障碍物可以具有比无生命障碍物更高的相关联的代价。而且，例如，碰撞类型可以表示碰撞类型(例如，将导致或可能导致主要车辆或障碍物损坏的与物理对象的硬碰撞；不会导致或可能不会导致损坏的与物理对象的或与表示空间或区域的逻辑概念(例如，围绕其它车辆的礼貌区域，或车道标记)的软碰撞；正面碰撞、T形(T-bone)碰撞，使得安全气囊或其它安全设备部署应用的碰撞、车辆的相对受保护的部分承受大部分撞击的碰撞与车辆的相对不受保护的部分承受大部分撞击的碰撞)，或映射到碰撞类型的相应值。例如，许多乘用车辆都针对不同类型的碰撞或撞击进行了评估和评级。这样的评级可以评估或反映给定碰撞类型对车辆的预期损坏，和/或可以评估或反映对于给定碰撞类型，车辆乘员的相对安全性。对于一些类型的撞击相对于其它类型的撞击来说，某些车辆(包括可能载客或可能未载客的自主驾驶车辆)可能具有相对较高的碰撞等级(例如撞击等级)。而且，例如，速度可以表示主要车辆的绝对速度、障碍物的绝对速度，或主要车辆相对于障碍物的相对速度，或映射到绝对或相对速度指示的相应值(例如，低速、中等速度、高速)。而且，例如，预期作为碰撞的一部分耗散的能量的量可以是参数，可以代替速度也可以作为速度的补充。耗散的能量的量通常是速度的函数。权重可以例如采取百分比、分数或十进制值的形式，并且总计可以为100％或1。
在运动规划器280至少部分地基于碰撞评估设置了主行为者102与动态障碍物B112的碰撞概率之后，运动规划器280执行优化，以识别生成的规划栅格500中的路径512，该路径提供由与动态障碍物B 112发生碰撞的可能性相对较低的路径指定的主行为者102的行进路线。
在一个实施方式中，一旦已经如图4所示地分配了规划栅格400的所有边的代价，运动规划器280就可以执行计算，以确定到或朝向由目标节点表示的目标状态的最小代价路径。例如，运动规划器280可以执行从规划栅格400中的主行为者102的当前状态到可能的最终状态的最小代价路径算法。然后，由运动规划器280选择规划栅格400中的最小代价(接近零)路径。如上文所解释的，代价不仅可以反映碰撞概率，而且还可以反映碰撞严重性，以及其它因素。在本示例中，主行为者102在规划栅格400中的当前状态在节点408a处，并且该路径在规划栅格400中表示为路径412(由从节点408a延伸直至节点408i的线段组成的加粗线路径)。
尽管规划栅格400中的路径示出为具有许多急转弯，这样的转弯不表示路线中的对应物理转弯，而是表示主行为者102的状态之间的逻辑转换。例如，所识别的路径412中的每个边可以表示关于环境100中的主行为者102的物理构形的状态改变，但不一定是对应于图4所示的路径412的角度的主行为者102的前进方向的改变。
可以使用各种方法用于确定最小代价路径，包括实施贝尔曼-福特算法的那些方法，但也可以使用其它方法，包括但不限于将最小代价路径确定为规划栅格400中的两个节点之间使得其构成边的代价或权重之和最小化的路径的任何方法。该方法通过使用规划栅格和碰撞检测提高寻找与所期望的对象碰撞的最佳路线的效率和响应时间，来改进用于与动态对象(104、112)发生碰撞的主行为者(例如，自主车辆)的运动规划技术。另外，一些实施方式使用相同的方法来识别与主行为者102在其中操作的环境中的一个或更多个障碍物发生碰撞的可能性相对高的主行为者102的路径。在寻求与这类障碍物碰撞的情况中，运动规划器280可以为规划栅格400中具有与环境100中的障碍物碰撞的相应概率的边分配较大负值的代价或权重。由此，当运动规划器在优化期间选择最小代价路径时，更可能选择这样的路径。在这种实施方式中，其中障碍物是静态的，不存在需要考虑的静态障碍物的速度、轨迹或加速度。
该方法通过使用规划栅格和碰撞检测提高寻找避免与动态对象碰撞的最佳路径的效率和响应时间，来改进避免与动态对象碰撞的运动规划技术。另外，一些实施方式使用相同的方法来识别与主行为者102在其中操作的环境中的一个或更多个静态对象发生碰撞的可能性相对低(例如，零)的主行为者102的路径。在要避免与这类静态障碍物碰撞的情况中，运动该规划器280为规划栅格400中具有与环境100中的静态对象碰撞的相应概率的多个边中的每个边分配值相对高的代价或权重。这样，当运动规划器在优化期间选择代价最小路径时，将避开边代价被设置为相对较高值的路径，因为这样就不存在如果通过该边则将与障碍物发生碰撞的不确定性。然而，在此类实施方式中，与静态障碍物的碰撞可以优于与另一个障碍物的碰撞，例如，静态障碍物是无生命的或道路标记或间距偏好，而另一个障碍物是人，或者另一个障碍物正在以相对较高的速度相对于主行为者或主要车辆移动，因此而导致的碰撞可能会产生严重的不利后果。
在一些实施方式中，可能存在多个其它行为者，例如动态障碍物(104、112)。在这样的实施方式中，可以并行、同时或以其它方式彼此结合地实施本文所述的用于主行为者102避免与动态障碍物(104、112)碰撞的方法。例如，一些障碍物可能被识别为要避免与之碰撞的障碍物。然后，运动规划器280执行如本文所述的优化，相应地考虑到对应于动态障碍物和静态障碍物的轨迹和感知信息，以及是否要避开这类对象，以及在某个给定速度下与障碍物碰撞的相对严重性。在这类情况中，基于碰撞评估来设置规划栅格的边的碰撞概率包括：相应地分配代价或权重(例如，通过改变/调整初始代价或权重)，以避免发生碰撞或严重碰撞。
考虑到对指示碰撞的预测严重性的各种参数的评估，运动规划器280可以执行优化，以识别生成的规划栅格400中沿主行为者102的整个路线与动态障碍物B 112发生碰撞的可能性最低的路径。还可以基于动态障碍物B 112的轨迹106中的改变或预测改变来识别路径。在动态障碍物B 112的轨迹106的每个改变或预测改变处，可以实时或接近实时地再次运行碰撞评估和优化方法。此外，所生成的规划栅格400可以具有表示对主行为者和/或动态障碍物的物理或性能约束、主行为者102的加速度、俯仰角、滚动角和偏航角的数据，在一些实施方式中，还有动态障碍物B 112的上述数据。用于识别路径的优化则可以基于这类变量来执行。例如，如果动态障碍物B 112的俯仰角、滚动角和偏航角改变，这可以指示动态障碍物B 112的轨迹中改变(或导致预测改变)。
运动规划器280可以针对各种各样的自主车辆和机器人(带有或不带有附属物)以及预期任务场景进行编程。运动规划器280可以针对不同车辆或机器人再次使用或重新编程，或运动规划器280可以针对具体车辆或机器人进行设计。一种机器人类型是自主车辆，例如本文所述的自主车辆。
图5是用于主行为者102(例如，自主车辆)的示例运动规划栅格500。栅格500中的每个节点(例如，n0、n1、n2)可以具有相应的关联值(例如，代价、权重)，这些值基于与该节点与主行为者102的目的地(例如，最终状态)之间的栅格的边关联的代价(例如，c0,4、c0,5等)。如本文所解释的，代价可以反映碰撞概率或可能性，以及表示碰撞的严重性，例如基于障碍物类型、碰撞类型和或碰撞速度或会在碰撞过程期间耗散的能量。
在一些实施方式中，可以通过执行静态背景碰撞检测寻找与静态障碍物(例如，静态障碍物C 108)发生碰撞的边来初始化栅格500。在这种情况中，可以向已经确定导致与静态障碍物碰撞的边(例如，n14与n15之间的边)，分配(或可以应用代价函数)相应代价，使得该边与相对高的代价关联或被分配相对高的代价。例如，可以将代价设置为十万，由此有效地阻止主行为者102的轨迹包括被识别为与静态障碍物碰撞的边。可以基于参数化代价函数，设置或调整分配给每个边或与每个边关联的代价，该参数化代价函数表示碰撞严重性或感知严重性，或按照偏好对碰撞类型的排序，其对(表示为参数的)碰撞的各个方面(例如，障碍物类型、碰撞类型、碰撞速度，或耗散的能量)进行加权，并且基本上将一些碰撞排序为与其它碰撞相比更不受欢迎。例如，在两个碰撞具有相等的发生可能性的情况中，一个可能具有比另一个高得多的代价，例如在一个表示与人或载有人的车辆的碰撞而另一个表示与无生命对象的碰撞的情况中。类似地，相比于以较低的相对速度发生的碰撞，代价函数可以为以较高的相对速度发生的碰撞返回更高的代价值，即使两个碰撞具有相同的发生可能性。
在一些实施方式中，可以在单个动作中执行向边分配或为其设置代价值或以其它方式将其与代价值关联，代价值既表示所评估的碰撞概率，也表示所评估的碰撞严重性。由此，在一些实施方式中，参数化代价函数可以包括表示碰撞概率的参数，以及可选地，用于调整碰撞概率相对于严重性相关参数的影响程度的相应权重。在其它实施方式中，可以向每个边分配表示与该边表示的转换相关联的相应碰撞概率的相应代价，并且可以基于表示碰撞严重性的代价函数，调整或微调代价值。在一些实施方式中，可以将表示严重性的代价值与表示碰撞概率的值相加。在其它实施方式中，可以用表示严重性的代价值乘以表示碰撞概率的值。
在栅格500的初始化的第二方面，对于每个节点，基于例如从所涉及的节点到目标节点(例如，n15)的最小代价路径来确定到目的地的代价。例如，可以通过n13与n16之间的边的代价(c13,16)和n16与n15之间的边的代价(c16,15)，确定节点n13的代价。
使用图5所绘制的栅格500的用于主行为者102的运动规划可以在时间T＝i时，在记为n的节点(例如，n0)处开始执行。如上文所解释的，运动规划可以有利地考虑到主行为者102的环境100中的其它行为者(例如，动态障碍物(104、112))的假设或推断的意图。可以例如使用基于概率函数的行为模型来对假设或推断的意图进行采样，以产生每个行为者Aj的轨迹t，生成轨迹集合S。如在下文中进一步解释的，在将每个轨迹t单独应用到栅格500时确定最小代价路径，然后可以执行代价的取平均值。这与在确定最小代价路径之前将整个轨迹集合应用到运动规划栅格的方式相反。
对于S中的每个轨迹t，确定运动规划栅格500中的哪些边(如果有的话)与轨迹碰撞，即哪些边将导致主行为者102与对应于轨迹t的另一行为者发生碰撞。例如通过应用确定与碰撞相关联的代价的代价函数来修改这些边的代价值，代价函数例如是如下的函数，其使较高的值被分配给发生碰撞的边，甚至还能使分配给具有相对较高的预测严重性碰撞后果的碰撞的边比分配给具有相对较低的预测严重性碰撞的那些边的值更高。
基于轨迹t修改栅格500的边的代价，并且可选地基于参数化代价函数(表示预测的严重性碰撞后果或评估的参数化代价函数)进行修改。在修改了边的代价之后，针对候选节点n’(即在单个时间步长中(即，在时间T＝i+1处)从当前节点n(例如，n0)可达的节点)中的每个节点计算代价。通过寻找从当前节点n(例如，n0)，经过候选节点n’，到目的地的最小代价路径，来计算候选节点n’(例如，n3、n4、n5和n1)的代价。图5示出了如下示例，从节点n0到目的地(节点n15)的经过候选节点n4、n9、n13和n16的第一最小代价路径(以加粗线示出)和从节点n0到目的地的经过候选节点n5、n10、n14和n16的第二最小代价路径(也以加粗线示出)。在这些示例中，对于轨迹t，节点n4的代价是沿着第一路径的边(例如，c0,4、c4,9、c9,13、c13,16和c16,15)的和。
对于轨迹集合中的每个轨迹(t1、t2、tm)，以上述方式计算候选节点n’的代价，每个轨迹对应于行为者Aj(j＝1至m)，其中m是其它行为者的数量。代价可以在轨迹集合上取平均值，以提供对于每个候选节点n’的平均代价。将具有最小平均代价的候选节点n’选择为对于主行为者的下一个节点。因此，在时间T＝i+1处，具有最小平均代价的候选节点n’变成下一个时间步长T＝i+2的当前节点n。这样继续到直至主行为者102达到目标节点(例如，n15)，即实现了目标节点表示的状态。
图6是示出根据至少一个所示实施方式的在基于处理器的系统中操作的用于实施运动规划的方法600的流程图。
方法600可以在602处开始，例如响应于来自调用例程的调用或激活，或在基于处理器的系统或其部分启动时，或在接收到表征包括静态障碍物、动态障碍物和车辆状态在内的操作环境的更新信息时。
在604处，基于处理器的系统将主要车辆，优选地表示为相应定向边界框。在进行操作时，基于处理器的系统可以确定或指定相应定向边界框的参数(例如，角、尺寸、方向)，或从实体(例如，制造该车辆的原始设备制造商(OEM))和/或从OEM基于处理器的系统接收车辆的相应定向边界框的参数。
可选地，在606处，基于处理器的系统以数字形式表示一个或更多个动态障碍物(例如，其它车辆)。例如，可以有利地将具有限定形式或形状的障碍物(例如车辆)表示为相应定向边界框。附加地或备选地，可以将围绕车辆或其它移动障碍物的礼貌空间表示为定向边界框。
可选地，在608处，基于处理器的系统以数字形式表示一个或更多个静态障碍物。例如，可以将具有限定形式或形状的障碍物表示为相应边界框，或某种其它数字形式。
可选地，在610处，基于处理器的系统将一个或更多个静态障碍物表示为相应曲线。例如，可以有利将道路标记或道路边缘表示为曲线。例如，可以将道路的中心线、道路边缘、道路的车道标记、或道路边缘中的的任一个或更多个数字地表示为曲线(例如，表示为样条(例如，b样条)或其它参数化表示)。
在612处，基于处理器的系统可以执行针对规划栅格的多个边中的每个边重复的循环或迭代评估。
作为循环612的一部分，基于处理器的系统在614处执行定向边界框碰撞检测，以确定定向边界框所表示的主要车辆在一对状态之间转换时是否将与障碍物表示碰撞。状态由通过规划栅格的相应边连接的一对节点的相应节点表示。障碍物可以采取静态障碍物(例如，建筑物、道路标记、道路边缘，无论其被标记了还是未被标记)和/或动态障碍物(例如，其它车辆或其它动态障碍物)的形式。
例如，在形式为其它车辆的障碍物被表示为相应定向边界框的情况中，系统可以执行定向边界框-定向边界框碰撞检测，以确定表示主要车辆的相应定向边界框在由通过规划栅格的相应边连接的相应节点表示的一对状态之间转换时是否将与表示其它车辆中的至少一个车辆的相应定向边界框碰撞。
又例如，在形式为行人的障碍物被表示为定向边界框的情况中，系统可以执行定向边界框-定向边界框碰撞检测，以确定表示主要车辆的相应定向边界框在由通过规划栅格的相应边连接的相应节点表示的一对状态之间转换时，是否将与表示该至少一个行人的相应定向边界框碰撞。
又例如，在形式为道路标记、中央区、道路边缘(无论其被标记了还是未被标记)的障碍物被表示为曲线(例如，样条，b样条，多项式)的情况中，系统可以执行定向边界框-曲线碰撞检测，以确定表示主要车辆的相应定向边界框在由通过规划栅格的相应边连接的相应节点表示的一对状态之间转换时，是否将与表示道路标记、中央区、道路边缘的曲线碰撞。
如本文更详细地描述的，在一组拟合函数表示对应于规划栅格的相应边的主要车辆的相应轨迹的情况中，系统可以执行定向边界框碰撞检测。在至少一些实施方式中，系统可以经由多个不同的硬件电路来执行定向边界框碰撞检测。
在616处，基于处理器的系统设置规划栅格的相应边的代价，以反映检测到的碰撞或不存在碰撞中的至少一者。设置规划栅格的相应边的代价以反映检测到的碰撞或不存在碰撞中的至少一者可以包括：根据参数化代价函数来设置规划栅格的相应边中一个或更多个边的代价，以反映碰撞的检测和反映对应的碰撞的严重性。
在618处，基于处理器的系统确定是否已经满足结束条件，例如最后的边。例如，基于处理器的系统可以确定是否已经处理了每个边(例如，针对每个边表示的转换执行碰撞评估)，或是否已经发生了超时的情况。
在620处，基于处理器的系统执行规划栅格的最小代价分析。例如，基于处理器的系统可以采用基于逻辑地与每个边关联或分配给每个边的代价的多种最小代价算法中的任一种算法，找到由规划栅格中的节点表示的状态之间的最小代价或最佳路径。
在622处，基于处理器的系统至少部分地基于最小代价分析，通过主要车辆来执行所生成的运动规划。例如，基于处理器的系统可以将命令提供给主要车辆的驱动系统或传动装置，以使主要车辆基于最小代价路径在状态之间转换，例如将命令发送给一个或更多个马达控制器。
方法600可以在624处终止，例如直至被再次调用或激活。替代地，方法600可以重复或连续地执行，例如在主要车辆操作时。
图7是示出根据至少一个所示实施方式的在基于处理器的系统中操作的用于实施运动规划的方法700的流程图。
方法700可以作为执行方法600的一部分被执行，例如作为执行定向边界框检测614(图6)的一部分或通过实施运动规划622(图6)来执行其它类型的碰撞检测的一部分。
在702处，基于处理器的系统可以执行针对规划栅格的多个边中的每个边重复的循环或迭代评估。
作为循环702的一部分，在704处，基于处理器的系统将与相应边对应的轨迹表示为一组拟合函数，例如一组拟合多项式函数。
例如，基于处理器的系统可以在主要车辆的基于处理器的系统处从配置系统接收一组拟合函数(例如，拟合多项式函数)。配置系统可以相对于主要车辆远程定位。配置系统可能已经在主要车辆不处于运动状态时，在运行前的配置期间，对该组拟合函数进行了有利的拟合，因此不存在对该组拟合函数的开发的实时限制。函数可以拟合由运动方程限定的轨迹。拟合函数可以省去任何三角函数，从而实现计算方面高效的碰撞评估。较不有利的是，主要车辆的基于处理器的系统可以创建或生成一组拟合多项式函数。
作为循环702的一部分，在706处，基于处理器的系统使用该组拟合函数来执行碰撞检测，以确定主要车辆的表示是否与其它车辆或其它障碍物的一个或更多个表示碰撞。
系统可以例如使用一对拟合多项式函数来对环境的二维表示中的行驶(例如，在真实的三维世界中行驶在常规街道和高速公路上的车辆)执行碰撞检测，这对拟合多项式函数中的一个拟合多项式函数表示相对于时间的第一维度中的位置，这对拟合多项式函数中的另一拟合多项式函数表示相对于时间的第二维度中的位置，第二维度不同于第一维度。系统可以例如使用一对拟合时间参数函数来执行碰撞检测，以确定主要车辆是否与其它车辆或其它障碍物碰撞。系统可以例如使用一对拟合时间参数五次函数来执行碰撞检测，以确定主要车辆是否与其它车辆或其它障碍物碰撞。系统可以例如使用由主要车辆的原始设备制造商提供的专用于主要车辆的品牌和型号的一对拟合函数来执行碰撞检测。系统可以例如使用具有由主要车辆的原始设备制造商提供的专用于主要车辆的品牌和型号的参数的一对拟合多项式函数来执行碰撞检测。系统可以例如通过使用一对拟合函数来表示主要车辆的对应于规划栅格的相应边的相应轨迹来表示主要车辆的相应轨迹，来执行碰撞检测。系统可以例如经由多个不同的硬件电路来执行碰撞检测。
在708处，基于处理器的系统设置规划栅格的相应边的代价，以反映当在由通过规划栅格的相应边连接的相应节点表示的一对状态之间转换时所确定的碰撞或不存在碰撞中的至少一者。系统可以例如根据参数化代价函数来设置规划栅格的相应边中一个或更多个边的代价，以反映碰撞的检测和反映所检测的碰撞的严重性。
在710处，基于处理器的系统执行规划栅格的最小代价分析。例如，基于处理器的系统可以基于逻辑地与每个边关联或分配给每个边的代价，采用多种最小代价算法中的任一种，寻找由规划栅格中的节点表示的状态之间的最小代价或最佳路径。
在712处，基于处理器的系统至少部分地基于最小代价分析，通过主要车辆来实施所生成的运动规划。例如，基于处理器的系统可以将命令提供给主要车辆的驱动系统或传动装置，以使主要车辆基于最小代价路径在状态之间转换，例如将命令发送到一个或更多个运动控制器，以控制一个或更多个电动马达(例如，牵引马达)。
图8是示出根据至少一个所示实施方式的在基于处理器的系统中操作的用于实施运动规划的方法800的流程图。
方法800可以作为执行方法600、700的一部分来执行，例如作为使用拟合多项式执行碰撞检测702的一部分。方法800可以在运行期间执行，例如在主要车辆操作期间。
在802处，基于处理器的系统执行循环，针对规划栅格的多个边中的每个边进行重复，或直至达到某个其它结束条件(例如，超出最大时间量或最大迭代数量)。
在804处，基于处理器的系统确定拟合到由相应边表示的轨迹表示的运动的一组拟合多项式函数。本领域普通技术人员应认识到，可以以多项式以外的形式来表示轨迹，尤其是在处理这些表示的计算强度不高的情况下。常规情况下，可以经由运动方程表示状态或运动之间的转换。在至少该实施方式中，基于处理器系统有利地将运动或转换表示为拟合多项式函数，从而增强了位于主要车辆上并执行针对主要车辆的实时运动规划的“搭载”的基于处理器的系统的计算性能。
例如，为了确定该组拟合多项式函数，基于处理器的系统可以将一组多项式拟合到由轨迹表示的运动，轨迹的形式为或遵循表示主要车辆运动的相应运动方程组。例如，基于处理器的系统可以确定一对多项式函数，该对多项式函数中的一个多项式函数表示相对于时间的第一维度中的沿轨迹的位置，该对多项式函数中的另一个多项式函数表示相对于时间的第二维度中的沿轨迹的位置，第二维度不同于第一维度。此外，例如，基于处理器的系统可以确定表示轨迹的一对时间参数函数。例如，基于处理器的系统可以确定表示轨迹的一对时间参数五次函数。此外，例如，基于处理器的系统可以确定由主要车辆的原始设备制造商指定的专用于主要车辆的品牌和型号的一对多项式函数。此外，例如，在主要车辆是自主车辆的情况中，基于处理器的系统还可以向主要车辆的基于处理器的控制系统，提供所确定的具有专用于主要车辆的品牌和型号的参数的一对多项式函数。
在某些实施方式中，主行为者或车辆102和一个或更多个动态障碍物(例如，其它车辆)可以具有相互依赖的轨迹。一个或更多个障碍物的轨迹可以概率建模(例如，XA和XB)。例如，一个或更多个障碍物可以对主要车辆102和环境中的所有动态障碍物两者(包括彼此)的移动做出反应，例如试图避免碰撞或甚至试图碰撞。相应地，开发每个行为者的行为模型，其将车辆或行为者的意图作为建模潜在原则或目标，而不是简单的轨迹。潜在原则或目标为能够被采样的形式，以确定车辆或行为者会如何对其它车辆或行为者的其它轨迹做出反应。当主要车辆或行为者102在当前时间T处于节点n时，基于处理器的系统寻求确定其它车辆或行为者在未来将处于何处。其它车辆或行为者的原则首先基于主要车辆或行为者从起始节点到节点n的路径，并考虑到次要车辆或行为者对主要车辆或行为者的动作以及所有次要车辆或行为者的动作的概率反应，向前模拟直至当前时间T。由此，给定次要车辆或行为者的概率函数表示主要车辆或行为者和次要车辆或行为者的直到当前时间的至少一些动作。这产生指示其它车辆或行为者在当前时间T所占据的空间的结果。这是因为另一车辆或行为者在当前时间T的位置取决于所有其它车辆或行为者和主要车辆或行为者102直至当前时间T所遵循的轨迹。
在806处，基于处理器的系统可以提供用于运动规划的一组拟合函数。例如，在一些实施方式中，例如由OEM实施的配置系统的基于处理器的系统可以将一组拟合函数提供给主要车辆的基于处理器的系统。例如，位于固定位置处的服务器(可能远离主要车辆)可以将一组拟合函数提供给构成主要车辆一部分并与其一起移动的基于处理器的系统。这可以无线或有线地或经由光纤来提供。
图9是示出根据至少一个所示执行方式的在基于处理器的系统中操作的用于实施运动规划的方法900的流程图。
方法900可以例如作为执行方法600(图6)、700(图7)和800(图8)的任一部分来执行。
在902处，基于处理器的系统执行碰撞检测，以确定主要车辆的表示是否将在一对状态之间转换时与障碍物的表示碰撞。相应状态由通过规划栅格的相应边连接的一对节点的相应节点表示。执行碰撞检测可以包括经由多个不同的硬件电路(多个边中的每个边一个硬件电路)，或经由本文所述的方法或通过引用并入本文的参考文献中所述的方法来执行碰撞检测。
在904处，基于处理器的系统至少部分地基于以下各项来设置与规划栅格的相应边关联的代价：i)碰撞检测，和ii)表示与特定碰撞关联的碰撞严重性或排序的参数化代价函数。特别地，参数化代价函数可以表示与至少两个或更多个参数相关联的值，例如障碍物类型、碰撞类型和车辆速度，或耗散的能量，以及每个类型的参数的相对加权。
障碍物类型可以表示或指示可能与之发生碰撞的障碍物的类型。碰撞类型可以表示或指示可能发生的碰撞的类型。车辆速度可以表示或指示在即将发生预测的碰撞之前(即在碰撞力开始使车辆或障碍物减慢之前)的至少主要车辆的速度。将耗散的能量是由于预测的碰撞而耗散的能量的估计，它可以是速度的函数。参数化代价函数可以表示基于车辆速度的碰撞严重性水平。由此，设置与相应边关联的代价可以有利地包括至少部分地基于严重性水平来设置代价，该严重性水平基于主要车辆和障碍物中的至少一个或两者的车辆速度。
障碍物类型可以指示障碍物是有生命的障碍物还是无生命的障碍物。设置与相应边关联的代价包括至少部分地基于障碍物是有生命的障碍物还是无生命的障碍物来设置代价。
碰撞类型可以指示碰撞是与将导致物理障碍物(例如，另一车辆、行人)或主要车辆的损坏的物理障碍物的碰撞，还是与不会或可能不会导致障碍物(例如，道路标记或礼貌框或其它逻辑间距概念)损坏的障碍物的碰撞其它。碰撞类型可以附加地或替代地表示车辆将被撞击的部分(例如，正面碰撞、尾部碰撞)或撞击的方向或角度。设置与相应边关联的代价包括至少部分基于碰撞是与将导致物理障碍物或主要车辆损坏的物理障碍物的碰撞，还是与不会或很可能不会导致障碍物或主要车辆损坏的非物理结构或物理对象的碰撞来设置代价。
车辆速度可以表示或指示主要车辆的速度或速率。速度可以在现实世界(例如，二维或三维现实世界参考系)中表示。设置与相应边关联的代价包括至少部分地基于主要车辆在现实世界参考系中的速度来设置代价。车辆速度可以表示或指示主要车辆相对于障碍物的速度的速度或速率。设置与相应边关联的代价可以包括至少部分地基于主要车辆相对于障碍物的速度的速度来设置代价。车辆速度可以表示或指示主要车辆的速度障碍物的速度两者。设置与相应边关联的代价可以包括至少部分地基于主要车辆的速度和障碍物的速度两者来设置代价。耗散的能量可以表示或指示将作为碰撞的一部分耗散的能量的估计的量，并通常是速度的函数。
设置代价可以包括分配或调整与栅格中的边中的每个边相关联的代价值。代价值可以作为栅格的一部分，或作为数据结构(例如，与栅格相关联的数据结构或实现该栅格的数据结构)的一部分来存储。
如上文参考图5所述，栅格中的每个节点(例如，n0、n1、n2)具有基于与该节点和主行为者102的目的地(例如，最终状态)之间的栅格的边(例如，c0,4、c0,5等)相关联的代价的关联值(即，代价)。与栅格的边相关联的代价尤其基于碰撞概率、表示碰撞严重性的参数函数和可选地与沿着所涉及的边的两个节点之间的移动相关联的固有代价(例如，燃料和/或能量代价)来确定。在实施方式中，基于从所涉及的节点到目标节点(例如，n15)的最小代价路径，来为每个节点确定到目的地的代价。基于处理器的系统确定在主行为者的环境100中的其它行为者Aj的轨迹t。对于当前节点n，即主行为者在运动规划栅格500中的当前位置，基于处理器的系统计算每个候选节点n’在轨迹集合S上的平均代价。主行为者102在运动规划栅格500中的状态(例如，姿态)从节点n移动到具有最小平均代价的候选节点n’。递增时间步长，在下一个时间步长重复该方法。
可能有用的是，计算已知轨迹集合上每个候选节点的平均代价。为此，发起循环，以针对t＝1至m，考虑轨迹集合S中的每个轨迹t，其中m是轨迹数量。基于处理器的系统确定运动规划栅格500的哪些边(如果有的话)与轨迹t碰撞。基于处理器的系统对被确定为与轨迹t碰撞的边(如果有的话)的值应用代价函数。基于处理器的系统基于从节点n经过相应候选节点n’到达目的地的最小代价路径来确定每个候选节点n’的代价。递增标识轨迹的指数t，并重复该方法直至所有轨迹被处理。
在一些实施方式中，一个或更多个基于处理器的系统可以执行经由规划栅格来识别主行为者102的路径的方法，路径经过具有最小平均代价的候选节点，该最小平均代价考虑了主行为者102到目的地的规划路径和其它行为者(例如，其它自主车辆、其它车辆、人、动物)的概率确定路径。基于处理器的系统可以执行静态背景碰撞检测。基于处理器的系统可以计算运动规划栅格的每个节点到目的地的代价。可以将行为者的行为模型提供给基于处理器的系统作为输入，例如在配置时(即，在运行之前)。在运行时，基于处理器的系统可以采样概率模型。概率模型可以为每个行为者Aj提供下一步Xj，或产生轨迹集合。基于处理器的系统可以基于从当前节点n到目的地的主行为者102的规划路径和其它行为者的概率确定路径来计算每个候选节点n’的值。主行为者102从其当前节点n移动到具有最小值(即代价)的候选节点n’。在下一个时间步长T＝T+1可以重复该方法。
基于处理器的系统可以执行基于主行为者102到目的地的规划路径和其它行为者的概率确定路径来计算每个候选节点的值的方法。例如，基于处理器的系统可以基于基于轨迹集合的其它行为者Aj的采样的下一步Xj来确定每个候选节点n’的值。然后，基于处理器的系统可以基于在时间T+1时从当前节点n到具有最小值的候选节点n’的移动来指定主行为者102的下一规划位置。如果主行为者102还没有处于目标节点，则递增时间，并在下一个时间步长重复该方法。
基于处理器的系统可以执行基于来自基于概率模型集合S的其它行为者Aj的采样的下一步Xj的边碰撞代价来确定每个候选节点n’在下一个时间步长T+1处的值的方法。例如，基于处理器的系统可以基于每个行为者的采样数，发起迭代循环。基于处理器的系统可以基于其它行为者的数量，发起迭代循环。基于处理器的系统可以基于模型集合S确定行为者Aj的概率下一步Xj的第k个样本。然后，基于处理器的系统确定运动规划栅格的哪些边(如果有的话)与所确定的在时间T+1处的行为者Aj的概率下一步Xj碰撞。然后，基于处理器的系统对被确定为与在时间T+1处的行为者Aj的概率下一步Xj碰撞的边(如果有的话)的值应用代价函数。对于其它行为者，重复迭代循环，直至所有其它行为者已经被处理。在完成了k次针对其它行为者的迭代循环之后，重复对样本的迭代循环，直至完成所有样本，即p次。
如上文所解释的，在实施方式中，行为者Aj的概率行为模型是相互依赖的，这是因为每个行为者Aj的轨迹取决于所有其它行为者和主行为者的轨迹。因此，将所有行为者Aj和主行为者的当前和过去位置，作为输入提供给概率行为模型，以确定行为者Aj中每个行为者的预测的下一步Xj。由此，通常会存在对于窗口或历史或回溯的某些限制。相应地，该方法的最内部的循环是用于确定在重复采样之前的所有行为者Aj的预测的下一步Xj的循环。由此，基于所有行为者Aj和主行为者的相同当前位置，执行所有样本。
前述详细说明通过使用框图、示意图和示例，阐述了设备和/或方法的各个实施方式。就这样的框图、示意图和示例包含一个或更多个功能和/或操作而言，本领域技术人员应理解，可以通过各种硬件、软件、固件，或它们的几乎任何组合，单独地和/或共同地实施这类框图、流程图或示例中的每个功能和/或操作。在一个实施方式中，本主题可以通过专用集成电路(ASIC)和/或FPGA来实施。然而，本领域技术人员应认识到，可以在标准集成电路的各个不同实施方式中，将本文公开的实施例整体或部分地实施为在一个或更多个计算机上运行的一个或更多个计算机程序(例如，作为在一个或更多个计算机系统上运行的一个或更多个程序)，实施为在一个或更多个控制器(例如，微控制器)上运行的一个或更多个程序，实施为在一个或更多个处理器(例如，微处理器)上运行的一个或更多个程序，实施为固件，或实施为它们的几乎任何组合，以及根据本公开，设计电路和/或为软件和/或固件编写代码都将在本领域普通技术人员的技能范围内。
本领域的技术人员应认识到，本文所述的方法或算法中许多可以采用附加的动作，可以省略某些动作，和/或可以以与指定的顺序不同的顺序执行动作。
此外，本领域的技术人员应认识到，本文所教导的机制能够作为程序产品以各种形式分发，并且示意性实施例同等地适用，而无论用于实际执行分发的信号承载介质的特定类型如何。信号承载介质的示例包括但不限于以下：可记录类型的介质，例如硬盘驱动器、CD ROM和计算机存储器。
可以组合上述各种实施例以提供进一步的实施例。本说明书中提及和/或申请数据表中列出的所有美国专利申请公开、美国专利申请、外国专利和外国专利申请，包括但不限于于2018年1月12日提交的题为《在具有动态对象的环境中促进自主车辆的运动规划的装置、方法和物品(APPARATUS,METHOD,AND ARTICLE TO FACILITTE MOTION PLANNING OFAN AUTONOMOUS VEHICLE IN AN ENVIRONMENT HAVING DYNAMIC OBJECTS)》的美国专利申请No.62/616,783；2017年6月9日提交的题为《自主驾驶车辆的运动规划和可重构运动规划处理器》的国际专利申请No.PCT/US2017/036880；2016年1月5日提交的题为《专用机器人运动规划硬件及制造和使用方法》的国际专利申请公布No.WO 2016/122840；于2018年8月23日提交的题为《在机器人运动规划中有效的碰撞检测》的美国专利申请No.62/722,067；2018年12月4日提交的题为《在具有动态对象的环境中促进运动规划的装置、方法和物品(APPARATUS,METHOD AND ARTICLE TO FACILITAE MOTION PLANNING IN AN ENVIRONMENTHAVING DYNAMIC OBJECTS)》的美国专利申请No.62/775,257；2019年4月17日提交的题为《运动规划图形生成用户界面、系统、方法和物品(MOTION PLANNING GRAPH GENERATIONUSER INTERFACE,SYSTEMS,METHODS AND ARTICLES)》的美国专利申请No.62/835,139；以及2019年6月3日提交的题为《在具有动态障碍物的环境中促进运动规划的装置、方法和物品(APPARATUS,METHODS AND ARTICLES TO FACILITATE MOTION PLANNING IN ENVIRONMENTSHAVING DYNAMIC OBSTACLES)》的美国专利申请No.62/856,548，其通过引用整体并入本文。根据以上详细描述，可以对实施例进行这些和其它改变。一般而言，在以下权利要求中，所使用的术语不应被解释为将权利要求限制在说明书和权利要求中公开的具体实施例，而应被解释为包括所有可能的实施例以及使这些权利要求享有权利的等同物的全部范围。因此，权利要求不受本公开的限制。

Claims (64)

1.一种在基于处理器的系统中操作的用于经由规划栅格来执行运动规划的运动规划方法，其中，每个规划栅格分别包括多个节点和边，每个节点表示在包括一个或更多个其它车辆和其它障碍物的环境中操作的主要车辆的状态，每个边表示在相应的一对节点之间的转换，所述方法包括：
通过基于处理器的系统将所述主要车辆表示为相应的定向边界框；
通过基于处理器的系统将至少一个其它障碍物表示为以样条或多项式形式的曲线表示，以及
针对所述规划栅格的多个边中的至少一个边，
通过基于处理器的系统执行定向边界框碰撞检测，以确定由所述定向边界框表示的所述主要车辆在一对状态之间转换时是否将与其它车辆或其它障碍物的表示碰撞，所述一对状态由通过所述规划栅格的相应边连接的一对节点的相应节点表示，其中，执行定向边界框碰撞检测，以确定由相应的定向边界框表示的所述主要车辆是否与其它车辆或其它障碍物碰撞包括：执行定向边界框-曲线碰撞检测，以确定表示所述主要车辆的相应的定向边界框在由通过所述规划栅格的相应边连接的相应节点表示的一对状态之间转换时是否将与表示所述其它障碍物中的至少一个障碍物的曲线碰撞；以及
通过基于处理器的系统设置规划栅格的相应边的代价，以反映检测到的碰撞或不存在碰撞中的至少一者。
2.根据权利要求1所述的运动规划方法，其中，将至少一个其它障碍物表示为曲线表示包括：将道路的中心线、道路的边缘，或道路的至少一个车道标记中的至少一个表示为样条表示。
3.根据权利要求1至2中任一项所述的运动规划方法，其中，执行定向边界框碰撞检测包括：使用一组拟合函数表示与所述规划栅格的相应边对应的所述主要车辆的相应轨迹，来在沿着所述主要车辆的相应轨迹的至少一个点中的每个点处执行定向边界框碰撞检测。
4.根据权利要求1至2中任一项所述的运动规划方法，其中，执行定向边界框碰撞检测包括：经由多个不同的硬件电路执行定向边界框碰撞检测。
5.根据权利要求1至2中任一项所述的运动规划方法，其中，设置规划栅格的相应边的代价以反映检测到的碰撞或不存在碰撞中的至少一者包括：根据参数化代价函数设置规划栅格的相应边中的一个或更多个边的代价，以反映碰撞的检测以及反映表示检测到的碰撞的严重性的至少一个参数。
6.根据权利要求1至2中任一项所述的运动规划方法，还包括：
通过基于处理器的系统执行所述规划栅格的最小代价分析；以及
通过基于处理器的系统至少部分地基于所述最小代价分析，通过所述主要车辆来实施所生成的运动规划。
7.根据权利要求1至2中任一项所述的运动规划方法，其中，所述样条为b样条。
8.一种用于经由规划栅格执行运动规划的基于处理器的系统，其中，每个规划栅格分别包括多个节点和边，每个节点表示在包括一个或更多个其它车辆和其它障碍物的环境中操作的主要车辆的状态，每个边表示在相应的一对节点之间的转换，所述基于处理器的系统包括：
至少一个处理器；
至少一个非暂时性处理器可读介质，其通信地耦接到所述至少一个处理器并存储处理器可执行指令，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器配置为：
将所述主要车辆表示为相应的定向边界框；
将至少一个其它障碍物表示为以样条或多项式形式的曲线表示，以及
针对所述规划栅格的多个边中的至少一个边，
执行定向边界框碰撞检测，以确定由所述定向边界框表示的所述主要车辆在一对状态之间转换时是否将与其它车辆或其它障碍物的表示碰撞，所述一对状态由通过所述规划栅格的相应边连接的一对节点的相应节点表示，其中，为了执行定向边界框碰撞检测，所述处理器可执行指令使所述至少一个处理器执行定向边界框-曲线碰撞检测，以确定表示所述主要车辆的相应的定向边界框在由通过所述规划栅格的相应边连接的相应节点表示的一对状态之间转换时是否将与表示所述其它障碍物中的至少一个障碍物的曲线碰撞；以及
设置规划栅格的相应边的代价，以反映检测到的碰撞或不存在碰撞中的至少一者。
9.根据权利要求8所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器还配置为：
将至少一个其它障碍物表示为曲线表示包括：将道路的中心线、道路的边缘，或道路的至少一个车道标记中的至少一个表示为样条表示。
10.根据权利要求8所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器经由一组拟合函数表示与所述规划栅格的相应边对应的所述主要车辆的相应轨迹，来在沿着所述主要车辆的相应轨迹的至少一个点中的每个点处执行定向边界框碰撞检测。
11.根据权利要求8所述的基于处理器的系统，其中，执行定向边界框碰撞检测包括经由多个不同的硬件电路执行定向边界框碰撞检测。
12.根据权利要求8所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器基于参数化代价函数设置规划栅格的相应边的代价，以反映碰撞的检测以及反映检测到的碰撞的严重性。
13.根据权利要求8至12中任一项所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器还配置为：
执行所述规划栅格的最小代价分析；以及
至少部分地基于所述最小代价分析，通过所述主要车辆来实施所生成的运动规划。
14.根据权利要求8至12中任一项所述的基于处理器的系统，其中，所述样条为b样条。
15.一种在基于处理器的系统中操作的用于经由规划栅格来执行运动规划的运动规划方法，其中，每个规划栅格分别包括多个节点和边，每个节点表征在包括一个或更多个其它车辆和其它障碍物的环境中操作的主要车辆的状态，每个边表示由相应的一对节点表示的状态之间的主要车辆的轨迹，所述方法包括：
在运行期间，针对规划栅格的多个边中的每个边，
通过基于处理器的系统将与相应边对应的轨迹表示为一组拟合函数，
通过基于处理器的系统使用所述一组拟合函数执行碰撞检测，以确定所述主要车辆的表示是否与其它车辆或其它障碍物的一个或更多个表示碰撞；以及
通过基于处理器的系统设置所述规划栅格的相应边的代价，以反映在由通过所述规划栅格的相应边连接的相应节点表示的一对状态之间转换时所确定的碰撞或不存在碰撞中的至少一者。
16.根据权利要求15所述的运动规划方法，还包括：
通过基于处理器的系统，在所述主要车辆的基于处理器的系统处，从远离所述主要车辆定位的配置系统接收一组拟合函数，所述一组拟合函数是由所述配置系统在运行之前拟合的。
17.根据权利要求15所述的运动规划方法，其中，使用所述一组拟合函数执行碰撞检测，以确定所述主要车辆是否与其它车辆或其它障碍物碰撞包括：使用一对拟合多项式函数来执行碰撞检测，所述一对拟合多项式函数中的一个拟合多项式函数表示相对于时间的第一维度中的位置，所述一对拟合多项式函数中的另一拟合多项式函数表示相对于时间的第二维度中的位置，所述第二维度不同于所述第一维度。
18.根据权利要求15所述的运动规划方法，其中，使用所述一组拟合函数执行碰撞检测，以确定所述主要车辆是否与其它车辆或其它障碍物碰撞包括：使用一对拟合时间参数函数来执行碰撞检测，以确定所述主要车辆是否与其它车辆或其它障碍物碰撞。
19.根据权利要求15所述的运动规划方法，其中，使用所述一组拟合函数执行碰撞检测，以确定所述主要车辆是否与其它车辆或其它障碍物碰撞包括：使用一对拟合时间参数五次函数来执行碰撞检测，以确定所述主要车辆是否与其它车辆或其它障碍物碰撞。
20.根据权利要求15所述的运动规划方法，其中，使用所述一组拟合函数执行碰撞检测，以确定所述主要车辆是否与其它车辆或其它障碍物碰撞包括：使用由所述主要车辆的原始设备制造商提供的专用于所述主要车辆的品牌和型号的一对拟合函数来执行碰撞检测。
21.根据权利要求15所述的运动规划方法，其中，使用所述一组拟合函数执行碰撞检测，以确定所述主要车辆是否与其它车辆或其它障碍物碰撞包括：使用具有专用于所述主要车辆的品牌和型号的且由所述主要车辆的原始设备制造商提供的参数的一对拟合多项式函数来执行碰撞检测。
22.根据权利要求15至21中任一项所述的运动规划方法，其中，使用所述一组拟合函数执行碰撞检测，以确定所述主要车辆是否与其它车辆或其它障碍物碰撞包括：在沿着所述主要车辆的相应轨迹的一个或更多个点处执行碰撞检测，其中，所述相应轨迹经由所述一组拟合函数指定以表示与所述规划栅格的相应边对应的所述主要车辆的相应轨迹。
23.根据权利要求15至21中任一项所述的运动规划方法，其中，使用所述一组拟合函数执行碰撞检测，以确定所述主要车辆是否与其它车辆或其它障碍物碰撞包括：经由多个不同的硬件电路来执行碰撞检测。
24.根据权利要求15至21中任一项所述的运动规划方法，其中，设置规划栅格的相应边的代价，以反映检测到的碰撞或不存在碰撞中的至少一者包括：根据参数化代价函数设置规划栅格的相应边中的一个或更多个边的代价，以反映碰撞的检测以及反映检测到的碰撞的严重性。
25.根据权利要求15至21中任一项所述的运动规划方法，还包括：
通过基于处理器的系统执行所述规划栅格的最小代价分析；以及
通过基于处理器的系统至少部分地基于所述最小代价分析，通过所述主要车辆来实施所生成的运动规划。
26.根据权利要求15至21中任一项所述的运动规划方法，还包括：
在发生于运行之前的离线配置期间，针对多个边中的每个边，将相应的一组多项式函数拟合到由该边表示的轨迹所表示的运动。
27.一种用于经由规划栅格来执行运动规划的基于处理器的系统，其中，每个规划栅格分别包括多个节点和边，每个节点表征在包括一个或更多个其它车辆和其它障碍物的环境中操作的主要车辆的状态，每个边表示由相应的一对节点表示的状态之间的主要车辆的轨迹，所述基于处理器的系统包括：
至少一个处理器；
至少一个非暂时性处理器可读介质，其通信地耦接到所述至少一个处理器并存储处理器可执行指令，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器配置为：
在运行期间，针对规划栅格的多个边中的每个边，
将与相应边对应的轨迹表示为一组拟合函数，
使用所述一组拟合函数执行碰撞检测，以确定所述主要车辆的表示是否与其它车辆或其它障碍物的一个或更多个表示碰撞；以及
设置所述规划栅格的相应边的代价，以反映在由通过所述规划栅格的相应边连接的相应节点表示的一对状态之间转换时所确定的碰撞或不存在碰撞中的至少一者。
28.根据权利要求27所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器还配置为：
在所述主要车辆的基于处理器的系统处，从远离所述主要车辆定位的配置系统接收一组拟合函数，所述一组拟合函数是由所述配置系统在运行之前拟合的。
29.根据权利要求27所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器利用一对拟合多项式函数来执行碰撞检测，所述一对拟合多项式函数中的一个拟合多项式函数表示相对于时间的第一维度中的位置，所述一对拟合多项式函数中的另一拟合多项式函数表示相对于时间的第二维度中的位置，所述第二维度不同于所述第一维度。
30.根据权利要求27所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器利用一对拟合时间参数函数来执行碰撞检测，以确定所述主要车辆是否与其它车辆或其它障碍物碰撞。
31.根据权利要求27所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器利用一对拟合时间参数五次函数来执行碰撞检测，以确定所述主要车辆是否与其它车辆或其它障碍物碰撞。
32.根据权利要求27所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器利用由所述主要车辆的原始设备制造商提供的专用于所述主要车辆的品牌和型号的一对拟合函数来执行碰撞检测。
33.根据权利要求27所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器利用具有专用于所述主要车辆的品牌和型号的且由所述主要车辆的原始设备制造商提供的参数的一对拟合多项式函数来执行碰撞检测。
34.根据权利要求27至33中任一项所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器在沿着所述主要车辆的相应轨迹的一个或更多个点处执行碰撞检测，其中，所述相应轨迹经由所述一组拟合函数指定以表示与所述规划栅格的相应边对应的所述主要车辆的相应轨迹。
35.根据权利要求27至33中任一项所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器经由多个不同的硬件电路来执行碰撞检测。
36.根据权利要求27至33中任一项所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器经由参数化代价函数设置规划栅格的相应边的代价，以反映检测到的碰撞或不存在碰撞中的至少一者，以反映碰撞的检测以及反映检测到的碰撞的严重性。
37.根据权利要求27至33中任一项所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器还配置为：
执行所述规划栅格的最小代价分析；以及
至少部分地基于所述最小代价分析，通过所述主要车辆来实施所生成的运动规划。
38.根据权利要求27至33中任一项所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器还配置为：
在发生于运行之前的离线配置期间，针对多个边中的每个边，将相应的一组函数拟合到由该边表示的轨迹所表示的运动。
39.一种在基于处理器的系统中操作的用于经由规划栅格来执行运动规划的运动规划方法，其中，每个规划栅格分别包括多个节点和边，每个节点表征主要车辆的状态，其中，所述主要车辆在包括一个或更多个其它车辆和其它障碍物的环境中操作，每个边表示由相应的一对节点表示的状态之间的主要车辆的轨迹，所述方法包括：
在发生于运行之前的离线配置期间，
针对规划栅格的多个边中的每个边，确定拟合到由该边表示的轨迹所表示的运动的一组拟合函数；以及
提供所述一组拟合函数以用于由主要车辆的基于处理器的系统进行的运动规划，以及
在发生于离线配置之后的运行期间，
将至少一个其它障碍物表示为以样条或多项式形式的曲线表示，以及
针对所述规划栅格的多个边中的至少一个边，
执行定向边界框碰撞检测，以确定由所述定向边界框表示的所述主要车辆在一对状态之间转换时是否将与其它车辆或其它障碍物的表示碰撞，所述一对状态由通过所述规划栅格的相应边连接的一对节点的相应节点表示，其中，执行定向边界框碰撞检测包括：使用一组拟合函数表示与所述规划栅格的相应边对应的所述主要车辆的相应轨迹，来在沿着所述主要车辆的相应轨迹的至少一个点中的每个点处
执行定向边界框碰撞检测；以及
通过基于处理器的系统设置规划栅格的相应边的代价，以反映检测到的碰撞或不存在碰撞中的至少一者。
40.根据权利要求39所述的运动规划方法，其中，所述样条为b样条。
41.根据权利要求39所述的运动规划方法，其中，确定拟合到由该边表示的轨迹所表示的运动的一组拟合函数包括：将所述一组拟合函数拟合到由所述轨迹表示的运动。
42.根据权利要求39所述的运动规划方法，其中，确定拟合到由该边表示的轨迹所表示的运动的一组拟合函数包括：确定一对拟合多项式函数，所述一对拟合多项式函数中的一个拟合多项式函数表示相对于时间的第一维度中的沿着所述轨迹的位置，所述一对拟合多项式函数中的另一拟合多项式函数表示相对于时间的第二维度中的沿着所述轨迹的位置，所述第二维度不同于所述第一维度。
43.根据权利要求39所述的运动规划方法，其中，确定拟合到由该边表示的轨迹所表示的运动的一组拟合函数包括：确定表示所述轨迹的一对拟合时间参数函数。
44.根据权利要求39所述的运动规划方法，其中，确定拟合到由该边表示的轨迹所表示的运动的一组拟合函数包括：确定表示所述轨迹的一对拟合时间参数五次函数。
45.根据权利要求39所述的运动规划方法，其中，确定拟合到由该边表示的轨迹所表示的运动的一组拟合函数包括：确定由所述主要车辆的原始设备制造商指定的专用于所述主要车辆的品牌和型号的一对拟合函数。
46.根据权利要求39所述的运动规划方法，其中，确定拟合到由该边表示的轨迹所表示的运动的一组拟合函数包括：确定具有通过所述主要车辆的原始设备制造商的专用于所述主要车辆的品牌和型号的参数的一对拟合多项式函数，以及将所确定的具有专用于所述主要车辆的品牌和型号的参数的一对拟合多项式函数提供给所述主要车辆的基于处理器的控制系统，其中，所述主要车辆是自主车辆。
47.一种在基于处理器的系统中操作的用于经由规划栅格来执行运动规划的运动规划方法，其中，每个规划栅格分别包括多个节点和边，每个节点表征在包括一个或更多个障碍物的环境中操作的主要车辆的状态，每个边表示一对相应节点之间的转换，所述方法包括：
针对所述规划栅格的多个边中的至少一个边中的每个边，
通过基于处理器的系统执行碰撞检测，以确定所述主要车辆的表示在一对状态之间转换时是否将与所述障碍物的表示碰撞，所述一对状态由通过所述规划栅格的相应边连接的一对节点的相应节点表示；以及
通过基于处理器的系统，至少部分地基于以下项来设置与所述规划栅格的相应边关联的代价：i)所述碰撞检测，和ii)表示以下项中的至少两项或更多项的参数化代价函数：障碍物类型、碰撞类型、车辆速度，或对将在碰撞期间耗散的耗散能量的至少估计，所述障碍物类型表示可能与之发生碰撞的障碍物的类型，所述碰撞类型表示可能发生的碰撞的类型，所述车辆速度表示在即将发生预测的碰撞之前至少主要车辆的速度。
48.根据权利要求47所述的运动规划方法，其中，所述障碍物类型表示所述障碍物是有生命的障碍物还是无生命的障碍物，并且设置与所述相应边关联的代价包括：至少部分地基于所述障碍物是有生命的障碍物还是无生命的障碍物来设置所述代价。
49.根据权利要求47所述的运动规划方法，其中，所述碰撞类型表示所述碰撞是与将对物理障碍物或主要车辆造成损害的物理障碍物的碰撞，还是与不直接对主要车辆造成损害的间距要求或道路标记的碰撞，并且设置与所述相应边关联的代价包括：至少部分地基于碰撞是与将对物理障碍物或主要车辆造成损害的物理障碍物的碰撞还是与不对道路标记造成损害的道路标记的碰撞来设置所述代价。
50.根据权利要求47所述的运动规划方法，其中，所述车辆速度表示所述主要车辆在现实世界参考系中的速度，并且设置与所述相应边关联的代价包括：至少部分地基于所述主要车辆在所述现实世界参考系中的速度来设置所述代价。
51.根据权利要求47所述的运动规划方法，其中，所述车辆速度表示所述主要车辆相对于所述障碍物的速度的速度，并且设置与所述相应边关联的代价包括：至少部分地基于所述主要车辆相对于所述障碍物的速度的速度来设置所述代价。
52.根据权利要求47所述的运动规划方法，其中，所述车辆速度表示所述主要车辆的速度和所述障碍物的速度两者，并且设置与所述相应边关联的代价包括：至少部分地基于所述主要车辆的速度和所述障碍物的速度两者来设置所述代价。
53.根据权利要求47所述的运动规划方法，其中，所述参数化代价函数还表示基于车辆速度的碰撞的严重性水平，并且设置与所述相应边关联的代价包括：至少部分地基于根据所述主要车辆和所述障碍物中至少一个或两者的车辆速度的严重性水平来设置所述代价。
54.根据权利要求47至53中任一项所述的运动规划方法，其中，执行碰撞检测包括经由多个不同的硬件电路来执行所述碰撞检测。
55.根据权利要求47至53中任一项所述的运动规划方法，还包括：
通过基于处理器的系统执行所述规划栅格的最小代价分析；以及
通过基于处理器的系统至少部分地基于所述最小代价分析，通过所述主要车辆来实施所生成的运动规划。
56.一种用于经由规划栅格来执行运动规划的基于处理器的系统，其中，每个规划栅格分别包括多个节点和边，每个节点表征在包括一个或更多个障碍物的环境中操作的主要车辆的状态，每个边表示相应的一对节点之间的转换，所述基于处理器的系统包括：
至少一个处理器；
至少一个非暂时性处理器可读介质，其通信地耦接到所述至少一个处理器并存储处理器可执行指令，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器配置为：
针对所述规划栅格的多个边中的每个边，
执行碰撞检测，以确定所述主要车辆的表示在一对状态之间转换时是否将与所述障碍物的表示碰撞，所述一对状态由通过所述规划栅格的相应边连接的一对节点的相应节点表示；以及
至少部分地基于以下项来设置与所述规划栅格的相应边关联的代价：i)所述碰撞检测，和ii)表示以下项中的至少两项或更多项的参数化代价函数：障碍物类型、碰撞类型、车辆速度，或对将在碰撞期间耗散的耗散能量的至少估计，所述障碍物类型表示可能与之发生碰撞的障碍物的类型，所述碰撞类型表示可能发生的碰撞的类型，所述车辆速度表示在即将发生预测的碰撞之前至少主要车辆的速度，以及对将在碰撞期间耗散的耗散能量的至少估计。
57.根据权利要求56所述的基于处理器的系统，其中，所述障碍物类型表示所述障碍物是有生命的障碍物还是无生命的障碍物，并且所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器配置为：至少部分地基于所述障碍物是有生命的障碍物还是无生命的障碍物来设置所述代价。
58.根据权利要求56所述的基于处理器的系统，其中，所述碰撞类型表示所述碰撞是与将对物理障碍物或主要车辆造成损害的物理障碍物的碰撞，还是与不直接对主要车辆造成损害的间距要求或道路标记的碰撞，并且所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器配置为：至少部分地基于碰撞是与将对物理障碍物或主要车辆造成损害的物理障碍物的碰撞还是与不对道路标记造成损害的道路标记的碰撞来设置所述代价。
59.根据权利要求56所述的基于处理器的系统，其中，所述车辆速度表示所述主要车辆在现实世界参考系中的速度，并且所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器配置为：至少部分地基于所述主要车辆在所述现实世界参考系中的速度来设置所述代价。
60.根据权利要求56所述的基于处理器的系统，其中，所述车辆速度表示所述主要车辆相对于所述障碍物的速度的速度，并且所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器配置为：至少部分地基于所述主要车辆相对于所述障碍物的速度的速度来设置与所述相应边关联的代价。
61.根据权利要求56所述的基于处理器的系统，其中，所述车辆速度表示所述主要车辆的速度和所述障碍物的速度两者，并且所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器配置为：至少部分地基于所述主要车辆的速度和所述障碍物的速度两者来设置与所述相应边关联的代价。
62.根据权利要求56所述的基于处理器的系统，其中，所述参数化代价函数还表示基于车辆速度的碰撞的严重性水平，并且所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器配置为：至少部分地基于根据所述主要车辆和所述障碍物中至少一个或两者的车辆速度的严重性水平来设置与所述相应边关联的代价。
63.根据权利要求56至62中任一项所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器配置为：经由多个不同的硬件电路来执行所述碰撞检测。
64.根据权利要求56至62中任一项所述的基于处理器的系统，其中，所述处理器可执行指令在被所述至少一个处理器执行时，使所述至少一个处理器还配置为：
执行所述规划栅格的最小代价分析；以及
至少部分地基于所述最小代价分析，通过所述主要车辆来实施所生成的运动规划。
CN202080055382.1A 2019-06-03 2020-05-26 在具有动态障碍物的环境中促进运动规划的装置、方法和物品 Active CN114206698B (zh)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US201962856548P 2019-06-03 2019-06-03
US62/856,548 2019-06-03
PCT/US2020/034551 WO2020247207A1 (en) 2019-06-03 2020-05-26 Apparatus, methods and articles to facilitate motion planning in environments having dynamic obstacles

Publications (2)

Publication Number Publication Date
CN114206698A CN114206698A (zh) 2022-03-18
CN114206698B true CN114206698B (zh) 2024-07-02

Family

ID=73550120

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202080055382.1A Active CN114206698B (zh) 2019-06-03 2020-05-26 在具有动态障碍物的环境中促进运动规划的装置、方法和物品

Country Status (6)

Country Link
US (1) US11634126B2 (zh)
EP (1) EP3977226A4 (zh)
JP (1) JP7479064B2 (zh)
CN (1) CN114206698B (zh)
TW (1) TWI851731B (zh)
WO (1) WO2020247207A1 (zh)

Families Citing this family (30)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11262756B2 (en) * 2018-01-15 2022-03-01 Uatc, Llc Discrete decision architecture for motion planning system of an autonomous vehicle
DK201970121A1 (en) * 2018-10-30 2020-06-04 Aptiv Technologies Limited GENERATION OF OPTIMAL TRAJECTORIES FOR NAVIGATION OF VEHICLES
US11803184B2 (en) 2018-12-18 2023-10-31 Motional Ad Llc Methods for generating maps using hyper-graph data structures
US11390300B2 (en) * 2019-10-18 2022-07-19 Uatc, Llc Method for using lateral motion to optimize trajectories for autonomous vehicles
EP3832420B1 (en) * 2019-12-06 2024-02-07 Elektrobit Automotive GmbH Deep learning based motion control of a group of autonomous vehicles
DE112021000216T5 (de) * 2020-02-19 2022-11-03 Nvidia Corporation Verhaltensplanung für autonome Fahrzeuge
RU2764479C2 (ru) * 2020-04-23 2022-01-17 Общество с ограниченной ответственностью «Яндекс Беспилотные Технологии» Способ и система для управления работой самоуправляемого автомобиля
EP4147007A4 (en) * 2020-05-04 2024-06-05 Magna Electronics Inc. MATCHING METHOD AND SYSTEM
US20210349450A1 (en) * 2020-05-06 2021-11-11 UiPath, Inc. Hierarchical assessment of processes for implementing robotic process automation
US11505211B2 (en) * 2020-06-18 2022-11-22 Baidu Usa Llc Relative speed based speed planning for buffer area
JP2022030664A (ja) * 2020-08-07 2022-02-18 株式会社東芝 情報処理装置、情報処理方法、プログラム、情報処理システム、および、車両制御システム
US12124261B2 (en) * 2020-11-20 2024-10-22 Rapyuta Robotics Co., Ltd. Systems and methods for optimizing route plans in an operating environment
WO2022133684A1 (zh) * 2020-12-21 2022-06-30 华为技术有限公司 控制方法、相关设备及计算机可读存储介质
WO2022241550A1 (en) 2021-05-17 2022-11-24 Cobionix Corporation Proximity sensing autonomous robotic systems and apparatus
US20220388531A1 (en) * 2021-06-08 2022-12-08 Yandex Self Driving Group Llc Method and device for operating a self-driving car
CN113335276A (zh) * 2021-07-20 2021-09-03 中国第一汽车股份有限公司 障碍物的轨迹预测方法、装置、电子设备及存储介质
US11932282B2 (en) * 2021-08-04 2024-03-19 Zoox, Inc. Vehicle trajectory control using a tree search
WO2023039261A1 (en) * 2021-09-10 2023-03-16 Cyngn, Inc. System and method of adaptive, real-time vehicle system identification for autonomous driving
US20230132179A1 (en) * 2021-10-26 2023-04-27 GM Global Technology Operations LLC Tow management systems and methods for autonomous vehicles
US12116017B1 (en) * 2021-11-30 2024-10-15 Zoox, Inc. Machine-learned component hybrid training and assistance of vehicle trajectory generation
CN114706400B (zh) * 2022-04-12 2023-04-07 重庆文理学院 一种越野环境下基于改进的a*算法的路径规划方法
US20230331217A1 (en) * 2022-04-14 2023-10-19 Mitsubishi Electric Research Laboratories, Inc. System and Method for Motion and Path Planning for Trailer-Based Vehicle
CN114852058B (zh) * 2022-05-11 2023-03-31 远峰科技股份有限公司 自动泊车路径规划方法、装置、系统及可读存储介质
US20240001959A1 (en) * 2022-06-30 2024-01-04 Zoox, Inc. Vehicle motion planner
US20240054008A1 (en) 2022-08-12 2024-02-15 Kabushiki Kaisha Toshiba Apparatus and method for performing a task
CN116036601B (zh) * 2023-01-28 2023-06-09 腾讯科技（深圳）有限公司 游戏处理方法、装置及计算机设备、存储介质
CN117429448B (zh) * 2023-10-24 2024-10-25 北京易航远智科技有限公司 障碍物未来占据空间的预测方法、装置、电子设备及介质
CN118096816B (zh) * 2024-03-01 2024-09-03 山东财经大学 一种基于概率密度分布的预测重定向漫游优化方法及终端
CN118295402B (zh) * 2024-03-15 2024-09-03 苏州纵苇科技有限公司 一种运动规划方法和系统、电子设备及存储介质
CN117962932B (zh) * 2024-04-02 2024-06-11 福瑞泰克智能系统有限公司 障碍物的行驶轨迹生成方法、装置和存储介质及电子设备

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2017214581A1 (en) * 2016-06-10 2017-12-14 Duke University Motion planning for autonomous vehicles and reconfigurable motion planning processors

Family Cites Families (135)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4862373A (en) 1987-05-13 1989-08-29 Texas Instruments Incorporated Method for providing a collision free path in a three-dimensional space
US4949277A (en) 1988-03-09 1990-08-14 North American Philips Corporation Differential budding: method and apparatus for path planning with moving obstacles and goals
US6089742A (en) 1989-11-01 2000-07-18 Warmerdam; Thomas P. H. Method and apparatus for controlling robots and the like using a bubble data hierarchy placed along a medial axis
US5544282A (en) 1991-04-05 1996-08-06 Chen; Pang C. Method and apparatus for planning motions of robot manipulators
US5347459A (en) 1993-03-17 1994-09-13 National Research Council Of Canada Real time collision detection
US5835684A (en) 1994-11-09 1998-11-10 Amada Company, Ltd. Method for planning/controlling robot motion
US6004016A (en) 1996-08-06 1999-12-21 Trw Inc. Motion planning and control for systems with multiple mobile objects
US5795297A (en) 1996-09-12 1998-08-18 Atlantis Diagnostics International, L.L.C. Ultrasonic diagnostic imaging system with personal computer architecture
US6049756A (en) 1997-11-12 2000-04-11 Lockheed Martin Corporation System and method for avoiding collision between vector and solid objects
JPH11296229A (ja) 1998-02-13 1999-10-29 Komatsu Ltd 車両の誘導装置
DE19831216A1 (de) 1998-07-03 2000-01-05 Amecon Gmbh Verfahren und Vorrichtung zur Bestimmung der Abhängigkeit einer ersten Meßgröße von einer zweiten Meßgröße
US6259988B1 (en) 1998-07-20 2001-07-10 Lockheed Martin Corporation Real-time mission adaptable route planner
US6526373B1 (en) 1999-10-08 2003-02-25 Dassault Systemes Optimization tool for robot placement
JP2002073130A (ja) 2000-06-13 2002-03-12 Yaskawa Electric Corp ロボットの大域動作経路計画方法とその制御装置
DE10063722C2 (de) 2000-12-20 2003-07-03 Siemens Ag Ruckbegrenzung mit Adaption der Bahndynamik
JP2003127077A (ja) 2001-10-19 2003-05-08 Komatsu Ltd 作業ロボットのロボットプログラム修正装置。
US10065317B2 (en) 2016-06-30 2018-09-04 General Electric Company Control system for coordinating robotic machines to collaborate on tasks
JP3834307B2 (ja) 2003-09-29 2006-10-18 ファナック株式会社 ロボットシステム
US7447593B2 (en) * 2004-03-26 2008-11-04 Raytheon Company System and method for adaptive path planning
CA2563909A1 (en) 2004-04-22 2005-11-03 Albert Den Haan Open control system architecture for mobile autonomous systems
JP2006224740A (ja) 2005-02-16 2006-08-31 Advics:Kk 車両用走行支援装置
US20060235610A1 (en) 2005-04-14 2006-10-19 Honeywell International Inc. Map-based trajectory generation
US20060247852A1 (en) * 2005-04-29 2006-11-02 Kortge James M System and method for providing safety-optimized navigation route planning
JP5112666B2 (ja) 2006-09-11 2013-01-09 株式会社日立製作所 移動装置
DE602006003435D1 (de) 2006-09-14 2008-12-11 Abb Research Ltd Verfahren und Vorrichtung zur Vermeidung von Kollisionen zwischen einem Industrieroboter und einem Objekt
US7974737B2 (en) 2006-10-31 2011-07-05 GM Global Technology Operations LLC Apparatus and method of automated manufacturing
JP2008134165A (ja) 2006-11-29 2008-06-12 Renesas Technology Corp ナビゲーションシステム
KR100888475B1 (ko) * 2007-02-02 2009-03-12 삼성전자주식회사 모델간 충돌 여부 검사 방법 및 장치
EP1972415B1 (en) 2007-03-23 2019-01-02 Honda Research Institute Europe GmbH Robots with collision avoidance functionality
US7865277B1 (en) 2007-05-07 2011-01-04 The United States Of America As Represented By The Secretary Of The Navy Obstacle avoidance system and method
US8380424B2 (en) 2007-09-28 2013-02-19 The Boeing Company Vehicle-based automatic traffic conflict and collision avoidance
EP2085279B1 (en) 2008-01-29 2011-05-25 Ford Global Technologies, LLC A system for collision course prediction
ES2553722T3 (es) 2008-02-20 2015-12-11 Abb Research Ltd. Método y sistema para optimizar la configuración de una célula de trabajo de robot
US8571745B2 (en) 2008-04-10 2013-10-29 Robert Todd Pack Advanced behavior engine
US8315738B2 (en) 2008-05-21 2012-11-20 Fanuc Robotics America, Inc. Multi-arm robot system interference check via three dimensional automatic zones
US9144904B2 (en) 2008-05-21 2015-09-29 Fanuc Robotics America Corporation Method and system for automatically preventing deadlock in multi-robot systems
US8706452B2 (en) 2008-06-26 2014-04-22 Siemens Product Lifecycle Management Software Inc. System and method for collision-free CAD design of pipe and tube paths
JP5086942B2 (ja) 2008-09-02 2012-11-28 トヨタ自動車株式会社 経路探索装置、経路探索方法、及び経路探索プログラム
KR101554515B1 (ko) 2009-01-07 2015-09-21 삼성전자 주식회사 로봇의 경로계획장치 및 그 방법
KR101105325B1 (ko) 2009-09-08 2012-01-16 부산대학교 산학협력단 실제 로봇의 다중 경로계획 방법
US8386080B2 (en) 2009-09-15 2013-02-26 Harris Corporation Robotic apparatus implementing collision avoidance scheme and associated methods
JP4975075B2 (ja) 2009-09-30 2012-07-11 クラリオン株式会社 ナビゲーション装置および経路演算方法
WO2011056633A1 (en) 2009-10-27 2011-05-12 Battelle Memorial Institute Semi-autonomous multi-use robot system and method of operation
US20110153080A1 (en) 2009-12-22 2011-06-23 Siemens Product Lifecycle Management Software Inc. Method and apparatus for industrial robotic pathscycle time optimization using fly by
US20120061155A1 (en) 2010-04-09 2012-03-15 Willow Garage, Inc. Humanoid robotics system and methods
JP2011249711A (ja) 2010-05-31 2011-12-08 Kyocera Corp 配線基板およびその実装構造体
US8855812B2 (en) 2010-07-23 2014-10-07 Chetan Kapoor System and method for robot safety and collision avoidance
JP2012056023A (ja) 2010-09-09 2012-03-22 Toyota Motor Corp ロボットの動作生成システム及び動作生成方法
CA2812723C (en) 2010-09-24 2017-02-14 Evolution Robotics, Inc. Systems and methods for vslam optimization
US8509982B2 (en) 2010-10-05 2013-08-13 Google Inc. Zone driving
JP2012190405A (ja) 2011-03-14 2012-10-04 Toyota Motor Corp 経路情報修正装置、軌道計画装置、及びロボット
JP5774361B2 (ja) 2011-04-28 2015-09-09 本田技研工業株式会社 軌道計画方法、軌道計画システム及び軌道計画・制御システム
JP2012243029A (ja) 2011-05-18 2012-12-10 Toyota Central R&D Labs Inc 経路探索機能付き移動体
CN103687702B (zh) 2011-06-29 2016-08-24 三菱电机株式会社 部件供给装置
TW201318793A (zh) 2011-11-08 2013-05-16 Univ Minghsin Sci & Tech 機器人光學定位系統及其定位方法
WO2013140401A2 (en) 2012-03-22 2013-09-26 Israel Aerospace Industries Ltd. Planning and monitoring of autonomous-mission
JP5724919B2 (ja) 2012-03-22 2015-05-27 トヨタ自動車株式会社 軌道生成装置、移動体、軌道生成方法及びプログラム
KR20130112507A (ko) 2012-04-04 2013-10-14 인하대학교 산학협력단 Ｓ＊ 알고리즘을 이용한 이동로봇의 안전경로계획 수립방법
JP6128767B2 (ja) 2012-07-05 2017-05-17 キヤノン株式会社 ロボット制御装置、及びロボット制御方法
KR101441187B1 (ko) 2012-07-19 2014-09-18 고려대학교 산학협력단 자율 보행 로봇 경로 계획 방법
JP6069923B2 (ja) 2012-07-20 2017-02-01 セイコーエプソン株式会社 ロボットシステム、ロボット、ロボット制御装置
JP2015526309A (ja) 2012-08-31 2015-09-10 リシンク ロボティクス インコーポレイテッド 安全ロボット動作のためのシステムおよび方法
US20150266182A1 (en) 2012-10-11 2015-09-24 Abb Technology Ltd Method And An Apparatus For Automatically Generating A Collision Free Return Program For Returning A Robot From A Stop Position To A Predefined Restart Position
KR102009482B1 (ko) 2012-10-30 2019-08-14 한화디펜스 주식회사 로봇의 경로계획 장치와 방법 및 상기 방법을 구현하는 프로그램이 기록된 기록 매체
US9405296B2 (en) 2012-12-19 2016-08-02 Elwah LLC Collision targeting for hazard handling
US8972057B1 (en) 2013-01-09 2015-03-03 The Boeing Company Systems and methods for generating a robotic path plan in a confined configuration space
US9227323B1 (en) 2013-03-15 2016-01-05 Google Inc. Methods and systems for recognizing machine-readable information on three-dimensional objects
JP5962560B2 (ja) 2013-03-22 2016-08-03 トヨタ自動車株式会社 経路探索装置、移動体、経路探索方法及びプログラム
US9753441B2 (en) * 2013-05-13 2017-09-05 Massachusetts Institute Of Technology Controlling dynamical systems with bounded probability of failure
US9280899B2 (en) 2013-08-06 2016-03-08 GM Global Technology Operations LLC Dynamic safety shields for situation assessment and decision making in collision avoidance tasks
JP6057862B2 (ja) 2013-08-29 2017-01-11 三菱電機株式会社 部品供給装置および部品供給装置のプログラム生成方法
US9352465B2 (en) 2013-11-12 2016-05-31 Canon Kabushiki Kaisha Control method for robot apparatus and robot apparatus
CN105980940B (zh) 2014-01-28 2019-01-01 Abb瑞士股份有限公司 用于优化机器人单元的性能的方法和装置
JP5897624B2 (ja) 2014-03-12 2016-03-30 ファナック株式会社 ワークの取出工程をシミュレーションするロボットシミュレーション装置
JP5877867B2 (ja) 2014-04-25 2016-03-08 ファナック株式会社 複数台のロボットのシミュレーション装置
DE102014212898A1 (de) * 2014-07-03 2016-01-07 Robert Bosch Gmbh Verfahren zum Ermitteln einer Notfall-Trajektorie und Verfahren zum teilautomatisierten oder automatisierten Führen eines Ego-Fahrzeugs
US11576543B2 (en) 2014-07-18 2023-02-14 Ali Ebrahimi Afrouzi Robotic vacuum with rotating cleaning apparatus
WO2016050274A1 (en) * 2014-09-30 2016-04-07 Nec Europe Ltd. Method and system for determining a path of an object for moving from a starting state to an end state set avoiding one or more obstacles
US9403275B2 (en) 2014-10-17 2016-08-02 GM Global Technology Operations LLC Dynamic obstacle avoidance in a robotic system
JP5980873B2 (ja) 2014-10-17 2016-08-31 ファナック株式会社 ロボットの干渉領域設定装置
US20160121487A1 (en) 2014-11-03 2016-05-05 Qualcomm Incorporated Communicating Configurable Instruction Sets to Robots for Controlling Robot Behavior
CN107206592B (zh) * 2015-01-26 2021-03-26 杜克大学 专用机器人运动规划硬件及其制造和使用方法
JP6556245B2 (ja) 2015-02-13 2019-08-07 アーベーベー シュヴァイツ アクツィエンゲゼルシャフト ２つのロボット間の衝突を回避するための方法
US10019006B2 (en) * 2015-04-08 2018-07-10 University Of Maryland, College Park Surface vehicle trajectory planning systems, devices, and methods
US9687982B1 (en) 2015-05-27 2017-06-27 X Development Llc Adapting programming of a robot and/or control of the robot based on one or more parameters of an end effector of the robot
US20160357187A1 (en) 2015-06-05 2016-12-08 Arafat M.A. ANSARI Smart vehicle
US20170004406A1 (en) 2015-06-30 2017-01-05 Qualcomm Incorporated Parallel belief space motion planner
US9707681B2 (en) 2015-07-27 2017-07-18 Siemens Industry Software Ltd. Anti-collision management of overlapping robotic movements
KR101724887B1 (ko) 2015-08-10 2017-04-07 현대자동차주식회사 전방 도로 형상과 연결을 분석해 차선 변경과 타이밍을 결정하는 자율주행 제어 장치 및 방법
US10464559B2 (en) 2015-09-29 2019-11-05 Sony Corporation Damage reduction device, damage reduction method, and program
KR101748632B1 (ko) 2015-10-29 2017-06-20 한국과학기술연구원 로봇의 구동 경로를 계획하기 위한 로봇 제어 시스템 및 로봇 구동 경로 계획방법
US9632502B1 (en) 2015-11-04 2017-04-25 Zoox, Inc. Machine-learning systems and techniques to optimize teleoperation and/or planner decisions
US10496766B2 (en) 2015-11-05 2019-12-03 Zoox, Inc. Simulation system and methods for autonomous vehicles
EP3171133B1 (en) 2015-11-19 2020-03-11 Sikorsky Aircraft Corporation Kinematic motion planning with regional planning constraints
US10093021B2 (en) 2015-12-02 2018-10-09 Qualcomm Incorporated Simultaneous mapping and planning by a robot
US10012984B2 (en) 2015-12-14 2018-07-03 Mitsubishi Electric Research Laboratories, Inc. System and method for controlling autonomous vehicles
US10705528B2 (en) 2015-12-15 2020-07-07 Qualcomm Incorporated Autonomous visual navigation
US10665115B2 (en) 2016-01-05 2020-05-26 California Institute Of Technology Controlling unmanned aerial vehicles to avoid obstacle collision
US10035266B1 (en) 2016-01-18 2018-07-31 X Development Llc Generating robot trajectories using a real time trajectory generator and a path optimizer
JP6576255B2 (ja) 2016-01-25 2019-09-18 キヤノン株式会社 ロボット軌道生成方法、ロボット軌道生成装置、および製造方法
US9645577B1 (en) 2016-03-23 2017-05-09 nuTonomy Inc. Facilitating vehicle driving and self-driving
WO2017168187A1 (en) 2016-03-31 2017-10-05 Siemens Industry Software Ltd. Method and system for determining optimal positioning of a plurality of robots in a simulated production environment
KR102499421B1 (ko) 2016-05-05 2023-02-14 하만인터내셔날인더스트리스인코포레이티드 운전자 지원을 위한 시스템 및 방법
US9687983B1 (en) 2016-05-11 2017-06-27 X Development Llc Generating a grasp pose for grasping of an object by a grasping end effector of a robot
US9880561B2 (en) 2016-06-09 2018-01-30 X Development Llc Sensor trajectory planning for a vehicle
US9981383B1 (en) 2016-08-02 2018-05-29 X Development Llc Real-time trajectory generation for actuators of a robot to reduce chance of collision with obstacle(s)
US10131053B1 (en) 2016-09-14 2018-11-20 X Development Llc Real time robot collision avoidance
US10345815B2 (en) 2016-09-14 2019-07-09 Qualcomm Incorporated Motion planning and intention prediction for autonomous driving in highway scenarios via graphical model-based factorization
DE102016120763B4 (de) 2016-10-31 2019-03-14 Pilz Gmbh & Co. Kg Verfahren zur kollisionsfreien Bewegungsplanung
WO2018087551A1 (en) 2016-11-09 2018-05-17 Inventive Cogs (Campbell) Limited Vehicle route guidance
KR102518532B1 (ko) 2016-11-11 2023-04-07 현대자동차주식회사 자율주행차량의 경로 결정장치 및 그 방법
US10012988B2 (en) * 2016-11-29 2018-07-03 Mitsubishi Electric Research Laboratories, Inc. Methods and systems for path planning using a network of safe-sets
US10480947B2 (en) * 2016-12-21 2019-11-19 X Development Llc Boolean satisfiability (SAT) reduction for geometry and kinematics agnostic multi-agent planning
US10296012B2 (en) 2016-12-21 2019-05-21 X Development Llc Pre-computation of kinematically feasible roadmaps
US10099372B2 (en) 2017-02-07 2018-10-16 Veo Robotics, Inc. Detecting and classifying workspace regions for safety monitoring
US11541543B2 (en) 2017-02-07 2023-01-03 Veo Robotics, Inc. Dynamic, interactive signaling of safety-related conditions in a monitored environment
DE102017102749A1 (de) 2017-02-13 2018-08-16 Festo Ag Automatische Trajektorienerzeugung zur Ansteuerung eines Antriebssystems
US10430641B2 (en) 2017-03-08 2019-10-01 GM Global Technology Operations LLC Methods and systems for object tracking using bounding boxes
KR101937269B1 (ko) 2017-05-15 2019-01-14 한국생산기술연구원 로봇 모션 경로 계획방법
US11014240B2 (en) 2017-09-05 2021-05-25 Abb Schweiz Ag Robot having dynamic safety zones
US10782694B2 (en) 2017-09-07 2020-09-22 Tusimple, Inc. Prediction-based system and method for trajectory planning of autonomous vehicles
US10571921B2 (en) * 2017-09-18 2020-02-25 Baidu Usa Llc Path optimization based on constrained smoothing spline for autonomous driving vehicles
US10928832B2 (en) * 2017-09-29 2021-02-23 Huawei Technologies Co., Ltd. Impedance-based motion control for autonomous vehicles
US10466707B2 (en) 2017-12-22 2019-11-05 X Development Llc Planning robot stopping points to avoid collisions
PL3769174T3 (pl) 2018-03-21 2022-10-24 Realtime Robotics, Inc. Planowanie przemieszczania robota do różnych środowisk i zadań oraz jego ulepszone działanie
US11216009B2 (en) 2018-06-25 2022-01-04 Intrinsic Innovation Llc Robot coordination in a shared workspace
JP7141665B2 (ja) 2018-08-23 2022-09-26 リアルタイム ロボティクス， インコーポレーテッド ロボットの動作計画に役立つ衝突検出
US10809732B2 (en) * 2018-09-25 2020-10-20 Mitsubishi Electric Research Laboratories, Inc. Deterministic path planning for controlling vehicle movement
JP7394853B2 (ja) 2018-12-04 2023-12-08 デューク・ユニバーシティ 動的物体を有する環境における運動計画を促進する装置、方法及び物品
CN109782763B (zh) * 2019-01-18 2021-11-23 中国电子科技集团公司信息科学研究院 一种动态环境下的移动机器人路径规划方法
EP3725472A1 (de) 2019-04-16 2020-10-21 Siemens Aktiengesellschaft Verfahren zum ermitteln einer trajektorie eines roboters
US11179850B2 (en) 2019-04-24 2021-11-23 Intrinsic Innovation Llc Robot motion planning
JP7222803B2 (ja) 2019-04-25 2023-02-15 株式会社日立製作所 軌道計画装置、軌道計画方法及びプログラム
GB202215836D0 (en) * 2019-05-07 2022-12-07 Motional Ad Llc Systems and methods for planning and updating a vehicle's trajectory
TWI699636B (zh) 2019-05-21 2020-07-21 華邦電子股份有限公司 協同型機器人控制系統和方法

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2017214581A1 (en) * 2016-06-10 2017-12-14 Duke University Motion planning for autonomous vehicles and reconfigurable motion planning processors

Also Published As

Publication number Publication date
EP3977226A1 (en) 2022-04-06
CN114206698A (zh) 2022-03-18
JP2022536263A (ja) 2022-08-15
WO2020247207A1 (en) 2020-12-10
TW202113524A (zh) 2021-04-01
JP7479064B2 (ja) 2024-05-08
US20200377085A1 (en) 2020-12-03
TWI851731B (zh) 2024-08-11
US11634126B2 (en) 2023-04-25
WO2020247207A8 (en) 2021-03-18
EP3977226A4 (en) 2023-06-07

Similar Documents

Publication Publication Date Title
CN114206698B (zh) 在具有动态障碍物的环境中促进运动规划的装置、方法和物品
JP7394853B2 (ja) 動的物体を有する環境における運動計画を促進する装置、方法及び物品
US11970161B2 (en) Apparatus, method and article to facilitate motion planning of an autonomous vehicle in an environment having dynamic objects
US11465619B2 (en) Vehicle collision avoidance based on perturbed object trajectories
JP6837558B2 (ja) 自車両の制御方法及び自車両の制御システム
JP2022513808A (ja) 軌道検証を用いた衝突回避システム
CN114270360A (zh) 让步行为建模和预测
CN112888612A (zh) 自动驾驶车辆规划
CN112334368A (zh) 车辆控制系统及控制车辆运动的控制方法
JP2023548272A (ja) 交差する確率に基づく安全システム資源の割り当て
CN110461676A (zh) 控制车辆的横向运动的系统和方法
US11814072B2 (en) Method and system for conditional operation of an autonomous agent
Reda et al. Path planning algorithms in the autonomous driving system: A comprehensive review
US11810365B1 (en) Perception error modeling
CN117794803A (zh) 使用具有响应型代理预测的树搜索和/或代理滤波进行车辆轨迹控制
JPWO2021242702A5 (zh)
JP2024528425A (ja) オブジェクト軌道に基づくアクティブ予測
Andersen et al. Trajectory optimization and situational analysis framework for autonomous overtaking with visibility maximization
JP2023547988A (ja) 衝突回避計画システム
TW202123031A (zh) 用以便利具有動態物件環境中之運動規劃的裝置、方法及物品
Ning et al. A Novel Motion Planning for Autonomous Vehicles Using Point Cloud based Potential Field
JP2024510058A (ja) オブジェクト輪郭を使用した衝突回避
Mondal DEVELOPMENT OF AUTONOMOUS VEHICLE MOTION PLANNING AND CONTROL ALGORITHM WITH D* PLANNER AND MODEL PREDICTIVE CONTROL IN A DYNAMIC ENVIRONMENT
Tahir Design and Implementation of an Autonomous Car for Navigation in Unknown Enviornments

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant