搜索
2012高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：D题我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：机器避障问题摘要本文研究了机器人避障最短路径及最短时间路径的问题。移动机器人路径规划是指在有障碍物的工作环境中，如何寻找一条从给定起点到给定目标点的运动路径，使机器人在运动过程中能安全无碰撞地绕过所有障碍物，并走的是最短路径以及最短时间路径，主要研究了在一个区域中存在１２个障碍物，由出发点到达目标点以及由出发点经过途中的若干目标点到达最终目标点的两种情形。根据定理一最短路径有直线和圆弧所组成，故而我们在以可视图法所建的求解环境基础上建立了线圆结构，这样可以将任何路径分割为若干个这种线圆结构来求解。对于途中经过节点再到达目标点的状况，我们在拐点和节点都采用最小转弯半径的形式，然后建立了最短路径最优化模型。对于问题一，把可能路径的最短路径采用穷举法列出来，得出最短路径为,最短路径为,最短路径为,最短路径为.对于问题二，建立了优化模型，得圆心，半径为时，时间最短为，最短时间路径如图所示。关键词：最短路径最短时间路径避障路径平面解析几何一、问题重述1.1 背景机器人技术应该说是一个科学技术发展共同的一个综合性的结果，同时，为社会经济发展产生了一个重大影响的一门科学技术，它的发展归功于在第二次世界大战中各国加强了经济的投入，就加强了本国商务经济发展。机器人避障技术是评价移动机器人智能程度的关键指标，就是看其对未知障碍物的处理能力及对路径最优的识别能力，理想的机器人处于一位未知的，复杂的，动态的非结构化环境中，在实际控制系统时，常常会碰到一些系统需要大量的实验和不断尝试才能达到很好地控制效果，这种控制方式带有大量的主观性，同时这些系统很难用具体的数学模型来描述，对它们的控制方法是从人的生活经验中得到的，而经典控制理论则无能为力，因此，而设计有效的定性与定量的转换模型（控制器），就成为摆在专家学者面前的重要课题。1.2 问题机器人避障问题下图是一个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个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯速度为，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中4个点O(0,0)，A(300,300)，B(100,700)，C(700,640)，具体计算：第一，机器人从O(0,0)出发，O→A、O→B、O→C和O→A→B→C→O的最短路径。第二，机器人从O(0,0)出发，到达A的最短时间路径。注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。2、模型假设（1）、假设机器人能够抽象成点来处理。（2）、假设机器人可以立即变速。三、符号说明符号符号说明路径的总长度转弯半径第段切线总长度第段圆弧的长度所走路径时间四、问题的分析1、问题一，要求定点（0,0）按照一定的行走规则绕过障碍物到达目标点的最短路径，利用线圆结构来解，然后采用穷举法列出到每个目标点的可能路径的最短路径，然后比较其大小便可得出到目标点的最短路径。要求定点经过中间的若干点按照一定的规则绕过障碍物回到点，这是除考虑经过障碍物拐点的问题外，还应考虑经过路径中的目标点处转弯的问题，我们在拐点即途中目标点处都采用最小转弯半径形式求的最短路径。2、问题二，就是机器人从定点出发到达目标点最短时间路径，由问题一的求解经验，我们可以知道最短时间路径不能用简单的线圆结构解决，而在此问中，圆心的坐标是可变的，并且半径也是一个大于10个单位的变量，这就增加了问题的难度。所以我们在题一的基础上，要对路径巧妙优化，一在拐点和目标点处都采用最小转弯半径的形式；二可以适当的变换拐点处的拐弯半径，使机器人能够沿直线安全通过途中的拐点。然后建立数学优化模型，最终求得最小时间的路径。五、模型的建立5.1模型准备引理【1】具有圆形限立区域的最短路径是有两部分组成的：一部分是平面上的自然最短路径（即直线段），另一部分是限立区域的部分边界，这两部分是相切的，互相连接的。根据引理【1】，起点到目标点无论中间障碍物有多少，最短路径应该是若干个线圆结构组成。在本题中存在障碍物的状况，且障碍物在拐点处的危险区域是一个半径为10的圆弧，结合引理【1】，易知求两点之间的最短路径中的转弯半径应按最小的转弯半径来算才能达到最优。（1）有已知定理可知，不管起点到目标点之间有多少障碍物，最短路径都是由若干个线圆结构组成。因为本题中障碍物在拐点处的危险区域是一个半径为10个单位的圆弧，所以，我们在求两点之间的最短路径取最小转弯半径计算可得到最优值。如上图，设圆心,起点为,目标点和，圆的半径为r，AB的长度为a，AO的长度为b，BO的长度为c，角度=,=,=，.为机器人经过拐点分别于隔离危险线拐角圆弧的切点。则：由上图可得：则：所以可得最短路径：（2）对于从起点经过若干点然后到达目标点的状况，因为不能走折线路经，就必须考虑在经过路径中的一个目标点时转弯的状况，在转弯处圆弧的半径均按照最小转弯半径来计算。要求出机器人从Ａ绕过障碍物经过Ｍ点到达目标点Ｂ的最短路径，我们把路径图抽象为下面的几何图形，对这段路径求解 如图，是出发点，是目标点,和是两个固定的圆，是一个可以绕点点转动的圆环，三个圆的半径均为,均为切点，a、b、c、e，f分别是A、、A、A、的长度，。均是已知点，是未知点，则最短可表示为：其中:用模型一求解，下面求 因为在的角平分线上，所以,因为与垂直，方向向量为:，;则综上可得的坐标，可求出，从而求出.5.2最短路径模型的建立假设机器人从起点到到目标点，经过的路径都是由圆弧和线段组成，设有m条线段，n条圆弧。有p个切点，那么目标函数可以表示为：5.3最短时间路径模型的建立假设和分别是两条切线的长度，为经过路径圆弧线所对的圆心角，那么目标函数表示为：6、模型的求解6.1问题一一、以下给出了到各个目标点及,的最短路径：（1）如图所示：（2）结果如下：最短路线长度为471.04，坐标如下起点（切点）终点（切点）圆弧圆心（69.51,213.14）（75.62,221.4）（80,210）（77.61,220.41）（300,300）最短路线长度为854.84坐标如下：起点（切点）终点（切点）圆弧圆心（0，0）（49.14，302.64）（54914，302.64）（51.68，305.55）（60，300）（51.68，305.55）（141.68,440.55，）（141.68,440.55，）(147.96,444.79)(150,435)(147.96,444.79)(222.04,460.21)(222.04,460.21)（230，469.99）（220，470）（230，469.99）（230，530）（230，530）（225.50，538.35）（220，530）（225.50，538.35）(144.50,591.65)(144.50,591.65)（140.69，596.35）（150，600）（140.69，596.35）（100，700）最短路线长为1088.42坐标如下：起点（切点）终点（切点）圆弧圆心（0，0）（232.11，50.23）（232.11，50.23）（238.54，54.79）（230，60）（238.54，54.79）（336.46，215.21）（336.46，215.21）(344.36,219.98)(345,210)(344.36,219.98)(500.64,230.02)(500.64,230.02)(508.51,234.74)(500,240)(508.51,234.74)（727.12，512.98）（727.12，512.98）（730，595.99）（720，520）（730，595.99）（730，600）（730，600）（727.72，606.36）（720，600）（727.72，606.36）（700，640）最短路线长度为2726.03坐标如下：起点（切点）终点（切点）圆弧圆心（300，300）（229.57，532.89）（229.57，532.89）（225.49，538.35）（220，530）（225.49，538.35）（158.35.605.49）（225.49，538.35）（140.69，596.35）（150，600）（140.69，596.35）（100，700）(100,700)（270.59，689.98）（270.59，689.98）（272，689.79）（270，680）（272，689.79）（368，670.20）（368，670.20）（369.99,670）(370,680)（369.99,670）（424.00，688.00）（424.00，688.00）（427.43，689.66）(430,680)（427.43，689.66）(534.41,738.29)(534.41,738.29)(540,740)(540,730)(540,740)(669.99,740)(669.99,740)(679.77,732.14)(670,730)(679.77,732.14)(700,640)（700，64