1、机器人避障建模论文概要承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网 上咨询等与队外的任何人(包括指导教师研究、讨论与赛题有关的问题.我们知道, 抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的 资料(包括网上查到的资料 ,必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出.我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性.如有违反竞赛规 则的行为,我们将受到严肃处理.我们参赛选择的题号是(从 A/B/C/D中选择一项填写 :D我们的参赛报名号为(如果赛区设置报名号的话
2、:13286005所属学校(请填写完整的全名 :黄冈职业技术学院参赛队员 (打印并签名 :1. 王欢2.3.指导教师或指导教师组负责人 (打印并签名 :数模教练组日期:2012年 9月 10日 赛区评阅编号(由赛区组委会评阅前进行编号:编 号 专 用 页赛区评阅编号(由赛区组委会评阅前进行编号:赛区评阅记录(可供赛区评阅时使用:评阅人评分备注全国统一编号(由赛区组委会送交全国前编号:全国评阅编号(由全国组委会评阅前进行编号:机器人避障行走路径的优化模型摘要在科学探索和紧急抢险中经常会遇到对与一些危险或人类不能直接到达的地域的探 测,这些就需要用机器人来完成.而机器人在复杂地形中行进时自动避障是
3、一项必不可 少也是最基本的功能.本文研究了机器人最短避障路径和最短时间的避障路径问题.主要研究了在一个区 域中存在 12个障碍物,由出发点到达目标点以及由出发点经过途中的若干目标点回到 出发点的两种情况.我们通过证明具有圆形限定区域的最短路径是由两部分组成的,一 部分是平面上的自然最短路径即直线段,另一部分是限定区域的部分边界,这两部分是相切的、 互相连接的 1.据此, 我们可以认为最短路径一定是由直线段和圆弧组成, 因此 我们建立了线圆结构,在这种结果上面,我们再运用解析几何的方法建立模型:AF=2122-210-30080-300+, OE =2122-0-2100-80+(+=22222
4、2222222122111021008021030080300203000300210300803000210080arccos 0210080arccos 21030080300arccos -2EF 然后运用 matlab 软件进行求解,最终得到最短路径:OA 最短距离为:471.005, OB 最短距离为:975.6588OC 最短距离为:1092.2892, OABCO 最短距离为:2714.3069对于最短时间路径,采取非线性规划法建立模型:(022222201. 010(30030012V y x y x V e ar T r+=, 然后运用 lingo 软件求解,最终得出最短时间
5、:OA 最短时间为:84.084919.关键字 :最短路径 最短时间路径 非线性规划 避障路径一 、问题的背景与提出下图中是一个 800800的平面场景图, 在原点 O(0,0点处有一个机器人, 它只能 在该平面场景范围内活动.图中有 12个不同形状的区域是机器人不能与之发生碰撞的障 碍物,障碍物的数学描述如下表:编号 障碍物名称 左下顶点坐标 其它特性描述1正方形 (300,400 边长 2002圆形 圆心坐标(550,450,半径 703平行四边形 (360,240 底边长 140,左上顶点坐标(400,3304三角形 (280,100 上顶点坐标(345,210,右下顶点坐标(410,1
6、00 5正方形 (80,60 边长 1506三角形 (60,300 上顶点坐标(150,435,右下顶点坐标(235,300 7长方形 (0,470 长 220,宽 608平行四边形 (150,600 底边长 90,左上顶点坐标(180,6809长方形 (370,680 长 60,宽 12010正方形 (540,600 边长 13011正方形 (640,520 边长 8012长方形 (500,140 长 300,宽 60在题中的平面场景中,障碍物外指定一点为机器人要到达的目标点(要求目标点与 障碍物的距离至少超过 10个单位.规定机器人的行走路径由直线段和圆弧组成,其中 圆弧是机器人转弯路径.
7、机器人不能折线转弯,转弯路径由与直线路径相切的一段圆弧 组成,也可以由两个或多个相切的圆弧路径组成,但每个圆弧的半径最小为 10个单位. 为了不与障碍物发生碰撞,同时要求机器人行走线路与障碍物间的最近距离为 10个单 位,否则将发生碰撞,若碰撞发生,则机器人无法完成行走.机器人直线行走的最大速度为 5个单位/秒.机器人转弯时, 最大转弯速度为 21. 01001+ev , 其中是转弯半 径,如果超过该速度,机器人将发生侧翻,无法完成行走.建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型. 对场景图中4个点O(0,0,A(300,300,B(100,700,C(700,64
8、0,具体计算:(1机器人从O(0,0出发,OA、OB、OC和OABCO的最短路径.(2机器人从O (0,0出发,到达A的最短时间路径.注:要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器 人行走的总距离和总时间.二 问题的分析问题一中要求机器人从定点 O(0,0按照一定的行走规则绕过障碍物到达目标点的 最短路径,我们可以采用穷举法列出 O 到每个目标点的可能的最短路径,然后比较其大小 便可得出 O 到目标点的最短路径.求机器人从定点 O(0,0经过中间的若干点按照一定的 规则绕过障碍物回到 O 点,这时我们考虑的就不仅仅是经过障碍物拐点的问题,也应该 考虑经过路径中的目标点
9、处转弯的问题,这时简单的线圆结构就不能解决这种问题, 我 们在拐点及途中目标点处都采用最小转弯半径的形式,求得最短路径.问题二中要求机器人从定点 O (0,0 按照一定的行走规则绕过障碍物到达目标点的 最短时间路径,我们可以对最短路径模型进行优化,从而求出最短时间路径.三 模型的假设1. 假设机器人在直线上和圆弧上均以最大速度行走,机器人改变速度时的时间忽略不 计.2. 假设机器人的体积、质量不计,可以把机器人看作一个点. 3四 符号的说明符号符号说明 L 路径的总长度 i d 第 i 段切线的长度 j l 第 j 段圆弧的长度r 转弯半径 EF 圆弧的弧长 T 时间五 模型的建立与求解5.1
10、先来证明一个猜想 猜想:具有圆形限定区域的最短路径是由两部分组成的:一部分是平面上的自然最短路径(即直线段,另一部分是限定区域的部分边界,这两部分是相切的,互相连接的(即问 题分析中的拉绳子拉到最紧时的状况.证明:假设在平面中有 A(a,0和 B(-a,0两点,中间有一个半圆形的障碍物证明从 A 到 B 的圆弧路径为 AEFB.平面上连接两点最短的路径是通过这两点的直线段,但是连接两点的线段于障碍物 相交,所以设法尝试折线路径.在 y 轴上取一点 C(0,y ,若 y 适当大,则折线 ACB 与 障碍物不相交,折线 ACB 的长度为:222y a ACB +=(1显然 ACB 随着 y 的减小
11、而减小, 减小 y 得 y 1y , 即 C 1C ,使得 1AC 与 B C 1与障碍物相切,切点分别为 E 和 F,显然 B AC 1是这种折线路径中最短的.由于满足 20的角满足,tan ,所以易知弧度 EF 小于 F EC 1的长, 即 F EC EF 1,从而 B AC FB EF AE 1+, 记线段 AE、弧度 EF、线段 FB 为 AEFB,那么 AEFB 比任何折线路径都短.下面在考察一条不穿过障碍物的任何一条路径,设其分别于 OE 和 OF 的延长线交与 P、 Q 两点, 记 A 和 P 之间的路径长度为 AP , 显然 AP |AP|,又由 EO AE ,所以|AP|AE
12、,从而 AP AE,同理可得 BQ BF.4再来比较 PQ 之间路径长度 PQ 和圆弧 EF 的长度的大小.若 PQ 之间的路径可 有极坐标方程 (=,则有 1,可得:+=EF d d PQ 322(2亦即路径 APQB 的长度超过路径 AEFB 的长度.以上证明足以说明了 AEFB 是满足条件 A 到 B 的最短路径.5.1.1建立 OA 的模型 方案一:图 1在图1中,令半径为 1,5号正方形的左上角坐标为D(80,210以D点画半径为 的圆, 从O,A两点向圆做切线,切点为E(1x , 2x 、F(x2,y 2 有AF=2122-210-30080-300+(3 OE=2122-0-21
13、00-80+(4圆弧EF(+=222222222222122111021008021030080300203000300210300803000210080arccos 0210080arccos 21030080300arccos -2EF 总长度L 1=AF+OE+EF,经MATLAB软件计算出 xmin =10lmin =471.005方案二:在图2中,令半径为 2,5号正方形的右下角坐标为G(230,60以G点画半径为 2的圆, 从O,A4两点向圆做切线, 切点为 H(3x , 3y 、I(4x , 5x 有 AH=2222 60300( 230300(+(55OI=2222 060(
14、 0230(+(6圆弧 IH(+=222222222222222222060023060300230300203000300603002303000600230arccos 0600230arccos 60300230300arccos-2IH 总长度L 2=AH+OI+IH,经MATLAB软件计算出 xmin =10lmin =498.39因为 1L 2L ,所以选方案一,则:E点的坐标方程是:=+=+22121212122210 210( 80(x 1021080y x y (7经 MATLAB 软件计算、我们筛选出 E 点的坐标是 =14. 21350. 7011y x F 点的坐标方程
15、是:+=+=+22222222222210 210300( 80300( 210( 80(10 210( 80 (y x y x 经 MATLAB 软件计算、我们筛选出 F 点的坐标是 =41. 21917. 8422y x 5.1.2建立 OB 的模型 :图 2假设机器人从起点 O 到目标点 B,由图 2知路径一定是由圆弧和线段组成, 设有 m 条线段, n 条圆弧.那么目标函数可以表示为:6=+=nj jm i i l d L 11min (8用此模型就可以对起点到目标点之间的路径进行优化求解.运用 matlab 求解最短线段与 弧长. 路径一:B号图右上顶点 号图右下顶点 号图右下顶点
16、8659188. 1060min =L ;路径二:B号图左下顶点 号图右上顶点 号图右下顶点 号图右下顶点 号图右下顶点 877656588. 9755161min =+=j j i i l d L ;路径三:B号图左下顶点 号图右上顶点 号图右下顶点 号图右下顶点 号图左上顶点 877659712. 9955161min =+=j j i i l d L 路径四:B号图左下顶点 号图右上顶点 号图右下顶点 号图上顶点 号图左下顶点 877669712. 9935161min =+=j j i i l d L 通过比较,机器人通过路径二走的路程最短 .表 1起点坐标终点坐标 圆弧的圆心 坐标直
17、线长或 弧长 线段 一 (0,0 (227.0709,69.5614237.4868弧形 二 (227.0709,69.5614(240,80 (230,60 7.6092线段 二 (240,80 (240,210130弧形 二 (240,210(239.9846,209.4453 (230,21014.9415线段 三 (239.9846,209.4453 (244.6126,297.243787.9196弧形 三 (244.6126,297.2437 (244.7897,302.0403 (235,300 4.7433线段 四 (244.7897,302.0403 (229.9957,46
18、9.7055 168.3166弧形 四(229.9957,469.7055(230,470(220,4700.29457线段 五 (230,470 (230,530 100弧形 五 (230,530 (227.07,537.07 (220,5307.8707线段 六 (227.07,537.07 (144.50,591.65 98.9787弧形 六 (144.50,591.65 (140.69,596.35 (150,600 6.1471线段 七(140.69,596.35(100,700111.3508则最短路线为 975.6588,总时间为 179.3427. 5.1.3建立 OC 的模型
19、图 3给出了 O 到 C 点的可能的最短路径.O 到 C 的路径是由多条直线段和多段圆弧组 成的,我们可以分别求出各条直线和各段圆弧的长,然后相加,就可求出各路径的长, 再相互比较可得到最短路径.图 3=+=mi nj ii l d L 11min 我们通过 MATLAB 求得机器人在最短路径中每段直线段和圆弧的起点和终点坐标、圆 弧的圆心坐标以及机器人行走的总距离和总时间(表 2 .表 2起点坐标 终点坐标圆弧的圆心 坐标 直线长或 弧长 机器人行走时间线段一 (0,0 (227.0709,60.5614237.486847.4974圆弧一 (227.0709,60.5614(232.169
20、3,50.2381(230,60 5.45923.0974线段二(232.1693,50.2381(412.1693,90.2381179.513235.9026圆弧 (412.1693,90.2381(418.3448,94.4897(410,1008.43093.3723二 线段 (418.3448,94.4897 (491.6552,205.5103 126.2093 三 圆弧 (491.6552,205.5103 (492.2017,206.2599 (500,200 1.9822 三 线段 (492.2017,206.2599 (727.9377,513.9179 387.5888
21、四 圆弧 (727.9377,513.9179 (730,520 (720,520 6.5381 四 线段 (730,520 (730,600 80 五 圆弧 (730,600 (727.7178,606.3689 (720,600 6.8916 五 线段 (727.7178,606.3589 （700，640） 43.689 六 由此可得机器人行走的总距离为 1092.2892，总时间为 223.3330. 5.1.4 建立 OABCO 的模型 25.2418 0.7928 77.5177 2.6152 16 2.7566 8.7178 图4 机器人从定点 O(0, 0经过中间的 A、B、C
22、 三点按照一定的规则绕过障碍物到达目标 点，这使我们考虑的就不仅仅是经过障碍物拐点的问题，也应该考虑经过路径中的目标 点处转弯的问题，这时简单的线圆结构就不能解决这种问题，我们在拐点及途中目标点 处都采用最小转弯半径的形式，最终求得最短路径.具体情况见表 3. 表3 起点坐标 线段一 圆弧一 线段二 圆弧二 （0,0） （70.506,213.1406） （76.6064,219.4066） （291.0754,296.7803） 终点坐标 （70.506,213.1406） （76.6064,219.4066） （291.0754,296.7803） （297.2537,309.0814）
23、8 圆弧的圆心坐标 直线长或弧长 224.4994 机器人行走时 间 44.8998 3.6204 45.5998 6.0728 （80,210） 9.051 227.9992 （287.6818,306.1869） 15.1822 线段三 圆弧三 线段四 圆弧四 线段五 圆弧五 线段六 圆弧六 线段七 圆弧七 线段八 圆弧八 线段九 圆弧九 线段十 圆弧十 线段十一 圆弧十一 线段十二 圆弧十二 线段十三 圆弧十三 线段十四 圆弧十四 线段十五 圆弧十五 线段十六 圆弧十六 线段十七 （297.2537,309.0814） （229.5719,532.8946） （225.4967,538.
24、3538） （144.5033,591.6462） （140.6916,596.3458） （105.7133,685.4465） （115.6079,699.0835） （270.5862,689.9828） （272.0119,689.7955） （366.7444,670.3384） （369.3239,670） （429.3239,670） （435.109,671.8432） （533.9915,738.2997） （539.5695,740） （669.5695,740） （679.3272,732.1881） （699.4778,642.3288） （701.5176,638.1
25、58） （727.7178,606.3689） （730,600） （730,520） (727.9377,513.9179 (492.2017,206.2599 (491.6552,205.5103 (418.3448,94.4897 (412.1693,90.2381 (232.1693,50.2381 (227.0709,60.5614 （229.5719,532.8946） （225.4967,538.3538） （144.5033,591.6462） （140.6916,596.3458） （105.7133,685.4465） （115.6079,699.0835） （270.58
26、62,689.9828） （272.0119,689.7955） （366.7444,670.3384） （369.3239,670） （429.3239,670） （435.109,671.8432） （533.9915,738.2997） （539.5695,740） （669.5695,740） （679.3272,732.1881） （699.4778,642.3288） （701.5176,638.158） （727.7178,606.3689） （730,600） （730,520） （727.9377,513.9179） (492.2017,206.2599 (491.6552,
27、205.5103 (418.3448,94.4897 (412.1693,90.2381 (232.1693,50.2381 (227.0709,60.5614 （0,0） (230,60 (410,100 (500,200 (720,520 (720,600 (709.2354,644.5159 (670,730 (540,730 (430,680 （370,680） （270,680） （115.0217,689.1007） （150,600） （220,530） 233.8229 6.1474 96.9536 20.0354 95.7205 6.1424 155.2453 1.4392
28、96.71 2.609 60 6.169 119.1394 5.9174 130 13.502 92.0909 4.6856 41.2023 6.8916 80 6.5381 387.5888 1.9822 126.2093 8.4309 179.5132 5.4592 237.4868 46.7645 2.4589 19.3907 8.0141 19.1441 2.4589 31.049 0.5756 19.342 1.0436 12 2.4676 23.8278 2.3669 26 5.4008 18.4181 1.8742 8.2404 2.7566 16 2.6152 77.5177
29、0.7928 25.2418 3.3723 35.9026 3.0974 47.4974 由此可得机器人行走的总距离为 2714.3069 ，总时间为 565.9679. 5.2 最短时间模型 机器人从定点 O （0,0） 按照一定的行走规则绕过障碍物到达目标点的最短时间路径， 圆弧上半径（ ）越大，机器人在弧线上的速度越大，则建立下面模型：设经过 O 点与 圆弧的切线与经过 A 点与圆弧的切线的切点分别为 9 ， 圆弧的圆心角为 a， 则两条切线的交点坐标为 经过两个切点的弦的终点坐标为 目标函数为： ， 2 2 ， ar 1 + e (100.1r T= + V0 约束条件为： ( 2 (
30、x 2 + y2 + (300 x + (300 y 2 2 V0 2 2 2r 2 (x 2 x1 ( y 2 y1 cos a = 2r 2 300( y 2 + x 2 y1 y 2 y1 300( y 2 + x 2 x1 x 2 x1 ( y 2 y1 (x x 300 x x y 300 y + x y 2 300 x x y 300 y + x y 2 = ( 1 2 1 1 1 2 1 2 1 1 1 2 1 2 1 2 2 2 300( y 2 + x 2 y1 y 2 y1 300( y 2 + x 2 x1 x 2 x1 y 2 y1 + + y1 2 300 x1 x1 y 2 300 y1 + x 2 y1 2 2 s.t = 300 x1 x1 y 2 300 y1 + x 2 y1 2 2 2 300( y 2 + x 2
