构建时空代价图的方法和装置

摘要

公开了一种构建时空代价图的方法和装置，该方法包括：获得至少两个离散时刻中的最先离散时刻的预定空间范围内的环境数据；根据所获得的环境数据对前述时空代价图的每个图层中的每个体素的代价值进行初始设置；以及对与前述至少两个离散时刻中不同于最先离散时刻的任何另一离散时刻相对应的图层中的一个或多个体素的代价值进行调整。通过该方法能够构建一种时空代价图，该时空代价图融合时间维度和空间维度的代价并且能够提供全局最优的规划轨迹。

权利要求

1.一种构建时空代价图的方法，包括：获得至少两个离散时刻中的最先离散时刻的预定空间范围内的环境数据；

根据所述环境数据对所述时空代价图的每个图层中的每个体素的代价值进行初始设置，所述时空代价图的每个图层分别与所述至少两个离散时刻中的每个离散时刻相对应；

以及

对于所述至少两个离散时刻中不同于所述最先离散时刻的任何另一离散时刻，根据与所述至少两个离散时刻中先于所述另一离散时刻的至少一个在前离散时刻相对应的至少一个图层，对与所述另一离散时刻相对应的图层中的一个或多个体素的代价值进行调整。

2.根据权利要求1所述的方法，其中，所述环境数据包括在所述最先离散时刻与所述预定空间范围内的地图元素有关的地图数据、在所述最先离散时刻与所述预定空间范围内的一个或多个地图元素有关的实时状态数据、在所述最先离散时刻与所述预定空间范围内的环境有关的实时感测数据以及在所述最先离散时刻与所述预定空间范围内的模拟环境有关的模拟数据之中的一个或多个。

3.根据权利要求1所述的方法，其中，所述初始设置包括：根据所述环境数据，确定在所述预定空间范围内的永久不可行驶区域；以及将所述时空代价图的每个图层中的与所述永久不可行驶区域相对应的所有体素的代价值设置为最高代价值。

4.根据权利要求3所述的方法，其中，所述永久不可行驶区域包括所述预定空间范围内的静态障碍物所在的静态障碍物区域、所述预定空间范围内的禁行区域、所述预定空间范围内的不可到达区域以及所述预定空间范围内的未知区域之中的一个或多个。

5.根据权利要求3所述的方法，其中，所述永久不可行驶区域包括可行驶的通道部分之外的区域。

6.根据权利要求3所述的方法，其中，所述初始设置还包括：确定所述时空代价图的每个图层中的与所述永久不可行驶区域之外的可行驶区域相对应的各个体素到所述永久不可行驶区域的距离；以及设置所述时空代价图的每个图层中的与所述可行驶区域相对应的各个体素的代价值，使得越靠近所述永久不可行驶区域，相应的值越高。

7.根据权利要求1所述的方法，其中，所述初始设置包括：获得与所述预定空间范围内的一个或多个地图元素在所述至少两个离散时刻中的每个离散时刻的状态数据；

根据所获得的状态数据，确定在所述预定空间范围内在所述至少两个离散时刻中的每个离散时刻的暂时不可行驶区域；以及将所述时空代价图的每个图层中的与相应的暂时不可行驶区域相对应的所有体素的代价值设置为最高代价值。

8.根据权利要求1所述的方法，其中，所述初始设置包括：获得与所述预定空间范围内的一个或多个地图元素在所述至少两个离散时刻中的每个离散时刻的状态数据；

根据所获得的状态数据，确定在所述预定空间范围内在所述至少两个离散时刻中的每个离散时刻的过渡区域，所述过渡区域是在所述预定空间范围内将在包括相应的离散时刻的第一预定时间段内转换为暂时不可行驶区域期间的可行驶区域和/或在所述预定空间范围内将在包括相应的离散时刻的第二预定时间段内转换为可行驶区域的暂时不可行驶区域；以及

将所述时空代价图的每个图层中的与相应的过渡区域相对应的各个体素的代价值设置为大于最低代价值并且小于或等于最高代价值。

9.根据权利要求1所述的方法，其中，所述初始设置包括：根据行驶规则和/或驾驶习惯，设置所述时空代价图的每个图层中的与所述预定空间范围内的可行驶区域相对应的各个体素的代价值。

10.根据权利要求9所述的方法，其中，所述可行驶区域包括可行驶的通道部分，并且在所述时空代价图的每个图层中，从所述通道部分的两侧开始越靠近所述通道部分的中间，相应的体素的代价值越小。

11.根据权利要求9所述的方法，其中，所述可行驶区域包括可行驶的第一通道部分以及可行驶且与所述第一通道部分相邻的第二通道部分，并且在所述时空代价图的每个图层中，与所述第二通道部分相对应的体素的代价值小于或等于与所述第一通道部分相对应的体素的代价值。

12.根据权利要求1所述的方法，其中，对于所述时空代价图的与所述最先离散时刻相对应的图层，所述初始设置包括：根据所述环境数据，确定在所述最先离散时刻在所述预定空间范围内的可行驶区域中的一个或多个动态障碍物；以及

将与所述最先离散时刻相对应的图层中的与所述可行驶区域中的每个动态障碍物所在的动态障碍物区域相对应的所有体素的代价值设置为最高代价值。

13.根据权利要求12所述的方法，其中，对于所述时空代价图的与所述最先离散时刻相对应的图层，所述初始设置还包括：确定与所述最先离散时刻相对应的图层中的与所述可行驶区域相对应的各个体素到所述一个或多个动态障碍物的距离；以及设置与所述最先离散时刻相对应的图层中的与所述可行驶区域相对应的各个体素的代价值，使得越靠近所述一个或多个动态障碍物，相应的值越高。

14.根据权利要求12所述的方法，其中，对于所述时空代价图的与所述最先离散时刻相对应的图层，所述初始设置还包括：根据所述一个或多个动态障碍物，确定所述可行驶区域中被所述一个或多个动态障碍物阻断而成为暂时不可行驶区域的部分；以及将与所述最先离散时刻相对应的图层中的与所述暂时不可行驶区域相对应的所有体素的代价值设置为最高代价值。

15.根据权利要求1所述的方法，其中，所述调整包括：根据所述至少一个图层，确定障碍物在所述另一离散时刻在所述预定空间范围内可能出现的区域和相应的概率；以及

根据所述概率，设置所述时空代价图的与所述另一离散时刻相对应的图层中的与所述区域相对应的各个体素的代价值。

16.根据权利要求15所述的方法，其中，确定所述障碍物可能出现的区域和相应的概率包括：

根据所述至少一个图层，通过时变线性系统的递归滤波确定所述障碍物在所述另一离散时刻在所述预定空间范围内可能出现的区域和相应的概率。

17.根据权利要求15所述的方法，其中，根据所述概率，设置所述时空代价图的与所述另一离散时刻相对应的图层中的与所述区域相对应的各个体素的代价值包括：计算所述概率在根据最小代价值和最大代价值确定的代价值范围内的投射值；以及将与所述另一离散时刻相对应的图层中的与所述区域相对应的各个体素的代价值设置为所述投射值。

18.根据权利要求1所述的方法，还包括：确定所述时空代价图的至少两个图层的融合图层。

19.根据权利要求18所述的方法，其中，对于所述融合图层中的任一关注体素，如果所述至少两个图层中的与所述关注体素相对应的一个或多个体素中的至少一个的代价值是最高代价值，则所述关注体素的代价值为最高代价值。

20.根据权利要求18所述的方法，其中，对于所述融合图层中的任一关注体素，如果所述至少两个图层中的与所述关注体素相对应的一个或多个体素中的任何一个的代价值均不是最高代价值，则所述关注体素的代价值为所述一个或多个体素的代价值总和与次高代价值之中的最小值。

21.根据权利要求1所述的方法，还包括：根据所述时空代价图的分别与所述至少两个离散时刻中的第一离散时刻和第二离散时刻相对应的第一图层和第二图层，确定所述时空代价图的与处于所述第一离散时刻和所述第二离散时刻之间的任一时间点相对应的图层。

22.根据权利要求21所述的方法，其中，确定所述时空代价图的与处于所述第一离散时刻和所述第二离散时刻之间的任一时间点相对应的图层包括：根据所述第一图层中的每个体素的代价值和所述第二图层中的每个对应的体素的代价值的加权和，确定与所述任一时间点相对应的图层中的每个对应的体素的代价值。

23.根据权利要求1至22中的任一项所述的方法，还包括：生成与所述时空代价图相关联的一个或多个代价查询表，所述一个或多个代价查询表中的每个代价查询表分别根据自主移动装置的主体朝向角和在所述预定空间范围内的位置提供所述自主移动装置的主体上的每个特征点在所述时空代价图中占据的所有体素。

24.一种计算机可读取的非临时性存储介质，在其上存储有程序指令，所述程序指令在被执行时执行根据权利要求1至23中的任一项所述的方法。

25.一种构建时空代价图的装置，包括：一个或多个处理器，被配置为在启动时至少执行根据权利要求1至23中的任一项所述的方法。

26.一种构建时空代价图的装置，包括：感测器，被配置为获得至少两个离散时刻中的最先离散时刻的预定空间范围内的环境数据；以及

渲染器，被配置为根据所述环境数据对所述时空代价图的每个图层中的每个体素的代价值进行初始设置，所述时空代价图的每个图层分别与所述至少两个离散时刻中的每个离散时刻相对应，以及对于所述至少两个离散时刻中不同于所述最先离散时刻的任何另一离散时刻，根据与所述至少两个离散时刻中先于所述另一离散时刻的至少一个在前离散时刻相对应的至少一个图层，对与所述另一离散时刻相对应的图层中的一个或多个体素的代价值进行调整。

说明书

构建时空代价图的方法和装置

技术领域

[0001] 本公开总体上涉及自主移动装置轨迹规划的技术领域，并且具体地涉及一种构建时空代价图的方法和装置。

背景技术

[0002] 在对诸如无人驾驶的交通工具、无人车、无人机、机械臂、移动机器人等自主移动装置进行轨迹规划和评价时，通常将空间维度的代价(例如，基于空间代价图)和时间维度
的代价(例如，基于动态对象的预测)分开处理，导致所获得的规划轨迹往往仅是局部最优
的。局部最优性将导致多次规划的不一致性，甚至单次规划的失败，而多次规划的不一致性
或单次规划的失败很可能引发诸如自主移动装置的碰撞事故等灾难性后果。

[0003] 另外，通常的轨迹规划和评价方法难以考虑传感器的观测误差和动态对象的预测误差。

发明内容

[0004] 为了解决或减轻上述问题，本公开提供一种全新的时空代价图，该时空代价图能够有效地融合时间维度和空间维度的代价，进而能够提供全局最优且具有一致性的规划轨
迹。

[0005] 一方面，本公开提供了一种构建上述时空代价图的方法，该方法可以包括：获得至少两个离散时刻中的最先离散时刻的预定空间范围内的环境数据；根据前述环境数据对前
述时空代价图的每个图层中的每个体素的代价值进行初始设置，前述时空代价图的每个图
层分别与前述至少两个离散时刻中的每个离散时刻相对应；以及对于前述至少两个离散时
刻中不同于前述最先离散时刻的任何另一离散时刻，根据与前述至少两个离散时刻中先于
前述另一离散时刻的至少一个在前离散时刻相对应的至少一个图层，对与前述另一离散时
刻相对应的图层中的一个或多个体素的代价值进行调整。

[0006] 另一方面，本公开提供了一种计算机可读取的非临时性存储介质，在其上存储有程序指令，前述程序指令在被执行时执行上述方法。

[0007] 另一方面，本公开提供了一种构建上述时空代价图的装置，该装置可以包括：一个或多个处理器，被配置为在启动时至少执行上述方法。

[0008] 另一方面，本公开提供了一种构建上述时空代价图的装置，该装置可以包括感测器和渲染器。感测器可以被配置为获得至少两个离散时刻中的最先离散时刻的预定空间范
围内的环境数据。渲染器可以被配置为根据前述环境数据对前述时空代价图的每个图层中
的每个体素的代价值进行初始设置，前述时空代价图的每个图层分别与前述至少两个离散
时刻中的每个离散时刻相对应，以及对于前述至少两个离散时刻中不同于前述最先离散时
刻的任何另一离散时刻，根据与前述至少两个离散时刻中先于前述另一离散时刻的至少一
个在前离散时刻相对应的至少一个图层，对与前述另一离散时刻相对应的图层中的一个或
多个体素的代价值进行调整。

[0009] 通过根据本公开的实施例的方法和装置，能够提供一种全新的时空代价图，该时空代价图能够有效地融合时间维度和空间维度的代价，进而能够提供全局最优且具有一致
性的规划轨迹。

附图说明

[0010] 图1示出根据本公开的实施例的时空代价图的示例。

[0011] 图2示出根据本公开的实施例的构建时空代价图的方法的示例。

[0012] 图3示出根据本公开的实施例的时空代价图的图层的示例。

[0013] 图4示出根据本公开的实施例的时空代价图的图层的示例。

[0014] 图5示出根据本公开的实施例的时空代价图的图层中的体素的示例。

[0015] 图6示出根据本公开的实施例的时空代价图的图层中的体素的示例。

[0016] 图7示出根据本公开的实施例的时空代价图的图层中的体素的示例。

[0017] 图8示出根据本公开的实施例的时空代价图的图层的示例。

[0018] 图9示出根据本公开的实施例的时空代价图的图层的示例。

[0019] 图10示出根据本公开的实施例的时空代价图的图层的示例。

[0020] 图11示出根据本公开的实施例的时空代价图的图层的示例。

[0021] 图12示出根据本公开的实施例的时空代价图的图层中的体素的示例。

[0022] 图13示出根据本公开的实施例的时空代价图的图层中的体素的示例。

[0023] 图14示出根据本公开的实施例的时空代价图的图层的示例。

[0024] 图15示出根据本公开的实施例的时空代价图的图层的示例。

[0025] 图16示出根据本公开的实施例的调整体素的代价值的示例。

[0026] 图17示出根据本公开的实施例的调整体素的代价值的示例。

[0027] 图18示出根据本公开的实施例的图层融合的示例。

[0028] 图19示出根据本公开的实施例的获得连续时间图层的示例。

[0029] 图20示出根据本公开的实施例的装置的示例。

具体实施方式

[0030] 对于复杂的导航算法，可以先使用基于栅格的空间代价图来静态地规划轨迹，其中，空间代价图的每个栅格可以表示仅与空间相关联的静态约束或静态代价(也可以被称
为“空间代价”)，然后可以通过动态规划来处理时序信息。

[0031] 在不同的示例中，空间代价图可以具有不同的维度，例如可以是一维的线性空间代价图、二维的平面空间代价图、三维的立体空间代价图，甚至可以具有更多的维度，例如
用于反映与不同的关注特征(例如，可能的危险区域、确定性障碍物等)有关的静态约束或
静态代价。

[0032] 然而，如前文所述，通过将空间维度的静态代价和时间维度的动态代价分开处理所获得的规划轨迹往往仅是局部最优的，而这样的局部最优性很可能导致多次规划的不一
致性或单次规划的失败，进而引发灾难性后果。为此，本公开提出一种能够融合空间维度代
价和时间维度代价的时空代价图。

[0033] 如图1所示，根据本公开的实施例的时空代价图可以包括至少两个图层L1至Ln(n是大于1的整数)，每个图层Li(i是大于或等于1并且小于或等于n的整数)分别与时间轴上的
每个离散时刻Mi相对应。例如，图层L1与离散时刻M1相对应，图层L2与离散时刻M2相对应，图
层L3与离散时刻M3相对应，以此类推，图层Ln与离散时刻Mn相对应。相应地，根据本公开的实
施例的时空代价图的分别与每个离散时刻Mi相对应图层Li也可以被称为“时间图层”。

[0034] 在一个实施例中，离散时刻M1可以对应于当前时刻。在另外的实施例中，离散时刻M1可以对应于某个过去时刻。

[0035] 在一个实施例中，可以在时间轴上等时间间隔地选择离散时刻M1至Mn。在该实施例中，对于离散时刻M1至Mn中的任何一个离散时刻Mj(j是大于或等于1并且小于n的整数)，Mj+1
＝Mj+Δt，其中，Δt可以是采用任意时间长度单位(例如，毫秒、秒、分钟、小时等)的大于0
的任意固定值(例如，0.2、1、1.5、30、100等)。

[0036] 在另外的实施例中，离散时刻M1至Mn可以不均匀地分布在时间轴上。在该实施例中，对于离散时刻M1至Mn中的任何一个离散时刻Mj(j是大于或等于1并且小于n的整数)，Mj+1
＝Mj+Δtj，其中，每个Δtj可以分别是采用任意时间长度单位(例如，毫秒、秒、分钟、小时
等)的大于0的数值(例如，0.2、1、1.5、30、100等)，并且不同的Δtj的值可以相同或不同。

[0037] 在图1的示例中，时空代价图的每个图层Li被表示为二维的平面图层，即，图1的示例中的时空代价图包括针对二维规划空间的不同的时间图层。然而，在另外的实施例中，时
空代价图的每个图层Li实际上可以对应于具有其他维度(例如，一维、三维或更多维度)的
规划空间。

[0038] 例如，如果规划空间为三维空间，例如，包括常规的三维空间中的三个维度，或者包括常规的平面空间中的两个维度和与某个关注特征(例如，平面地图中的车道轮廓)有关
的另外一个维度，则与该规划空间有关的时空代价图的每个图层Li可以分别对应于该三维
规划空间在离散时刻Mi时的时空代价，并且相应地，根据该实施例的时空代价图可以包括
四个维度，即，所对应的规划空间的三个维度和一个时间维度。

[0039] 例如，如果规划空间为四维空间，例如，包括常规的三维空间中的三个维度和与某个关注特征的有关的另外一个维度，或者包括常规的一维线性空间中的一个维度和与三个
关注特征有关的另外三个维度，则与该规划空间有关的时空代价图的每个图层Li可以分别
对应于该四维规划空间在离散时刻Mi时的时空代价，并且相应地，根据该实施例的时空代
价图可以包括五个维度，即，所对应的规划空间的四个维度和一个时间维度。

[0040] 一般地，如果关注的规划空间包括D个维度，则根据本公开的实施例的时空代价图可以包括D+1个维度，即，关注的规划空间本身的D个维度和一个时间维度，其中，时空代价
图的图层Li可以对应于该D维的规划空间在离散时刻Mi时的时空代价。

[0041] 在图1的示例中，根据本公开的实施例的时空代价图的各个图层按照对应的离散时刻在时间轴上的顺序“从底到高”地组织在一起。然而，根据本公开的实施例的时空代价
图中的各个图层的组织方式和/或存储方式和/或呈现方式不局限于图1所示的方式。例如，
根据本公开的实施例的时空代价图的各个图层可以按照任意次序(例如，乱序地)存储在存
储器中，只要能够在需要时通过例如索引、链接、指针或其他适当方式读取到所需的图层即
可。在另外的示例中，可以按照从M1到Mn的次序(即，顺序地)或者从Mn到M1的次序(即，逆序
地)存储和/或呈现根据本公开的实施例的时空代价图的各个图层。

[0042] 根据本公开的实施例的时空代价图在D+1维的时空中的最小分割单位或最小构成单位可以被称为“体素(Voxel)”。根据本公开的实施例的时空代价图的每个体素可以代表
同时与时间和空间两者相关联的一个时空代价值(在下文中简称为“代价值”)或者可以具
有相应的代价值。在本文中，在不会引起混淆的情况下，例如在一些等式中，也可以简单地
使用措词“体素”本身或者表示“体素”的符号来代替表述“体素的代价值”。

[0043] 根据不同的实施例，根据本公开的实施例的时空代价图的每个体素的代价值的取值范围可以是根据最低代价值(例如，0)和最高代价值(例如，100)确定的连续或离散的数
值范围(例如，[0,100]范围内的整数或实数)，其中，具有最高代价值的体素可以表示在与
该体素相对应的时刻(即，该体素所在的图层)、在关注的规划空间中与该体素相对应的位
置处的代价最高，例如必然发生碰撞。根据需要，可以选择任何适当的值作为最低代价值和
最高代价值。在一个实施例中，最低代价值可以大于或等于0。

[0044] 在本文中，为了方便，如图1所示，将以关注的规划空间为二维平面空间为例进行说明，并且相应地，根据本公开的实施例的时空代价图中的每个体素可以表示为栅格或像
素。

[0045] 然而，应当理解，与根据本公开的实施例的时空代价图相关联的规划空间不局限于二维平面空间，并且根据本公开的实施例的时空代价图也不局限于图1所示的形式。例
如，在一个实施例中，时空代价图的每个图层可以是或者可以具有相应的经过渲染的图像，
例如，单通道、三通道或者具有任意通道的二维、三维或更多维的彩色图像、单色图像等。在
另外的实施例中，也可以不实际地生成和/或渲染时空代价图的各个图层。例如，可以使用
例如一个或多个具有适当维度的数组或数据表来表示每个图层Li，并且可以使用例如图层
的编号以及每个体素的位置坐标来获得对应的体素的代价值。

[0046] 图2示出可以用于构建根据本公开的实施例的时空代价图的方法的示例100。

[0047] 如图2所示，根据本公开的实施例的示例方法100可以开始于步骤S110，以获得至少两个离散时刻中的最先离散时刻的预定空间范围内的环境数据。

[0048] 例如，在图1的示例中，离散时刻M1至Mn中的最先离散时刻为离散时刻M1，即，在时间轴上，离散时刻M1先于离散时刻M2至Mn中的任何一个。相应地，在示例方法100的步骤S110
中，可以获得离散时刻M1时的预定空间范围内的环境数据。

[0049] 在一个实施例中，在步骤S110中，可以获得至少在离散时刻M1与预定空间范围内的地图元素有关的地图数据作为环境数据之一。

[0050] 例如，在自主移动装置为地面交通工具(例如，车辆)的情况下，关注的规划空间可以对应于该地面交通工具能够行驶通过的地面空间，相应的地图元素可以包括但不限于例
如车道、车道线、信号灯、人行横道、交叉路口、停止线、车位、标志牌、禁行线、围栏、栏杆、限
高杆、路障、限速带、墙体、建筑物、环岛、花坛、路灯等，并且能够通过解析地图而获得的地
图数据可以包括但不限于与地图中的地图元素的位置(例如，相应的地图元素上的一个或
多个特征点的坐标)、形状(例如，能够描述相应的地图元素的形状的一个或多个特征点的
坐标序列，能够描述相应的地图元素的形状的曲线方程，相应的地图元素的包围盒上的一
个或多个特征点的坐标，相应的地图元素的包围盒的表征方程，等等)、长度、宽度、高度、颜
色、姿态、角度等一个或多个数据，例如，车道的位置、形状、宽度和长度，车道线的位置、形
状、宽度和长度、限速带的位置、宽度、高度和长度，环岛的位置、形状和面积，等等。

[0051] 例如，在自主移动装置为飞行器(例如，无人飞机)的情况下，相应的地图元素可以包括但不限于例如起落台、建筑物、信号塔、水域、山峰、空中悬浮物、空中航道等，并且能够
通过解析地图而获得的地图数据可以包括但不限于与地图中的地图元素的位置、形状、面
积、高度等。

[0052] 根据本公开的实施例的自主移动装置可以包括诸如车辆、水下航行器、船舶、飞行器、机械臂、移动机器人等能够按照规划轨迹和参数而自主移动的任何类型的装置或机器。
可以根据自主移动装置的类型，确定相应的地图元素以及获得与地图元素有关的地图数据
的方法。

[0053] 在一个实施例中，可以通过解析地图(例如，高精度地图)获得与预定空间范围内的地图元素有关的地图数据。在另外的实施例中，可以基于例如来自安装在自主移动装置
上的扫描器(例如，激光雷达、声纳)或摄像头(例如，前置摄像头)或者来自卫星或无人机等
的感测数据(例如，点云、图像、图像序列、声音信号等)推测(例如，通过深度学习网络或三
维重建)预定空间范围内的地图元素有关的地图数据。

[0054] 在预定空间范围内的地图元素至少在一段时间内相对稳定的情况下，可以通过解析离线地图(例如，在M1至Mn的时间段内未更新的离线高精度地图)获得与预定空间范围内
的地图元素有关的地图数据。在另外的实施例中，可以解析更新时间与离散时刻M1最近的
离线地图并获得在离散时刻M1时与预定空间范围内的地图元素有关的地图数据。在另外的
实施例中，还可以根据在离散时刻M1时的感测数据，通过例如三维重建等方式推测出预定
空间范围内的地图元素有关的地图数据。

[0055] 在一个实施例中，在步骤S110中，还可以获得至少在离散时刻M1时与预定空间范围内的一个或多个地图元素有关的实时状态数据作为环境数据之一。例如，可以根据在离
散时刻M1时的感测数据确定信号灯在离散时刻M1时的颜色，也可以基于例如V2X技术从例如
交通指挥中心或基站或指挥塔等获得信号灯在离散时刻M1时的颜色信息。

[0056] 在另外的实施例中，还可以进一步结合与地图元素的状态变化(例如，信号灯的颜色变化)有关的历史数据和/或规则，推测地图元素在M2至Mn中每个离散时刻的状态数据。在
另外的示例中，也可以基于例如V2X技术从例如交通指挥中心或基站或指挥塔等获得地图
元素在M2至Mn中每个离散时刻应当处于何种状态的信息或数据。

[0057] 在一个实施例中，在步骤S110中，还可以通过例如安装在自主移动装置上的扫描器(例如，激光雷达、声纳)或摄像头(例如，前置摄像头)等或者卫星或无人机等，获得在离
散时刻M1时与预定空间范围内的环境有关的实时感测数据作为环境数据之一。

[0058] 在一个实施例中，在离散时刻M1时与预定空间范围内的环境有关的实时感测数据还可以包括在离散时刻M1时的预定空间范围内的绝对静态对象，例如，在离散时刻M1安装在
自主移动装置上的扫描器或摄像头能够感测到的预定空间范围(例如，可以是扫描器或摄
像头的感测范围)内的静态地图元素，例如，限速带、围栏、建筑物、墙体、车道、车道线等。

[0059] 在一个实施例中，在离散时刻M1时与预定空间范围内的环境有关的实时感测数据还可以包括至少在一段时间内(例如，从M1到Mn的时间段内)的静态对象，例如路边的垃圾
箱、停靠在路边的放弃车辆、在一段时间内存在的诸如落石等静态障碍物。

[0060] 在一个实施例中，在离散时刻M1时与预定空间范围内的环境有关的实时感测数据还可以包括位置固定但可能具有不同形态或状态的对象，例如可以变换颜色的信号灯、可
以更改显示信息的指示牌等。

[0061] 在一个实施例中，在离散时刻M1时与预定空间范围内的环境有关的实时感测数据还可以包括在离散时刻M1时处于静止状态或者在某个预定的较小的范围内处于不稳定的
状态但是可能在随时的时刻移动的潜在动态对象，例如停靠在路边的车辆、站立的人、正在
启动的车辆、悬浮在空中的飞行器或动物、处于停泊状态的船只等。

[0062] 在一个实施例中，在离散时刻M1时与预定空间范围内的环境有关的实时感测数据还可以包括至少在离散时刻M1时正在处于运动状态的动态对象，例如行驶中的车辆、行人、
运动中的动物、空中飞行的飞行器或动物等。

[0063] 在另外的示例中，在离散时刻M1时与预定空间范围内的一个或多个地图元素有关的实时状态数据还可以包括另外的数据，而不局限于上述示例。

[0064] 另外，根据不同的实施例，实时感测数据可以包括诸如点云数据等具有任何适当形式和/或包括任何适当内容的感测数据。另外，在一个实施例中，获得在离散时刻M1时的
实时感测数据还可以包括通过例如三维重建等方式重构预定空间范围内的一个或多个实
时感测到的静态/动态对象。

[0065] 在一个实施例中，根据本公开的实施例的方法还可以应用于例如用于算法调试和验证的模拟器或虚拟平台。在该实施例中，在步骤S110中，还可以获得在最先离散时刻M1与
预定空间范围内的模拟环境有关的模拟数据作为环境数据之一。例如，可以通过模拟器生
成在最先离散时刻M1时在预定空间范围内的一个或多个静态和/或动态的虚拟对象，例如
虚拟车辆、虚拟行人、虚拟飞行器、虚拟障碍物等。

[0066] 如前文所述，根据本公开的实施例的示例方法100可以适用于诸如车辆、水下航行器、船舶、飞行器、机械臂、移动机器人等任何类型的自主移动装置，步骤S110中的环境数据
还可以包括对于轨迹的规划和评价有用的任何其他类型和内容的数据，而不局限于上述示
例中的环境数据中的一个或多个，并且可以根据要获取的环境数据的类型、形式、内容等选
择适当的获得数据的方法。

[0067] 在下文中，为了方便，将以车辆在陆面上行驶的情况为例描述根据本公开的实施例的方法和装置。

[0068] 在通过步骤S110获得至少在离散时刻M1时的至少预定空间范围内的环境数据之后，如图2所示，示例方法100可以继续到步骤S120，以根据所获得的环境数据对根据本公开
的实施例的时空代价图的每个图层(例如，图1的示例中的L1至Ln中的每个图层)中的每个体
素的代价值进行初始设置。

[0069] 在一个实施例中，在步骤S120中，可以根据在步骤S110中获得的环境数据确定在预定空间范围内的永久不可行驶区域，并且可以将时空代价图的每个图层(例如，图1中的
Li)中的与所确定的永久不可行驶区域相对应的所有体素的代价值设置为最高代价值。

[0070] 在一个实施例中，永久不可行驶区域可以包括但不限于预定空间范围内的静态障碍物所在的静态障碍物区域、预定空间范围内的禁行区域、预定空间范围内的不可到达区
域以及预定空间范围内的未知区域之中的一个或多个。

[0071] 在另一个实施例中，永久不可行驶区域可以包括但不限于可行驶的通道部分之外的区域，例如地面车道之外的区域和/或车辆在地面上不可行驶通过的区域(例如，障碍物
所在的区域或者被障碍物阻拦而无法行驶通过的区域)。

[0072] 例如，假设图1的示例中的每个图层Li如图3所示，其中，由水平和垂直的虚线定义的每个方格或栅格(例如，图3中的v1、v2、v3)分别对应图层Li的每个体素。应当理解，图3中
的方格或栅格仅仅是示意性的，而不代表体素在每个图层中实际应当具有的实际形状和大
小。

[0073] 另外，如图3所示，假设在步骤S110中获得的在离散时刻M1时的环境数据(例如，通过三维重构)包括大致“十”字形的车道，其中，由任何两个相邻的粗实线(即，车道边界线)
定义的通道表示车辆能够在某一方向上行驶的道路，在道路中间的粗虚线将道路划分成不
同的车道，使得车辆可以在该同一方向的不同车道上切换行驶轨迹。在图3的示例中，还包
括位于十字路口处的一个路障，其将道路分成两个部分并使得与图3中的C1和C2相对应的道
路部分成为不可行驶的区域。

[0074] 对于图3的示例，在步骤S120中，可以将路障所在的区域、道路之外的区域和被路障阻碍而成为不可到达或不可行驶的区域(即，图3中的C1和C2)中的一个或多个确定为在预
定空间范围内的永久不可行驶区域，并且将每个图层Li中的与这些永久不可行驶区域相对
应的所有体素(例如，图3中的v1、v2、v3)的代价值设置为最高代价值(例如，100)。

[0075] 在一个实施例，如图3所示，可以根据在步骤S110中确定的环境数据，例如通过三维重构或贴图等方式，将与环境数据相对应的对象渲染到每个图层Li中或者L1中或者单独
的地图元素渲染图层中。

[0076] 在另外的实施例中，如图4所示，可以针对每个图层的每个体素设置相应的代价值，或者可以将每个体素渲染为与相应的代价值相对应的形式(例如，颜色等)，而不必关心
或实际渲染与环境数据相对应的各个对象。例如，在图4的示例中，可以将具有最高代价值
的体素渲染为使用深色进行填充。

[0077] 在另外的实施例中，也可以不实际地生成时空代价图的各个图层。例如，对于图1中的示例，如前文所述，可以使用例如一个或多个具有适当维度的数组或数据表来表示每
个图层Li，并且可以使用例如图层的编号以及每个体素的位置坐标来获得对应的体素的代
价值。在另外的示例中，可以只记录例如与永久不可行驶区域之外的区域相对应的体素的
代价值。

[0078] 对于每个图层中的与永久不可行驶区域之外的可行驶区域相对应的各个体素，在一个实施例中，可以确定这样的体素到永久不可行驶区域的距离，并且可以根据所确定的
距离来设置这样的体素的代价值，例如，使得越靠近永久不可行驶区域，相应的代价值就越
高。在该实施例中，永久不可行驶区域之外的可行驶区域可以包括至少在离散时刻M1至Mn的
时间段内具有行驶可能性的区域。

[0079] 在一个实施例中，对于可行驶区域中的任一体素Va，可以使用从该体素Va的质心发出的一个或多个射线，通过直线投影的方式确定永久不可行驶区域中到该体素Va最近的体
素Vf，并根据体素Va和体素Vf之间的距离确定体素Va的代价值。例如，对于可行驶区域中的
任何两个体素Va1和Va2，如果体素Va1到体素Vf的距离da1‑f小于或等于体素Va2到体素Vf的距离
da2‑f，则可以将体素Va1的代价值设置为大于或等于体素Va2的代价值。

[0080] 在另外的实施例中，对于可行驶区域中的任一体素，可以确定位于该体素周围且属于永久不可行驶区域中的一个或多个体素。

[0081] 例如，在图5的示例中，使用深色填充的方格对应于具有最高代价值的绝对不可行驶区域中的体素。对于位于可行驶区域的两个体素Va和Vb，可以分别以体素Va和Vb为中心逐
渐地(例如，在图5的示例中，按照一个体素的步幅)扩大检索范围，并确定在每次扩大后的
相应的检索范围内是否变得包括属于永久不可行驶区域中的一个或多个体素。例如，与体
素Va紧邻的周围8个体素(范围Sa1)中未包括属于永久不可行驶区域中的体素，而在按照一
个体素的步幅扩大范围之后，包围体素Va的24个体素(范围Sa2)中有6个体素属于永久不可
行驶区域；与体素Vb紧邻的周围8个体素(范围Sb1)中有3个体素属于永久不可行驶区域。对
于相同的检索范围Sa1和Sb1，Sb1中包括更多的属于永久不可行驶区域体素，因此可以将体素
Vb确定为相比于体素Va更靠近永久不可行驶区域，并且相应地，可以将体素Vb的代价值设置
为大于或等于体素Va的代价值。

[0082] 在另一个示例中，如图6所示，与体素Va紧邻的周围8个体素(范围Sa1)中有1个体素属于永久不可行驶区域，而与体素Vb紧邻的周围8个体素(范围Sb1)中有3个体素属于永久不
可行驶区域，即，对于相同的检索范围Sa1和Sb1，Sb1中包括更多的属于永久不可行驶区域体
素，因此可以将体素Vb确定为相比于体素Va更靠近永久不可行驶区域，并且相应地，可以将
体素Vb的代价值设置为大于或等于体素Va的代价值。

[0083] 在另外的实施例中，还可以结合行进方向或自主移动机的主体朝向等设置可行驶区域的体素的代价值。例如，在图7的示例中，与体素Va紧邻的周围8个体素有2个体素属于
永久不可行驶区域，而与体素Vc紧邻的周围8个体素只有1个体素属于永久不可行驶区域。
然而，按照行进方向(如图7中的箭头所示)，位于体素Va前方的3个体素Vb、Vc和Vd均不属于
永久不可行驶区域，而与体素Vc相关的唯一的属于永久不可行驶区域的体素位于体素Vc的
前方。在该实施例中，可以将体素Vc的代价值设置为大于或等于体素Va的代价值。

[0084] 应当理解，根据本公开的实施例的确定时空代价图的每个图层中的与永久不可行驶区域之外的可行驶区域相对应的各个体素到永久不可行驶区域的距离的方式不限于上
述示例，并且根据本公开的实施例可行驶区域的各个体素到永久不可行驶区域的距离也不
局限于体素的质心到永久不可行驶区域的物理距离或者体素与永久不可行驶区域中的体
素之间的体素数量。

[0085] 如前文所述，在步骤S110中可以获得的环境数据还可以包括与预定空间范围内的一个或多个地图元素在每个离散时刻Mi的状态数据，例如，交通信号灯的颜色。

[0086] 相应地，在一个实施例中，在步骤S120中，还可以获得与预定空间范围内的一个或多个地图元素在每个离散时刻的状态数据(该处理也可以在步骤S110中实现)，并且根据所
获得的状态数据，确定在预定空间范围内在每个离散时刻的暂时不可行驶区域。然后，可以
将时空代价图的每个图层Li中的与相应的暂时不可行驶区域相对应的所有体素的代价值
设置为最高代价值。

[0087] 例如，如图8所示，在该示例的“丁”字路口中设置有一个交通信号灯，该交通信号灯用于指示在相应的时刻是否可以在该丁字路左转，例如，在M1时刻为绿色(即，可以左
转)，在M2至M6期间为红色(即，不可以左转)。于是，时空代价图中的图层L1(与离散时刻M1相
对应)可以例如被渲染为如图9所示，其中，网状阴影部分表示与绝对不可行驶区域相对应
的体素；而时空代价图中的图层L2至L6中的每一个(分别与离散时刻M2至M6相对应)可以例
如被渲染为如图10所示，其中，使用深色填充的部分可以表示与受交通信号灯的影响而成
为暂时不可行驶区域的体素，这些体素的代价值可以被设置为最高代价值。

[0088] 在另一个实施例中，还可以根据所获得的状态数据，确定在预定空间范围内在每个离散时刻的过渡区域。

[0089] 根据不同的实施例，过渡区域可以是在预定空间范围内将在包括相应的离散时刻的预定时间段P1内转换为暂时不可行驶区域期间的可行驶区域，或者也可以是在预定空间
范围内将在包括相应的离散时刻的预定时间段P2内转换为可行驶区域的暂时不可行驶区
域。

[0090] 例如，对于图8的示例中的信号灯，如果该信号灯在M1时刻为绿色(即，可以左转)，在包括时刻M2但不包括时刻M1和时刻M3的时间段P1期间为黄灯，并且在M3至M6期间为红色
(即，不可以左转)。于是，时空代价图中的图层L2(与离散时刻M2相对应)可以例如被渲染为
如图11所示，其中，使用深色填充的部分可以表示与受交通信号灯(黄色)的影响而成为过
渡区域的体素，这些体素的代价值可以被设置为大于最低代价值并且小于或等于最高代价
值。

[0091] 在另外的实施例中，在步骤S120中，还可以根据行驶规则和/或驾驶习惯，设置时空代价图的每个图层Li中的与预定空间范围内的可行驶区域相对应的各个体素的代价值。

[0092] 例如，可行驶区域可以包括可行驶的通道部分，并且在时空代价图的每个图层中，可以使得从通道部分的两侧开始越靠近所述通道部分的中间，相应的体素的代价值越小。

[0093] 例如，在地面交通的情况下，根据驾驶习惯(例如，出于安全性等心理因素)，可能更习惯于使交通工具在道路中间(或按照中间的车道)行驶。相应地，如图12所示，可以使相
对位于道路中间的体素V2的代价值小于或等于相对位于道路两侧的体素V1和V3的代价值。

[0094] 例如，可行驶区域可以包括相邻的可行驶的通道部分，并且在时空代价图的每个图层中，可以使得与一个通道部分相对应的体素的代价值小于或等于与相邻的另一个通道
部分相对应的体素的代价值。

[0095] 例如，在地面交通的情况下，根据很多国家的交通法规，倾向于从左侧车道超车。于是，在图12的示例中，对于分别位于相邻的三个车道(三个邻的可行驶的通道部分)上的
体素V1至V3，可以按照从左到右的次序，将V1至V3的代价值设置为V1≥V2≥V3，即，与左侧车
道(或可行驶的通道部分)相对应的体素的代价值大于或等于与右侧车道(或可行驶的通道
部分)相对应的体素的代价值。对于规定左侧通行的另外一些国家，可以将右侧车道(或可
行驶的通道部分)相对应的体素的代价值设置大于或等于与左侧车道(或相邻的可行驶的
通道部分)相对应的体素的代价值。

[0096] 在另外的实施例中，在步骤S120中，还可以根据环境数据，确定在最先离散时刻M1在预定空间范围内的可行驶区域中的一个或多个动态障碍物，并且将图层L1中，将与所确
定的每个动态障碍物所在的动态障碍物区域相对应的所有体素的代价值设置为最高代价
值。

[0097] 例如，如图13所示，根据在离散时刻M1至Mn中的最先离散时刻M1针对预定空间范围内的环境的实时感测数据(例如，点云数据、所拍摄到的图像或视频、所录制的声音等)，确
定在离散时刻M1在中间车道处存在诸如移动的车辆或行人这样的动态障碍物。例如，可以
确定动态障碍物上的一个或多个特征点或者该动态障碍物的包围盒等，确定该动态障碍物
所在的动态障碍物区域(例如，图13中由粗线矩形包围的障碍物区域)，并且将图层L1中与
所确定的动态障碍物区域相对应的所有体素(例如，图13中由粗线矩形包围的6个体素)的
代价值设置为最高代价值。

[0098] 在一个实施例中，还可以进一步确定图层L1中的与可行驶区域相对应的各个体素到动态障碍物(或者动态障碍物所在的动态障碍物区域)的距离，并且可以将与图层L1中的
与可行驶区域相对应的各个体素的代价值设置为使得越靠近动态障碍物，相应的值越高。
例如，可以参考前文所述的用于确定每个图层中的可行驶区域的各个体素到永久不可行驶
区域的距离的方式，使用类似的方式来确定图层L1中的与可行驶区域相对应的各个体素到
动态障碍物或者动态障碍物所在的动态障碍物区域的距离。进一步地，如图13所示，对于图
层L1中的可行驶区域中的体素V1、V2和V3，可以根据各个体素到障碍物区域的距离，将相应
的代价值设置为V1≤V2≤V3。

[0099] 在另一个实施例中，还可以根据在最先离散时刻M1时的一个或多个动态障碍物，确定图层L1的可行驶区域中被一个或多个动态障碍物阻断而成为暂时不可行驶区域的部
分，并且可以将与图层L1中的与暂时不可行驶区域相对应的所有体素的代价值设置为最高
代价值。

[0100] 例如，如图14所示，在离散时刻M1时检测到在预定空间中存在诸如移动的车辆或行人这样的动态障碍物，即，图14中的分别位于道路的三个车道的障碍物1至3，相应的障碍
物区域如图15中的左斜线阴影部分所示。如图14所示，道路在行进方向(如图14或图15中的
箭头所示)的前方被障碍物1至3阻断而具有一部分暂时不可行驶区域，如图15中被粗线框
包围且用深色填充的部分。相应地，可以将与图层L1中的与障碍物区域以及暂时不可行驶
区域相对应的所有体素的代价值设置为最高代价值。

[0101] 如上所述，根据不同的实施例，在示例方法100的步骤S120中，可以确定和/或渲染时空代价图的与最先离散时刻M1相对应的图层L1中与在离散时刻M1存在于预定空间内的各
种(静态或动态)对象相对应的各个体素(的代价值)，也可以确定和/或渲染时空代价图的
各个图层Li中与预定空间内的静态对相对应的各个体素(的代价值)，还可以确定和/或渲
染时空代价图的各个图层Li中与位置不变但状态(例如信号灯的颜色、栏杆的开合等)随着
不同的离散时刻Mi而具有规律性变化的对象相对应的各个体素(的代价值)。

[0102] 回到图2，在步骤S120之后，示例方法100可以继续到步骤S130。在步骤S130中，对于离散时刻M1至Mn中不同于最先离散时刻M1的任何另一离散时刻，即，离散时刻M2至Mn中的
任何一个离散时刻Mk(2≤k≤n)，根据与离散时刻M1至Mn中先于离散时刻Mk的至少一个在前
离散时刻Mp1、……、Mpr(1≤r至少一个图层Lp1、……、Lpr，对与离散时刻Mk时刻相对应的图层Lk中的一个或多个体素的代
价值进行调整。步骤S130中的处理可以针对时空代价图的图层L2至Ln中的无法在步骤S120
中确定和/或渲染的对象(例如，诸如移动的车辆或行人等动态对象或动态障碍物)所对应
的体素。

[0103] 在一个实施例中，对于图层Lk，可以根据至少一个图层Lp1、……、Lpr，例如根据至少一个图层Lp1、……、Lpr中的体素、在至少一个图层Lp1、……、Lpr中确定/渲染的动态对象或动
态障碍物、动态对象或动态障碍物在至少一个在前离散时刻Mp1、……、Mpr时的位置和/或状
态等，确定障碍物在离散时刻Mk在预定空间范围内可能出现的区域和相应的概率。

[0104] 在一个实施例中，在步骤S130中，可以针对至少一个图层Lp1、……、Lpr执行诸如卡尔曼滤波、互补滤波、α‑β滤波、扩展卡尔曼滤波、施密特扩展滤波、信息滤波、平方根滤波等
时变线性系统的递归滤波，从而获得一个或多个障碍物在离散时刻Mk在预定空间范围内可
能出现的区域和相应的概率，甚至直接获得时空代价图的图层Lk。

[0105] 例如，如图16所示，可以将经过渲染的至少一个图层Lp1、……、Lpr(可以将经过渲染的图层Lp1、……、Lpr中的每个图层视为一个图像)输入给卡尔曼滤波器，并获得一个或多
个障碍物(例如，图16中的障碍物1至x)在离散时刻Mk在预定空间范围内可能出现的区域和
相应的概率。

[0106] 然后，可以根据所确定的概率，设置时空代价图的图层Lk中的与障碍物可能出现的区域相对应的各个体素的代价值。

[0107] 在一个实施例中，可以计算障碍物可能出现的概率在根据最小代价值和最大代价值确定的代价值范围内的投射值，并将图层Lk中的与该障碍物可能出现的区域相对应的各
个体素的代价值设置为投射值。

[0108] 例如，假设最小代价值和最大代价值分别为0和100，并且例如通过卡尔曼滤波预测出某个障碍物(例如，移动的车辆)在离散时刻Mk可能按照50％的概率出现在图17中由粗
线矩形表示的障碍物区域处，则可以将图层Lk中与障碍物区域相对应的各个体素(在图17
中用阴影块表示)的代价值设置为(100‑0)×50％＝50，其中，50为障碍物可能出现的概率
50％在代价值范围[0,100]内的投射值。

[0109] 如上所述，在示例方示100中，可以先初始化分别与每个离散时刻Mi相对应的图层Li，并在步骤S120中确定和/或渲染时空代价图的与最先离散时刻M1相对应的图层L1中与在
离散时刻M1存在于预定空间内的各种(静态或动态)对象相对应的各个体素(的代价值)、时
空代价图的各个图层Li中与预定空间内的静态对相对应的各个体素(的代价值)以及时空
代价图的各个图层Li中与位置不变但状态(例如信号灯的颜色、栏杆的开合等)随着不同的
离散时刻Mi而具有规律性变化的对象相对应的各个体素(的代价值)中的一个或多个；然
后，可以在步骤S130中确定和/或渲染时空代价图的图层L2至Ln中的无法在步骤S120中确定
和/或渲染的对象(例如，诸如移动的车辆或行人等动态对象或动态障碍物)所对应的体素。

[0110] 在另一个实施例中，可以先通过步骤S110和步骤S120生成与最先离散时刻M1相对应的图层L1，然后对于与其他每个离散时刻所对应的图层Lj+1(j是大于或等于1并且小于n
的整数)，可以迭代地执行步骤S130，以通过诸如卡尔曼滤波等时变线性系统的递归滤波并
根据前一图层Lj获得该图层。例如，步骤S130可以形式化地表示为下面的等式：

[0111] Lj+1＝KF(Lj)

[0112] 其中，KF表示例如卡尔曼滤波，。

[0113] 在另外的实施例中，与其他每个离散时刻所对应的每个图层Lj+1均可以基于图层L1来获得。在不同的实施例中，可以根据所采用的时变线性系统的递归滤波的方式来确定
步骤S130中的迭代方式。

[0114] 通过示例方法100，可以构建具有例如n(n≥2)个离散图层的时空代价图。这样的时空代价图的每个图层分别与一个离散时刻相对应，并且每个图层中的每个体素有效地反
映了在相对应的离散时刻时的在时间维度和空间维度这两个维度上的融合代价。

[0115] 另外，根据本公开的实施例的方法(例如，示例方法100)还可以包括确定所构建的时空代价图的至少两个图层的融合图层。融合图层可以综合地反映与多个离散时刻相对应
的时空代价或者在一段时间内的时空代价。

[0116] 图18示出确定与时空代价图的所有图层有关的融合图层的示例。在图18的示例中，体素VL1,q、VL2,q、……、VLn,q、VLF,q分别表示时空代价图的图层L1、L2、……、Ln和融合图层LF
中的与位置q相对应的体素，其中，图18中的粗虚线用于强调这些体素处于不同图层的对应
位置处，并且位置q不局限于图18的示例中的图层的最右上角，而是可以对应于图层的任意
位置，即，例如，VLF,q可以是作为目标的融合图层中的任意一个关注体素。

[0117] 如果体素VL1,q、VL2,q、……、VLn,q中的至少一个的代价值为最高代价值(例如，100)，则融合图层中的关注体素VLF,q的代价值也为最高代价值。

[0118] 如果体素VL1,q、VL2,q、……、VLn,q中的任何一个的代价值均不是最高代价值，则融合图层中的关注体素VLF,q的代价值可以是体素VL1,q、VL2,q、……、VLn,q的代价值的总和与次高
代价值之中的最小值。例如，如果最高代价值为100，则次高代价值可以是(最高代价值‑1)
＝99，于是融合图层中的关注体素VLF,q的代价值可以是Σ1≤i≤nVLi,q和99之中的最小值，即
VLF,q＝min(Σ1≤i≤nVLi,q,99)。

[0119] 应当理解，可以确定时空代价图的任意多个(例如，至少两个)图层的融合图层，并且这些图层对应的离散时刻可以是相继的，也可以是不相继的。

[0120] 另外，根据本公开的实施例的方法(例如，示例方法100)还可以包括根据时空代价图的任何两个图层(不局限于与相继的两个离散时刻相对应的相继的两个图层)，确定与在
这两个图层所对应的两个离散时刻之间的任一时间点相对应的图层。

[0121] 在一个实施例中，可以根据时空代价图中的上述两个图层中的每对对应的体素的代价值的加权和，确定与上述任一时间点相对应的图层中的每个对应的体素的代价值。在
不同的实施例中，可以根据需要来选择不同的权重。

[0122] 图19示出确定与相继的两个离散时刻Mj和Mj+1之间的时间点t相对应的图层L’t的示例。如上所述，根据本公开的实施例的方法可以不局限于与相继的两个离散时刻相对应
的相继的两个图层。

[0123] 在图19的示例中，图层L’t中的体素的Vt,q的代价值以根据下式来确定：

[0124] Vt,q＝αVLj,q+βVLj+1,q

[0125] 其中，α和β分别为权重，VLj,q和VLj+1,q分别表示时空代价图的图层Lj和Lj+1中与图层L’t中的体素Vt,q的位置相对应的位置q处的体素的代价值。

[0126] 在一个实施例中，可以认为时间点t时的情况受到与时间点t更接近的离散时刻的影响较大，或者时间点t时的情况更接近于或更类似于与时间点t更接近的离散时刻时的情
况。

[0127] 在该实施例中，可以比较例如|Mj+1‑t|和|t‑Mj|的值，从而确定t更靠近离散时刻Mj和Mj+1中的哪个。例如，如果t更靠近Mj+1，即|Mj+1‑t|≤|t‑Mj|，则可以选择适当的权重值使
得α≤β，甚至使得α＝0(即，根据VLj+1,q设置Vt,q)；反之，则可以选择适当的权重值使得α≥β。
例如，可以将α和β分别设置为α＝(Mj+1‑t)/(Mj+1‑Mj)并且β＝(t‑Mj)/(Mj+1‑Mj)。

[0128] 在另外的实施例中，也可以认为时间点t时的情况受到与时间点t更远的离散时刻的影响较大，或者时间点t时的情况更接近于或更类似于与时间点t更远的离散时刻时的情
况，从而相应地选择或设置权重值。

[0129] 在另外的实施例中，还可以进一步地考虑其他因素来设置权重值。例如，除了时间因素之外或者在时间因素的基础上，还可以根据体素所在区域的类型或者体素所在区域对
应的对象的类型来选择或设置权重值。

[0130] 由此，可以基于时空代价图的离散结构的图层确定时空代价图的连续时间图层，这对于随后的轨迹规划中的路径采样、曲线拟合、轨迹筛选和评价以及用于补偿采样的不
连续性的非线性优化等处理都将是非常有利的。

[0131] 另外，根据本公开的实施例的方法还可以包括生成与时空代价图相关联的一个或多个代价查询表，其中，每个代价查询表均可以根据自主移动装置的主体朝向角和在预定
空间范围内的位置提供自主移动装置的主体上的每个特征点在时空代价图中占据的所有
体素，从而使时空代价图能够更方便地用于轨迹规划。

[0132] 如上所述，通过根据本公开的实施例的方法，能够提供一种全新的时空代价图，该时空代价图能够有效地融合时间维度和空间维度的代价，进而能够提供全局最优且具有一
致性的规划轨迹。

[0133] 在一个实施例中，可以在一个或多个计算机可读取的非临时性存储介质上存储或实施能够执行上述方法的各个步骤的程序指令，使得这样的非临时性存储介质能够在被计
算机或其他计算装置(例如处理器)读取时提供相应的程序指令，并使得计算机或其他计算
装置能够根据所读取的程序指令执行相应的操作。根据不同的实施例，程序指令能够以诸
如源代码、二进制代码、中间代码等各种形式或各种形式的不同组合而实施或存储在非临
时性存储介质上。

[0134] 图20示出能够应用根据本公开的实施例的方法的示例装置200，该示例装置200可以包括感测器SEN和渲染器REN。

[0135] 感测器SEN可以被配置为获得至少两个离散时刻中的最先离散时刻M1的预定空间范围内的环境数据。在一个实施例中，感测器SEN可以包括诸如雷达、声纳、摄像头等能够感
测周围环境的环境数据的感测装置和感测部件。在另外的实施例中，感测器SEN可以包括能
够解析例如离线高精度地图的地图解析器。在另外的实施例中，感测器SEN还可以包括能够
从模拟器接收模拟数据的接口。

[0136] 在一个实施例中，示例装置200还可以包括一个或多个控制器，以控制感测器SEN执行例如示例方法的步骤S110。

[0137] 渲染器REN可以被配置为根据来自感测器SEN的环境数据，对时空代价图的每个图层中的每个体素的代价值进行初始设置，以及对于不同于最先离散时刻的任何另一离散时
刻，根据与先于另一离散时刻的至少一个在前离散时刻相对应的至少一个图层，对与另一
离散时刻相对应的图层中的一个或多个体素的代价值进行调整。

[0138] 在一个实施例中，渲染器REN可以包括一个或多个处理器，例如，诸如中央处理单元(CPU)和现场可编程门阵列(FPGA)这样的通用处理器或处理装置或者其他专用处理器或
处理装置，并且渲染器REN或者其中的处理器可以被配置为执行例如示例方法100的步骤
S120、S130和/或根据本公开的实施例的方法的步骤S110之外的其他步骤(例如，图层融合、
连续时间图层生成/渲染、查底表生成等)。

[0139] 在一个实施例中，渲染器REN还可以包括一个或多个诸如卡尔曼滤波器、互补滤波器、α‑β滤波器、扩展卡尔曼滤波器、施密特扩展滤波器、信息滤波器、平方根滤波器等时变
线性系统的递归滤波器，以便协助执行例如示例方法100中的步骤S130。

[0140] 应当理解，图20所示的结构仅是示例性的，而非限制性的。根据本公开的实施例的装置还可以具有其他部件和/或结构。

[0141] 例如，根据本公开的实施例的装置可以包括一个或多个处理器(例如CPU和FPGA等通用的处理器或处理装置和/或专用的处理器或处理装置)，并且这样的一个或多个处理器
可以被配置为在启动时至少执行根据本公开的实施例的方法，例如示例方法100。

[0142] 例如，根据本公开的实施例的装置还可以包括I/O接口、网络接口和/或存储器，从而通过有线或无线地方式与其他部件或装置进行信息/数据交互。

[0143] 例如，根据不同的实施例，装置中的存储器可以包括各种形式的计算机可读写存储介质，例如易失性存储器和/或非易失性存储器。易失性存储器例如可以包括随机存取存
储器(RAM)、高速缓冲存储器(cache)、片上存储器等。非易失性存储器例如可以包括只读存
储器(ROM)、硬盘、闪速存储器等。可读写存储介质例如可以包括但不限于电、磁、光、电磁、
红外线、或半导体的系统、装置或器件、或者任意以上的组合。在一个实施例中，存储器可以
存储用于指示装置中的一个或多个处理器执行根据本公开的实施例的方法的步骤的程序
指令。在一个实施例中，存储器还可以存储根据本公开的实施例的方法的执行过程中生成
的中间数据以及通过根据本公开的实施例的方法获得的时空代价图、查询表等数据。

[0144] 贯穿说明书和权利要求书，除非上下文清楚地另有要求，否则措词“包括”、“包含”等应当以与排他性或穷尽性的意义相反的包括性的意义来解释，也就是说，应当以“包括但
不限于”的意义来解释。另外，措词“在本文中”、“上文”、“下文”以及相似含义的措词在本申
请中使用时应当指作为整体的本申请，而不是本申请的任何具体部分。在上下文允许时，在
使用单数或复数的以上描述中的措词也可以分别包括复数或单数。例如，前文所提到的“第
一障碍物”或“第二障碍物”可以指一个或多个的“第一障碍物”或“第二障碍物”，并且“另
一”也可以表示另外的一个或多个。关于在提及两个或多个项目的列表时的措词“或”，该措
词涵盖该措词的以下解释中的全部：列表中的任何项目，列表中的所有项目，以及列表中的
项目的任何组合。另外，措词“第一”、“第二”等旨在用于区分，而不是用于强调次序或重要
程度。

[0145] 虽然已经描述了本公开的一些实施例，但是这些实施例仅作为示例而呈现，而不打算限制本公开的范围。实际上，在本文中所描述的方法和系统可以采用多种其他形式来
实施。另外，可以在不脱离本公开的范围的情况下，在本文中所描述的方法和装置的形式上
做出各种省略、替换和改变。