[法学]赣南师范学院2012D国家一等奖论文.doc

D题 机器人避障问题 摘 要 本文综合运用分析法、图论方法、非线性规划方法，讨论了机器人避障最短路径和最短时间路径求解问题。 针对问题一，首先，通过分析，建立了靠近障碍物顶点处转弯得到的路径最短、转弯时圆弧的半径最小时和转弯圆弧的圆心为障碍物的顶点时路径最短、转弯在中间目标点附近时，中间目标点位于弧段中点有最短路径的三个原理，基于三个原理，其次对模型进行变换，对障碍物进行加工，扩充为符合条件的新的区域并在转弯处圆角化构成障碍图，并通过扩充的跨立实验，得到切线和圆弧是否在可避障区的算法，第三，计算起点、中间目标点和最终目标点和各圆弧及圆弧之间的所有可避障切线和圆弧路径，最后给这些定点赋一个等于切线长度或弧度的权值构成一个网络图，然后利用Dijkstra算法求出了O-A、O-B，O-C的最短路径为O-A：471.0372个单位，O-B：853.7001个单位，O-C：1086.0677个单位；对于需要经中间目标点的路径，可运用启发规则分别以相邻的目标点作为起点和终点计算，确定路径的大致情况，在进一步调整可得到O-A-B-C-O的最短路径为2748.699个单位。 针对问题二，主要研究的是由出发点到达目标点A点的最短时间路径，我们在第一问的基础上考虑路径尽可能短且圆弧转弯时的圆弧尽量靠近障碍物的顶点，即确定了圆弧半径最小时的圆弧内切于要确定的圆弧时存在最小时间路径，建立以总时间最短为目标函数，采用非线性规划模型通过Matlab编程求解出最短时间路径为最短时间路程为472.4822个单位，其中圆弧的圆心坐标为，最短时间为94.3332秒。圆弧两切点的坐标分别为（70.88,212.92）、（77.66,219.87）。 关键字： Dijkstra算法 跨立实验 分析法 非线性规划模型 一.问题的重述 图是一个800×800的平面场景图，在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表：编号 障碍物名称 左下点坐标 其它特性描述 1 正方形 (300, 400) 边长200 2 圆形 圆心坐标(550, 450)，半径70 3 平行四边形 (360, 240) 底边长140，左上点坐标(400, 330) 4 三角形 (280, 100) 上点坐标(345, 210)，右下点坐标(410, 100) 5 正方形 (80, 60) 边长150 6 三角形 (60, 300) 上点坐标(150, 435)，右下点坐标(235, 300) 7 长方形 (0, 470) 长220，宽60 8 平行四边形 (150, 600) 底边长90，左上点坐标(180, 680) 9 长方形 (370, 680) 长60，宽120 10 正方形 (540, 600) 边长130 11 正方形 (640, 520) 边长80 12 长方形 (500, 140) 长300，宽60 在图1的平面场景中，障碍物外指定一点为机器人要到达的目标点要求目标点与障碍物的距离至少超过10个单位。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。 机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯速度为，是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。 请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中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的最短时间路径。 注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。 机器人的行走路径由直线段和圆弧组成不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成每个圆弧的半径最小为10个单位 要求机器人行走线路与障碍物间的最近距离为10个单位指每段路径的长度 ：机器人直线行走时的最大速度 ：机器人的最大转弯速度 ：每段路径所用的时间 五、模型的建立与求解 5.1模型的准备 模型的准备一 首先给出以下三个前提及其证明： 1.靠近障碍物顶点处转弯得到的路径最短 如图1所示： 图1 设A为起点，B为终点，矩形的阴影部