英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料
IEEE TRANSACTIONS ON CONTROL SYSTEMS TECHNOLOGY, VOL. 17, NO. 5, SEPTEMBER 2009
应用于城市环境的自动驾驶汽车实时运动规划
Justin Teo，Gaston Fiore，Sertac Karaman，Emilio Frazzoli，Jonathan P. How
摘要本文介绍了一种基于快速搜索随机树（RRT）方法的实时运动规划算法，适用于在城市环境中运行的自动驾驶汽车。需要对标准RRT进行改进的原因主要包括：1）需要实时生成动态可行的计划； 2）安全要求;；3）由不确定的行驶（城市）环境所决定的约束。主要的创新点在RRT的框架中使用闭环预测。提出的算法是MIT团队在2007年DARPA城市挑战赛中所用赛车的规划与控制软件核心，车辆展示了完成60英里模拟军事供应任务的能力，同时安全地与其他自主和人类进行交互驱动车辆。
关键词 ：自主性，DARPA城市挑战，动态和不确定环境，实时运动规划，快速搜索随机树（RRT），城市驾驶。
1引言
2007年11月11日，来自世界各地的几款自主知识产权汽车在DARPA城市挑战赛（DUC）中进行了竞争，DARPA是自主地面机器人系列赛的第三批。与以前在沙漠土路上的赛事不同，DUC挑战赛的赛道由多种路况组成，综合了一些特征路况如十字路口，环道，停车场，连续弯道和高速公路等一些在城市和郊区经常出现的路况。道路交通工具的主要特点是引入车流，多达70台机器人和人力车辆同时行进。这导致了无人机器人机器人（和人造车上的机器人）相互作用影响。在具有共同交通和/或交通基础设施的环境中实施这种自主车辆的长期目标是，所有车辆都必须遵守交通法规和道路规则。车辆预计将停留在正确的车道上，在特定速度限制下保持安全速度，在交叉口正确屈服于其他车辆，在安全的情况下通过其他车辆，在需要时识别堵车并执行U型转弯，并停放在一个分配的空间。
开发能够完成DUC的机器人车辆是一项主要的系统工程工作，需要开发和整合在计划，控制和感测[2]，[3]方面最先进的技术。读者参考[3]。关于麻省理工学院车辆Talos的设计和开发的系统级报告。本文的重点是运动规划子系统（或“运动规划器”）和相关联的控制器（与运动规划器紧密耦合）。运动规划器是一个中级规划器，主要接收更上一层，导航层的输入，然后输出指令到底层控制器。给定最新的环境信息和车辆状态，运动规划器计算一个可行的轨迹，以达到由导航器指定的目标点。这种轨迹在避免静态障碍物和其他车辆，遵守道路规则的意义上是可行的。然后将运动规划器的输出发送到控制器，该控制器直接连接到车辆，并且负责执行运动计划。
运动规划子系统设计的主要挑战主要有以下几个因素：1）车辆动力学复杂； 2）在不确定的时变环境中有限的感测能力，例如范围和可见度；3）由道路规则引起的车辆行为的时间和逻辑限制。
文中提出了解决运动规划问题的多种方法，参考文献[1]，[4] - [8]。对于我们的运动规划系统，我们选择在快速探索的随机树（RRT）算法[9] - [11]上构建它，它属于基于增量抽样的方法[7，Sec。 14.4]。这个选择的主要原因是：1）基于抽样的算法适用于非常通用的动力学模型；2）算法的的增量特性使系统更容易满足实时性要求，在线实现，同时保留一定的完整性保证；3）基于采样的方法不需要明确列举约束，而是允许对可能非常复杂的约束进行轨迹检查。
尽管它们具有通用性，但是对于具有复杂和不稳定动态的机器人车辆，例如用于比赛的全尺寸Landrover LR3，对采用基于增量采样的运动规划方法的应用并不简单。例如，车辆动力学的不稳定性需要添加路径跟踪控制回路，其性能通常难以表征。 此外，必须考虑到车速的动量，使得不可能通过逐点约束检查确保碰撞避免。 事实上，据我们所知，RRT已经被限制在模拟或者运动学（基本上是无偏移的）机器人（即通过将控制输入设置为零可以立即停止），并且从未被用于在线规划具有先前特点的机器人车辆系统。
本文设计和实现了基于RRT的高效可靠的通用运动规划系统，用于我们团队参加DUC。特别地，我们提出了一种方法，使得在具有复杂，不稳定的动态和显著漂移的智能车辆上的在线使用RRT，同时在面对不确定性和有限的感测的同时保持安全性。基于对DUC比赛中收集的实际数据的分析，讨论了我们的运动规划系统的有效性。
2 系统建模
本节定义了运动规划问题。车辆具有非线性动力学
（1）
和是系统的状态和输入栏，t=0时为初始输入值。 输入是在（未指定的）有限范围(0, )内设计的。控制输入的界限以及各种驾驶条件的要求，如静态和动态障碍物的避免以及道路规则都可以通过一系列对状态和输入的约束来描述
（2）
随时间变化的序列表达了躲避障碍物的安全区域。 假设运动规划问题的目标区域由较高级别的路线规划者给出。主要目标是在最短的时间内实现这一目标
（3）
规定，空集合的下界是。车辆太靠近某些约束，例如车道边界会产生一些惩罚，这是以功能为模型的。运动规划问题现在定义如下
1）问题2.1（近最小时间运动规划）：
给定初始状态和约束集，
图1 . 闭环预测。
给定一个参考命令，控制器产生高速率车辆命令以用车辆动力学来闭合回路。
求解控制输入序列u(t)，使下面的代价函数取最小值。
同时满足（1）- （3）。
3 闭环动态规划
现有的随机规划算法通过对输入本身进行采样或通过采样配置和反向计算来解决车辆的输入，通常采用查表的方式[9]，[10]，[12] - [14]。本文介绍了闭环RRT（CL-RRT）算法，通过利用低层控制器和闭环动态规划来扩展RRT。与现有工作相反，CL-RRT将输入采样到由车辆和控制器组成的稳定闭环系统[15]。
图1显示了闭环动力学的正向仿真。低级别控制器采用参考命令。对于具有复杂动力学的车辆，其状态尺寸可能相当大，但是参考命令通常具有较小的尺寸。例如，在我们的应用中，参考命令是转向控制器的二维路径和速度控制器的速度命令轮廓。在这种情况下，车辆模型包括七个状态，参考命令由一系列三元组组成，其中x和y是参考路径的位置，是相关联的期望速度。对于城市驾驶，车辆运动（正向或反向）的方向也是参考命令的一部分，但是该方向只需要在每个参考路径中定义一次。
给定参考命令，CL-RRT使用车辆模型仿真前向运行，控制器运行预测状态轨迹。根据车辆和环境限制来检查输出的可行性，例如翻车和避障障碍。
这种闭环方法在与输入到车辆的标准方法相比较时具有几个优点[7]，[13]。首先，CL-RRT通过使用固定控制器，用于具有不稳定动力的车辆，如汽车和直升机。第二，使用稳定控制器保证较小的预测误差，因为它减少了车辆动力学中的任何建模误差对预测精度的影响，并且还拒绝了作用在实际车辆上的干扰/噪声。第三，正向模拟可以处理任何非线性车辆模型和/或控制器，并且所得到的运动通过构造满足（1）。最后，当控制器向车辆提供高速稳定反馈时，闭环系统的单个输入可以产生较长的轨迹（几秒钟）。这需要少得多的样本来构建树，从而提高随机规划方法的效率（例如，每个轨迹长度的样本数）。
4 随机树扩展
总结上一节，CL-RRT算法生成源自目标车辆状态的可行轨迹树，试图达到指定的目标集。在树生长阶段结束时，选择最佳轨迹进行执行，循环重复。本节讨论如何使用第三部分中介绍的前向仿真来生成车辆轨迹树，并确定对现有工作的几个扩展。 算法1显示了树扩展的主要步骤（称为函数）。 与原始RRT算法相似，CL-RRT采样（第1行），选择从（线2）连接的最佳节点，将样本连接到选定节点（第4行），并评估其可行性 7）。线6将新添加的节点与其父节点之间的轨迹分割为（但通常）段，以便将来的样本可以连接到这样的节点，以在树中创建新的分支。
CL-RRT算法与原始RRT的不同之处在于，包括：样本在控制器的输入空间（第1行）中绘制; 执行非线性闭环仿真以计算动态可行轨迹（线5）; 传播确保车辆在轨迹结束时停止和安全（第5行）; 并且通过对目标的另一个正向模拟获得成本估算值（行15）。
图2. 车辆轨迹
是使用车辆动力学模型生成的。然后对生成的轨迹进行可行性和性能评估。
图2示出了由CL-RRT算法的功能生成的树的示例。该树由构成控制器输入的参考路径（橙色）和预测的车辆轨迹（绿色和红色）组成。发现不可行的轨迹标记为红色。树的叶子处的大点表示车辆停止并处于安全状态（在第IV-E节中详细讨论）。鉴于这个基本概要，以下细节更详细地讨论了[13]中RRT方法的附加扩展。
4.1采样策略
在诸如城市驾驶的结构化环境中，以纯粹随机的方式对空间进行采样可能会由于众多的限制而导致大量的浪费样本。已经提出了几种提高效率的方法[16] - [20]。 本小节讨论了一种使用物理和/或逻辑环境偏置高斯采样云以实现复杂演习的实时生成的简单策略。
控制器的参考指令由三元组的有序列表指定，与驱动方向（正向/反向）一起指定。2-D位置点是通过随机采样产生的，并且每个点的相关联的速度指令被确定地设计成在参考命令结束时导致停止状态[15]。每个采样点相对于一些参考位置和标题生成
其中和是具有标准高斯分布的随机变量，是径向标准偏差，是圆周方向上的标准偏差，并且是相对于偏移。通过根据车辆位置和道路规则改变这些参数，可以简单地产生各种机动。
图3. 各种采样云
（点显示在一个规划周期中生成的样本;线显示预测的轨迹）
1）物理环境作为偏差：在一条车道上，抽样开始于沿横向方向随机移动估计的车道中心点，以充分利用车道形状。经过几百个样本，它切换到长而窄的高斯云，其纵轴跟随汽车航向。
2）在交点处，使用宽而相对较短的高斯分布，其覆盖交叉点边界内的开放空间[参见图3（a）]。交叉点中的值设置为与目标的距离，并设置为。 请注意，样品不一定位于泳道内。 这是因为它们仅用于构建参考路径，而重新运行的车辆轨迹可能不会精确地跟踪它。
样品可以由有序的一组点组成, ，称为批量采样。 通过连接这些有序点生成控制器的输入，样本中的第一个点连接到树中的一个节点（第4行）。当预期的轨迹具有一些特定的形状，例如到达具有特定标题的目标时，批量采样是有用的。通过沿着目标标题的方向放置批次样品的最后两点，规划系统可以将飞行物朝向目标航向对齐。
在停车场中，车辆周围和停车位周围都会进行抽样。在车辆周围，使用在车辆方向上的宽而高的高斯分布，而在停车位周围，沿着预定停车位的中心线进行采样。图3（b）表示停车样本的一例。停车区使用的值为米和米。
5 在线重规划
在一个动态和不确定的环境中，由于行驶环境的不断更新，树需要在执行期间继续增长。此外，实时执行要求需要从先前的计算周期重新使用信息[26] - [28]。
算法2显示CL-RRT如何执行树的一部分，并在控制器执行计划时继续生长树。 规划系统以每秒固定的速率将控制器发送给控制器。树扩展继续，直到达到时间限制（第6行）。选择最佳轨迹，并将参考路径发送到控制器执行（第13行）。更新车辆状态和环境后恢复树的扩展（第2行）。
注意，在第7行，选择最佳轨迹时，只考虑以安全状态结束的节点序列。如果没有找到，那么规划系统将向控制器发出紧急制动操作，以尽快使汽车停下来。
5.1 树的继承部分
实施基于RRT的规划系统的一种天真的方法是在每个规划周期建立一个新的树（丢弃旧的），并且独立于当前正在执行的规划来选择执行计划。如果前一个规划周期的树被丢弃，则必须重复几乎相同的计算。在具有有限计算重新源的实时应用中，与使用可用计算来向现有树添加新的可行轨迹的情况相比，这种低效率可能导致相对稀疏的树。另外，如果每个循环都丢弃树，因此执行计划是独立于被执行的计划而选择的，规划系统可以在每个规划周期之间切换不同的边际成本/效用的不同轨迹，从而可能导致波浪状轨迹。
为了解决这些问题，CL-RRT算法维护一个“承诺”轨迹，其结尾与根节点相符。在第一个规划周期之后，将可行的计划发送到控制器执行。从根到下一个节点的部分被标记为已提交。对于下一个规划周期，该节点被初始化为新的根节点，然后删除来自旧根的所有其他子分支，因为这些分支将永远不会被执行。 然后，树生长阶段将继续源自此新根节点的所有后续轨迹。当传播的车辆状态（线3）到达提交的轨迹的结束时，根的最佳子节点被初始化为新的根，并且所有其他的子节被删除。因此，车辆总是朝着树根移动。
这种方法确保从以前的规划周期维护树，并且控制器执行的计划（对应于树的承诺部分）始终是连续的。因为规划系统没有改变对继承部分的裁定，所以重要的是不要在一个动态和不确定的环境中提出一个漫长的轨迹。CL-RRT确保承诺的轨迹不超过1米，如果根的最好的子节远远超过该距离，则通过添加分支点。
5.2 惰性重估
在动态和不确定的环境中，每当更新感知环境时，应重新检查存储在树中的每个轨迹的可行性。 然而，一棵大树可能需要不断重新评估其成千上万的边缘，减少了分析子节的时间。
本文提出的克服这个问题的方法是，只有当选择要执行的最佳轨迹序列时，才能重新确定某一边缘的可行性。如果发现最佳轨迹不可行，则树的不可行部分被删除，并选择下一个最佳序列进行重新评估。 这种“惰性重估”使算法能够主要集中在生长树上，同时确保执
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[140685]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
课题毕业论文、外文翻译、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
