当前位置首页 > 建筑/施工 > 施工组织
搜柄,搜必应! 快速导航 | 使用教程  [会员中心]

机器人避障路径问题数学建模

文档格式:DOC| 21 页|大小 841KB|积分 10|2022-05-14 发布|文档ID:90272662
第1页
下载文档到电脑,查找使用更方便 还剩页未读,继续阅读>>
1 / 21
此文档下载收益归作者所有 下载文档
  • 版权提示
  • 文本预览
  • 常见问题
  • 2012高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白,在竞赛开场后参赛队员不能以任何方式〔包括、电子、网上咨询等〕与队外的任何人〔包括指导教师〕研究、讨论与赛题有关的问题我们知道,抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料〔包括网上查到的资料〕,必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出我们重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性如有违反竞赛规则的行为,我们将受到严肃处理我们授权全国大学生数学建模竞赛组委会,可将我们的论文以任何形式进展公开展示〔包括进展网上公示,在书籍、期刊和其他媒体进展正式或非正式发表等〕我们参赛选择的题号是〔从A/B/C/D中选择一项填写〕: 我们的参赛报名号为〔如果赛区设置报名号的话〕:所属学校〔请填写完整的全名〕:参赛队员 (打印并签名) :1. 2. 3.指导教师或指导教师组负责人 (打印并签名): 日期: 2012 年月日赛区评阅编号〔由赛区组委会评阅前进展编号〕:2012高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号〔由赛区组委会评阅前进展编号〕:赛区评阅记录〔可供赛区评阅时使用〕:评阅人评分备注全国统一编号〔由赛区组委会送交全国前编号〕:全国评阅编号〔由全国组委会评阅前进展编号〕:机器人避障问题摘要本文研究了机器人避障最短路径及最短时间的问题。

    主要解决在一个区域中存在12个不同形状障碍物,机器人由出发点到达目标点、由出发点经过途中的假设干目标点到达原点以及到*目标点最短时间路径的三种情形首先,我们通过证明具有圆形限定区域的最短路径是由两局部组成的:一局部是平面上的自然最短路径〔即直线段〕,另一局部是限定区域的局部边界这两局部是相切的、互相连接的我们依据这个结果,可以认为最短路径一定是由线和圆弧组成,因此我们建立了线圆构造,这样无论路径多么复杂,我们都可以将路径划分为假设干个这种线圆构造来求解其次,我们对于途中经过节点的再到达目标点的状况,我们采用了两种方案,一种是在拐点和节点都采用最小转弯半径的形式,另一种是适当扩大拐点处的转弯半径,使得机器人能够沿直线通过途中的目标点然后,建立了最优化模型对两种方案分别进展求解接下来,我们利用解析几何、解三角形以及线圆构造,结合题目给出的限定因素进展最优求解,建立起具有可操作性的模型,利用穷列法与层次分析法对机器人避障最短路径和最短时间路径进展筛选假设机器人从起点到到目标点,一定是由圆弧和线段组成,设有m条线段,n条圆弧则目标函数可以表示为:用此模型可对起点到目标点之间的路径进展优化求解得出目标函数。

    最后,我们对得出的模型进展综合评价,在评价过程中,我们根据题目给出的条件以及问题的分析,分别对最短路径和最短时间路径进展系统、合理的解答使得出的结果与模型更加合理,到达全局最优问题一,我们将其分解成线圆构造来求解,然后把可能路径的最短路径采用穷举法列举出来,最终用层次分析法得出最短路径::471.0312:853.8869:1082.3445:2989.3562问题二,我们利用物理中时间、速度与路程的关系就可以得出O(0,0)到达*目标点的最短的时间路径::471.0312起点坐标终点坐标圆心坐标线段一0,070.52,213.13弧一70.52,213.1376.61,219.4180,210线段二76.61,219.41300,300总路径471.03总时间96.02线段一0,050.18,301.91弧一50.18,301.9150.05,305.5460,300线段二50.05,305.54141.68,440.55弧二141.68,440.55145.28,443.52150,435线段三145.28,443.82222.09,460弧三222.09,460230,470220,470线段四230,470230,530弧四230,530225.49,538.45220,530线段五225.49,538.45146.35,590.69弧五146.35,590.69144.50,591.65150,600线段六144.50,591.65100,700总路径853.89总时间177.71线段一0,0412.22,90.25弧一412.22,90.25419.79,97.97410,100线段二412.79,97.97725.94,511,95弧二725.94,511.95730,520720,520线段三730,520730,600弧三730,600737.72,606.59720,600线段四737.72,606.59700,640总路径1082.24总时间219.55线段一0,070.52,213.13弧一70.52,213.1376.61,219.4180,210线段二76.61,219.41290.59,296.61弧二290.59,296.61309.41,296.63290.41,296.58线段三309.41,296.63232.43,536.21弧三232.43,536.21225.50,538.36220,530线段四225.50,538.36146.35,590.70弧四146.35,590.70144.50,591.65150,600线段五144.50,591.6596.10,690.80弧五96.10,690.80109.07,703.91102.51,696.51线段六109.07,703.91360.00,670.02弧六360,670.02370,670370,680线段七370,670430,670弧七430,670435.52,670.03430,680线段八435.52,670.03534.48,740.00弧八534.48,740.00540,740670,730线段九540,740702.43,638.52弧九702.43,638.52697.56,641.46696.43,637.53线段十697.56,641.46737.72,606.59弧十737.72,606.59730,600720,600线段十一730,600730,520弧十一730,520725.94,511.95720,520线段十二725.94,511.95419.79,97.97弧十二419.79,97.97412.22,90.25410,100线段十三412.22,90.250,0总路径2989.3562总时间615.21关键词最优化模型最优路径层次分析避障路径解析几何解三角形评价模型一、 问题重述1.1问题背景图1是一个800×800的平面场景图,在原点O(0, 0)点处有一个机器人,它只能在该平面场景围活动。

    图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物,障碍物的数学描述如下表:编号障碍物名称左下顶点坐标其它特性描述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长方形(500, 140)长300,宽60在图1的平面场景中,障碍物外指定一点为机器人要到达的目标点〔要求目标点与障碍物的距离至少超过10个单位〕规定机器人的行走路径由直线段和圆弧组成,其中圆弧是机器人转弯路径机器人不能折线转弯,转弯路径由与直线路径相切的一段圆弧组成,也可以由两个或多个相切的圆弧路径组成,但每个圆弧的半径最小为10个单位。

    为了不与障碍物发生碰撞,同时要求机器人行走线路与障碍物间的最近距离为10个单位,否则将发生碰撞,假设碰撞发生,则机器人无法完成行走机器人直线行走的最大速度为个单位/秒机器人转弯时,最大转弯速度为,其中是转弯半径如果超过该速度,机器人将发生侧翻,无法完成行走1.2问题提出通过建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型对场景图中4个点O(0, 0),A(300, 300),B(100, 700),C(700, 640),具体计算以下问题:(1) 机器人从O(0, 0)出发,O→A、O→B、O→C和O→A→B→C→O的最短路径2) 机器人从O (0, 0)出发,到达A的最短时间路径注:要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间图1 800×800平面场景图二、问题分析2.1问题一首先,要求求定点O〔0, 0〕按照一定的行走规则绕过障碍物到达目标点的最短路径,我们可以用包络线画出机器人行走的危险区域,这样的话,拐角处就是一个半径为10的四分之一圆弧,则通过采用拉绳子的方法寻找可能的最短路径〔比方求O和A之间的最短路径,我们就可以连接O和A之间的一段绳子,以拐角处的圆弧为支撑拉紧,则这段绳子的长度便是O到A的一条可能的最短路径〕,然后采用穷举法列出O到每个目标点的可能路径的最短路径,然后比拟其大小便可得出O到目标点的最短路径。

    然后,要求求定点经过中间的假设干点按照一定的规则绕过障碍物到达目标点,这使我们考虑就不仅仅是经过障碍物拐点的问题,也应该考虑经过路径中的目标点处转弯的问题,这时简单的线圆构造就不能解决这种问题,我们在拐点及途中目标点处都采用最小转弯半径的形式,也可以适当的变换拐点处的拐弯半径,使机器人能够沿直线通过途中的目标点,然后建立优化模型对这两种方案分别进展优化,最终求得最短路径2.2问题二要求求O(0,0)到点A的最短时间路径在问题一中,我们根据求得的最短路径算出直线距离与圆弧的距离,再利用机器人在直线与拐弯处的最大速度,利用物理中时间、速度与路程的关系就可以得出O(0,0)到达*目标点的最短的时间路径三、模型假设1、假设障碍物全是规则图形2、假设机器人能够抽象成点来处理四、符号说明符号符号说明路径的总长度第段切线的长度第段圆弧的长度转弯半径障碍物上的任意点与行走路径之间的最短距离五、根本信息与数据处理5.1 最优化模型在机器人避障中的应用最优化模型在多样化选择性问题上具有优越性,我们所研究的机器人避障问题路径较多,所得最短路径将需要最优化模型来处理要找到最短历经及最短时间,最终使用最优化模型综合各方面因素来详细分析。

    5.2 最优化模型概述最优化问题,是指在日常生活过适当的规划安排,使得完成一件事所用的费用最少、路线最短、时间最短、产值最高、容积最大等的效率与分配问题,也就是要在各种方案中,寻找一个最节约、合理的方案解决这类问题要注意两点:一是明确问题,即通过问题描述中的数量关系把活问题转化为单纯的数学问题,我们称之为数学建模的过程;二是建模后的求解问题,即用相关的数学知识求解出最优的处理方案5.3 最优化模型的应用程序穷列法根本原理和步骤步骤1:将线性规划问题化成矩阵的标准形式,设系数矩阵的秩,则对应线性方程组的根底解系自由变量的个数为个步骤2:穷举法求解:令,解得对应线行方程组一组解为;对应目标函数值为从个变量中选个作为自由变量,令它们的值为,可得到组解步骤3:确定最优解:如果最优解存在,则上述求解得到的对应个目标函数中,最小者〔或最大者〕即为所求最小〔或最大〕最优值,对应的解为最优解步骤4:证明解为最优解: 1〕将最优解对应的自由变量看成参数;解对应线性方程组得,2〕将对应线性方程组解,代入目标函数得:如果,则所求为最小值最优解;否则,线性规划问题无最小值最优解如果,则所求为最大值最优解;否则,线性规划问题无最大值最优解。

    六、模型建立与处理6.1 先来证明一个猜测:猜测一:具有圆形限定区域的最短路径是由两局部组成的:一局部是平面上的自然最短路径〔即直线段〕,另一局部是限定区域的局部边界,这两局部是相切的,互相连接的〔即问题分析中的拉绳子拉到最紧时的状况〕证明:假设在平面中有A〔a,0〕和B〔-a,0〕两点,中间有一个半圆形的障碍物,证明从A到B的最路径为 Y *平面上连接两点最短的路径是通过这两点的直线段,但是连接两点的线段于障碍物相交,所以设法尝试折线路径在y轴上取一点C〔0,y〕,假设y适当大,则折线ACB与障碍物不相交,折线ACB的长度为:显然随着y的减小而减小,减小y得,即,使得与与障碍物相切,切点分别为E和F,显然是这种折线路径中最短的由于满足的角满足,所以易知弧度EF小于的长,即,从而,记线段AE、弧度EF、线段FB为AEFB,则AEFB比任何折线路径都短下面在考察一条不穿过障碍物的任何一条路径,设其分别于OE和OF的延长线交与P、Q两点,记A和P之间的路径长度为,显然>|AP|,又由AEEO,所以|AP|>AE,从而>AE,同理可得>BF。

    再来比拟PQ之间路径长度和圆弧EF的长度的大小假设PQ之间的路径可有极坐标方程,则有,可得:亦即路径APQB的长度超过路径AEFB的长度以上证明足以说明了AEFB是满足条件A到B的最短路径6.2 模型准备一有了6.1中的定理,我们就可以这样认为,起点到目标点无论中间障碍物有多少,最短路径都应该是假设干个线圆构造所组成在此题中存在障碍物的状况,且障碍物在拐点处的危险区域是一个半径为10的圆弧,所以结合定理一,我们易知,求两点之间的最短路径中的转弯半径我们应该按照最小的转弯半径来算才能到达最优线圆构造6.21 1〕如上图,设A为起点,B为目标点,C和D别为机器人经过拐点分别于隔离危险线拐角小圆弧的切点,圆心为O,圆的半径为r,AB的长度为a,AO的长度为b,BO的长度为c,角度,,,.求的长度,设为L.解法如下:如上图可得有以下关系::在:在中:所以:从而可得:2〕而对于以下图两种情况我们不能直接采用线圆的构造来解决,需要做简单的变换情况一:线圆构造6.22我们假设两圆心坐标分别为和,半径均为r,M点坐标为,则我们很容易可以求得:这样我们就可以利用1〕中的方法,先求A到M,再求M到B,这样分两段就可以求解。

    同理如果有更多的转弯,我们同样可以按照此种方法分解情况二:线圆构造6.23这里我们依然设圆心坐标分别为和,半径均为r,这样我们可以得到:则直线方程为:因为公切线DE与平行,则DE的直线方程可以表示为:其中:则把公切线的方程于圆的方程联立,渴可以求得切点D和E的坐标这样用D和E任意一点作为分割点都可以将上图分割成两个6.21所示的线圆构造,这样就可以对其进展求解同理多个这样的转弯时,用同样的方法可以进展分割6.3 模型准备二一、对于从起点经过假设干点然后再到达目标点的状况,因为不能走折线路径,我们就必须考虑在经过路径中的一个目标点时转弯的状况为了研究这个问题的方便,我们先来证明一个猜测:猜测二:如果一个圆环可以绕着环上一个定点转动,则过圆环外两定点连接一根绳子,并以该圆环为支撑拉紧绳子,到达平衡状态时,圆心与该顶点以及两条切线的延长线的交点共线图6.31证明猜测:如图6.31所示,E点就是圆环上的一个顶点,就是拉紧的绳子,就是切线AC和BD的延长线的交点,证明、E、三点共线我们可以用力学的知识进展证明,因为是拉紧的绳子,所以两边的绳子拉力相等,设为,它们的合力设为,定点对圆环的作用力设为。

    则由几何学的知识我们可以知道一定与共线,而又由力的平衡条件可知:即与共线综上所述、和三点一定共线二、有了以上这个定理我们可以建立以下模型:如图6.32,要求求出机器人从A绕过障碍物经过M点到达目标点B的最短路径,我们采用以下方法:用一根钉子使一个圆环定在M点,使这个圆环能够绕M点转动然后连接A和B的绳子并以这些转弯处的圆弧为支撑〔这里转弯处圆弧的半径均按照最小转弯半径来计算〕,拉紧绳子,则绳子的长度就是A到B的最短距离我们可以把路径图抽象为以下的几何图形下面我们对这段路径求解:图6.32如图,A是起点,B是终点,和是两个固定的圆,是一个可以绕M(p,q)点转动的圆环,三个圆的半径均为r,C、D、E、F、G、H均为切点a、b、c、e,f分别是A、、A、A、的长度A、B、、均是点,是未知点则最短路径就可以表示为:因为点的坐标未知,所以我们就不能用模型一中的线圆构造对其进展求解故得先求出点的坐标设坐标为〔m,n〕,、、、、分别为〔=1、2、3、4、5〕,、、分别为、、.便有以下关系:在中:在中:在中:在中:则:又因为一定会在的角平分线上,所以满足:我们采用向量的形式来求,易知的一个方向向量:而与垂直,故其一个方向向量:而:所以:综合以上式子可以求得的坐标,从而可以得出路径的长为:,这可以采用模型一中的线圆构造来求解。

    6.4 模型准备三求解从起点经过假设干个点再到达目标点的问题,与6.3不同,我们还可以有另一种方案,即适当扩大障碍物拐点处的拐弯半径使机器人能够沿直线通过路径中的目标点这样拐点处拐弯圆弧的半径和圆心都是个变量,对于该题,则我们可以首先设定三个圆心、、,然后按照以下步骤进展作图:1) 给定,以为圆心,为半径,画圆,然后过R点做圆的切线,切点为D然后过A点做的切线设为,切点为E2) 然后做F垂直于,垂足为F,F的长就是,然后以为圆心,为半径画圆很显然能由来确定,即3) 然后过B点做的切线为,切点为G,再过F垂直于,垂足为H,则H的长度就是,然后以为圆心,为半径,画圆很显然能由来确定,即=4) 过C做的切线这就完成了由R经过A和B在到达C的路径5) 然后再变换、、、、、,可得到新的路径找出最小者即可6.5 模型的建立假设机器人从起点R到到目标点,由6.2知路径一定是由圆弧和线段组成,设有m条线段,n条圆弧则目标函数可以表示为:用此模型就可以对起点到目标点之间的路径进展优化求解七、模型的建立与求解7.1 问题一一、以下给出了到个目标点的可能路径的最短路径:1〕如图一,解决的就是到目标点的最短路径问题,通过分析我们找到了两种最短路径,又通过计算得出红色路线为最短路,这样计算出绳子的长度就是到的最短路径为:471.03122〕如图二,解决的是到目标点的最短路径问题,图中给出了可能的三条路径的最短路径,我们可以分别计算出三条可能路径的最短路径的长度,然后进展比拟,取最小者就是到目标点的最优路径为:853.88693)如图三,解决的是到目标点的最短路径问题。

    图中给出了两条可能路径的最短路径,我们同样可以分别计算出两条可能的最短路径,取最小者就是到目标点的最优路为:1082.34454〕如图四,解决的是到目标点再到最短路径问题图为两种路径,我们采用模型优化进展求解,最终求得最短路径为:2989.3562图一图二图三图四7.2 问题二 解决的是最短时间路径,由分析可得路径为471.03〔时间:86.70〕与492.38〔时间:90.32〕,故最短路径为:471.03八、模型的评价与推广在此题中只有四个障碍物,按照线圆构造画出从起点到达目标点的路径是有限的,我们完全可以采用穷举法把这些路径列出来,然后比拟大小取最小者即可,但是我们可以设想如果这个区域有n个障碍物,则按照线圆构造从起点到达目标点的可能路径就有无数多条,这时我们如果在采用穷举法是不现实的所以我们必须寻求新的算法来解决这个问题由上述分析我们有了这样一个想法:先求出所有的切线,包括出发点和目标点到所有圆弧的切线以及所有圆弧与圆弧之间的切线,然后把这且曲线看成是图7.11中的,给这些定点赋一个等于切线长度的权值,如果*两条切线有一个公切圆弧,则代表这两条曲线的顶点是一条直线的两个端点,边上的权值等于这两条切线之间的劣弧长度。

    然后在这图中加一个源点和终点,则在所有代表出发点与其它圆弧之间切线的顶点与源点连成一条边,权值均为0,同理在所有代表目标点到其它圆弧切线的顶点与终点连成一条边,权值均为0,这样题目就转化成了求源点到达终点之间的最短路径问题了,这里最短路径就是指经过所有顶点与边的权值之和最小我们可以采用Dijkstra算法进展求解九、参考文献【1】薛定宇 "高等应用数学问题的MATLAB求解"清华大学【2】启源 金星 叶俊 "数学模型〔第三版〕" 高等教育【3】启源 "数学模型〔第二版〕" 高等教育 1993年【4】中庚 "数学建模方法及应用" 高等教育 2005年【5】叶其孝 "大学生数学建模竞赛辅导教材" 教育附录:1〕%求解一次转弯所经路线总长%T:初始点 V:转弯圆弧圆心 W:到达点 Function result=longhand(T,W,V,10)TV=sqrt((T(1)-V(1))^2+(T(2)-V(2))^2);TW=sqrt((T(1)-W(1))^2+(T(2)-W(2))^2);VW=sqrt((V(1)-W(1))^2+(V(2)-W(2))^2);alpha1=acos((TV^2+VW^2-TW^2)/(2*TV*VW));alpha2=acos(r/TV);alpha3=acos(r/VW);alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4为转弯圆心角TS1=sqrt(TV^2-r^2);%TS1,TS2均为圆弧切线%S2W=sqrt(VW^2-r^2);S1S2hu=r*alpha4;result=TS1+S1S2hu+S2W;2〕%判定是否经过路障,采用跨立实验〔计算几何算法〕function m=intersect(H1,H2,G1,G2)if min(H1(1),H2(1))<=ma*(G1(1),G2(1))&min(G1(1),G2(1))<=ma*(H1(1),H2(1))&min(G1(2),G2(2))<=ma*(H1(2),H2(2))&min(H1(2),H2(2))<=ma*(G1(2),G2(2))&((G1(1)-H1(1))*(H2(2)-H1(2))-(H2(1)-H1(1))*(G1(2)-H1(2)))*((H2(1)-H1(1))*(G2(2)-H1(2))-(H2(2)-H1(2))*(G2(1)-H1(1)))>=0 m=1;else if (abs((G2(2)*H2(1)-G2(2)*G1(1)-G1(2)*H2(1)+G1(1)*G1(2))/(G2(1)-G1(1))+G1(2)-H2(2)))/(sqrt(1+(G2(2)-G1(2))^2/(G2(1)-G1(1))^2))<=1%保证障碍圆弧局部与两点连线相切 m=1; else m=0; end3〕%求解R经过中间节点到达目标点的最短路径model:min=d1+b+d3+u+v+t;a=sqrt(40^2+15^2);b=sqrt((*1-40)^2+(y1-15)^2);c=sqrt(*1^2+y1^2);d1=3*3.1415926/2-acos((a^2+b^2-c^2)/(2*a*b))-acos(1/a);(*1-50)^2+(y1-40)^2=1;*1>49;*1<50;d2=acos(abs((50-*1+(1600-40**1-40*y1+*1*y1)/(y1-15))/(sqrt(1+(*1-40)^2/(y1-15)^2)*sqrt((50-*1)^2+(40-y1)^2))));e=sqrt();. z.。

    点击阅读更多内容
    卖家[上传人]:沈阳哈登
    资质:实名认证