分析机器人Dijkstra改善算法在机器人避障理由运用学术

论文导读：
摘要： 本文研究了机器人避障问题中如何计算最短路径，建立了相应的数学模型。利用Dijkstra最短路径改进算法对该模型进行求解，解决了由确定起点经过若干目标点到达终点的问题。
Abstract： Author is to set up a corresponding mathematical model by studying how to work out the shortest routes in the robot collision oidance problem. The model is solved by using the shortest routes of improved Dijkstra Algorithm， thus the problem of arriving at the terminal point from the fixed starting point with several target points in the course has been settled.
关键词： 机器人避障；最优化问题；Dijkstra算法
Key words： robot collision oidance；problem of optimization；Dijkstra Algorithm
1006-4311（2013）03-0232-02
1 问题重述
在一个800×800的平面场景图1中，原点O（0，0）点处有一个机器人，它只能在该平面场景范围内活动。该场景图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如表1。
机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。机器人直线行走的最大速度为v0=5个单位/秒，最大转弯速度为v=v（ρ）=■，其中ρ是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。
对场景图中4个点O（0，0），A（300，300），B（100，700），C（700，640），具体计算：机器人从O（0，0）出发，O→A→B→C→O的最短路径。
2 符号说明和基本假设
R：机器人与障碍物的最小安全距离（10个单位）；v0：机器人直线行走的最大速度；v（ρ）：最大转弯速度，其中ρ为转弯半径；L：路径的总长度；di：第i段切线的长度；lj：第j段圆弧的长度；r：转弯半径；k：障碍物上的任意点与行走路径之间的最短距离。基本假设：①机器人抽象为点；②机器人以最大速度v0匀速直线前进，以v（ρ）速度匀速转弯；③机器人除了与障碍物相碰撞的情况以外均正常行走。
3 问题分析
问题要求机器人从O（0，0）出发，绕过障碍物按照一定的行走规则行走。求出O→A→B→C→O的最短路径。要考虑机器人不能与障碍物发生碰撞，始终保持一定的安全距离。考虑到机器人在运动过程中，并非关心所有的障碍物，它仅避开阻碍其向目标点运动的障碍物即可，没有必要将到目标点所有的障碍物考虑进来。机器人经过中间的若干节点按照一定的规则绕过障碍物到达目标点，我们考虑经过障碍物拐弯点的问题，同时也考虑经过路径中的目标点处转弯的问题，利用Dijkstra算法计算出确定起点到达目标点的最短路径。
4 模型的建立
4.1 节点路径图 利用Dijkstra算法计算最短路径之前，首先要给出节点的定义。我们用以下方法定义了节点：每个障碍物的角对应一个节点，该节点在这个角的角平分线上，并且位于角顶点略大于安全距离R（R=10）个单位的位置，这样就避免了机器人和障碍物发生摩擦或碰撞。给平面区域图中每个节点一个标识符，把任意两个节点的连线不经过障碍物的两个节点连结起来，如果连接时和已经连好的路径相交，理论上也可以把该路径加入图中，但这样做并不可取。因为一来这样会加大数据量，给计算处理造成很大的负担，另外，计算处理后期还可以对路径距离进行优化。
如何确定节点的连线经论文导读：的长度，就可以得到路径网络图。如图2所示。其中，图2中圆形障碍物的节点就是该圆的外切正方形的顶点所对应的节点。障碍物与边界相接的交点不计入节点。4.2Dijkstra最短路径改进算法实现我们可以运用经典的Dijkstra最短路径算法。经典的Dijkstra算法是计算对某一确定起点到其它任何一节点的最短路径。本模型只关心从确定
过障碍物或与障碍物小于安全距离安全距离R（R=10）个单位呢？根据障碍物的不同形状设计规则如下：
①检测两个节点的连线是否在障碍物内部。对于三角形的障碍物，即检查两个节点连线的直线方程与三角形三条边的直线方程的联立方程组是否有解；对于正方形、矩形、平行四边形、圆（外切正方形）则检查两个节点连线的直源于：论文格式范文模板www.7ctime.com
线方程与障碍物两条对角线的直线方程的联立方程组是否有解。以上两种情况，如有解说明相交连线与障碍物相交。②检测两个节点的连线与障碍物边界小于安全距离。实际上检查两个节点连线的直线方程与障碍物的节点的距离是否小于安全距离。
在连接好节点的基础上，计算出每条路径的长度，就可以得到路径网络图。如图2所示。其中，图2中圆形障碍物的节点就是该圆的外切正方形的顶点所对应的节点。障碍物与边界相接的交点不计入节点。
4.2 Dijkstra最短路径改进算法实现 我们可以运用经典的Dijkstra最短路径算法。经典的Dijkstra算法是计算对某一确定起点到其它任何一节点的最短路径。本模型只关心从确定起点到另一确定终点的最短路径，没必要计算所有节点。
Dijkstra改进算法的基本思想可以如下：以始发点（假设为uo）为树根，按照据Uo的最短距离以及节点的相邻关系，逐次放入树中．由近至远，直到目标点放入树中，形成最短路树，树上每一个节点与UO的路径都是最短路径，其节点标记与Dijkstra算法完全相同，算法步骤的方法、原理也相同，只是算法的停止条件是目标点是否进入最短路树，而不是把所有节点是否都标记作为运算停止的判断条件，因此计算量则大大减少。经过以上改进Dijkstra算法的初步处理，可以得出最短路径。但此路径多是折线，机器人不能此法行走，我们可以对该路径进行进一步的优化。在机器人行走速度一定的情况下，可以大大减少到达目的地的时间。
优化算法如下：
①初始化，令K=l，p=N，N为节点数；②从k号节点开始，给p节点作连线，检查该连线是否通过障碍物（不能忽略机器人的半径R，否则会发生摩擦或碰撞）。不通过则转④；通过障碍物时，如果p=K+2时，转③，否则p=p-l，转②。③若k=N．转⑤：否则K=k+1，p=N，N=N-[（p-l）-（k+1）+1]，p=n．并对剩余的且大干k的节点进行重新顺序编号，k=k+l，转②。④把该直线作为路径加入图中，删除编号为k+l到p-l的节点和相关边。⑤算法结束。
4.3 最短路径中圆弧长度的计算 最短路径中的直线段长度的计算很简单，根据Dijkstra改进算法计算出节点及其对应的坐标可得。具有圆形限定区域的最短路径是由两部分组成的：一部分是平面上的自然最短路径（即直线段），另一部分是限定区域的部分边界，这两部分是相切的，互相连接的。以上分析表明从起点到目标点无论中间有多少障碍物，最短路径都应该是若干个直线段和圆弧结构所组成，如图3所示。最短路径中圆弧长度的计算即求出圆弧■的长度。
如图3，设Ax■，y■为起点，Bx■，y■为目标点，Cx■，y■和Dx■，y■分别为机器人经过拐点分别于隔离危险线拐角小圆弧的切点，圆心为Ox■，y■，圆的半径为r，角度∠AOB=α，∠AOC=β，∠BOD=γ，∠COD=K。求A■B的长度。
如图3可得有以下关系：AB=■AO=■BO=■，在ΔAOB中：α=arccos■，在RtΔAOC中：β=arccos■，在RtΔBOD中：γ=arccos■，因此，K=2π-α-β-γ。从而可得A■B的长度：
■+■+rK
假设机器人从起点O到到目标点路径一定是由圆弧和线段组成，设有m条直线段，n条圆弧。那么路径总长度L的目标函数可表示为：
minL=■d■+■l■d■∈D，l■∈D。
其中，d■第i段切线的长度，l■表示第j段圆弧的长度。D表示路径集合。
摘自：毕业论文格式设置www.7ctime.com
5 模型的求解
利用Dijkstra改进算法经计算机器人从O（0，0）出发，O→A→B→C→O的最短总距离为：2726.623个单位，路径总时间为：56

5.56秒。机器人从O（0，0）出发，O→A→B→C→O的最短路径图4所示。

6 模型评价
本模型的优点有：①运论文导读：tra改进算法在地震救援中的应用.2008，（22）.周培德.计算几何—算法与设计.北京：清华大学出版社，200

5.上一页123

用多个方案对路径进行优化，在相对优化之中取得最优解；②模型优化后用解析几何进行求解，精确度较高；③模型简单易懂，便于实际检验及应用。本模型的缺陷有：1）此模型适于给予环境先验完全信息的全局规划，对于动态规划却失去了效率。2）在障碍物较多时，且形状不规则时，本模型还需进一步改进。
参考文献：
姜启源.数学模型[M]，北京：高等教育出版社，1993.
邓博斌.Dijkstra改进算法在地震救援中的应用[J].2008，（22）.
[3]周培德.计算几何—算法与设计[M].北京：清华大学出版社，2005.