一种移动机器人的路径规划算法

一种移动机器人的路径规划算法作者：霍迎辉，张连明（广东工业大学自动化研究所广州510090文章来源：自动化技术与应用 点击数：1419更新时间：2005-1-24摘要：本文提出一种移动机器人路径规划最短切线路径算法。依据此算法，机器人能顺利地避 开障碍物到达目标位置，其原理简单，计算快捷，容易实现。仿真结果验证了它的有效性和实用性。关键词：移动机器人；路径规划；机器人避障1引言移动机器人路径规划问题是指在有障碍物的工作环境中寻找一条恰当的从给定起点到终点的运动 路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物。障碍环境中机器人的无碰撞路径规划是智能机器人研究的重要课题之一，由于在障碍空间中机器 人运动规划的高度复杂性使得这一问题至今未能很好地解决。路径规划问题根据机器人的工作环境模型可 以分为两种，一种是基于模型的路径规划，作业环境的全部信息都是预知的；另一种是基于传感器的路径 规划，作业环境的信息是全部未知或部分未知的。对机器人路径规划的研究，世界各国的专家学者们提出了许多不同的路径规划方法，主要可分为全 局路径和局部路径规划方法。全局路径规划方法有位形空间法、广义锥方法、顶点图像法、栅格划归法； 局部路径规划方法主要有人工势场法。这些方法都各有优缺点，也没有一种方法能够适用于任何场合。本文提出一种最短切线路径的规划方法，其涉及的理论并不高深，计算简单，容易实现，可供侧重 于应用的读者参考。下面将详细介绍该算法的基本原理，最后给出仿真实现的结果。2最短切线路径算法2.1算法基本原理（1）首先判断机器人和给定的目标位置之间是否存在障碍物。如图1所示，以B代表目标位置，其 坐标为（x，y ），以R、A分别代表机器人及障碍物，坐标为（x ，y ）、（x ，y ）Rr和Ra表示机器人BBRRAA和障碍物的碰撞半径，也就是说在其半径以外无碰撞的危险。这里对碰撞半径的选择作出一点说明，碰撞 半径越小，发生碰撞的危险度越大，但切线路径越短；碰撞半径越大，发生碰撞的危险度越小，但同时切 线路径越长。要根据实际情况和控制要求来确定碰撞半径。若机器人与目标位置之间不存在障碍物，机器 人可走直线直接到达目标位置，此时的直线方程可由两点式确定：写成ax+by+c=O的标准形式得：(yjr - y&) ? + (-(2)氏| y U =期一“ 一称,=Xti -顶帝斓体A逸RB旌线的即為为d詁的值M由卜式点知xI + 山斗 4- r I4尼弟/ rr + fr若dRa+Rr，则机器人可沿直线到达目标点而不碰物体A,此时物体A不是障碍物。若dVRa+Rr，机器人走直线可能碰上物体A,此时物体A应被视为障碍物。(4k ,k为待求斜率，联立方程组:1 2fy- ?jf n jt- 心1( -刊卩* 1 y - “F 二(民1 * 恥1CI - !|RC | + |BC |,最短切线路径112 2应为路径2。(2)在切线路径上存在障碍物。可把绕过多个障碍物到达最终位置的任务分割成若干子任务，每个子任务要求绕过一个障碍物。这样，一个子任务就相当于前面只有一个障碍物的情况。以氏、Ci分别表示 第i个子任务的目标点和中途点，执行第i个子任务时，如果在到达Bi的路径上存在障碍物，则增加第i +1个子任务，此时目标点Bi+1就是Bi；如果在到达Ci的路径上存在障碍物，贝吐曾加第i+1个子任务，此 时目标点Bi+1是Ci。以此类推，寻找切线路径直至到达给定的最终目标位置，计算最短切线路径之和即为 所求的最优路径。图3给出了机器人绕过两个障碍物并到达目标位置的行走路径。3实际应用(1) 搬运机器人对于厂房车间的移动搬运机器人，切线路径规划方法是一种可行而且实用的方法。 首先，机器人及障碍物的位置可以实时测得，且障碍物一般为固定不动；其次，障碍物数量固定，形状大 小可预知；再次，搬运的效率要求机器人的行走路径为最短，而且走直线比走曲线更能讲究效率。(2) 足球机器人Mirosot足球机器人为两轮驱动机器人。机器人足球比赛中，双方机器人以及球的 坐标由悬挂在球场上方的摄像头识别并传入计算机，比赛过程中，机器人要把球踢进对方球门而得分。机 器人首先要避开其他机器人并捉到球，根据算法，把球的坐标作为目标位置，把其他阻挡其前进路线的机 器人作为障碍物，进行实时路径规划。出于目的只是避碰，而不是完全不能碰撞(事实上比赛中碰撞是难免 的)，碰撞半径可以尽量选小，刚好包住机器人便足够，这样做虽然碰撞危险度上升，但切线路径可以尽量 缩短。4仿真结果图4是运用该算法在Simurosot 5对5机器人足球仿真比赛平台上进行策略编程并运行得到的仿真 结果。需要说明的是，为了观察的方便，例子中，球和障碍物设为固定不动。但这并非说这算法不能应用 于运动比赛中，算法中各坐标是实时测得的，路径是实时计算的，得到的结果应该是实时有效的。然而基 于比赛过程中运动变化快速，实际效果需经长期试验观察才能看出，而且效果的好坏不但取决于算法的先进与否，在很大程度上还依赖于编程者软件水平的高低。5结论移动机器人路径规划的方法有很多，可以说各有优缺点，也没有一种方法能够适用于任何场合。这 样的结果是，各种新的算法不断涌现，一方面丰富了解决问题的手段，不同的情况总能找到合适的算法； 另一方面也不断吸收新的理论，促进了课题不断向前发展。值得提出的是，一些新的算法不管实用与否， 为了赶潮流，将一些刚刚研究出来的理论成果拿来就用，这些理论要么过于复杂，要么本身并未成熟，结 果得到的算法冗长难懂，不切实际，无法实现。还有一些算法为了让机器人走出一条平滑完美的曲线而牺 牲了速度和时间，这些都是不可取的。应该说，一个好的算法，不在于其包含的理论的高深度，而在于其 实用性；相反，理论简单，计算快捷的算法更容易被接受，关键是要看最后实现的效果。本文介绍的切线 路径算法是一种几何方法，并没有高深的理论，容易理解，便于实现，而且计算简单，能够提高运行效率。 不过，最终运行效果还得依赖于编程水平。参考文献：1 张纯刚基于滚动窗口的移动机器人路径规划J.系统工程与电子技术，2002，24(6)： 63-652 王伟，储林波，马玉林一种改进的机器人路径规划算法J.哈尔滨工业大学学报，1998，30(2): 9798