《数学建模 机器人避障问题》由会员分享,可在线阅读,更多相关《数学建模 机器人避障问题(16页珍藏版)》请在金锄头文库上搜索。
1、机器人避障问题机器人避障问题一、摘要一、摘要本文讨论了机器人在平面场景中避障行走的问题,已知机器人的行走模式(直线与相切圆弧)以及场景障碍物的分布,计算出到平面各个给定点的最短路径,以及到 A 点的最短时间。文中,首先,考虑到机器人与障碍物之间有 10 个单位的碰撞距离,故用 CAD 软件将平面场景图进行改进,再用 CAD 设计可能的最短路径。接着,对每条具体路径进行分解,得到三种基本线圆形模型(点圆模型,双圆异侧模型,双圆同侧模型) ,对这三种模型进行求解,得到各个模型直线长度以及转弯圆弧圆形角的表达公式。之后,参照具体的行走路径,构造合适的行走矩阵,用以判断每段路径所属的基本模型。路径总的
2、长度可用如下公式表达:12,1,1,2 11NNi ii ii iismr 最后,通过计算设计的集中可能的最短路径,我们得到每段的最短路径的长度分别为:OA 路段:471.0372(单位) ;OB 路段: 853.7001(单位) ;OC 路段: (单位) ;3100915. 1OABCO 路段: (单位) 。32.6778 10对于问题二,我们在问题一的基础上分别利用直线最大速度和转弯最大速度计算出时间的表达式。为了方便计算,我们将转弯圆弧的圆心定在 P(80,210) (场景中正方形 5 的左上角) ,这样得到时间 T 与转弯半径的函数关系式:2222210 0.10(1) (2arcco
3、sarccos)abeabTv 通过 MATLAB 编程,画出其图像,求解得出:当半径=11.435 时,时间 T 最小,其大小为94.5649(秒) 。关键词:最短路径 线圆模型 行走矩阵 MATLAB二、问题重述二、问题重述在一个 800800 的平面场景图(见附录一) ,在原点 O(0, 0)点处有一个机器人,它只能在该平机器人避障问题面场景范围内活动。图中有 12 个不同形状的区域是机器人不能与之发生碰撞的障碍物,障碍物的数学描述如下表:编号障碍物名称左下顶点坐标其它特性描述1正方形(300, 400)边长2002圆形圆心坐标(550, 450),半径703平行四边形(360, 240
4、)底边长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在图中的平面场景中,障碍物外指定一点为机器人要到达的
5、目标点(要求目标点与障碍物的距离至少超过 10 个单位) 。规定机器人的行走路径由直线段和圆弧组成,其中圆弧是机器人转弯路径。机器人不能折线转弯,转弯路径由与直线路径相切的一段圆弧组成,也可以由两个或多个相切的圆弧路径组成,但每个圆弧的半径最小为 10 个单位。为了不与障碍物发生碰撞,同时要求机器人行走线路与障碍物间的最近距离为 10 个单位,否则将发生碰撞,若碰撞发生,则机器人无法完成行走。机器人直线行走的最大速度为 个单位/秒。机器人转弯时,最大转弯速度为 50v,其中 是转弯半径。如果超过该速度,机器人将发生侧翻,无法完成行走。21 . 010 0 e1)(vvv现需建立机器人从区域中一
6、点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中 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 的最短时间路径。机器人避障问题并要求给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。三、模型假设三、模型假设1、假设机器人可看做一个质点,不考虑其实际大小;2、假设机器人能够准确的按照设计的路线行走行走,在其行走中不发生任何突发事故;3、机器人以最大速
7、度行驶,在转弯过程中没有发生侧翻,速度发生突变,不考虑加速减速。四、符号说明四、符号说明:圆到圆圆心的距离;ijliOjO:机器人经过的第 i 个圆弧的圆心角;,1,2i ii:第 i 段直线多对应的圆心角,1i i:圆的半径;r:机器人经过的第 i 段直线的长度;,1i imS:行走路径的总的长度;T:机器人行走的总的时间N:机器人行走经过的总点数(包括起点终点以及转弯圆弧的圆心) ;A:行走矩阵。五、模型建立五、模型建立对于该题建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型的研究,主要是用尽可能短的路径和时间避开障碍物到达目标点。根据题目中的要求可知,机器人行走线路
8、与障碍物间的最近距离为 10 个单位,否则将发生碰撞,若碰撞发生,则机器人无法完成行走,故可把各障碍物的边界扩大 10 单位。利用 CAD 软件制图可在距每个障碍物的边缘 10 个单位处添加外边框,形成新的屏障,特别注意的是在障碍物顶点处使用圆弧。机器人就可在新屏障外的范围内随意活动,不用担心发生碰撞,根据原图修改后的图形见下图 1。机器人避障问题机器人行驶路线是由直线段和圆弧组成。机器人从 O(0, 0)出发,建立数学模型求得OA、OB、OC 和 OABCO 的最短路径。现将各个路段的情况进行综合分析,根据每个路段所遇到的情况,从起始点到目标点的最短距离应该是直线段与圆弧组成,由已知的数学知
9、识,两点之间线段最短,故机器人走的直线越多,路径越短,也就是说当机器人绕过障碍物的时候,半径越小,路径越短,根据题意,转弯半径可按最小半径 10 来计算,经过分析,可建立如下三个线圆模型。模型一:(点圆模型)该模型主要求解的路径长度,该路径只有一个转弯,由图 2 易知,1O2O,C、D 均为直线与圆的切点,CD 为圆弧,为圆弧对应的圆心角的大小,12CODCDOS根据已积累的知识,圆弧的长度为圆弧对应的圆心角与圆半径的乘积,即,同时利用余弦定理r ,即可求得总距离为:abcbaC2cos222B(100, 700) C(700, 640)图 1A(300,300)机器人避障问题S=;rrlrl
10、22 1222 13其中 = 2 12132 232 122 1312132arccosarccosarccoslllll lr lr模型二:(双圆异侧模型)该模型是为了计算的距离,从起始点到目标点经过圆弧异侧拐弯(如图 3) ,1O4O根据已知点、可求得的长度。,AB、CD1O2O3O4Oijl41DOCDBCABAOS为两段圆弧,、为其对应的圆心角,BC 与的交点 E 是这两条线段的中点,根据两个全122O3O等三角形以及勾股定理,可求得 BC 长度。rrSrlrlrl2222234122122232其中,222122313 1 1223122322arccosarccosarccos2r
11、rlll lll l lllll llrr3423224234223233422arccos2arccosarccos21O2OCD图 23O机器人避障问题模型三:(双圆同侧模型)该模型是为了计算的距离,从起始点到目标点经过圆弧同侧拐弯(如图 4) ,添加1O4O辅助线,连接、,运用几何知识轻易能够证明。由图 4 易知1O3O2O4O32/OOEF,可以根据已知点的坐标求出所需线段的长度,进而求得起始点41COFCEFDEDOS到目标点的总距离。22 34223122 12rlrlrrlS其中,)2arccos2arccosarccos2(232342 242 322 3423122 132
12、232 12121lllll lllll lr)2arccos2arccosarccos2(213232 122 132 2323342 242 232 34342lllll lllll lr图 31O4O2O3OABCD E机器人避障问题综合模型:在实际情况中,机器人所走的路线是以上三种模型的结合。设计好机器人的行走方案,可根据设计好的方案构建行走矩阵,构建方法如下:1 2 3iA 则 i 段的直线长度为:22 ,12 ,12,1,122i ii ii ii ilrlrml其中 i=1,2N-1;1O2O3O4OCFE D图 4i 段为模型 1i 段为模型 2i 段为模型 3i 段为模型 1
13、i 段为模型 2i 段为模型 3机器人避障问题第 i 段与 i+1 段之间的转弯圆弧所对应的的圆心角为:其中 i=1,2N-2;iiii,11,机器人行走的总的长度为: 12,1,1,2 11NNi ii ii iismr 六、模型求解六、模型求解问题(1):根据所建立的数学模型,用 CAD 画出可能的最短路径,构建每条路线的行走矩阵,通过MATLAB 编程计算出每天路线的实际长度,从而得到最短路径。1、OA 路段,这是四个路段中最简单的情况,从 O 到 A 经过了一个转弯,从图 5 中易看出有两种方案,虚线与实线各代表一个方案。2, 1, 12 2,2 2, 12 , 1 2, 1, 12,
14、 1, i2arccos2 iiiiiiiiii iiiiiilllll22arccosarccos1,1,1,lliiiiiirri 段为模型 1i 段为模型 2i 段为模型 3机器人避障问题利用 MATLAB 编程求解,计算结果如下:机器人从 O 到 A 的行走路线长度为 471.0372;同理,O 从下面绕到目标点 A 的总的路线长度为 498.4259;通过比较两种方案的结果易知,机器人在点 O 从上面绕到目标点 A 的距离最短,期最短路线长度为 471.0372 。2、OB 路段,经过分析与整理,我们得到四种方案,如图 6 所示,在这四种方案中,三种模型全部都要用到,模型一在 OA
15、路段已详细说明,模型二就是从起始点到目标点经过的圆弧在所走路径的异侧,而模型三就是从起始点到目标点经过的圆弧在所走路径的同侧,从OB 路段,有多次转弯,具体见图 6。A(300,300)图 5(80,60)1O(0,0)O机器人避障问题就路线而言,机器人经过了五次转弯,根据三种模型中的理论公式,需要把各个圆弧与直线长度求得,可利用 MATLAB 软件对其进行编程。计算结果如下:路线机器人行走的总距离为 853.7001;路线机器人行走的总距离为 877.3841;路线机器人行走的总距离为 990.1608;路线机器人行走的总距离为;3100584. 1经过比较可得路线为最短路径,即机器人在点 O 从上面绕到目标点 B 的距离最短,期最短路线长度为 853.7001 。3、OC 路段,经过整理分析,我们得到四种方案,具体见图 7, 图 6B(100,700 )O(0,0 )机器人避障问题每条路线都是由圆弧与直线段,但是该路段与其他路段相比,又有其不同之处,在路线中有一部分