数学建模论文-基于网络图的机器人避障问题.doc

1 基于网络图的机器人避障问题【摘要】本文研究的是机器人避障最短时间路径的问题，总体思想是：根据无约束“混合规划”模型和“floyd算法”，得出各路径的几种短折线路线；其次通过折线路径“切线化”和“弧线化”构造出切线与圆弧的组合路径（即为可视网络图）；最终建立基于网络图的模型，并求解。文中模型的建立与求解均基于无量纲化，所有模型均是以时间最短或路径最短为目标。其中，第二个问题划分为两个问题进行研究。问题（一），根据切线定理把路径优化为直线段和圆弧，建立有约束条件的“网络规划”模型，并利用“贪心算法”计算网络图中的各最短路径，得oa、ob、oc和oabco四条最短路径分别为471.04、852.42、1086.45、2715.24。问题（二），是最短时间的路径问题。根据问题（一）中的可视网络图，以“最短时间的路径”为优化目标，利用“蚁群算法”建立蚁群最优化模型，并求出最短时间对应的路径分别为94.91和473.45。问题（三），是最短时间与路径问题。时间和路径具有相互约束的性质，根据问题（二）中的“蚁群算法”，建立“多目标蚁群优化模型”，并利用lingo编写程序，求出最短时间与路径分别为95.25、472.07。本文在求解过程中，运用lingo实现“混合规划”和c语言实现“贪心算法”，对二者进行综合、比较，使得结果更趋于最优化。关键字：可视网络图; 贪心算法; 混合规划模型; 蚁群算法;多目标优化;1 问题重述一个800800的平面场景图，在原点o(0, 0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述表（参见附件1）。平面场景图中（参见附件2），障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯速度为，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中4个点o(0, 0)，a(300, 300)，b(100, 700)，c(700, 640)，具体计算：(1) 机器人从o(0, 0)出发，oa、ob、oc和oabco的最短路径。(2) 机器人从o (0, 0)出发，到达a的最短时间的路径。(3) 机器人从o (0, 0)出发，到达a的最短时间与路径。2 符号说明符号说 明第个特征顶点标号第个各种点轴坐标第个各种顶点轴坐标机器人是否从顶点到顶点 第与特征顶点的距离出发点到终点的总路径第个k切线圆心第个k切线圆的切点（：起1终2）机器人的最小转弯曲率半径机器人直线行走的平均速度机器人转弯行走的平均速度机器人行走好路途的总时间3模型假设1.假设机器人看作为质点；2.假设机器人在所设的路线行驶顺畅无阻；3.假设机器人在各路况中均以匀速行驶，且其速度为各最大速度；4.假设机器人从二种路况过度无加速度，可直接达到应具有的速度；5.假设机器人行走线路与障碍物间距离小于10单位则碰撞6.假设机器人在途中不会发生故障而影响正常行驶；7.假设机器人能够准确按照设定路线行驶；8.假设可以忽略影响机器人行走非最小转弯半径以及最小安全距离因素；4 问题分析对机器人的最短路径和时间规划问题研究，主要是尽可能短的路径和时间避开要出现的障碍物。从题中可知机器人行走线路与障碍物间距离小于10单位则碰撞，所以把各障碍物的边界扩大10单位。可使用autocad软件画出场景图，由工程制图原理，画出障碍物边界扩大10单位后的新的障碍物边界，特别注意在障碍物顶点处使用圆弧。虚线表示原障碍物边界，实线表示新障碍物的边界如下图1所示。欲使机器人行驶路径避开障碍物必须使它避开各障碍物的特征顶点。各种特征顶点如下图2所示。 图1 新障碍物的边界图 图2 特征顶点标号图机器人行驶路线是由直线段和圆弧组成。使机器人避开障碍物的特征顶点，各特征顶点构造出路径图，转化为无约束最短路径问题，建立无约束规划模型，使用floyd搜索算法求解。然后根据切线定理优化已知的折线路径，构造出折线与圆弧组合的路径，即为可视网络图。问题(一)是最短路径问题，根据切线定理把路线优化为直线段和圆弧，使机器人避开障碍物的特征顶点，建立有约束网络规划模型，根据贪心算法来计算可视网络图中的最短路径。 问题(二)是最短时间的路径问题。机器人oa的路途上，在问题（一）求解的可视网络图的基础上，根据蚁群算法，结合有约束混合规划，建立网络规划模型，求最短时间对应的路径。问题(三)时间和路径作为目标，求时间和路径最短的多目标规划问题。在问题（一）的最短路径模型和问题（二）的最短时间的路径模型的基础上，时间和路径相互约束，建立多目标蚁群优化模型，利用lingo编程求解最短时间与路径的方案。 5 模型准备5.1 ，取值根据工程制图原理，画出新的障碍物边界，各特征顶点标号对应坐标表1所示 。表1 各特征顶点标号对应坐标标号x轴y轴标号x轴y轴标号x轴y轴v100v16227463v31633513v27353v17227537v32550530v323753v18247593v33533593v473237v19393337v34507607v527393v20507233v35277687v6237217v21547337v36363673v753293v22550370v37437673v841793v23497390v38533737v9345220v24247593v39630590v10242293v25100700v40727513v11150445v26247593v41727607v12493132v27173687v42680610v13493207v2829360v43677737v14353233v29510520v44700640v15300300v306304505.2 取值由前面符号说明可知表示机器人是否从顶点到顶点，则引入变量，赋值如下： 5.3 两点之间的距离根据题目中的已知条件，场景图内任意相邻障碍物顶点的距离可用下式计算：我们用matlab编程（参见附录3），计算得到任意机器人有可能行走的特征顶点两点之间的距离如下表2所示。为后面的搜索算法，规划路径做了很好的准备。 表2 特征顶点两点之间的距离表终起点的距离 89 229 165 16552 80 141165 126145路线起点(顶点标号)v1 v1 v2 v2 v3 v4v4 v4v5 v5路线终点(顶点标号)v2 v4 v3 v4 v5 v7 v15 v6 v6 v9终起点的距离 104 187 60 921782 18080 93 111 路线起点(顶点标号)v6 v4 v10 v9 v9 v14 v7v11 v25v14路线终点(顶点标号)v15 v10 v15 v15 v14 v15 v11 v16 v18 v19 终起点的距离10215615637967410256204125路线起点(顶点标号)v15 v14 v19 v21 v18 v17 v17 v17 v18 v22 路线终点(顶点标号)v19v20 v21 v22v16 v16 v26 v24 v23 v30 终起点的距离115 73 99 101203849686 76 89路线起点(顶点标号)v26 v25 v26 v24 v18 v28 v28 v35v36v29 路线终点(顶点标号)v25 v27 v27 v35 v24 v35 v36 v36 v37 v34 终起点的距离103213 215 62 95 30 114 66 9743路线起点(顶点标号)v24 v18 v28 v32 v37 v34 v37 v32 v41 v41 路线终点(顶点标号)v26 v28 v34 v29 v34 v33 v38 v33 v40 v44 6 模型建立与求解6.1 避障问题的总体分析与建模对机器人的避障问题的最短路径和时间规划问题研究，尽可能短的路径和时间避开障碍物。模型建立与求解的总体思想与模型流程如下图3所示。 图3 总体思想与模型流程框图6.2 构造可视网络图通过阅读问题分析，机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，其切线长度作为特定点之间的权值可以构成一个可视网络图。先求各路途比较短的几种折线路径，然后根据切线定理优化已知的那些折线路径，构造出折线与圆弧组合的路径，即为可视网络图。6.2.1 无约束混合规划模型的建立44个特征顶点已经给定利用观察法构造出可能的路径图如下图4所示，为了不与障碍物发生碰撞，机器人在避开这些特征顶点，从图可知即要求出、的几种较短的折线短路径。 图4 机器人可能行驶路径图 从出发点到终点的总路径为，在一定范围的较优规划方案，可设定目标函数量在一定幅值内得各路途比较接近最短路径的几种折线路径求出，可得目标函数： ， 每次从出发点到终点最少要经过一个折线，不可能直接一天直线到达终点: 从出发点到终点的总路径为，且要满足的不等式为： 6.2.2 无约束规划模型的求解运用lingo软件编写floyd算法（参见附件4），求得路径：。特征顶点之间的较短路径的方案，具体方案，以机器人行驶路途的方案路线图如下图4 所示。图4 路途方案路线图6.2.3 切线网络图 在求圆弧的切线的过程中，将各点上的圆弧当做整个圆来求解。特征顶点到圆弧的切线，如图5.2.1所示，点向半径为的圆引切线，设圆心坐标为，则切线满足到圆心的距离为，由下公式可求得两条切线。 圆弧与圆弧的切线，如下图5所示，在两个半径都为的圆上，有4条公切线。设为任意公切线的直线方程，于是其满足到两圆心：、的距离皆为。于是由下公式四条切线的方程在求出切线后，由于切线为机器人的运动路径，固存在一些不符合要求的切线，要将这些切线剔除。切线两个端点是否在障碍物内部或切线是否与障碍物的对角线相交；两个大小相同在同一水平或者竖直位置上，在此种情况下外公切线是重复的。则该切线不符合要求，我们规定对应这段切线的顶点为m（m为无穷大），要将这些切线剔除。通过阅读问题分析出有以下情况我们不能直接采用线圆结构来解决，需要做简单的变换。图5 切线圆结构图我们假设两个圆如上图5所示，其圆心分别为，半径均为,交点，原特征顶点，并设左切点，由几何原理可得各关系式如下： ,将符合要求的切线与这些切线之间转化成图的形式。将弧与弧，起点、终点与弧用切线连接起来，将切点和起点、终点之间相连的切线或弧作为边，其切线长度作为特定点之间的权值可以构成一个可视网络图，如下图6可视网络图是oa路途的直线与圆弧的网络图其他ob、oc和oabco。图6 oa路途可视网络图6.3 问题（一）最短路径问题欲使机器人行驶路径避开障碍物必须使它避开各障碍物的特征顶点，使机器人行驶oa、ob、oc和oabco最短路径，通过阅读问题分析，上述所建的可视网络图其切线长度作为特定点之间的权值。 6.3.1 网络规划模型的建立通过阅读问题分析，机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，其切线长度作为特定点之间的权值可以构成一个可视网络图。而且机器人避开障碍物。机器人从oa、ob、oc和oabco直线与圆弧组成或两个级多个相切的圆弧路径组成的最短路径，设起点直线，为终点直线长，为该切线圆弧长，为多个相切圆相邻圆弧长，为相邻圆弧切点直线长，目标函数：每次从出发点到终点最少要经过一个折线，不可能直接一天直线到达终点: 每个圆弧的半径最小为10个单位：6.3.2 切线网络规划模型的求解将避障路径规划问题利用可视图网络图方式表达后，现在的避障路径规划问题就等价于单源最短路径问题，用贪心算法计算和搜索避障最短路径。贪心算法是图论中求解单源点最短路径的经典方法，它本质上是一类贪心算法。对于这类问题应该想出一个多级解决办法和一种最优的量度标准。方法之一是逐条构造这些最短路径，可以使用迄今已生成的所有路径长度之和作为量度标准，为了使这一量度达到最小，其单独的每一条路径都必须具有最小长度。 算法流程:q.clear(); /初始化数列 q.push(node(u,-3); /将u点放入队列 while(true) u=q.front(); /将时间权值最小的点出队列 q.pop();k=u; / 从某起点到已知终点 r=; / 存放机器人行驶过的且点for(i=1;i=numx;i+) /numx:所有圆弧且点数 if(usedi=true) continue; /已经行驶过的切点不能再行走 if(disxuu.t) /u可以最短时间内没有经过点x r=r+i; /把切点i加到集合r中 if(r!=) /r集合不为空 id=x /(x属于r 且 x切点距离 u最近) else/r集合为空则向外扩展节点 /从u点向外扩展新的切点v1.v2;q.push(node(v,t);/将新节点加入队列 print(); /输出最短路径方案通过该程序对模型的求解输出最短路径方案图如下图7所示。 图7 机器人行驶最短路径方案图通过该程序对模型的求解各路途最短路径值的如下表3和柱状图8所示: 表3 各路途最短路径值表路途oaobocoabco路途标号1234最短总路径q471.04852.421086.452715.24图8 各路途最短路径值柱状图其有约束网络规划模型的求解过程中得出最短路径的圆弧切点和圆心如下表4： 表4 最短路径的圆弧切点和圆心坐标 圆属性圆心x轴104.2279.0252.1213.0307.8220.0448.3y轴190.1300.0343.1475.8427.0530.0274.7起点切点x轴64.250.7269.8216.4292.3230.0439.03y轴200.1305.6281.2457.0393.3529.7357.0终点切点x轴93.7145.1145.1232.1273.2223.3419.4y轴230.2443.7443.7476.5414.4539.4352.3圆属性圆心x轴173.2400.0604.9150.0741.9697.9550.0y轴674.4706.5632.3600.0662.4541.2450.0起点切点x轴95.8362.3539.6144.5696.8737.9606.6y轴670.0673.6739.6591.7647.4548.3393.5终点切点x轴141.1437.3672.6140.0727.5727.4549.4y轴745.0673.1739.7599.4606.6513.3370.06.4 问题（二）最短时间的路径问题最短时间的路径问题是以时间为目标的最优化问题，基于蚁群寻找食物时的最优时间的路径选择问题，可以构造人工蚁群，来解决最优化问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。6.4.1 蚁群最优化模型的建立两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。根据蚁群算法建立最优化模型，网络图表示为一个个目标点的有向图，其中, 是转弯半径。 两特征顶点之间有圆弧切点，其距离为: （注：当时，多个相切的圆弧组成;当时，）行走速度：两点之间行走时间:目标函数为:6.4.2蚁群最优化模型的求解根据蚁群算法，利用matlab编程（参见附录5），可求出路途oa的最短时间的路径。具体给出四种代表性的方案，其中方案四是最有时间的路径，即为最短时间的路径。将四种方案的总路径和总时间求出如下表5和柱状图10所示。表5 总路径和总时间表方案一方案二方案三方案四总时间100.6495.93104.1895.25总路径502.07477.29505.6472.07图10 oa的总时间和总路径图可知方案四是时间最优化的路径，其中方案三是问题一中求解出的最短路径的路线，但此方案不是最优化时间的路径。可以从中直观看出机器人从oa所用的最短时间是94.91，对应的总路径为473.45。最优方案中机器人转弯一次，根据问题（一）建立切线网络图所运用的几何定理计算的圆，圆弧起点和终点坐标，即为左右切点，其值分别为，。6.5 问题（三）最短时间与路径问题最短时间与路径问题是采用多信息素和多启发式信息的方式来求解多目标优化问题。每个目标根据其实际要求，设置该目标相应的启发式信息值和信息素值，设置的方法与单目标优化问题中的设置类似，即针对所有的目标中的某一个目标，对该目标进行启发式信息和信息素值的设置。6.5.1 多目标蚁群优化模型的建立由上述分析引入在模糊理论前提下的多目标蚁群算法，对于求oa的最短时间路径，即必须满足：目标函数： 约束条件：对于启发式信息一般取权重的倒数，并对所有目标的启发式信息进行标准化，通过标准化所有优化目标的启发式信息经过标准化后统一到一个相同的标准下，便于在进行各目标间平等的进行搜索。对于信息素值的初始化，针对每个优化目标，通过利用启发式信息值的最近邻方法求得一个初始最优目标值，并以该值为参数设置信息素的初始值。 在进行参数初始化之后，根据初始启发式值和初始信息素值对每个蚂蚁（即时间路径条件）构建多目标优化问题的可行解。首先，求法采用一种伪随机比例选择机制选择下一个路径节点，位于特征顶点的蚂蚁按下式选择下一特征特征顶点。在每只蚂蚁构建完一个可行解后，立即进行局部信息素更新，对蚂蚁构建的路径上的所有路径段进行各目标的信息素挥发，每只蚂蚁完成局部信息素更新后，开始对可行解进行评估。首先，更新非支配解外部存档，并对外部存档中的所有非支配解进行全局信息素更新，在进行全局信息素更新之后，再根据模糊理论的云模型次支配解模糊评估算法找出所有当前迭代中的次支配解， 最后，在完成次支配解的信息素更新之后，求解算法进入下一次迭代。此算法的流程图如下图11所示，经过若干次迭代后，算法返回一系列非支配解，即算法求出的 pareto 最优解集。 图11 多目标蚁群算法的流程图6.5.2多目标蚁群优化模型的求解为了达到时间与路径最短，我们采用多目标蚁群规划，达到多个目标共同最优。由问题一求得从的最短路径，再结合第二问的图7 oa的总时间时间和总路径图可知，该多目标规划满足的条件为。图12 oa的优化时间和路径的路线图根据多目标蚁群算法，为追求时间和路径等多目标最优，利用lingo编程（参见附录6）计算，可求出路途oa的最短时间与路径。具体方案如上图12所示，给出四种代表性的方案，其方案四是最优时间与路径，即为时间最短和路径最短。从下图13和图14中可知最优总路径和总时间分别为472.07、95.25，此路线有一个圆弧，其圆心,圆弧起点和终点坐标，即为左右切点，其值分别为，。图13 优化方案路线图的总时间 图14 优化方案路线图的总路径7 模型检验与改进7.1 模型检验对问题（一）进行模型结果分析,最小半径的变化对最短路径长和改进度的影响从求解过程中可知，最小转弯半径对最佳路径影响较大。最小转弯半径既反映了机器人灵敏性能，又影响着机器人从出发点到目标点最佳路线总长。机器人越灵敏，其最小转弯半径就越小。当机器人可以折线转弯时，灵敏性能达到最佳，从初始点到目标点最短路径长也会最短。于是引入可该进度来说明机器人的性能提升空间，可该进度定义为：下面考虑最小转弯曲率半径的浮动对最短路径长和改进度的影响，其各相应的变化数据表(参见附件7)，整理数据，生成簇状图如下图15所示： 图15由表格数据和图中信息可得知，最小转弯半径浮动对机器人从出发点到目标点最佳线路总长影响较大。增大最小转弯半径，机器人从分别到目标点的最佳路线总长均变大;减小机器人的最小转弯半径,机器人从出发点到目标点的最佳路线总长变小。图16对机器人性能的衡量可通过机器人的灵活度来分析，通过定义的可改进度可知，机器人越灵活其转弯半径越小，图16中信息恰好说明了这点。纵向比较可知，可该进度与最小转弯半径负相关。横向比较可知，可该进度反映了机器人从出发点到目标点路线可优化度，进而可以确定此模型是较优的。对问题（二），由多目标蚁群算法结合对问题（一）的分析，可判断出结果与模型较优。7.2 模型的探究与改进本文为典型的避障问题，解决避障问题具有很强的现实意义。因此，对此类模型的求解很重要。在本题中障碍物只有12个，按弧线的关系画出从起点到达目标点的路径是有限的，我们完全可以采用穷举法把这些路径列出来，然后比较大小取最小者即可，但是我们可以设想在实际生活中对于未知区域，障碍物则是完全未知的。即需要满足通过的目标就会无限增大，那么再以简单的搜索算法就很难再解决现实问题，因此必须换用其他算法。在对于第二问时间路径两个目标最优时，我们引用了多目标蚁群算法，再次基础上对问题有了较好的解答。不过在对问题的求解时对参数与收敛速度上不能很好的定义。因此应在实际问题的基础上，对多目标的遗传算法进行进一步改进。9 参考文献 1 姜启源，谢金星，叶俊，数学模型，高等教育出版社，2004。2 孙祥，matlab 7.0基础教程,北京：清华大学出版社，2005。3 胡运权， 运筹学基础及运用（第四版）m，高等教育出版社，2008。4 丁绪东编著，autocad2007实用教程m，中国电力出版社，2007。5 倪安顺编著，excel 统计与数量方法应用，北京：清华大学出版社，1998。6 谭浩强，c程序设计教程，北京：清华大学出版社，2007。7 王海英，黄强等，图论算法及其matlab实现，北京：北京航空航天大学出版社，2010。8 崔逊学. 多目标进化算法及其应用. 北京: 国防工业出版社, 2006, 39-74 9 戴光明.避障路径规划的算法研究d.华中科技大学，计算机科学与技术学院,2004.10 段海滨.蚁群算法原理及其应用.北京:科学出版社,2005,24-29 11 黎锁平，张秀媛，杨海波，人工蚁群算法理论及其在经典tsp问题中的实现，交运输系统工程与信息，vol.2,no.1,(2002),54-57。附录：附件1： 障碍物描述表编号障碍物名称左下顶点坐标其它特性描述1正方形(300, 400)边长2002圆形圆心坐标(550, 450)，半径703平行四边形(360, 240)底边长140，左上顶点坐标(400, 330)4三角形(280, 100)上顶点坐标(345, 210)，右下顶点坐标(410, 100)5正方形(80, 60)边长1506三角形(60, 300)上顶点坐标(150, 435)，右下顶点坐标(235, 300)7长方形(0, 470)长220，宽608平行四边形(150, 600)底边长90，左上顶点坐标(180, 680)9长方形(370, 680)长60，宽12010正方形(540, 600)边长13011正方形(640, 520)边长8012长方形(500, 140)长300，宽60附件2：平面场景图附件3：距离公式计算 clear,clc c=xlsread(data.xls,sheet1,a1:c18);b=xlsread(data.xls,sheet2,a1:c44);a=c(1:44,:);m,n=size(a);x=a(:,2);xx=x(1:18,:);y=a(:,3);yy=y(1:20,:);plot(xx,yy,r.)hold onplot(x(21:end,:),y(21:end,:),b.)for i=1:mtext(x(i),y(i),num2str(i);endp=b(:,1);q=b(:,2);zb=c(p,2) c(p,3) c(q,2) c(q,3);t=sqrt(zb(:,1)-zb(:,3).2+(zb(:,2)-zb(:,4).2);xlswrite(data.xls,t,sheet2,c1)附件4：flody算法model:sets:jw/1.20/:;lk/1.92/: w ;links(jw,lk): t,x;endsetsdata:!t=ole(distc.xls,data);w=ole(d:2011facs92.xls,data);t=ole(d:2011t2092.xls,data);ole(d:2011taa.xls,$a$1:$cn$20)=x;enddatainit:endinitobjmin=k;!for(links(i,j):x(i,j)*t(i,j)=0);for(lk(j)|j #ne# 28 #and# j #ne# 29 #and# j #ne# 38 #and# j #ne# 39 #and# j #ne# 61 #and# j #ne# 92: sum(jw(i):x(i,j)*t(i,j)=3);for(jw(i): sum(lk