探索2012年专科组D题最短路径问题特等奖论文 201211.doc

　　探索2012年专科组D题最短路径问题特等奖论文 201211 探索2012年专科组D题最短路径问题特等奖论文 201211 导读：引用别人的成果或其他公开的资料（包括X上查到的资料），必须按照规定的 探索2012年专科组D题最短路径问题特等奖论文 201211 导读：最短时间路径。3三、模型假设与符号约定模型假设1、在获得稳定的初始步态后，机器人可以稳定连续行走。2、机器人在平面场景活动范围内的每一点若非障碍下可以自由通行。3、机器人可以看成质点，且道路宽度不计。4、机器人在转弯时能及时调整路径，调整时间忽略不计。5、机器人在调整速度时，不考虑加速度时间。 面场景图，在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障 障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。 机器人直线行走的最大速度为v0?5个单位/秒。机器人转弯时，最大转弯速度为v?v(?)?v0 1?e10?0.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的最短时间路径。 注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。 2 二、问题分析 1、问题一中求点O（0,0）到点A（300,300）的最短路径，我们可以采用穷举法列出所 有可能的路径，然后比较其大小，得出起始点到目标点的最短距离。有图可知，点O（0,0）到点A(300，300)的路径是由两条与圆相切的切线，和一条弧线组成，取最小转弯半径可求得最小路径，所以我们把点（0,0）到点A(300，300)的路径看做是一个线圆结构，已知其起点、圆心、和终点坐标，运用编程计算，求的路径长度。同样所以在求O→B、O→C和O→A→B→C→O的路径时，我们将它们分成若干个线圆结构进行计算，然后比较求出各个线路的最短路径。 2、问题二求点O（0，0）到点A(0,0)的最短时间路径，不仅要考虑路径要短，还要考 虑机器人在直线路段和弧线路段所用时间总和最短，通过第一题中我们可以判断，最短时间路径在障碍物上方。未得到最短路径，我们让新弧线所在的圆与原先经过的弧线内切，让后通过编程算出最短时间路径。 3 三、模型假设与符号约定 模型假设 1、在获得稳定的初始步态后，机器人可以稳定连续行走。 2、机器人在平面场景活动范围内的每一点若非障碍下可以自由通行。 3、机器人可以看成质点，且道路宽度不计。 4、机器人在转弯时能及时调整路径，调整时间忽略不计。 5、机器人在调整速度时，不考虑加速度时间。 6、机器人在场地内行走过程中不发生打滑。 符号约定 1、Ai通往终点为A的路径上圆弧所在圆的圆心坐标，其中i表示不 3 4 5 6 7 探索2012年专科组D题最短路径问题特等奖论文 201211 导读： 同障碍物的不同圆弧。 Ai1表示圆弧起点，Ai2表示圆弧终点。 2、Bi通往终点为B的路径上圆弧所在圆的圆心坐标，其中i表示不同障碍物的不同圆弧。 Bi1表示圆弧起点，Bi2表示圆弧终点。 3、Ci通往终点为C的路径上圆弧所在圆的圆心坐标，其中i表示不同障碍物的不同圆弧。 Ci1表示圆弧起点，Ci2表示圆弧终点。 4、Ti通往O→A→B→C→O的路径上圆弧所在圆的圆心坐标，其中i表示不同障碍物的不同圆弧。 Tia表示圆弧起点，Tib表示圆弧终点。 5、L表示路径的总长度。 四、模型的分析与准备 分析一： 在寻找O→A、O→B、O→C和O→A→B→C→O的最短路径时，起点到目标点无论中间障碍物有多少，最短路径都可看做是若干个线圆结构所组成。所以我们只要能找到两点之间的最短路径中的最小转弯半径就能得到最优解。经过分析，一个线圆结构的求解有以下两种情况。 情况一： 当障碍物与终点在起点与圆心连线的同侧时，路径图如线圆结构图1所示。 4 线圆结构图1 设A(x1,y1)为起点，B(x2,y2)为目标点，C(x3,y3)和D(x4