CVM避障算法 翻译_纽马克的翻译方法
CVM避障算法 翻译由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“纽马克的翻译方法”。
基于曲率速度的局部避障方法(草稿)
作者：Reid Simmons 翻译：Luo Qijun 本文提出了一种新的室内移动机器人的局部避障方法，它将避障问题描述为速度空间的约束优化问题。将速度和加速度的物理限制和障碍物分布的环境约束置于机器人的线速度和角速度上，机器人选择满足所有约束，并使得目标函数最大化的速度指令，目标函数折中考虑速度、安全性和目标方向。这种方法的高效实时的应用，已经经过广泛测试，表明其在办公室环境下可以可靠、平滑而快速的导航。这种避障方法可以作为更复杂导航行为的基础，从简单的漫游到基于地图的导航都可以使用。
1，引言
局部避障算法针对 未知的 或 部分已知的环境。
（1）机器人应该能够安全的导航，即使面临感知器的噪声 和 航迹的错误
（2）机器人应该在试图避障的同时趋向目标；
（3）算法必须高效的运算，以至于实时运行于机器人主机 另外，有一些其他算法没有考虑在内的内容：
（1）机器人的动态性应该纳入计算，使之能够以高速运动于拥挤的环境中（2）算法应该明确的尽量最大化机器人的前进进程（3）算法应该同时控制机器人的方向和速度
我们的方法，CVM算法，针对上述的内容。该算法的主要特点是它在机器人的速度空间操作，而不是Cartesian或者配置空间，它通过最大化目标函数来选择命令，用于综合考虑车体安全性、速度和目标导向性。这种方法认为机器人能够控制线速度和角速度，但是不能瞬间转向。也就是说，它只能沿着圆弧走。满足这种方式的机器人包括差动机器人，差速驱动机器人，和多种 非完整车辆。然而 我们的论述忽略了加速度的影响，实际上，对于以步行速度运行的室内机器人来说，这是一个好的近似。
曲率速度算法通过在速度空间添加约束，并在此空间中选择满足所有约束并且最大化目标函数的点进行工作的。约束条件来源于机器人速度和加速度的物理限制，和表示障碍物分布的传感器数据。后者（对于每个可能的曲率），用于表示机器人在撞上障碍物之前能运行多远。
为了达到实时性能，到障碍物的曲线距离用一个分段函数来近似描述。这种近似将速度空间划分为多个离散的区间，每个区间考虑一个确定的距离。该算法在各个区间中找到一个点，使目标函数最大化。这个全面最大化的点用于操作机器人。几个简单的扩展使该基本算法对于传感器噪声更具鲁棒性，并减小了机器人陷入困境的可能性。在我们室内机器人上的测试证明：它能在有人办公室环境内快速、平滑和安全行驶。相关工作
一些著名的局部避障通过计算机机器人将要朝向的方向进行的，但是没有将车体的动态特性计算在内。例如：势场趋近法使用排斥和吸引特性的向量和来计算期望的机器人朝向。速度控制 通过按势向量大小比例选择速度来确定。在该算法基础上改进得到的向量场直方图方法，通过计算一个一维极性直方图进行的，处理该直方图以检测开放区域以便机器人行进。在方向被选择后，再根据到障碍物的距离按比例选择机器人速度。虽然该方法可以产生平滑的轨迹并能同时处理窄、宽的开放处。就像势场趋近法，它没有把下列情况计算在内：当机器人转向时沿着圆弧移动，而不是沿着直线。在混乱复杂的环境中，它忽略了车辆的动态特性，而这时很关键的。
那些引入车辆动态特性和非完整约束计算的方法已经在线下路径规划中作了研究[]，对于快速的局部避障来说，这些方法通常计算代价太高。
然而，最近报告了一些局部避障方法，通过选择一些驾驶命令而不是行驶方向来引入车辆的动力学特性。驾驶角度场算法，跟我们的算法类似，使用到障碍物的曲率正切 来约束一个连续的空间（在那个情况下的驾驶角度一维空间）。曲率和连接弧的距离，在驾驶角度范围内用于阻止行驶。该算法计算几个距离阈值的约束，并试图行驶到最自由的空间。速度控制是一个在驾驶者模块和局部避障模块间的迭代“商议、谈判”过程，与此相反，在我们的算法中，速度和转向弧度通过仿真选择，速度空间的点使得目标函数最大化。针对室内高速导航，有一个类似的基于速度空间操作的算法，就有人作了更早但是独立的研究。该算法针对受车辆动力学约束的弧线的离散集合，并选择其中一个最接近目标方向，保证机器人不会在几秒行驶范围内不会撞上障碍物。初始方法采用两步趋近法来选择曲率和速度；后来，他们研究出了一步选择曲率和速度的算法[6]。针对室外导航，也有一种类似的的方法[7]。考虑了所有的车体动力学，所以路径不必是一个圆弧，为每条路径计算一个可行度量，并选择其中一个最好的结果。但是这些方法的问题在于：仅仅通过分析弧线的离散集合，好的路径可能淹没在碰撞中，并且不被考虑到。曲率速度法
我们描述局部避障问题为一个在机器人的速度空间内的约束优化问题。机器人的速度空间就是可控制速度的稽核。对于差速驱动机器人来说，就像我们的机器人，速度空间包括线速度和角速度的正交空间。通过约束优化，我们试图使机器人选择某个（tv, rv）对，使得目标函数最大化，同时在允许的速度情况下满足所有的约束。
用这种公式描述局部避障问题有几个优点：首先，通过在速度空间内的计算，我们能够同时控制机器人的速度和朝向，并得到一个直接产生命令用于控制机器人的解决方法。通过将此问题作为一个约束优化问题，我们能够很简单地合并来自于环境和机器人动力学的约束条件，并能够得到使速度和安全折中的描述（公式）（规则）。
首先，我们假设机器人总是沿着圆弧线行驶，该弧线曲率由c = rv/tv得到，正的曲率表示顺时针的移动。所以，速度空间中的每个点，对应于笛卡尔空间中的约束曲率的运动。然而，这实际上是一种近似，如果考虑加速度的影响因素的话，如果在绝大所属室内移动机器人的相对较低速度和高加速度的情况下这些影响都被忽略。[6] 机器人的物理限制包括两种类型的速度空间约束。一个是机器人有最大角速度和线速度：tv=-tv(max), rv=-rv(max).在我们的方案中，我们又加入了一个约束条件：tv〉=0，以此防止机器人的后退运动。角加速度和线加速度的限制，ra（max）和ta(max)构成了另外一些约束。给定机器人当前速度 rv(cur)和tv（cur），和时间间隔T(accel)(基于CVM算法周期来选择)，我们再加入3个约束条件，这些条件给出了在下一时刻可达的速度：
考虑到安全原因，tv的明显的其他约束没有加入。我们试图保证tv=0是速度空间中可以达到的部分。另外一个重要的约束源是由环境障碍物构成的。我们可以按照如下方式将笛卡儿空间障碍物转换为速度空间的约束：首先，转化障碍物到配置空间，并且对所有曲率c,计算机器人在碰到障碍物obs可能行驶的距离dc(c,obs).然后定义每个障碍物在速度空间的距离函数：
给定障碍物集合OBS, 累积距离函数定义为：
最后，由于传感器探测距离的限制（为了避免无限值的计算），我们修剪了函数D，利用某个限制距离L（3m, 在我们的实现中）
通常，计算障碍距离函数dc(c,obs)将会非常复杂，由于任意形状的障碍物。为了解决此，我们将障碍物近似为圆形。这是一个有根据的接近，在给定传感器输入-声纳和激光测距仪的情况下。由于我们的机器人也是圆形，笛卡空间到配置空间的转化仅仅通过机器人的半径增加障碍物的半径。现在，计算dc是直接进行的。由于在原始位置的机器人面向y轴正半轴，给定曲率c在（xj,yj）与障碍物相交，我们可以得到：
给定这些物理的和环境的速度空间的约束，通过优化目标函数来选择机器人的命令。从第1节的要求中，可以清楚的发现目标函数会偏好更高的速度，在碰到障碍物前可以行驶更远距离的曲率，并且试图使机器人面向期望的目标方向。我们利用一个简单的线性目标函数来描述这些准则，其中，每项都要在0和1间进行归一化：
速度项简单地表明了对更快速运行的偏好，而其他的则一般。距离项表明沿着给定曲率rv/tv无碰撞运行更远的距离。朝向项是与目标朝向的偏差，它对期望的目标朝向的速度转动时间Tc后将要达到的朝向之间的区别作了解释。
值表示每一项在目标函数中的相关权重。利用目标函数机器人可以展示不同的行为，这依赖于权重和障碍物分布，从为了避障急转弯的减速到除了为了躲避同一障碍物而进行提前转向外的全速行驶。第6节展示了关于选择权重值对算法敏感性的试验结果。
(在机器人局部坐标内)和机器人如果以rv实时实现
在前述章节中描述的曲率速度法，满足局部避障的所有准则，除了他不是计算高效的外。计算Dlimit 是很困难的，即使在圆形障碍物的简化假设条件下。另外，给定Dlimit的一个通用描述，函数f寻优也是耗时的，即使使用如模拟退伙的近似技术。在这一节里，我们描述了实现细节以解决计算的相关问题。
利用一个区间的有限集合的近似Dlimit可以达到实时性能，这种区间是等距划分的。这种曲率区间集合，通过使用障碍物的切线曲率，将速度空间划分为常量距离的区间，进而划分那些重叠区域，以使 与区间对应的距离是所有重叠区域中的最小距离。最小和最大速度、加速度约束加入到这个空间，并且，对于每个曲率区间，求出在约束上限的最高点（因为使目标函数最大化的点必在上限边界处）。机器人在所有曲率区间中选择使目标函数最大化的命令。
我们通过速度距离函数dv来计算Dlimit。需要注意的是 对于一个给定的障碍物obs，dc(c, obs)在障碍物曲率切线区外是无限大的。所以，我们仅仅需要考虑Cmin和Cmax之间的那些曲率：
交点（用于计算dc）是:
注意：公式6没有定义 障碍物圆覆盖的区域
。因为，在实际中，障碍物和机器人是不可能占据同一位置的，这仅仅会在传感器噪声或者确定障碍时的圆形近似的情况下产生。另外一种方式，我们通过定义半径robs为
（这里e设置为1厘米）来处理这样一个障碍物。那么我们就可以使用公式6来计算所有障碍物的最小最大曲率。
给定切线曲率，第一个近似（接下来将被精确计算）是将dv置为最大至最小曲率间的常量：
每个确定的距离将产生一个障碍物区间的集合。为了计算Dlimit的精确确定近似值，我们通过分裂重叠障碍物区间和用更大的联合距离去除重叠片找到了障碍物区间的最小合并。针对此的一个有效算法使用了一种曲率区间数据结构(,d1,2)其中c1,c2是两个曲率，d1,2时区间内的确定的距离值。从几何学上来说，每个曲率区间定义为速度空间上的一对直线，直线间的距离是确定的值。
最小合并算法从曲率区间个新的曲率区间：
开始，对于每个障碍物，用一对切线曲率与其关联距离算法组成一，根据该区间与已存在区间的关系，修改该区间
将切线曲率间的距离函数近似为常量，不是很合适的，因为dv实际上是完全非线性的。在某些情况下，这种近似太过保守，特别是在两个切线曲率的距离值是非常不同的。更重要的是，这种近似常常太过自由主义，实际最小值可能比每个切线曲率距离都要小。
为了修正这些问题，我们精炼dv的近似为一个分段常量。思想为：将区间
分裂为多个区间，对每个区间计算出一个常量距离值，然后使用上述描述的最小合并算法来近似全部的Dlimit函数。我们的方法是要选择障碍物圆上离原点直线距离最近的一个点，并从该点开始把障碍物划分为四个象限。为最小和最大切线曲率的邻近点，定义曲率区间，每个区间的距离值设为两个端点曲率的最小值。
为了使目标函数最大化，我们注意到：每个曲率区间提供了速度空间的一对线性不等式。在上述章节中描述的速度和加速度约束也是一些线性不等式。因此，我们有了一个线性不等式稽核和一个线性目标函数---一种通常容易求解的形式。然而，在我们的问题里，有一个附加问题的附加结构，它会使的计算更加简化：因为曲率线对间的距离值是常量，目标函数对于tv是单调递增的，对于每个曲率区间的函数优化值，存在于约束线的边界上。这导向了一个非常高效的算法：对于每个曲率区间，在每个关联约束的上边界的顶点计算目标函数，并在所有曲率区间中选择全局最优值（利用一个小的扩张：我们也需要在朝向误差dthata是零，时，计算目标函数）扩展
在前述两节中描述的曲率速度法，有一些实际问题。首先，由于传感器噪声，障碍物可能不是很精确，他们可能在内部显现。因此，我们可能要让机器人与障碍物保持接近，并使之减速，如果不能在他们旁边行驶的话。第二，虽然目标函数通常能够很好的获得趋向目标方向并且躲避障碍物行为，有两种情况不能很好的工作：当所有的选择都一样糟糕时，表示机器人被挂住，和当机器人离目标方向很远时。在这一节内容里，我们描述基本曲率速度算法的简单的扩充，以解决上述每个问题。一个简单的扩充，帮助补偿传感器噪声，它使用一个安全区来生长障碍物。我们使用一个相对小的安全区（5cm）,因为安全区的大小与机器人可通过开放区间宽窄成反比例的。安全区太大，机器人通过房间门和在拥挤的走廊里经过人群会有困难。
另外一个扩充，文献3，6提出，帮助机器人保持远离障碍物（或者，至少，使它更小心，当从障碍物边行驶时），它添加了一个最大的可允许的线速度，该速度与到障碍物距离成比例。特别是，对于每个曲率区间,我们约束最大线速度tv
对于一些曲率区间，距离d 比极点,中的一个或两个都大，表示机器人将擦边障碍物经过，如果它沿着此极点曲率行驶的话。（例如，d1, 的值图3中，比dc(C3,B)大）。虽然添加一个安全区能够有所帮助，我们通过增加一个约束进一步增加了安全性，机器人仅在它离所有障碍物距离至少为S时，才全速行驶。
我们通过首先计算远离障碍物S的曲率，它在距离d正切于曲率c，来确定这个约束:
然后，我们添加约束，线速度减低到由点（）组成的直线下。
这就确保机器人将不会全速行驶，除非它保留与障碍物至少距离S经过。一个类似的约束，使用公式9中的r+S，针对曲率区间的下界被加入。
有时候，使目标函数最优的值使其机器人行驶很慢，或者完全不动。这常常发生，例如，当机器人在三面被障碍物包围而它的目标朝向就在正前方，就在障碍物区域。为了处理这一情况，我们采用了原地转身算法，机器人原定不动并且作旋转直到最好的角速度命令为零。这将允许机器人终于看到前方开放的区间并且向前移动，足够使其移动到距离陷阱外。
最后一个扩充，目标函数权重参数的选择，是必要的。选择的权重工作良好，当机器人面向目标方向很近时（在正负60度以内），但是当它面向相反方向时却效果很差。在这种情况下，我们要强烈鼓励机器人开始转动，从而面向目标方向。我们通过增加朝向项的权重来实现，该权重正比于机器人离目标方向的大小。
特别是，我们用
代替目标函数中的。下一节，讨论各参数值对算法的灵敏性。试验结果
CVM算法已经在在Xavier移动机器人上实现和测试。Xavier是一个四轮同步驱动底盘的机器人，由RWI制造，可以独立控制其线速度和角速度。他使用一圈24个声纳传感器（1-2Hz）和一个30度激光测距仪（5-10Hz）。声纳和激光数据组合起来并采用一个简单的20cm精度histogram grid 文献[2]。
底盘得到8 Hz的航迹推算信息，cvm算法也以此速度运行。但接受到一个新的数据报时，每一个被占的格子单元被转化为自身局部坐标并处理产生曲率约束。一般有15-30个障碍物，产后10-15个不同的曲率区间（由于曲率区间重叠，区间数小于障碍物数）。相应的速度约束被添加进去，最优的（tv，rv）发给底盘计算机。算法（包括感知数据处理）运行于在66MHz主频的486计算机上，大概耗时12毫秒。
CVM依赖一些参数，特别是目标函数中的。为了确定这些参数对算法的灵敏度，我们在仿真环境下做一个一系列测试。环境被设置为测试算法的逃离局部最优和避障趋向目标的能力。每次开始机器人在一个点和给定方向，并向前直线运行，当机器人越过虚线时结束。
改变参数完成了一些列路径。基于完成路径的平均时间，我们总结出算法对于目标朝向权重参数 a3的相对值比较敏感，而对a1, a2的相对值不敏感。如果a3置为0，a3/(a1+a2)的值大于15%的话，算法进展缓慢（机器人常陷入局部陷阱）。在此范围内，每个路径中的标准差比 其值和最优设置的值的差 一般较大，但是在a1>a2时平均稍大。
改变a4执行类似的路径，额外的权值鼓励机器人在远离前进运行。结果显示CVM是相对不敏感的，对于a4>0但小于3（此时，机器人又容易陷入局部）。最优好的设置是a1=0.6, a2 = 0.3, a3 =0.1 a4=1.0(平均完成时间67.5s, 标准10.2s), 该设置用于图8的显示结果。
图9为Xavier的不同运行轨迹。为更好的强调差别，图中，障碍物（2个盒子，一个圆的垃圾罐，一个消防门）用机器人半径进行了生长，而机器人为一个点。在每种情况下，机器人从图上方开始，面向底部，且要求其转90度面向左侧。每种情况下，机器人必须环绕围墙并导航绕过三个离散的障碍物。我们在30，45，60cm/s的速度行驶对CVM算法与60cm/s运行的势场法进行了对比。结果显示，CVM较势场法产生更为显著的平滑轨迹。另外，在更高速度下，机器人保持离障碍物更远，而且路径较为平滑。这主要归结与 “靠近障碍物”约束在高速情况更加重要，这使机器人较早对目标做出响应。
局部避障算法供几个更高级别的行为使用。“漫游”通过设置机器人局部目标朝向为0，这偏向是机器人持续沿着当前方向行驶。“朝向方向”行为通过设置为当前机器人朝向和目标方向的差值来实现。最后，为机器人朝向到局部目标点的角“朝向目标”行为通过变换全局目标位置到机器人坐标框架，并且设置度 来实现。对于最后那个行为，我们需要一个附加的扩充：如果目标点在曲率区间内，其相关距离较到目标点的直线距离小，那么目标朝向项的权重被设置为很高以强烈鼓励机器人瞄向目标行驶。
这些行为，逐个构成基于地图导航规划的基础[文献10，11]。最后系统展示出在人类办公室、走廊环境下的可靠、快速导航。讨论
我们描述了针对局部避障的曲率速度算法，它将此问题视为机器人速度空间的约束优化问题。这种描述的优点包括 同时控制速度和机器人朝向的能力，合成环境和机器人动力学、以及处理速度、安全和目标朝向的平衡能力约束的简化。
CVM实现了实时性能，通过近似化机器人在碰到障碍物前能够行驶多远的弧线距离来实现。近似处理是一个分段常量函数，由到障碍物切线曲率来定义。附加的速度约束被加入，在机器人物理限制和保持远离障碍物的期望的基础上，或者至少慢速行驶当接近障碍物时。
该方法已经被实现，并且在Xavier上进行了测试，Xavier是一个差速驱动机器人（它可以使用差分驱动车，并且是沿圆弧行驶的非完整约束车辆。）实现是高校的，并能使机器人在人员办公室环境下达到60CM/s的速度行驶。速度限制的原因，在于声纳传感器的速率（激光视场范围限制阻碍它成为障碍物检测的主要传感器）。通过提高传感器的检测周期，我们希望达到一米每秒（travel）。
基于该算法的下一步工作包括：找到更好的距离函数的近似方法，尝试更精炼的目标函数。我们也要致力于扩展以曲率为基础的速度空间算法来进行多步导航规划问题。
本文展示了通过考虑测量动力学，和使平衡速度、安全和目标趋向的目标函数最大化，我们可以创造一种高效的、实时的局部避障算法，用于在布满障碍物的环境中产生安全、平滑、快速的轨迹。
