机器人避障问题-一等奖论文.pdf
《机器人避障问题-一等奖论文.pdf》由会员分享,可在线阅读,更多相关《机器人避障问题-一等奖论文.pdf(43页珍藏版)》请在咨信网上搜索。
1、D题机器人避障问题摘 要本文综合运用分析法、图论方法、非线性规划方法,讨论了机器人避障最短 路径和最短时间路径求解问题。针对问题一,首先,通过分析,建立了靠近障碍物顶点处转弯得到的路径 最短、转弯时圆弧的半径最小时和转弯圆弧的圆心为障碍物的顶点时路径最短、转弯在中间目标点附近时,中间目标点位于弧段中点有最短路径的三个原理,基 于三个原理,其次对模型进行变换,对障碍物进行加工,扩充为符合条件的新的 区域并在转弯处圆角化构成障碍图,并通过扩充的跨立实验,得到切线和圆弧是 否在可避障区的算法,第三,计算起点、中间目标点和最终目标点和各圆弧及圆 弧之间的所有可避障切线和圆弧路径,最后给这些定点赋一个等
2、于切线长度或弧 度的权值构成一个网络图,然后利用Dijkstra算法求出了 O-A、0-B,0-C的最 短路径为 0-A:471.0372 个单位,0-B:853.7001 个单位,0-C:1086.0677 个单 位;对于需要经中间目标点的路径,可运用启发规则分别以相邻的目标点作为起 点和终点计算,确定路径的大致情况,在进一步调整可得到0-A-B-C-0的最短路 径为2748.699个单位。针对问题二,主要研究的是由出发点到达目标点A点的最短时间路径,我们 在第一问的基础上考虑路径尽可能短且圆弧转弯时的圆弧尽量靠近障碍物的顶 点,即确定了圆弧半径最小时的圆弧内切于要确定的圆弧时存在最小时间路
3、径,建立以总时间最短为目标函数,采用非线性规划模型通过Mat lab编程求解出最 短时间路径为最短时间路程为472.4822个单位,其中圆弧的圆心坐标为(81,430,209.41),最短时间为94.3332秒。圆弧两切点的坐标分别为(70.88,212.92)(77.66,219.87)0关键字:Dijkstra算法 跨立实验 分析法 非线性规划模型一.问题的重述图是一个800X800的平面场景图,在原点0(0,0)点处有一个机器人,它只 能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生 碰撞的障碍物,障碍物的数学描述如下表:编号障碍物名 称左下顶点坐 标其它特性描述
4、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长方形(50
5、0,140)长300,宽60在图1的平面场景中,障碍物外指定一点为机器人要到达的目标点(要求目标 点与障碍物的距离至少超过10个单位)。规定机器人的行走路径由直线段和圆弧 组成,其中圆弧是机器人转弯路径。机器人不能折线转弯,转弯路径由与直线路 径相切的一段圆弧组成,也可以由两个或多个相切的圆弧路径组成,但每个圆弧 的半径最小为10个单位。为了不与障碍物发生碰撞,同时要求机器人行走线路与 障碍物间的最近距离为10个单位,否则将发生碰撞,若碰撞发生,则机器人无法 完成行走。机器人直线行走的最大速度为%=5个单位/秒。机器人转弯时,最大转弯速度为u=v(p)=-其中P是转弯半径。如果超过该速度,机器
6、人将发生 1+e 0侧翻,无法完成行走。请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的 数学模型。对场景图中4个点0(0,0),A(300,300),B(100,700),C(700,640),具体计算:(1)机器人从0(0,0)出发,0-A、0-B、0-C和0-A-B-C-0的最短路径。(2)机器人从0(0,0)出发,到达A的最短时间路径。注:要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以 及机器人行走的总距离和总时间。图800X800平面场景图二.问题的分析本问题的难点在于机器人要到达指定的目标点需要满足以下两个约束条件:1.机器人的行走路径由直线段和圆弧
7、组成,不能折线转弯,转弯路径由与 直线路径相切的一段圆弧组成,且每个圆弧的半径最小为10个单位;2.要求机器人行走线路与障碍物间的最近距离为10个单位。因此,我们在建立模型求解机器人到达目标点的最短路径时需优先考虑这两 个约束条件。首先我们可以根据约束条件将机器人行走的危险区域进行扩张,即所有的障 碍物都向外扩张了 10个单位。机器人所走的路径都是直线与圆弧的构成,故存在 线和弧、弧与弧之间的切线,可以考虑在所有代表出发点与其它圆弧之间切线的 顶点与源点连成一条边,权值均为0,同理在所有代表目标点到其它圆弧切线的 顶点与终点连成一条边,权值均为0,这样题目就转化成了求源点到达终点之间 的最短路
8、径问题了。对于问题二,要求最短时间路径,则要考虑的是要以最大速度行走。直线行 走时就是最大速度,但在转弯圆弧处因为转弯半径越小,行走的速度就越慢,则 需在第一问的前提下增大圆弧的半径,则圆弧的转弯半径和圆心都不确定,通过 建立模型确定0-A之间的转弯时圆弧的半径和圆心。三、模型的基本假设根据对该问题的分析,本文对所建立的模型提出以下基本假设:1.机器人的性能足够好,能准确地沿圆弧转弯2.机器人行走过程中不会意外停止3.图中所给数据障碍物都是真实的4.机器人能够抽象成点来处理四、符号说明4:指每段路径的长度%:机器人直线行走时的最大速度V:机器人的最大转弯速度中 每段路径所用的时间五、模型的建立
9、与求解5.1模型的准备模型的准备一首先给出以下三个前提及其证明:1.靠近障碍物顶点处转弯得到的路径最短如图1所示:E DI.图1设A为起点,B为终点,矩形的阴影部分是障碍区,C为障碍物的顶点,D为障 碍物外任意一点,连接AD,BD,AC,BC延长交AD于E点,因为在三角形中两边之 和大于第三边,所以有:BD+DEBE;BE=BC+CE;AE+CEAC;AD=AE+DE;两个不等式相加,得:AE+DE+AE+CEBE+AC;即:BD+ADAC+BC.于是,得证由A到B在顶点C处转弯时为最短路径。2.转弯时圆弧的半径最小时路径最短和转弯圆弧的圆心为障碍物的顶点时 路径最短要证明机器人转弯时圆弧的半
10、径最小时路径最短,则可以把P到A的路径比拟 成一条弹性绳,由于路径要绕过障碍物,故要拉长弹性绳以绕过障碍物,由于机 器人转弯时只能是走圆弧路径且有圆弧半径约束,即可以在障碍物的顶点处加入 圆环,将其圆心固定在顶点处,由于弹性绳的弹性势能与和伸长量心存在如下能量关系:Ep=-kx故弹性绳弹性势能最小时伸长量最小,此时正是路径最短的情况:如图2所示:图2根据最小势能原理可知,当弹性体平衡时,系统势能最小。即弹性体在自由 条件下,有由高势能向低势能转化的趋势。现在将圆环看成也有弹性,在如图所 示的条件下为初始状态。圆环受力为F,此时圆环有缩小的趋势,随着圆环的缩 小系统趋于平衡,弹性绳有最小势能。由
11、能量守恒也可以说明,弹性绳的弹性势 能转化为弹性圆环的弹性势能,于是弹性绳的弹性势能减小。因此,随着圆环的半径的减小,弹性绳的势能减小,即最短路径变短。所以 转弯时圆弧的半径最小时路径最短。转弯圆弧的圆心为障碍物的顶点时路径最 短。3.转弯在中间目标点附近时,中间目标点位于弧段中点有最短路径当机器人从0点出发不能直接到达另一目标点,而需经过中间目标点A时,则 必须在A点转弯处形成一个圆弧,中间目标点位于弧段中点时且半径最小时有最 短路径,下面给予证明:由上述2的证明可仍然采用此证法,设从两转向处引出一根弹性绳,要使其经过A点,如图所示,在其自然伸长的前提下,必定 会在A点出弯折。由于机器人有转
12、弯时圆弧的半径最小时路径最短,从两转向处 引出一根弹性绳,要使其经过A点,如图所示,在其自然伸长的前提下,必定会 在A点出弯折。由于机器人有最小转弯半径约束,故在A处加一最小转弯半经的 圆,即厂10个单位,使其受力平衡时,即为路径的最优解。根据以上证明作出如下图形(图3):图3作法:过A点分别作圆上M,N的切线,作/MAN的角平分线,在/上距离A 点10个单位处选取一点0,以0为圆心,10个单位为半径,作圆0,再过M,N 分别作圆0的切线,即为路径。模型准备二:切线的剔除:基于上述准备一的三个前提条件和题中给出的两约束条件即(1)机器人的 行走路径由直线段和圆弧组成,不能折线转弯,转弯路径由与
13、直线路径相切的一 段圆弧组成,且每个圆弧的半径最小为10个单位(2)要求机器人行走线路与障 碍物间的最近距离为10个单位。故存在一些不符合要求的切线,要将这些切线剔 除,可做示意图如下:图4如图所示,阴影部分为障碍物,用圆来代表弧,AC、BC、AD、BD、EH、FG 分别如图示的切线,由于AD、BC、BD、FG、EH经过障碍物,所以要剔除,AC为符 合要求切线。(图中应该剔除的切线用虚线表示)。模型准备三由上准备一和准备三可知,对于机器人转弯的路径按照一个圆弧、两个圆弧、三个圆弧等多个圆弧枚举出转弯的情况:转过了一个圆弧,如图5:B图5如图,设3(%,乂),0(%,为),A(知为),E、F的坐
14、标分别为(x4,%)和(%,K),r/+2 2BO-a,BA=b,OA=c,贝(J:ZBOF-ar cos,ABO A=ar cos-,a lacrZAOE=cos,cX ZEOF=27t-ZBOF-ZBOA-ZAOE=0,可知:4=。2一玉)2+(%一%)2,=(%3-石)2+(-%)2,C=(%3-%a)?+(%-2)2 故B到A的路径长度为:Lb_a=BF+FE+EA o其中,FE=rO,BF=ya2-r2,|EA|=7c2-r2,即 Lb_a=r0+J/+“2 一/。_ _ /一产=、/(%y+(义y)2并且利用相切的关系可以得出下面两个方程:Y5_yj-x2+(y5-y2)2=r可以
15、解出切点厂(%5,%),同理可以解出切点4%4,”)。转过了两个圆弧,如图6:情况一:B图6假设两圆心坐标分别为0(和)和。(%,为),半径均为,0点坐标为(尤3,%),则容易求得:_x+x22%+%2%=这样我们就可以利用只有一个圆弧中的方法,先求A到0,再求0到B,于是分 两段就可以求解。同理如果有更多的转弯,同样可按照此种方法分解。情况二:图7设圆心坐标分别为。(%2,乃)和0(%3,丁3),半径均为r,尸(%,%),。(%4,、4),P0的长为。,00长为,P。长为C,。长为d,。长为e;ZP00=a,ZPOA=a2,ZQ0 0=a3,ZQO D=a4,ZAOB=0 x,/COD=用;
16、由这些点 的几何关系可以得到:a=(一2 一)2+(%一)2,b=y(X3-X2)2+(%-丁2 C=J(%3-J+(%)?,d=J(%4-%2)2+(%-%)2,e=(%4-%3)2+(%-I-甘+./+/一。2其中:a.=ar cos-,2abr 3。4=ar cos ,。=一 a?则PA=la2-r2,AB=rOx,r b2+e2-d2a.=ar cos ,a.=ar cos-a 2bec 3兀,。2=下一%BC=b,CD=r02,DQ=y/e2-r2所以:L=PA+AB+BC+CD+DQ.情况三:当障碍物本身是个圆弧时:图8此种情况计算路径的方法同情况二。综上几种情况的讨论,可以知道:
17、机器人的避障路径都是由以上几种情况组成,故我们在求由0点到各目标点时路径长度都可以将路径分解成以上几种情况 来求解。5.2模型的建立与求解5.2.1问题一的模型建立与求解模型的建立:题中给出了 12个多边形障碍物的区域,故我们根据图中的约束条件利用 Matlab(程序见附录一)将障碍物扩充为如图9:即形成一个新的障碍区域,先求出所有的切线,包括出发点和目标点到所有 圆弧的切线以及所有圆弧与圆弧之间的切线,给这些定点赋一个等于切线长度的 权值,如果某两条切线有一个公切圆弧,则代表这两条曲线的顶点是一条直线的 两个端点,边上的权值等于这两条切线之间的劣弧长度。那么在所有代表出发点 与其它圆弧之间切
18、线的顶点与源点连成一条边,权值均为0,同理在所有代表目 标点到其它圆弧切线的顶点与终点连成一条边,权值均为0,这样题目就转化成 了求源点到达终点之间的最短路径问题了,这里最短路径就是指经过所有顶点与 边的权值之和最小。对于最短路径的求解,有以下步骤:1)画出出发点和目标点和各个圆弧的切线,以及圆弧与圆弧之间的切线,但是切线有可能经过障碍物的内部或危险区域,也可能出现切线重复的状 况,既有很多不合理的切线,再根据约束条件我们对模型做了以下修正:检验切线两个端点是否在障碍物内部。检验切线两切线是否相交 检验圆弧所对应的圆心,即障碍物的顶点到切线的距离是否小于10。除上述三个指标外还需考虑一种特殊情
19、况,即公切线在一个圆弧上只有一个 切点(如图10)因此我们作如下规定:如果某条切线与某段圆弧相切,且切点不在切线的端 点上,则该切线为不合理。AB图102)然后将不合理的切线剔除,假设剔除过后有m条合理切线,那么就有加个 顶点,设这些点的权值耳(1相),即第i条合理曲线的长度。,为边的权 值,即第/条弧的长度。3)然后把路径确定下来,按照求得权值矩阵给图中的顶点及边长赋值。利 用Di jkstra算法对其求解出最短路径。根据上述的模型通过编程求解和几何求解求出了最短路径,并且求出了最短 路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标。模型的结果通过编程求解得出最短路径的线路坐标和最短路
20、径:表一各线路的最短路径路径最短路径的坐标线路最短路 径的长 度(个单 位)0-A(0,0)-(70.506,213.1406)-(76.6064,219.4066)-(300,300)471.03720-B(0,0)T(50.1353,301.6396)-(52.0372,306.0493)-(147.96,444.799)一(152.4059,444.7062)-(224.4721,461.0557)f(230,470)f(230,530)-(225.4967,538.3538)-(144.5033,591.6462)-(140.6912,596.3458)-(100,700)853.70
21、010-C(0,0)9(232.5242,50.3238)f(232.1693,50.2381)f(412.1693,90.2381)f(418.3448,94.4897)f(492.5671,507.4329)f(506.1273,208.9125)f(727.9377,513.9178)f(730,520)f(730,600)f(728.9443,604.4721)一(700,640)1086.0677O-A-B-c-o(0,0)-(70.506,213.1406)-(76.6215,219.412)t(294.4385,298.5652)t(289.9197,306.5856)-(229
22、.4072,533.36169)-(225.4967,538.3538)-(144.5033,591.6462)f(140.865,595.9316)f(98.9499,690.0466)f(108.9534,704.0772)9(270.8686,689.9622)9(272,689.798)f(368,670.798)一(370,670)-(430,670)T(435.5878,738.2932)-(534.4122,738.2932)-(540,740)-(670,740)f(639.7738,732.1149)f(699.2162,642.2645)f(701.3151,637.968
23、8)f(710.2187,602.0799)f(730,600)7(730,520)f(727.9377,513.9178)f(506.1273,208.9125)T(492.5671,507.4329)f(418.3448,94.4897)f(412.1693,90.2381)f(232.1693,50.2381)f(232.5242,50.3238)f(0,0)2748.699其中:0-A:圆弧圆心坐标为(80,210)。0-B:圆弧圆心坐标依次为:(60,300),(345,210),(220,470),(220,530),(150,600)o0-C:圆弧圆心坐标依次为(230,60),
24、(410,100),(500,200),(720,520),(720,600)。O-A-B-C-O:圆弧圆心的坐标:A(299.327,309.9773),B(108.0849,694.115),C(708.990,644.3794)(其他圆心在障碍物的顶点时未列出,只列出了在A,B,C 三个目标点的圆心坐标)。各路径最短线路图如下:图11 0-A的最短路径图12 0-B的最短路径图13 0-C的最短路径图14 0-A-B-C-0最短路径图5.2.2问题二模型的建立与求解 模型分析由第一问的模型可知,当转弯圆弧的圆心在顶点时,行走路径越靠近两点连 线,且圆弧半径越小路径越短,所花的时间也就越少
25、;但根据最大转弯速度为 v=v(p)=一卷斯,其中是转弯半径,圆弧半径越小转弯的速度也就越慢,1 C所花的时间又更长,基于这两者结合,将转弯路径的圆弧与问题一中。点到A点圆弧相内切,如图15所示图15t设圆弧的圆心为。(x,y),问题一中的顶点圆心为P(80,210),OP=l00=a,OA=b,OA=c,ZOO A=,ZOOM=10 x,y0利用Mat lab编程求得总时间最小为=94.3332秒,最小时间总路程为472.4822 个单位,其中转弯处圆弧圆心坐标为(81430,209.41),此时圆弧的半径为11.197 个单位,圆弧两切点的坐标分别为(70.88,212.92)、(77.6
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 机器人 问题 一等奖 论文
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【曲****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【曲****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。