机器人避障问题研究报告.docx

1、机器人避障问题研究报告D題：机器人避障问題本文就机器人避强冋題，建立了相应的优化模里。模1-：关干Hl器人从区域中一点到达另一贞的遐障最短路径的问题。首先， 题恿，师出HI器人行走的可行区域与危险区域；其次，在证明了具有園形限定区域的最 皱路径间题为根据的前提下，可以得岀最短路径一定是由直线和闊弘组成，并依此建立 了线岡结沟，将路径则分为若干个逆种线圆结构来求辭最短路径通用模型；最后，根弼 最姬路径通用模型，采用穷举法把可能路径的最短路径列举出来，通il比较最终得出各 种最短路径的坐标及总路程8UT：(1 ) 0-A的最矯路程为：471.04个单位(2) OtB的最短路程为:853.71个单位

2、(3 ) 0-C的最短路程1088.20个单位(4 ) OtABtCtO的最短路径为：2730.01个单E模塑二：关于机器人UEM中一点到这另一点的避障最類时间路径的间题。首先， 根锯題意,找出公共切点，得出转弯时最大圆和最小圆的圆心坐标,确定冏心的变化X 围；其次，依擴圆心的变ItX围，得出转弯半径的变化X围；然后，利用MATLAB件 编程来求解最姬时间路径通用模型；最后，根据最短时间路径通用模里，得出所有结果， 通过比较最终得岀机器人U 0 (0,0)岀发，到达A的1SK间路径的总路程和总时间以及 fit路径如下:0-A最短时间471.12个单位，晟矯时同为94.229枚第一条线段起始坐标

3、为(0, 0)终点坐标为( 77.66, 220.07 )第二条裁段起峪坐标为( 69.82, 212.07 )终点坐标为( 300, 300)半gJl 12.83个单也6!心坐标为( 82, 208)最后,我1对模型进行了改进、检验、评价与推广。关键词：优化模型最短路程 线圆结构 最短时间 穷举法1问題重述1.1背景资料图1是一个800x800的平面场景图,在原点0(0,0)点处有一个机器人，它只能在该平 面场景X围内活动。图中有12f不同形状的区域是机器人不能与之发生磁撞的障碍物， 障碍物的数学描述如下表：编号障碍物名称左下顶点坐标貝它特性描述1正方形(300, 400)进长2002岡形凰

4、。坐标(550, 450),半径703平行四边形(360, 240)庇进长140,左上顷点坐标(400, 330)4三角形(280,100)上顶点坐标(345, 210),右下硕点坐8(410,100)5正方形(80, 60)边长1506三角形(60, 300)上顶点坐标(150, 435),右下II点坐标(235, 300)7长方形(0, 470)长220,宽608平行四边形(150, 600)竈边长90,左上硕点坐标(180,680)9长方形(370, 680)长60,宽12010正方形(540, 600)ia 长 13011止方形(640, 520)遊长8012长方形(500,140)长

5、300,宽601.2 息(1)在图1的平面场景中，障碍物外荷定一点为机器人要到这的目标点。现定机器 人的行走路径由直筑段和冏弧组成，其中冏弧是机器人转弯路径。(2)机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弘组成，也可以由 两个或多个相切的凰聲路径组成，但毎个圆聲的半径最小为10个单也。(3)HI器人直线行走的最大速度为v0 = 5个单位/秒。机器人转弯时，最大转弯速度为卩=卩3)= ，貝中q是转弯半径。如果超11该速度，HI器人冷发生MSI,无法1 + e10-0.1X完成行走。1.3问題要*(1)机器人不与肾碍物发生亚撞，若亚撞发生，则机器人无法完成行走。(2)机器人行走线路与肾

6、碍物的距离至少起过10个单位，否!M将发生碰撞。1.4同题提出请建立机器人UEM中一点到达另一点的遐障最短胳径和最短时rg的数学模里。对场景图中 4 个点 0(0, 0), A(300, 300), B(100, 700), C(700, 640),具体廿算;冋題一：机器人从0(0, 0)出发，OtA、OtB、OtC和OtAtBtCtO的最短胳径0 NSZ：机器人U 0 (0,0)岀发，到达A的最姬时间路径。a：要给出路径中每段直线段或叭的起点和终点坐标、圆的同心坐标以及机器 人行走的总距离和总时间。2冋題假按与符号说明2.1冋愿假扱1.假设机器人为一个质点；2.假设机器人在转弯时的速度可以瞬

7、间变换；2.2符号说明P：转弯半径L:路径的总长度心：机器人行走的速度/；：第j段圆*的长度：第/Hfll线的长B!V：机器人的最大转弯速度k：障碍物上的任意点与行走路径之间的最短距离3冋題分析3.1Bfi-的分析首先，根据题恿可知，机器人行走线路与障碍物的距离至少481410个单也，由此条 件可ii岀机器人的危险区域与行走EMo其次，每f拐轴处画一个半径为10的四分之一圆恥，通il釆用拉绳子的方法寻找可 能的最姬路径(比如求o和a之间的最短胳径，可以连接ofnA之间的一段绳子，以拐 角处的冏孤为支撑也紧，那么这段绳子的长度便是。到A的一条可能的最短路径)。然后採用穷举袪列出o舅每个目标点的可

8、能路径的最短路径,比较其大小便可求得 。到目标点的最矯路径。最后,求定点0(0,0)经过中间的若干点按照一定的规则绕过障碍物到达目标自，& 使借不仅要考虑经U障碍物拐点的间题，还需考虑经过路径中的目标点处转弯的间题， 泄时简单的线圆緒构就不能解决这种间题，可以在拐自及迩中目标点处胡采用最小转弯 半径的形式，最终求得最短路径。3.2HKZ的分林首先，由题恿可知，转弯速度与转弯半径有关，在一定XIB内半径越大，速18越大。 因此。到a的最短路径不一定是最短时间路径。其次,在冋題一中以求岀，机器人走限定区域的部分ill界时路径能这到最小。在机 器人不发生碰撞目路径尽可能最姬的同时，选择扩夫半径以保i

9、if时同最短。通与 证明，计算出圓心的坐标X围与转弯半径。最后,把所有可能路径化成冋題一中的线IS给构,利用MATLAB件进行求解找出 最姬时同路径。4模型准备4.1模型准备一假毀：具有冏形限定区域的最短路径是由两部分组成的：一部分是最短直线路径， 另一部分是限定区域的部分ill界，这两部分是相切的，互相连接的。址明：假设在平面中有A(a, 0 )和B(-a, 0)两点，中间有一 f半圆形的肾碍物, 证明从A到B的最路径为AEFB。平面上连接两点最短的路径为直MS, ffl是连接两点的线段于障碍物相交，所以设 法尝试折线路径。在y轴上取一点D(0, d),若d适当大，则折线ADB与障碍物不相

10、交，折M ADB的长度为：ADB l= 2/a2+d2显然ADB着d的减小而械小，肖d减小时db, &DC,使得BC、 CA与障碍物相幼，切点分别为E和F,显然ACB是折线胳径中最短的。由于0 “彳，所以 dvtane 因此易 fll 1 EF 小干 ECF 的长，E|1 EF ECF , U 而 BE + EF + FA v ACB ,记 线段BE、IEF.线段FA为AEFB朋么AEFB为折线路中最短路径。准备：由個设可知，起点到目标点最短路径应该是若干个线圆結构所级成。障碍物 在拐点处的危险区域是一个半径为10的|即版，求两点之间的最短路径中的转弯半径应 该按照最小的转弯半径来算才能达到最

11、优。凰的半径为 r, C和D分别为机器人经过拐点分别于隔离危险线拐角小I即张的切点,AB的长度为a, A0 的长度为 b, B0 的长度为 C, ZAOB = al,ZAOC = a2,ZBOD = a3t ZCOD = 0. 求ACDB的长度，设为厶，解法如下:3= J（X2-Xl）+（y2-X）2 -b = J（ 一西）+（3一） C =/兀_勺）2+（儿_儿）在AAOB中：在 RtAAOC :jb2-r + ylc2-r +r0（2）对于下面两种悄况不能直接采用线岡结构来解决，需要做简单的变换。 悄况_：对于同心连线与切点连线交叉的悄况。线Bl结构43假设两圆心坐标分别为和N（x29y2

12、）,半径均为，P点坐标为（可,旳），可以 求得:西+“2儿=因此可以利用（1 ）中的方法，先求A到P,再求P到B,这样分两段就可以求解。 同理血果有更名的转弯，同样可以按照此种方法分解。悄况二:对于圆心连线与切点连线平行的悄况。D Ey = %d)+xM/V直线方程为:因为公UJSDE与MN平行，所以DEM直线方程可以表示为:=%（兀_召）+ ”+3其中:把公切线的方程于圆的方程联立,可求和E的坐标。用D和E任直一自作 为分劃点都可以将上图分创成两个4-2所示的线冏结枸，这样就可以对其进行求解。同 3,多个这样的转弯时，用同样的方法可以进行分创。4.2模璽准备二假按:如果一个圆坏可以绕着坏上一

13、个定自转动，朋么过圜坏外两定点连接一根绳 子，并以该圆坏为支撑拉紧绳子，达到平衡状态H, |心与该顶点以及两条幼线的延长 线的交点共线。证明:血图4-5所示，E点就是惻坏上的一个顷点，ACDB与圆坏相切的胳线，N就是 切线AC和BD的延长线的交点，込明M、E、N三点共线。用力学的知识afiil明，RiHfi力相等，设为戸，它们的合力设为丘，定点对岡坏 的作用力设为E。由几何学的知识可知，&与顾共线，根据力的平術条件可得：_ FT即顾与石可共线。妹上所述M、 E和N三点一定共线。准备：根据假设的定理可求出机器人UA绕过障碍物经UP到达目标自B的最短 路径（血图4-6 ）,釆用以下方法：用一根知子

14、使一个岡坏定在P点，使这个圆坏能册绕P点转动。然后连接A和B 的绳子并以这些转弯处的圆弧为支（S里转弯处Bill的半径均按照最小转弯半径来it 算），拉紧绳子，册么绳子的长度就是A到B的最短距离。可以把路径图抽象为以卞的 几何图形2H亍求解:0 V ./MPE D图4-6如图,A（西,廿）是起点，B（x2,y2）是终点，M （羽,旳）和N （刃,）打）是两彳、固定的圆， 0是一个可以绕P（P, q）点转动的圆环,三个圆的半径均为r, C、D、E、F、G、H均为 切点。a、b、c、e, f分别是AM、MO、AO、AN、0N的长度。A、B、M、N均是已知点, 0是未知点。那么最短路径就可以表示为：

15、L = AC + CD + DE + EF + FG + GH + HB因为o点的坐标未知，不能用线冏结沟对其亍求解。故得先求出o点的坐标。设 O 坐标为（m, n ）, ZAMC、ZAMO、ZAOM、ZAON、ANOF 分别为 af （ Z=1、2、 3、4、5 ）, ZCMD. ZEOF、ZEOM 分别为 0、y、0Q得到如下关系:=J（斗 73）2+（开_卩3）b = yl（xy-m）2 +（y3-n）2 ）2 e = yl（xl-x4）2 +（yi-y4Y f = yl（x4-m）2+（y4-n）2在R3MC中：rax = arccos a在AAMO中：a2 +b2-c24 = arc

16、cos 22abZr+L/a. = arccos 32bc在AON中：c2+f2-e2a. = arccos 2cf在 RtQOF 中:2ra. = arccos f0=_4_冬3兀/ = -4-5Q81为PO 定会在ZEOF的用平分线上，所以满足： e = L2了果用向量的形式来求,易知莎的一个方向向量:心(】,g) x2 -n而OEMO垂直，故其一个方向向量：/；=(!,-AZ1)y2-mffij:OP = (p-tn.q-n)所以:a /八 OM = arc cos .l/jOMI综合以上式子可以求借O的坐标，从而可以得出路径的长为:L = yja2-r2 +pr + b + yr +

17、2)2-r2 +/0l=GH + HB5模型的建立与求解5.1 S-W建立与求解根据题恿，机器人行走线路与障碍物间的最ifi距离为10 f单位，由此可以画岀机 器人行走的可Item与危险EM,则下图5-1 示，阴影部分代表可行区域，白色部分 代表危险EMo图5-1机器人行走的可行区域与危险区域假设机器人从起点0到目标点由题可知路径由冏恥和线股组成，设有m条线 股，n ftlll。那么目标函数可以表示为：ni nmin 厶= 2X+*/=1 J=1X?10s.t = 10用此模型就可以对起点到目标点之间的路径进行优化求解。(1)#0图5-2解决的是0到目标点A的最姬路gro，图中给出了可能的两条

18、路径 的最短胳径(图中的蓝色所示)，可以分别计算岀两条可能路径的最短路径的长度，滋 后进行比较，取最小者就是0到目标点A的最优路径。g0图5-2到ft A可能最短路径利用MATLAB编程（程序见附录A ）对模型进行求解，结果如下:10U胳线1到达目标点A,解借最姬路径为498.97个单位。20从路线2到达目标虑A,解借最矯路径为471.04个单位。综合2嘶述，0到目标点A的最姬路径为471.04个单位。（2） ffl图5-3解决的是0到目标点B的最短路径问!图中给岀了可能的兀条路 径的最短胳径（图中的线条所示），可以分别廿算岀穴条可能路径的最短路径的长度， 然后进行比较，取最小者就是0到目标点

19、B的最优路径。Y利用MATLAB编程（程序见附录A ）对模型进行求解，结果如下：10从路线1到达目标点B,在拐贞a处分为两条胳线，即图巾的黄色路线与红色 路线。al.USS线1走红色路线：这条路径是由5条直线和4段岡恥组成，直接用简单 的线同箱构无法解岀。于是做血下变换：首先，找岀两圆的幼线段与两囿心连线 的交点M；其次，用线凰给枸42的解法计算,分别求0到M和M到下一个交点, 以此类推直到目标点B,分四部分求解;最后把这El部分的和相加，便可求岀0到 B的最姬路径。求得结果为945.96 t单位。bl.UJS线1走黄色路线：同理这条路径是由4条貞线和3段圆恥组成，同样可 以采取肋中的变换,分

20、三部分求解，求得结果为1058.4个单位。妹上：0 1USS1到达目标自B走红色路线路径最短，最短路径为945.96个单 位。20从路线2到达目标自B,在拐自b处分为两条胳线，即图中的黄色路线与红 色路线。a2.Uffi线2走红色路线：同理这条路径是由5条直线和4段圆弘组成，同样可 以采取肋中的变换,分四部分求解,求得结果为878.05个单位。b2.U路线2走黄色路线：同理这条路径是由4条貞线组成，同样可以果取a1中的变换,分三部分求解，求得结果为990.17个单位。妹上：0从路线2到达目标自B走红色路线路径最短，最短路径为878.05个单 位。30从路线3到达目标自B,在拐点c处分为两条胳线

21、，即图中的黄色胳线与红色 路线。a3.UJS线3走红色路线：同理逆条路径是由6条直线和5H组成，同样可 以采取肋中的变换,分五部分求解，求得结果为853.71个单位。b3.U路线3走黄色路线：同理这条路径是由5条直线和4段圆弘组成，同样可 以采取a1中的变换,分皿部分求解，求得结果为971.23个单位。综上：0从路线3到这目标点B走红色路线路径最短，最婕路径为853.71个单位。综合所述，0到目标虑B的最短路径为853.71个单位。（3） M图5-4解决的是0到目标点C的最短路径冋題，图中给岀了可能的三条路 径的最短路径（图中的蓝色所示），可以分别廿算岀三条可能路径的最短胳轻的长度，图5-4到

22、达C的可能最短路径利用MATLAB编程（程序见附录A ）对模型进行求解，结果如下:1OU胳线1到这目标点C,同理这条路径是由6条fiSfll 5 011组成，同样 可以呆取刖中的变换,分五部分求解,求借结果为1088.20个单位。20从胳线2到这目标点C,同理逆条路径是由6条貞线fl!5Hia组成，同样 IJUa1中的变换，分五部分求解，求得结果为1102.60 f单位。30从胳线3到这目标自C,同理这条路径是由7条貞线和6 Kl|组成，同样 可tt a1中的变换，分兀部分求解，求骨结果为1253.40 f单位。40 UJSS4到达目标自C,同理这条路径是由8条育线和7段圜飯组成，同样 可以呆

23、取砧中的变换,分七部分求解,求得结果为1239.80个单位。综合2）所述，0到目标点C的最姬路径为108&20个单位。如图5-5解决的是Ot AtBtCtO的最短路径问题，可利用准备二的理论对其进 行廿算，棉出最姬路径。蓝色线为OtAtBtCtO的最短JS6,这条路径由17条貞线和16 Kia组成，在 个目标处用准备二进行廿算，同样果取31中的变换，分十五部分求解，求得给果为 2730.01个单位。5.2模型二的建立与求解机器人最大转弯速度为v = v(p) = ,其中是转弯半径。所以，在一定X围内,1 + e转弯半径越大，最大转弯速度也就極大，行走时间减小。根据以上分折，做岀以下假设：SS：

24、 JDJ走弧线的中自C为公共切点，将最小圆的圆心与公共切点C连接并延长, 所得直线即为以相同半径不同冏心所有冏的最优路径(为所走弧长路径)，其中所有最 优圆的圆心，即为在不与障碍物发生碰撞的悄况下岡心的变化x围。证明:以任意虑m、n为圆心，其中点m、”不在公共切虑c与最小圓的圆心(80,210) 连线的直线上，另外在这条直线上找一然后分别以点?、z为圜心，作出相 同半径的闊并部内切于公共切点c,如图所示：分别求得以点加、z为圆心，相同半径的圆的不同路径距离分别为489.61个单位、 483.47个单fi. 472个单位，通过对比可8l,当半径相同时，圆心在公共切点c与最小岡 的冏心(80,21

25、0)连线的直线上所走的路径最短。Q因为公共切点c正好为所走版线的中 点，所以此直线与正方形的対角线重合，因此可得直线为y = x + 290。同时也騎込假 设是正确的。通社上述证明可JU, III心在貞线y = -x + 290上变化为最优。找出圓心在直缆 y = -x+290上变化时，没有与障碍物同发生碰撞的最大圆的凰心位置与最小圆的圆心 位置，设最大BI的H心坐标为心刃，如下图所示：当线段力=必时，以交点0为冏心，心为半径师圆，此时的圓为没有与障碍物间发 生碰撞的最大冏，Q因为点c为直线y = 一兀+290与以点(80,210)为圓心半径为10个单位圆的交虑,由此可得;y = -x + 2

26、90 (x-80)2+(y-210)2=102解得点c坐标为(80-572,210+5)根据两点之间的距离公武 =/兀-*+(儿+肘可知：y = 一兀 + 290(80 - 52 - x)2 + (210 + 5 VI- y)2 = (x - x)2 + (290 - y)2解得最大H的圆心坐标为0(249,41)同理,可知最小U的圓心坐标为(80,210) o由上述可知，同心是在直线y = -x + 290 (80 a-/(x-80)2+(y-210)2 +10根据題恿，机器人转弯时，最大转弯速度为V = V(P)= ,其中Q是转弯半1 I e径。所以，当 定时，机器人转弯的半gpi大，最大

27、转弯速度也就越大。乂因为机 器人直线行走的最大速度为v0 = 5个单位/秒，所以当p趋于无穷大时严Wo (其中 因为不能碰撞障碍物所以Q不能无限范于无穷大)，最大转弯速v = v(p) = 1 + e 卩也就范于v = v(p) = v0=5个单位/秒，所以在转弯时，眠的半glt,转弯速度加快。 如图5-9解决的是0到目标点A的最短时同路径问SSoia心dU小園到大同内变化, 图巾给岀了 OtA的所有可能时间路线。计算岀所有路线的时间，比较其大小，找出最 短时同路径。图5-9因为圆心是一个动点，所以可以得到很多条路径。结合准备以中的定理，利用 MA7UB编程(程序见附录B )对模型进行求解，找

28、岀时间最姬的路径，结果如下：0-A的最姬时间路径为471.12 f单位，最短时间为94.229杪。5.3模型结果由題恵可知，路径由圆恥和线段组成，设有m条线段，n条凰恥。机器人貞线行走 的最大速度为v0=5f单位/枚。机器人转弯时，最大专弯速度为y = = o| + glU-U.l经过推算可th专弯半径Q=io,假设机器人在貞线上一貞以5f单位/枚行走，根摇公式 可以借到最大转弯速度为v = 2.5个单创秒。5.3.1模型一的结果(1 ) 0-A的最類路径为471.04个单位，根据上述公式得到总时同为96.022秒。最 姬路径中每段宜线段或圆*的起点和终点坐标、冏版的圓心坐标以尺机器人行走的总

29、更 离和总时间如下表：表5-10 0-A9条线段与冏醫的坐标及总路桿与息时间O-ASJ路为471.04个单总时间为96.022杪第条线段dd2起始坐标X076.61y0219.41终点坐标X70.5300y213.12300第厶条圆礼h風心坐标(80,210)(2)0-B的最矯路径为853.71个单位，根据上述公式得到总时间为179.084秒。 最短路径中毎段直线段或圓的起点和终点坐标、圓11的圓心坐标以及机器人斤走的总 距离和总时间如下表：表5-11 0-B毎条找段与岡醫的坐标及总路桿与息时间O-BggSg 853.71个单位,总时间为179.084杪第/条裁段山d2爲46駅始坐标X052147.96,230225.5,140.69y0305.55444.79470538.35596.35冥点坐标X50.14141.68222.04230144.5100y301.06440.55460.21530591.65700第C条同取h仁厶h&岡心坐标X60150220220150、300435470530600(3)OtC的最矯