第1页机器人避障问题的最短路径分析摘要本论文研究了机器人避障最短路径和最短时间路径的问题。主要讨论了在一个区域中存在12个障碍物，由出发点到达目标点以及由出发点经过若干目标点最终到达出发点的两种情况。采用传统的避障方法——切线图法。建立了线圆结构，这样任何路径，我们都可以将路径划分为若干个这种线圆结构来求解。对于途中经过节点再到达目标点的状况，我们采用在转弯点和节点都采用最小转弯半径，以节点为切点的形式。然后建立了最优化模型，利用MATLAB软件对方案进行求解。问题一：把路径分解成若干个线圆结构来求解，然后把可能的最短路径采用穷举法列举出来，最终得出最短路径：AO最短路径为：471.0BO最短路径为：869.5CO最短路径为：1093.3对于OCBAO我们将A、B、C看作切点，同样采用线圆结构计算。OCBAO最短路径为：2827.1问题二：考虑避障路径和转弯速度，我们建立时间与路径之间的模型，用MATLAB软件求出最优解。当转弯半径为11.5的时候，可以得出最短时间为：T=94.3关键词最优化模型避障路径线圆结构切线图法第2页一、问题重述本文是求一个机器人在800×800的平面场景图中避开障碍物，建立从原点O(0,0)点处出发达到终点的最短路径和最短时间路径的模型。即求：1、O→A、O→B、O→C和O→A→B→C→O的最短路径。2、O→A的最短时间路径。机器人在行走时的要求是：1、它只能在该平面场景范围内活动2、图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物（障碍物的分布如图1）3、障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。4、规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。5、为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞。机器人直线行走的最大速度为50v个单位/秒。机器人转弯时，最大转弯速度为21.0100e1)(vvv，其中是转弯半径。已知场景图中4个点O(0,0)，A(300,300)，B(100,700)，C(700,640)。图中各个点的坐标见下表。图1编号障碍物名称左下顶点坐标其它特性描述1正方形(300,400)边长2002圆形圆心坐标(550,450)，半径703平行四边形(360,240)底边长140，左上顶点坐标(400,330)第3页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、把机器人抽象成质点。2、机器人直线行走都是以最大速度做匀速运动。3、机器人转弯时同样以最大允许速度做匀速运动。三、符号说明符号符号说明ia每一个线圆结构起点到终点的长度ib每一个线圆结构起点到圆心的长度ic每一个线圆结构终点到圆心的长度r转弯半径（即题上的）i转弯圆心角)y,x(Oiii转弯圆心坐标A到Z)y,x(ii各个切点，节点的坐标il每个弧长的长度第4页Li第i段直线段的长度Kj第j段圆弧的长度ti第i段直线段所用的时间pj第j段圆弧所用的时间d障碍物上的任意点与行走路径之间的最短距离四、模型分析与准备一、最短路径和最短时间路径的分析（1）问题一：要求从)0,0(O出发，沿AO,BO,CO和OCBAO的行走路线按照一定规则，绕过障碍物到达目标点的最短路径。在求AO，BO，CO时。我们将所有的障碍物扩大10个单位，在障碍物的顶点处，就是以10为半径圆弧。我们采用拉绳子的方法寻找所有可能的最短路径。然后利用线圆结构的方式求解。即列举法。（例如求解O到A的最短路径，我们就可以连接O和A之间的一段绳子，以障碍5左上角的拐角处的圆弧为支撑拉紧，那么这段绳子的长度便是O到A的一条可能的最短路径）。在求OCBAO时，在过点A、B、C处我们采用最小半转弯的方式，使机器人经过这些过点时，都是按圆弧通过。其他情况就是按线圆结构的方式进行求解。（2）问题...
