​通路规划的行为树（自动驾驶）

小编推荐：

DeepAction八期飞跃计划还剩10个名额，联系小编，获取你的专属算法工程师学习计划（联系小编SIGAI_NO1）

SIGAI特约作者

黄浴

奇点汽车美研中心总裁兼自动驾驶首席科学家

自动驾驶汽车的通路规划

城市环境中自动驾驶车辆的通路规划和决策使得自动驾驶汽车能够找到从A点到B点最安全、最方便、最经济的路线。因为车辆必须识别并绕过所有静态和机动障碍，所以路线变得复杂。今天，主要的通路规划方法包括预测控制模型、可行模型和基于行为的模型。让我们首先熟悉一些术语，以了解这些方法的工作原理。

• 通路（path）是以边界配置开始和结束的连续配置序列。这些配置也称为初始和终止。

• 通路规划（path planning）涉及查找从初始配置到给定配置的几何通路，以便通路上的每个配置和状态都是可行的（如果时间要考虑的话）。

• 机动（maneuver）是车辆运动的高级特征，包括车辆在道路上的位置和速度。机动的例子包括直道、换道、转弯和超车（overtaking）。

• 机动规划（maneuver planning）旨在为车辆做出最佳的高级决策，同时考虑通路规划机制规定的通路。

• 轨迹（trajectory）是车辆访问的一系列状态，由时间参数化，最可能是速度参数化。

•轨迹规划（trajectory planning）或轨迹生成（trajectory generation）是车辆从一个可行状态到另一个可行状态的实时规划，基于其动力学并且受导航（navigation）模式的约束来满足车辆的运动学限制。

下图是自动驾驶自主系统集成的一般性视图：

容器内的块是道路规划过程的一部分。

轨迹生成

对于每个有效目标，我们计算相应的轨迹。我们将命令以一组航点（waypoints）方式发送到控制器，即通常以控制器采样时间的固定间隔分布在轨道上的离散点（按说彼此相近）。

该项目使用四点三次样条生成轨迹:(注意：这个解释在Frenet坐标中，我们使用变量s和d来描述车辆在路（road）上的位置。s坐标表示沿着路的距离（ 也称为纵向位移），d坐标表示路的左右位置（也称为横向位移），r是路的宽度（以米为单位）

• 当前位置（s，d）

• 期望的车道（s + 30，r *车道+（r / 2））

• 期望的车道（s + 60，r *车道+（r / 2））

• 期望的车道（s + 90，r *车道+（r / 2））

然后，控制器必须在两个连续的航点之间重新生成轨迹段，使得操纵器在固定的时间间隔内到达下一个航点，同时保持在结合处限制，速度限制和加速度限制内。但是，控制器甚至不会考虑避免碰撞或其他任何事情。

预测

我们预测环境中的状况（situations），以便安全有效地到达目的地。这个项目不得不建立碰撞检测，即预测两辆汽车可能发生碰撞。

行为

行为规划者需要输入：

• 世界地图，

• 前往目的地的通路

• 预测静态和动态障碍可能会发生什么

输出：建议车辆的机动，其中轨迹规划器负责无碰撞、平稳和安全的行为。

行为树

行为树（BT，behavior tree）是计算机科学、机器人、控制系统和视频游戏中使用的规划执行的数学模型。它们以模块化方式描述有限任务集之间的切换。优势来自于创建由简单任务组成的复杂任务的能力，不必担心简单任务是如何实现的。BT与分层状态机（hierarchical state machine）有一些相似之处，主要区别在于，行为的主要构建块是任务而不是状态。BT易于人类理解，所以不易出错，在游戏开发者社区非常受欢迎。BT已经被证明可以概括其他几种控制架构。

采用行为树的优点

• 有不少状态过渡（state transition）时很有用

• 难以看见的状态机可转换为分层系统（hierarchical system）

• 将条件任务封装并分离到类（class）

• 每项任务轻松自动化测试

• 当任务的通过/失败成为核心部分时性能更好

• 可重用性

• 目标驱动（goal driven）行为的出现

• 多步行为

• 快速

• 从错误中恢复

采用行为树的缺点

• 基于状态的行为笨拙

• 根据外部变化改变行为

• 并没有真正考虑过独特（unique）的情况

• 最多和设计者一样（只需遵循菜单）

复合节点（Composite Node）

复合节点是可以包含一个或多个子节点的节点。他们将按照从头到尾的顺序或随机顺序处理这些子节点（children）中的一个或多个，具体取决于特别讨论的复合节点；并且，在某个阶段，通常由子节点的成功或失败决定，将他们的处理完整（compete）并将成功或失败传递给他们的父节点（parent）。在处理子节点的期间，他们将继续返回“运行（running）“给其父节点。

叶（Leaf）

最低级别的节点类型，无法生成任何子节点。

然而，叶子是最强大的节点类型，您的智能系统将通过它的定义和实现来执行特定的操作和行为或特定角色的测试或操作，这样您的树实际上在做有用的东西。叶节点可以是条件或任务（行动）。

条件

条件可以为成功返回true，否则返回false。

任务

如果完成，任务可以返回true，否则返回false。

序列

在行为树中找到最简单的复合节点，它们的名字说明一切。序列将按顺序访问每个子节点，从第一个开始，当成功时将调用第二个，依此类推子列表。如果任何一个子节点失败，它将立即将失败归还给父节点。如果序列中的最后一个子节点成功，则序列将成功返回其父节点。

重要的是要明确行为树中的节点类型有相当广泛的应用。序列最明显的用途是定义必须完整地完成的任务序列，其中一个任务的失败意味着进一步处理该任务序列变得多余。

下面的示例是Selector层次结构（hierarchy），作为用于通路规划项目行为树的一部分：

执行：这个选择器的主要目标是选择左子节点（检测我们是否有一辆车在面前非常接近，并相应地调整速度）或右子节点（正常驾驶）

当且仅当所有子节点根据有序的执行步骤返回true时，此选择器将返回true：

1. 汽车在第二道（IsCurentLane条件返回true / false）

- （如果此块返回false，那么我们将停止检查此序列中的其余块）

2. 切换车道是安全的（SafeToSwitchLane条件返回true）

- （如果此块返回false，那么我们将停止检查此序列中的其余块）

3. 成功执行切换任务（SwitchLane任务成功执行，返回true）

4. 实现目标（goal）

选择器（Selector）

如果一个序列是一个AND，要求所有子节点返回成功，则选择器将在其任何子节点成功时返回成功，不再处理任何其他子节点。它将处理第一个子节点，如果失败将处理第二个子节点，如果失败将处理第三个子节点，直到成功，此时它立即返回成功。如果所有子节点都失败，它返回失败。这意味着，选择器类似于OR门，并且条件语句可用于检查多个条件以查看它们中的任何一个是否为真。

下面的示例是Sequence层次结构，作为用于通路规划项目的行为树的一部分：

执行：这个选择器的主要目标是选择左子节点（检测在面前是否有一辆车，并相应地调整速度）或右子节点（正常驾驶）

仅当其中一个子节点返回true时，此选择器才会返回true，执行以下步骤：

左子节点（序列）：如果我们面前有一辆车，我们能够调整速度，则返回true

1. 我们面前有车靠近吗？（IsCarCloseBeforeUs条件通过）

- （如果此块返回false，那么停止检查此序列中的其余块）

2. 近似速度

- （如果此块返回false，那么我们将停止检查此序列中的其余块）

3. 开车

- （如果左子节点返回true，那么将停止检查此选择器中的其余块

右子节点（任务）

1. 正常驾驶

优先级选择器（Priority Selector）

非常简单，它与选择器相同，但以某种方式排序。如果使用优先级选择器，则子节点行为排序在列表中并一个接一个地尝试。

在这个项目，使用了一个优先级选择器来选择并优先考虑应该驱动/切换（drive/switch）哪条车道。下面是一张描述此行为的框图：

优先级估计

在这个项目，根据以下公式优先考虑应该开车或切换哪条车道：

其中

Vx - 可以影响我们在车道x的汽车的平均速度（奖励）

Dx - 可以影响我们在车道x的车辆的封闭距离（奖励）

Cx - 车道x前面的车辆数量（惩罚）

奖励越大，惩罚越小，访问车道的优先级越高。

通路规划的行为树架构

下面是完整的通路规划的行为树架构图：

模拟仿真的几分钟视频【3】。

GitHub的实现【2】。

作者简介：

黄浴，奇点汽车美研中心总裁和自动驾驶首席科学家，上海大学兼职教授。曾在百度美研自动驾驶组、英特尔公司总部、三星美研数字媒体研究中心、华为美研媒体网络实验室，和法国汤姆逊多媒体公司普林斯顿研究所等工作。发表国际期刊和会议论文30余篇，申请30余个专利，其中13个获批准。

参考文献

1. 原文：https://medium.com/behavior-trees-for-path-planning-autonomous/behavior-trees-for-path-planning-autonomous-driving-8db1575fec2c

2. GitHub：https://github.com/kirilcvetkov92/Path-planning?source=post_page---------------------------

3. 视频演示：https://www.youtube.com/watch?v=6qxCNcYnzPo

本文为SIGAI原创