数学建模论文-基于网络图的机器人避障问题.doc
《数学建模论文-基于网络图的机器人避障问题.doc》由会员分享,可在线阅读,更多相关《数学建模论文-基于网络图的机器人避障问题.doc(21页珍藏版)》请在三一文库上搜索。
1、1 基于网络图的机器人避障问题【摘要】本文研究的是机器人避障最短时间路径的问题,总体思想是:根据无约束“混合规划”模型和“Floyd算法”,得出各路径的几种短折线路线;其次通过折线路径“切线化”和“弧线化”构造出切线与圆弧的组合路径(即为可视网络图);最终建立基于网络图的模型,并求解。文中模型的建立与求解均基于无量纲化,所有模型均是以时间最短或路径最短为目标。其中,第二个问题划分为两个问题进行研究。问题(一),根据切线定理把路径优化为直线段和圆弧,建立有约束条件的“网络规划”模型,并利用“贪心算法”计算网络图中的各最短路径,得OA、OB、OC和OABCO四条最短路径分别为471.04、852.
2、42、1086.45、2715.24。问题(二),是最短时间的路径问题。根据问题(一)中的可视网络图,以“最短时间的路径”为优化目标,利用“蚁群算法”建立蚁群最优化模型,并求出最短时间对应的路径分别为94.91和473.45。问题(三),是最短时间与路径问题。时间和路径具有相互约束的性质,根据问题(二)中的“蚁群算法”,建立“多目标蚁群优化模型”,并利用lingo编写程序,求出最短时间与路径分别为95.25、472.07。本文在求解过程中,运用lingo实现“混合规划”和C语言实现“贪心算法”,对二者进行综合、比较,使得结果更趋于最优化。关键字:可视网络图; 贪心算法; 混合规划模型; 蚁群算
3、法;多目标优化;1 问题重述一个800800的平面场景图,在原点O(0, 0)点处有一个机器人,它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物,障碍物的数学描述表(参见附件1)。平面场景图中(参见附件2),障碍物外指定一点为机器人要到达的目标点(要求目标点与障碍物的距离至少超过10个单位)。规定机器人的行走路径由直线段和圆弧组成,其中圆弧是机器人转弯路径。机器人不能折线转弯,转弯路径由与直线路径相切的一段圆弧组成,也可以由两个或多个相切的圆弧路径组成,但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞,同时要求机器人行走线路与障碍物间的最近距离为
4、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 符号说明符号说
5、 明第个特征顶点标号第个各种点轴坐标第个各种顶点轴坐标机器人是否从顶点到顶点 第与特征顶点的距离出发点到终点的总路径第个K切线圆心第个K切线圆的切点(:起1终2)机器人的最小转弯曲率半径机器人直线行走的平均速度机器人转弯行走的平均速度机器人行走好路途的总时间3模型假设1.假设机器人看作为质点;2.假设机器人在所设的路线行驶顺畅无阻;3.假设机器人在各路况中均以匀速行驶,且其速度为各最大速度;4.假设机器人从二种路况过度无加速度,可直接达到应具有的速度;5.假设机器人行走线路与障碍物间距离小于10单位则碰撞6.假设机器人在途中不会发生故障而影响正常行驶;7.假设机器人能够准确按照设定路线行驶;8
6、.假设可以忽略影响机器人行走非最小转弯半径以及最小安全距离因素;4 问题分析对机器人的最短路径和时间规划问题研究,主要是尽可能短的路径和时间避开要出现的障碍物。从题中可知机器人行走线路与障碍物间距离小于10单位则碰撞,所以把各障碍物的边界扩大10单位。可使用AutoCAD软件画出场景图,由工程制图原理,画出障碍物边界扩大10单位后的新的障碍物边界,特别注意在障碍物顶点处使用圆弧。虚线表示原障碍物边界,实线表示新障碍物的边界如下图1所示。欲使机器人行驶路径避开障碍物必须使它避开各障碍物的特征顶点。各种特征顶点如下图2所示。 图1 新障碍物的边界图 图2 特征顶点标号图机器人行驶路线是由直线段和圆
7、弧组成。使机器人避开障碍物的特征顶点,各特征顶点构造出路径图,转化为无约束最短路径问题,建立无约束规划模型,使用Floyd搜索算法求解。然后根据切线定理优化已知的折线路径,构造出折线与圆弧组合的路径,即为可视网络图。问题(一)是最短路径问题,根据切线定理把路线优化为直线段和圆弧,使机器人避开障碍物的特征顶点,建立有约束网络规划模型,根据贪心算法来计算可视网络图中的最短路径。 问题(二)是最短时间的路径问题。机器人OA的路途上,在问题(一)求解的可视网络图的基础上,根据蚁群算法,结合有约束混合规划,建立网络规划模型,求最短时间对应的路径。问题(三)时间和路径作为目标,求时间和路径最短的多目标规划
8、问题。在问题(一)的最短路径模型和问题(二)的最短时间的路径模型的基础上,时间和路径相互约束,建立多目标蚁群优化模型,利用Lingo编程求解最短时间与路径的方案。 5 模型准备5.1 ,取值根据工程制图原理,画出新的障碍物边界,各特征顶点标号对应坐标表1所示 。表1 各特征顶点标号对应坐标标号X轴Y轴标号X轴Y轴标号X轴Y轴v100v16227463v31633513v27353v17227537v32550530v323753v18247593v33533593v473237v19393337v34507607v527393v20507233v35277687v6237217v2154733
9、7v36363673v753293v22550370v37437673v841793v23497390v38533737v9345220v24247593v39630590v10242293v25100700v40727513v11150445v26247593v41727607v12493132v27173687v42680610v13493207v2829360v43677737v14353233v29510520v44700640v15300300v306304505.2 取值由前面符号说明可知表示机器人是否从顶点到顶点,则引入变量,赋值如下: 5.3 两点之间的距离根据题目中的已知条件
10、,场景图内任意相邻障碍物顶点的距离可用下式计算:我们用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 V7
11、V11 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 V2
12、4 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 构造可视网络图通过阅读问题分析,机器人不能折线转弯,转弯路径由与直
13、线路径相切的一段圆弧组成,其切线长度作为特定点之间的权值可以构成一个可视网络图。先求各路途比较短的几种折线路径,然后根据切线定理优化已知的那些折线路径,构造出折线与圆弧组合的路径,即为可视网络图。6.2.1 无约束混合规划模型的建立44个特征顶点已经给定利用观察法构造出可能的路径图如下图4所示,为了不与障碍物发生碰撞,机器人在避开这些特征顶点,从图可知即要求出、的几种较短的折线短路径。 图4 机器人可能行驶路径图 从出发点到终点的总路径为,在一定范围的较优规划方案,可设定目标函数量在一定幅值内得各路途比较接近最短路径的几种折线路径求出,可得目标函数: , 每次从出发点到终点最少要经过一个折线,
14、不可能直接一天直线到达终点: 从出发点到终点的总路径为,且要满足的不等式为: 6.2.2 无约束规划模型的求解运用Lingo软件编写Floyd算法(参见附件4),求得路径:。特征顶点之间的较短路径的方案,具体方案,以机器人行驶路途的方案路线图如下图4 所示。图4 路途方案路线图6.2.3 切线网络图 在求圆弧的切线的过程中,将各点上的圆弧当做整个圆来求解。特征顶点到圆弧的切线,如图5.2.1所示,点向半径为的圆引切线,设圆心坐标为,则切线满足到圆心的距离为,由下公式可求得两条切线。 圆弧与圆弧的切线,如下图5所示,在两个半径都为的圆上,有4条公切线。设为任意公切线的直线方程,于是其满足到两圆心
15、:、的距离皆为。于是由下公式四条切线的方程在求出切线后,由于切线为机器人的运动路径,固存在一些不符合要求的切线,要将这些切线剔除。切线两个端点是否在障碍物内部或切线是否与障碍物的对角线相交;两个大小相同在同一水平或者竖直位置上,在此种情况下外公切线是重复的。则该切线不符合要求,我们规定对应这段切线的顶点为M(M为无穷大),要将这些切线剔除。通过阅读问题分析出有以下情况我们不能直接采用线圆结构来解决,需要做简单的变换。图5 切线圆结构图我们假设两个圆如上图5所示,其圆心分别为,半径均为,交点,原特征顶点,并设左切点,由几何原理可得各关系式如下: ,将符合要求的切线与这些切线之间转化成图的形式。将
16、弧与弧,起点、终点与弧用切线连接起来,将切点和起点、终点之间相连的切线或弧作为边,其切线长度作为特定点之间的权值可以构成一个可视网络图,如下图6可视网络图是OA路途的直线与圆弧的网络图其他OB、OC和OABCO。图6 OA路途可视网络图6.3 问题(一)最短路径问题欲使机器人行驶路径避开障碍物必须使它避开各障碍物的特征顶点,使机器人行驶OA、OB、OC和OABCO最短路径,通过阅读问题分析,上述所建的可视网络图其切线长度作为特定点之间的权值。 6.3.1 网络规划模型的建立通过阅读问题分析,机器人不能折线转弯,转弯路径由与直线路径相切的一段圆弧组成,其切线长度作为特定点之间的权值可以构成一个可
17、视网络图。而且机器人避开障碍物。机器人从OA、OB、OC和OABCO直线与圆弧组成或两个级多个相切的圆弧路径组成的最短路径,设起点直线,为终点直线长,为该切线圆弧长,为多个相切圆相邻圆弧长,为相邻圆弧切点直线长,目标函数:每次从出发点到终点最少要经过一个折线,不可能直接一天直线到达终点: 每个圆弧的半径最小为10个单位:6.3.2 切线网络规划模型的求解将避障路径规划问题利用可视图网络图方式表达后,现在的避障路径规划问题就等价于单源最短路径问题,用贪心算法计算和搜索避障最短路径。贪心算法是图论中求解单源点最短路径的经典方法,它本质上是一类贪心算法。对于这类问题应该想出一个多级解决办法和一种最优
18、的量度标准。方法之一是逐条构造这些最短路径,可以使用迄今已生成的所有路径长度之和作为量度标准,为了使这一量度达到最小,其单独的每一条路径都必须具有最小长度。 算法流程: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可
19、以最短时间内没有经过点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 各路
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 论文 基于 网络图 机器人 问题
链接地址:https://www.31doc.com/p-3933321.html