机器人行走路径的最优方案.doc

《机器人行走路径的最优方案.doc》由会员分享，可在线阅读，更多相关《机器人行走路径的最优方案.doc（14页珍藏版）》请在三一文库上搜索。

1、机器人行走路径的最优方案 2012高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的 资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规 则的行为，我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会，可将我们的论

2、文以任何形式进行公开展 示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： D 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 重庆市正大软件软件职业技术学院 参赛队员 (打印并签名) ：1. 王永清 指导教师或指导教师组负责人 (打印并签名)： 日期： 2012 年 9 月 10 日 赛区评阅编号（由赛区组委会评阅前进行编号）： 2012高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 全国统一编号（由赛区组委会送交全国前编号）： 全国

3、评阅编号（由全国组委会评阅前进行编号）： 摘要 本文研究的是机器人避障路径行走的最优方案。 针对问题一，机器人在行走时，首先考虑与障碍物的最小距离为转弯时的半径。然后，用各种几何知识（如：可视图法）分析OA、OB、OC以及 将障碍物的起始点和目标点用直线和圆弧画出来，OABCO的路径有哪些， 而且要求不能穿越障碍物。图中的弧段就是集合，其中，起始点O连接的任何目标点都均不能与障碍物相交，在绕A、B、C时采用的是LINGO13编程，本队用MATLAN7.0软件编程计算从起始点到目标点的最优路径。 机器人从O到A的最短路径为471.0372，所花时间为96.0177秒； O到B的最短路径为853.

4、1178，所花的时间为179.34276秒； O到C的最短路径为1088.195，所花的时间为222.0105秒； O绕A、B、C再回到O点，其最短路径为2729.885，所花时间为568.6497秒。 针对问题二，采用与问题一类似的方法解决此问题，用LINGO13软件编程计算出当机器人从障碍物上方绕过时到达A的最短时间为94.2283秒。此时，机器人所绕圆弧的半径和圆心分别为12.9885、（82.1414,207.9153）。 关键词：可视图法 最短路径 最优方案 MATLAB7.0 LINGO13 一、问题的提出 在一个800*800的平面场景图中，在原点O(0,0)点处有一个机器人，机

5、器人只能在800*800的范围内活动。在图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物左下顶点的数学描述见表1： 碍物的距离至少超过10个单位）。因此，需要确定机器人的最优行走路线，由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由于直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法达到目标点，即行走失败。 机器人直线行走的最大速度为v0=5个单位/秒。机器人转弯时，最大转弯速度为v

6、0v=v()=，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法 10-0.121+e 完成行走。 需要解决的问题： 1、场景图中有四个目标点O(0,0)、A(300,300)、B(100,700)、C(700,640)，用数学模型的方法给出机器人从O(0,0)出发安全到达每个目标点的最短路线,即OA、OB、OC和OABCO； 2、机器人从O(0,0)出发，求出到达A的最短路径的时间。 二、问题的分析 1、对于移动机器人路径规划的问题的方法有很多种。要求求顶点O(0,0)按照行走规则绕过障碍物到达目标点的最短路径，我们可以画出机器人能行走的区域。 2、机器人的活动范围受到限制，不能超过可

7、行走的区域。 3、机器人行走时为了安全不碰到障碍物，因此，机器人离障碍物樾近就越危险。 4、机器人灵活度有限不能折线转弯，转弯路径是由直线和圆弧组成，也可以由两个或多个相切的圆弧路径组成。 对于问题一，经过理论分析，机器人的行进路径必定是由两个或多个相切的圆弧路径组成。 对于问题二，机器人直线行走的最大速度为v0=5个单位/秒。机器人转弯时，最大v0转弯速度为v=v()=，其中是转弯半径。那么，其中最重要的两个因素就 10-0.121+e 是圆心和半径。 三、模型的假设 1、假设机器人是一个质点； 2、假设机器人在行走过程中不出现任何意外； 3、假设机器人能准确的按弧线行走； 4、假设机器人一

8、直以最大速度行走； 四、符号说明 di 表示第i段路径的长度（起点到下一切线中点的路径、中点外）； lj 表示第j条余线的长度； fi 表示第j条圆弧的长度； r 表示转弯半径； q 表示机器人到障碍物的最短距离。 五、模型的建立与求解 5.1模型的准备 我们可以这样认为，无论图中有多少障碍物，那么，机器人所行走的途径必定是由很多条直线和圆弧组成。本题中所存在的障碍物是在拐点处，其中这个危险区域的半径为10。因此，我们结合定理可以知道，求两点之间的最短路径，他所转的弯，我们可以按照最小的转弯半径来计算，才能使所计算的路径达到最短 D 图5.1.1 如图5.1.1设A(x1,y1)为起点，B(x

9、2,y2)为目标点，C和 D两点分别为机器人经过 的拐点和隔离危险线拐角圆弧的切点，圆心为O(x3,y3),圆的半径为r，AB的长度为a， AO的长度为b，BO的长度为c，角度AOB=，AOC=,BOD=,COD=, 求ACDB的长度L： B C r 由图可得： ?a=? ?b=? ?c=? b2+c2-a2?=arccos() ?2bc ?r?=arccos b? ?r?=arccos c? ?=2- 又： +BDL=AC+CD =r面对图5.1.2这两种情况，我们不能直接采用直线与圆弧组成的方法来计算他的最 O2(x2,y2)，假设图5.1.2两个圆心的坐标分别为O1(x1,y1)、圆心连

10、线O1O2与切线AB 交于点C(x3,x3) x1+x2?x=?32? ?y=y1+y2 3?2 A C 同样，我们假设图5.1.3两个圆心的坐标分别为O1(x1,y1)、O2(x2,y2) (y-y) Ko1o2=21 (x2-x1) 那么O1O2的直线方程为： y=Ko1o2(x-x1)+y1 因为公共切线AB与O1O2平行，那么AB的直线方程可以表示为： y=Ko1o2(x-x1)+y1+c 其中： c= 因此，联立公共线和圆的方程，可以求得切点A和B坐标。 52模型的建立求解 针对问题一： OA、OB的模型为： dj j=1n ?r10 s.t? q10? OC、OABCO的模型为：

11、li+fi i=1 i=1 mm-1 ?r10 s.t? q10? 由于在计算OC和OABCO时误差太大，因此，本队决定换另外一种方法解决此问题。 5.2.1对于问题一的求解，以下给出了O到A、B、C各个目标点的最短路径。 解决的是O到目标点A的最短路径问题，从图5.2可以看出有两条可能性的路劲分别是OO1A和OO2A，再计算出两条路径，最后进行比较。 OO1A根据图5.2可以看出从O点出发到目标点A有两条路径可以走，即：（1） （2）OO2A这两条路径都是由直线和圆弧组成。用MATLAB软件编程求得的结果如下： OO1A:471.0372 OO2A:498.4295 计算得出O1=471.0

12、372、O2=498.4295,所以从O点出发到目标点A的最短路径是OO1A,因此，应该选择OO1A:471.0372这条路径。 5.2.2对于问题二的求解，以下给出O到A、B、C各个目标点的最短路径。 解决的是O到目标点B的最短路径问题。如图5.3，红线表示出来的可能的路径有三条，先分别计算出可能的三条路径，再对这三条路径进行比较，看那条最短。哪条最短就是O到目标点B的最短路径。 根据图5.3可以看出从O点出发到目标点B有三条路径可以走，即：（1）OO1O2O3O4O5B（2）OO6O7O4O5B（3）OO8O7O4O5B这三条路径都是由直线和圆弧组成。用MATLAB软件编程 求得的结果如下

13、： 第一条路径：391.1356+126.7324+81.4875+88.3651+165.3962=853.1178 第二条路径：321.7278+216.5186+172.9581+165.9795=877.3840 第三条路径：372.5440+237.7924+172.9581+165.9575=949.2740 从所得的结果看第一条路径是到达目标点B点最短，第一条的路径为853.7001，第二条路径为877.384，0第三条的路径为949.2740，因此，机器人应选择走OO1O2O3O4O5B这条路径。 5.2.3对于问题三的求解，以下给出O到A、B、C各个目标点的最短路径。 解决的

14、是O到目标点C的最短路径问题。如图5.4，红线表示出来的可能的路径有一条。 根据图5.4可以看出从O点出发到目标点B有一条条路径可以走，即： （OO1O2O3O4O5C这一条路径都是由直线和圆弧组成，用MATLAB 软件编程求得的结果如下： OO1O2O3O4O5C为1088.195 5.2.4对于问题四的求解，以下给出O到A、B、C各个目标点的最短路径。 如图5.5，解决的就是OABCO的最短路径问题，我们采用直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由于直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。 从图5

15、.5可知从O点出发机器人能行走的路线有 解决OABCO的最短路径，见表5.2.1、5.2.2、5.2.3以及5.2.4 针对问题二： 机器人直线行走的最大速度为v0=5个单位/秒。机器人转弯时，最大转弯速度为v0 v=v()=，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法 10-0.12 1+e 完成行走。从已知条件可知行走直线的最大速度和转弯最大速度是限制了的，那么，最主要的因素是圆心和半径。 模型的建立： minz= (l1+l2)f + v0v1 (l1+l2)f?v=5,v=+1?0 v0v1 =r =r =10 s.t =ry(y-y) ?1*31=-1?x1(x3-x1)

16、 ?(300-y)(y-y) 22?*3=-1 (300-x)(x-x)?232?y>y?24 根据我们建立的模型，用LINGO13软件编程求解。(见附录2） 由软件求得的最优结果为94.2283 六、模型的评价 模型的优点： 1、根据题目中的已知条件，我们建立了比较优化的模型并计算出了机器人从起始点到达目标点的最短路径； 2、本模型采用的方法是可视图法； 3、本文所求出的最短路径比较符合实际。 模型的缺点： 1、当障碍物数量较多时，会影响速度减小； 2、机器人行走路径考虑的不够全面。 参考文献 2 谭勇基，数学建模，上海，复旦大学出版社，2011。 3 张德丰，MATLAB，北京，机械

17、工业出版社，2010. 附录1： 附录 问题一 该程序求出了机器人在绕A点时，过A点那一圆弧的圆心，及与它相邻的两天切线的切点，和这两条切线与圆弧的总长度; min=sqrt(x2-x1)2+(y2-y1)2)+sqrt(x4-x3)2+(y4-y3)2)+r*2*asin(sqrt(x3-x2)2+(y3-y2)2)/2/r);!AAAAAAAAAAA; r=10; (y2-y1)/(x2-x1)*(y1-210)/(x1-80)=-1; (y4-y3)/(x4-x3)*(530-y4)/(220-x4)=-1; (y5-y2)/(x5-x2)*(y2-y1)/(x2-x1)=-1; (y5

18、-y3)/(x5-x3)=(530-y4)/(220-x4); (y4-y3)/(x4-x3)=(530-y5)/(220-x5); sqrt(x1-80)2+(y1-210)2)=r; sqrt(x5-x2)2+(y5-y2)2)=r; sqrt(x5-x3)2+(y5-y3)2)=r; sqrt(x4-220)2+(y4-530)2)=r; sqrt(x5-300)2+(y5-300)2)=r; 该程序求出了机器人在绕B点时，过B点那一圆弧的圆心，及与它相邻的两天切线的切点，和这两条切线与圆弧的总长度; min=sqrt(x2-x1)2+(y2-y1)2)+sqrt(x4-x3)2+(y4

19、-y3)2)+r*2*asin(sqrt(x3-x2)2+(y3-y2)2)/2/r);!BBBBBBBBBBB; r=10; (y5-y2)/(x5-x2)*(y2-y1)/(x2-x1)=-1; (600-y1)/(150-x1)=(y5-y2)/(x5-x2); (y5-y3)/(x5-x3)*(y4-y3)/(x4-x3)=-1; (y4-680)/(x4-270)=(y5-y3)/(x5-x3); sqrt(150-x1)2+(600-y1)2)=r; sqrt(x5-x2)2+(y5-y2)2)=r; sqrt(x5-100)2+(y5-700)2)=r; sqrt(x5-x3)2

20、+(y5-y3)2)=r; sqrt(270-x4)2+(680-y4)2)=r; x2<x3; 该程序求出了机器人在绕C点时，过C点那一圆弧的圆心，及与它相邻的两天切线的切点，和这两条切线与圆弧的总长度; min=sqrt(x2-x1)2+(y2-y1)2)+sqrt(x4-x3)2+(y4-y3)2)+r*2*asin(sqrt(x3-x2)2+(y3-y2)2)/2/r);!CCCCCCC; r=10; (y5-y2)/(x5-x2)*(y2-y1)/(x2-x1)=-1; (730-y1)/(670-x1)=(y5-y2)/(x5-x2); (y5-y3)/(x5-x3)*(y4

21、-y3)/(x4-x3)=-1; (y4-600)/(x4-720)=(y5-y3)/(x5-x3); sqrt(670-x1)2+(730-y1)2)=r; sqrt(x5-x2)2+(y5-y2)2)=r; sqrt(x5-700)2+(y5-640)2)=r; sqrt(x5-x3)2+(y5-y3)2)=r; sqrt(720-x4)2+(600-y4)2)=r; 附录2： 问题二用LINGO13编程如下： min=sqrt(x12+y12)/5+sqrt(300-x2)2+(300-y2)2)/5+r*2*asin(sqrt(x2-x1)2+(y2-y1)2)/2/r)/(5/(1+e(10-0.1*r2); e=2.7183; y1/x1*(y3-y1)/(x3-x1)=-1; (300-y2)/(300-x2)*(y3-y2)/(x3-x2)=-1; sqrt(x3-x1)2+(y3-y1)2)=r; sqrt(x3-x2)2+(y3-y2)2)=r; sqrt(x4-80)2+(y4-210)2)=10; sqrt(x3-80)2+(y3-210)2)+10=r; y2>y4;