机器人的避障方法可以被粗糙的分为两类:全局路径规划方法和局部路径规划方法。典型的全局路径规划算法有road-map,cell decomposition 和势能场等方法(see 【10】 for an overview and futher references)。这些方法通常假设预先已知一个完备的地图。The advantage of global approaches lies in the fact that a complete trajectory from the starting point to the target point can be computed off-line。不过这些方法对具有较快速度的动态障碍物效果很差。Their strength is global path planning。除此之外,当全局地图是不准确的或者并不是完全已知的时候(特别是在复杂的室内环境中),这些方法被证明存在较大问题。Hu/Brady, Moravec and others【5,11】, have shown how to update global world models based on sensory input, using probabilistic representations。全局路径规划方法的第二个缺点是它们通常很慢(由于机器人运动规划的复杂性)【12】。This is particularly problematic if the underlying world model changes on-the-fly, because of the resulting need for repeated adjustments of the global plan。在上述的场景中,重复进行全局路径规划算法代价比较大。
在参考文献【2】中,提出了“vevtor field histogram”方法,这个方法是对“virtual force field histogram”【1】的扩展。这个方法使用占据栅格地图(基于超声波传感器数据生成和不断更新)构建了机器人周边的环境。Occupancy information is transformed into a histogram description of the free space around the robot,which is used to compute the motion direction and velocity for the robot。综上所述,局部路径规划算法计算速度很快,并且能够快速的适应环境中不可预知的变化。
大部分局部路径规划算法一般通过两个阶段生成运动指令【1,2,8】。在第一个阶段确定机器人的方向。在第二个阶段则生成相应的the steering commands(使得机器人在相应方向上运动)。严格来讲,如果施加给机器人上的力是无穷大的,那么以上的这些方法都是非常合适的。然而由于机器人会受到加速度的约束,因此必须要考虑the impulse of the robot。
举个例子,如图2所示,一个具有较大前向速度的机器人在走廊中进行运动,其中目标点则在它右侧的一个门内。很明显,此时最优的方向应该是右转。但如果不考虑无法给机器人一个无穷大的力进行右急转这一点的话,机器人就会撞到右边的墙上。 By only considering the admissible velocities in the dynamic window our method detects that the robot cannot perform the sharp turn。这时,机器人就会还保持着当前的直线运动,最终也就不会撞到墙上了。
3 运动方程
这部分主要描述了机器人的基本运动学方程【4】。The derivation begins with the correct dynamic laws, assuming that the robot's translational and rotational velocity can be controlled independently (with limited torques)。为了使运动学方程更加实用,我们另外假设了在很短的一段时间内机器人的速度为一个恒定值。基于以上的这些假设,我们发现机器人的运动轨迹是由有限段的圆弧组成的。由于计算圆是否与障碍物相交是非常简单的一件事情,因此采用圆弧表示机器人的运动轨迹能够十分方便的进行碰撞检测。最后我们也推导出了逼近误差的上界。The piecewise circular representation forms the basis of the dynamic window approach to collision avoidance, described in Section 4。
3.1 通用的运动学方程
令 、和分别代表机器人在世界坐标系下的机器人t时刻的坐标和方位角。这个状态空间包含了机器人的运动学属性。The motion of a synchro-drive robot is constrained in a way such that the translational velocity always leads in the steering direction of the robot, which is a non-holonomic constrain【10】。令 和分别代表机器人在世界坐标系下的机器人在和时刻横坐标, 和分别代表机器人在世界坐标系下的机器人在和时刻纵坐标,相应的, 和分别代表机器人在时刻的平移速度和旋转速度。和是关于、和的函数:
由于硬件数字电路的性能限制,所以我们能够设置的电机电流是存在一个范围的(这同时也意味着加速度有一个上下限)。因此,方程(3) can be simplified by assuming that between two arbitray points in time, and , the robot can only be controlled by finitely many acceleration commands。令表示时间段的数量,时间段[, ](其中)内的平移加速度和旋转加速度为常数和,和(其中);然后基于每一个时间段内的加速度都是常数这一假设对方程(3)进行离散,最后得到的机器人运动学方程如方程(4)所示:
我们注意到,在方程(5)和(9)中,除了初始条件外,机器人的运动轨迹是由机器人的速度控制的。当我们进行控制机器人的时候,since the dynamic constraints of the robot impose bounds on the maximum deviation of velocity values in subsequent intervals,因此我们不可能随意的给机器人一个任意的速度。
3.3 逼近误差的上界
Obviously, the derivation makes the approximate assumption that velocities are piecewise constant within a time interval。This error is bounded linearly in time between control points, ,a fact which will be used below for modeling uncertainty in the robot's position。
令和分别代表了在时间段[, ]内的X轴和Y轴误差。另外令。The deviation in the direction of any of the two axes is maximal if the robot moves on a straight trajectory parallel to that axis(意思就是沿着X或者Y轴线直行的时候逼近误差最大)。Since in each time interval we approximate by an arbitrary velocity ,an upper bound of the error and for (i+1)-th time interval is governed by , ,which is linear in 。
以上完成了对机器人运动的推导。总结一下:经推导机器人的运动轨迹可以近似由一系列的圆弧组成,and we have derived a linear bound on the error due to an approximate assumption made in the derivation (速度为常数假设)。
4 动态窗口法
动态窗口法直接在速度空间中搜索机器人的控制指令。The dynamics of the robot is inporporated into the method by reducing the search space to those velocities which are reachable under the dynamic constraints(意思是考虑了运动学特性后可以减小了需要搜索的速度空间)。除此之外,我们只考虑那些遇到障碍物能够保证停下来的速度。对速度空间的裁剪是在算法的第一步完成的。在算法的第二步我们会选择那些令目标函数值最大的速度。A Brief outline of the different parts of one cycle of the algorithm is given in 图 3。在我们当前的实现中执行上述一个周期需要大概0.25s的时间。
在本文的剩余部分我们将使用图2为例来阐述DWA算法的不同部分。
4.1 搜索空间
4.1.1 圆弧轨迹
在第3章我们得到了这么一个结论:机器人的运动轨迹能够使用一系列的圆弧近似。在本文的剩余部分我们称这些圆弧为curvatures。每段curvature 是由一对速度向量唯一确定,我们称这些速度向量为速度。To generate a trajectory to a given goal point for the next time intervals the robot has to determine velocities , one for each of the n intervals between and (意思是说找到一条去目标点的轨迹就是确定在每个时间段内速度)。当然以上的前提是轨迹不会与障碍物相交。需要搜索的空间大小与时间段的数量成指数关系。
To make optimization feasible, DWA只着重考虑第一个时间段内的速度,然后假设剩余段的速度为常数(这也就意味着在内的加速度为零)。以上的这些简化基于以下的这些事实(a) the reduced search space is two-dimensional and thus tractable, (b) the search is repeated after each time interval, and (c) the velocities will automatically stay constant if no new commands are given。
4.1.2 推荐的速度
复杂环境中的障碍物对进一步缩小搜索速度空间也提供了一定的帮助。例如,最大的admissible 速度 on a curvature depends on the distance to the next obstacle on this curvature。Assume that for a velocity the term represents the distance to the closet obstacle on the corresponing curvature( 在第5.2节我们将介绍怎么计算到给定轨迹的距离)。如果机器人能够在撞到机器人停下来,那么这个速度是admissible。Let 和 be the acceleration for breakage。admissible的速度定义如下所示:
上述方程所定义的集合就是机器人遇到障碍物时能够确保停下来的速度。
4.1.3 例1
再次考虑图2给出的例子。图4展示了当加速度和角加速度时admissible速度。此外,黑色的区域代表了non-admissible速度。例如 right wall II 空间内的速度会导致机器人向右急转然后撞到 right wall。The non-admissible areas are extracted from real world proximity information; in this special case this information was obtained from sonar sensors(参考第5部分内容)。
4.1.4 动态窗口
考虑到加速度是有界的这种情况我们可以进一步的把搜索空间缩小为一个窗口(包含了在下次积分时can be reached的速度)。令代表积分时间,代表平移和角加速度,代表机器人实际的速度,那么动态窗口可以被定义为如下:
动态窗口是以机器人的实际速度为中心,并且其窗口大小依赖于机器人的加速度。在动态窗口外面的速度是在下次积分时can not be reached,因而我们也不必考虑它们是否会撞到障碍物。
An exemplary dynamic window obtained in the situation shown in Figure 2, given acceleration of 50 and 60 and a time intercal of 0.25 sec is shown in Figure 5。到长方形两角的点划线代表了can be reached 极限轨迹。
4.2 最大化目标函数
确定速度区域后接下来我们考虑从中选出一组最优的速度。为了综合考虑target heading,clearance, and velocity等准则,我们在中找到令一下目标函数最大的一组速度。当然这是在离散的搜索空间(速度)中完成的。
4.2.1 目标航向
The target heading 度量的是机器人是否朝着目标点移动,它等于,其中是目标点与机器人前进方向的夹角(如图6所示)。由于这个方向随着不同的速度而变化,所以θ是根据机器人的预测位置来计算的。为了确定预测的位置,我们假设机器人在下一个时间间隔内以选定的速度移动。不过在测量机器人真实的target heading的时候,还需要考虑到机器人旋转的动力学特性。因此,在机器人在下一个间隔后施加最大减速度时将到达的位置计算。这使得机器人在规避障碍物的时候可以产生一个朝着目标点的平滑转向。
目标函数的三个分量最后被归一化为[0,1]。这些分量的加权和如图10所示,其中。正如预期的那样,通过门区域的最快轨迹得到的评价最高(与图4相比)。Smoothing increases side-clearance of the robot.。结果目标函数如图11所示,其中的最大值的位置用垂直线表示。
在我们以前的方法(见【3】)中,寻找最佳速度是分两步进行的。在第一步中,只选择了curvatures。This was done by evaluating the target angle and the so-called "n-sec-rule",namely a linear function of the clearance。在第二步,在curvatures上确定最大的速度。Although the resulting behavior of the robot was the same, we decided to use this single step evaluation of the objective function。以上是受到了文献【13】的启发。
4.3 动态窗口的角色
在上一节中,我们介绍了要最大化目标函数从而使得机器人的轨迹平滑和朝向目标前进。为了便于说明上述最大化的目的,我们展示了对于整个速度空间的评价结果。正如第4.1节所述的,速度空间被减少为只有动态窗口中的admissible velocities。In this section we describe how the robot respects the dynamics by this restriction。此外,我们讨论了不同速度和加速度下的the dependency of the behavior。在这两个例子中,时间间隔均固定为0.25秒。
The restricted search space,评价函数和动态窗口均取决于给定的加速度。考虑当加速度为20和30时的速度空间,如图15所示。由于相比之下加速度较小,因而admissible velocities的空间也比图4小一点。所以我们只需要考虑最高速度为60和50的情况。以40的平移速度进行直线运动的动态窗口在这里以白色表示。另外由于依赖于加速度,动态窗口的大小也小了一点。
我们使用obstacle line field 作为局部地图,which is a two-dimensional description of sensory data relative to the robot's position(如图18所示)。we adjusted our sonar sensors such that most erroneous readings indicate a too long distance。To be maximally conservative,每次数据都被转换成一条障碍线。如果传感器产生虚假数据时(例如,due to cross-talk),那么可以需要使用一些更复杂的模型如占据栅格地图【11】。
obstacle line field是由获取的传感器数据构建,并以机器人位置为圆心。It contains a line for each reading of a sonar sensor, which is perpendicular to the main axis of the sensor beam at the measured distance。The length of the line is determined by the breadth of the beam in the given distance。其中机器人与curvatures上的障碍物的距离计算如下:设r为curvatures轨迹的半径,设为obstacle line 交点与机器人的位置的夹角(见图19)。那么距离下一个障碍定义为。
为了让机器人能够对环境的变化做出快速反应,我们限制obstacle lines的数量为72;并且使用了先入先出的策略移除the least actual lines from the obstacle line field。我们发现这些值可以让机器人在速度高达95cm/s的情况下安全行驶,同时在i486计算机上保持0.25s的计算时间。
Speed dependent side clearance。为了使机器人能够根据其与障碍物之间的距离自动调整速度,我们在机器人附近引入了一个safety margin(它随着机器人的平移速度线性增长)。这样可以使得机器人以较快的速度通过走廊,同时在经过门的时候缓慢通行。可能的偏差来自于第3.3节所述的近似误差。
第一个实验展示了动态窗口对机器人行为的影响。图20中的三条路径是在不同动力学约束下机器人典型行为的示例(对于速度和加速度,我们使用了与第4.3节相同的值)。实验的关键是机器人在阴影区域采取的路径。在这个区域的时候机器人会检测到右侧的门并决定是否向右进行急转弯。这个决定很大程序上取决于机器人的动力学特性。只有当实际的速度和可能的加速度允许向右急转弯时,机器人才会直接移动到目标点。这个轨迹在图20中采用虚线表示。In the other two cases the robot decides to pass the opening and moves parallel to the wall until the evaluation of the target heading angle becomes very small。
下一个轨迹是在AAAI'94移动机器人比赛的竞技场上生成的。图23显示了竞技场的占据栅格地图和机器人的轨迹。 Here the robot moved free of collisions in an artificial indoor environment during an exploration run。The target points for the collision avoidance were generated by a global planning algorithm。这里的门宽约80-110。
The authors thank Thomas Hofmann and the other members of the RHINO team for insightful discussion, help and advice.
One author (S.T.) is sponsored in part by the National Science Foundation under award IRI-9313367, and by the Wright Laboratory, Aeronautical Systems Center, Air Force Materiel Command, USAF, and the Defense Advanced Research Projects Agency (DARPA) under grant number F33615-93-1-1330. The views and conclusions contained in this document are those of the author and should not be interpreted as necessarily representing official policies or endorsements, either expressed or implied, of NSF, Wright Laboratory or the United States Government.
8 参考文献
[1] J. Borenstein and Y. Koren. Real-time obstacle avoidance for fast mobile robots in cluttered environments. In Proc. IEEE Int. Conf. Robotics and Automation , volume CH-2876, pages 572{577, 1990.
[2] J. Borenstein and Y. Koren. The vector field histogram - fast obstacle avoidance for mobile robots. IEEE Transactions on Robotics and Automation , 7(3):278{288, 1991.
[3] J. Buhmann, W. Burgard, A.B. Cremers, D. Fox, T. Hofmann, F. Schneider, J. Strikos, and S. Thrun. The mobile robot Rhino. AI Magazine , 16(1), 1995.
[4] L. Feng, J. Borenstein, and H.R. Everett. "Where am I?" Sensors and Methods for Autonomous Mobile Robot Positioning. Technical Report UM-MEAM-94-21, University of Michigan, December 1994.
[5] H. Hu and M. Brady. A bayesian approach to real-time obstacle avoidance for a mobile robot. In Autonomous Robots , volume 1, pages 69{92. Kluwer Academic Publishers, Boston, 1994.
[6] J.L. Jones and A.M. Flynn. Mobile Robots: Inspiration to Implementation . A K Peters, Ltd., 1993. ISBN 1-56881-011-3.
[7] M. Khatib and R. Chatila. An extended potential field approach for mobile robot sensor-based motions. In Proc. International Conference on Intelligent Autonomous Systems (IAS'4) , 1995.
[8] O. Khatib. Real-time obstacle avoidance for robot manipulator and mobile robots. The International Journal of Robotics Research , 5(1):90{98, 1986.
[9] Y. Koren and J. Borenstein. Potential field methods and their inherent limitations for mobile robot navigation. In Proc. IEEE Int. Conf. Robotics and Automation , April 1991.
[10] J. Latombe. Robot Motion Planning . Kluwer Academic Publishers, Boston, MA, 1991. ISBN 0-7923-9206-X.
[11] H.P. Moravec. Sensor fusion in certainty grids for mobile robots. AI Magazine , pages 61{74, Summer 1988.
[12] J.T. Schwartz, M. Scharir, and J. Hopcroft. Planning, Geometry and Complexity of Robot Motion . Ablex Publishing Corporation, Norwood, NJ, 1987.
[13] R. Simmons. The curvature-velocity method for local obstacle avoidance. In Proc. IEEE Int. Conf. Robotics and Automation , 1996.
[14] S. Thrun. Exploration and model building in mobile robot domains. In Proceedings of the ICNN-93 , pages 175{180, San Francisco, CA, 1993. IEEE Neural Network Council.
[15] S. Thrun and A. Bucken. Integrating grid-based and topological maps for mobile robot navigation. In Proceedings of the Thirteenth National Conference on Arti cial Intelligence AAAI-96 , 1996.
[16] S. Thrun, A. Bucken, W. Burgard, D. Fox, T. Frohlinghaus, D. Hennig, T. Hofmann, M. Krell, and T. Schimdt. Map learning and high-speed navigation in RHINO. In D. Kortenkamp, R.P. Bonasso, and R. Murphy, editors, AI-based Mobile Robots: Case studies of successful robot systems . MIT Press, Cambridge, MA, to appear.