2012高教社杯全国大学生数学建模竞赛
承 诺 书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： D 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：
参赛队员 (打印并签名) ：1. （此部分内容不便公开，见谅） 2. 3. 指导教师或指导教师组负责人 (打印并签名)：
日期： 2012 年 9 月 10 日
赛区评阅编号（由赛区组委会评阅前进行编号）：
2012高教社杯全国大学生数学建模竞赛
编 号 专 用 页
评 阅 人 评 分 备 注 赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
机器人避障问题
摘要
针对机器人避障问题，本文分别建立了机器人从区域中一点到达另一点的避障的最短路径、最短时间路径的非线性0-1整数规划模型。同时，本文为求带有NP属性的非线性0-1整数规划模型，构建了有效启发式算法，利用MATLAB软件编程，求得了O→A、O→B、O→C、O→A→B→A→C的最短路径，同时得到了O→A的最短时间路径，求得的各类最短路径均是全局最优。
针对区域中一点到达另一点的避障的最短路径问题，首先，本文证明了圆弧位置设定在需要绕过障碍物的顶角上，且圆弧半径为10个单位时，能够使得机器人从区域中一点到达另一点的行进路径最短；其次，本文将最短路径选择问题转化成了最短路径的优选问题，根据避障条件，建立了具有较高普适性的避障最短路径的优化模型。为便于求解，本文巧妙地将此优化模型转化成了以可行路径不与障碍物边界相交、不与圆弧相交为约束条件，以机器人从区域中一点达到另一点避障路径最短为目标的0-1规划模型；再次，本文构建了两种有效的启发式算法，利用MATLAB软件编程求得了O→A、O→B、O→C、O→A→B→A→C的最短路径，最短路径长分别为471.0372、853.7001、1088.1952、2725.1596，其中O-->A的最短路径为(0,0)→(70.5063,213.1405) →(75.975,219.1542)→（300,300)，对应圆弧的圆心坐标为(80,210)，O→B的最短路径，对应圆弧的圆心坐标：(60,300)、(150,435)、（220、470）、(220,530)、(150,600)， O→C经过的圆心：(410,100)、(230,60)、(720,520)，（720,600），(500,200)， O→A→B→C→O经过的圆心：(410,100)，(230,60)， (80,210)，(220,530)，(150,600)，(270,680)，(370,680)， (430,680)，(670,730)，(540,730)，(720,520)，(720,600)，(500,200)。
针对最短时间路径问题，我们建立了从o点出发到任意目标点的0-1非线性整数规划模型，同时针对题意要求，具体构建了从o点出发到A的最短时间路径的0-1非线性整数规划模型，利用LINGO软件求解，获得了机器人从o点出发，到达A的最短时间路径，求得最短时间路径下转弯半径为12.9885 ，同时最短时间路径时间长为94.2283个单位。相应圆弧的圆心坐标为（82.1414，207.9153），两切点坐标分别为（69.8045，211.9779）、（77.7492,220.1387）。
本文确定路线思路循序渐进，先建立了有计算避障约束公式的普适性模型，再建立了以不取相交点来简化0-1变量取值关系的简化模型；给出了二种启发式算法，最短路径即最短时间路径具有一定可信度。同时第一个启发算法可以求得全局最优解，第二个启发算法是针对问题的NP属性减少求解时间而构建的，两个算法都具有较重要的意义。
…… 此处隐藏1404字 ……
三、模型假设
1.假设将机器人看成一个质点；
2.假设半径不变时，机器人在行进、转弯过程中能一直保持最大的速度； 3.假设启发算法是针对问题的NP属性减少求解时间而构建的。
四、符号说明
符号 Z aij 含 义 避障最短路径 圆弧i切点到圆弧j切点的直线距离，即机器人从圆弧i切点到圆弧j切点的直线路径 单位 备注 i,j?1...n,n?36,i?j bij 机器人从圆弧i行进至圆弧j切点时的转弯路径 i,j?1...n,n?36,i?j xi yi 圆弧i的横坐标 圆弧i的纵坐标 圆弧对应圆心角 圆弧的半径 度 度 i?1..36 j?1..36 ? ?
3