机器人避障问题的最短路径分析
摘要
本论文研究了机器人避障最短路径和最短时间路径的问题。主要讨论了在一个区域中存在12个障碍物，由出发点到达目标点以及由出发点经过若干目标点最终到达出发点的两种情况。采用传统的避障方法——切线图法。建立了线圆结构，这样任何路径，我们都可以将路径划分为若干个这种线圆结构来求解。对于途中经过节点再到达目标点的状况，我们采用在转弯点和节点都采用最小转弯半径，以节点为切点的形式。然后建立了最优化模型，利用MATLAB软件对方案进行求解。
问题一：把路径分解成若干个线圆结构来求解，然后把可能的最短路径采用穷举法列举出来，最终得出最短路径：
O?A 最短路径为：471.0 O?B 最短路径为：869.5 O?C 最短路径为：1093.3
对于 O?A?B?C?O 我们将A、B、C看作切点，同样采用线圆结构计算。
O?A?B?C?O 最短路径为：2827.1
问题二：考虑避障路径和转弯速度，我们建立时间与路径之间的模型，用MATLAB软件求出最优解。当转弯半径为11.5的时候，可以得出最短时间为：T=94.3
关键词 最优化模型 避障路径 线圆结构 切线图法
第 1 页
一、问题重述
本文是求一个机器人在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个单位，否则将发生碰撞。
机器人直线行走的最大速度为v0?5个单位/秒。机器人转弯时，最大转弯速
v0度为v?v(?)?，其中?是转弯半径。 10?0.1?21?e已知场景图中4个点O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)。图中各个点 的坐标见下表。
图1 编号 障碍物名称 左下顶点坐标 其它特性描述 1 正方形 (300, 400) 边长200 2 圆形 圆心坐标(550, 450)，半径70 3 平行四边形 (360, 240) 底边长140，左上顶点坐标(400, 330)
第 2 页
4 5 6 7 8 9 10 11 12 三角形 正方形 三角形 长方形 平行四边形 长方形 正方形 正方形 长方形 (280, 100) (80, 60) (60, 300) (0, 470) (150, 600) (370, 680) (540, 600) (640, 520) (500, 140) 上顶点坐标(345, 210)，右下顶点坐标(410, 100) 边长150 上顶点坐标(150, 435)，右下顶点坐标(235, 300) 长220，宽60 底边长90，左上顶点坐标(180, 680) 长60，宽120 边长130 边长80 长300，宽60
二、模型假设
1、把机器人抽象成质点。
2、机器人直线行走都是以最大速度做匀速运动。 3、机器人转弯时同样以最大允许速度做匀速运动。
三、符号说明
符号 ai bi ci 符号说明 每一个线圆结构起点到终点的长度 每一个线圆结构起点到圆心的长度 每一个线圆结构终点到圆心的长度 转弯半径（即题上的?） 转弯圆心角 转弯圆心坐标 各个切点，节点的坐标 每个弧长的长度 r ?i Oi(xi,yi) A到Z(xi,yi) li
第 3 页
Li Kj 第i段直线段的长度 第j段圆弧的长度 第i段直线段所用的时间 第j段圆弧所用的时间 障碍物上的任意点与行走路径之间的最短距离 ti pj d
四、模型分析与准备
一、最短路径和最短时间路径的分析
（1）问题一：要求从O(0,0)出发，沿O?A,O?B,O?C和
O?A?B?C?O的行走路线按照一定规则，绕过障碍物到达目标点的最短路径。在求O?A，O?B，O?C时。我们将所有的障碍物扩大10个单位，在障碍物的顶点处，就是以10为半径圆弧。我们采用拉绳子的方法寻找所有可能的最短路径。然后利用线圆结构的方式求解。即列举法。（例如求解O到A的最短路径，我们就可以连接O和A之间的一段绳子，以障碍5左上角的拐角处的圆弧为支撑拉紧，那么这段绳子的长度便是O到A的一条可能的最短路径）。在求O?A?B?C?O时，在过点A、B、C处我们采用最小半转弯的方式，使机器人经过这些过点时，都是按圆弧通过。其他情况就是按线圆结构的方式进行求解。
（2）问题二、要求从O点出发到达A点的最短时间路径问题，采用穷举法和CAD画图可以得出最短时间路径。 二、在模型的建立中会大量用到线圆结构来计算，证明起点到终点之间最短的路径就是我们所用的线圆结构。
证明：如图所示的线圆结构CA,OB和圆弧BC之和为最短避障路径。
假设在平面中有A(a,0)和O(b,0)两点，中间有一个半圆形的障碍物，证明从O到B的最路径为圆弧BC和线段OB、AC的和。
第 4 页
图2
平面上连接两点最短的路径是通过这两点的直线段，但是连接两点的线段被障碍物遮挡，所以设法尝试绕过障碍物的折线路径。在y轴上取一点P(0,y)，若y适当大，当折线OPA与障碍物相切时，OPA是这种折线路径中最短的。由于满足0????/2的角满足??tan?,所以易知弧度BC小于BPC的长，即证明到了线圆结构为最短避障路径。 线圆结构的长度：
~~ 设CD?r，O(x1,y1) 为起始点，A(x2,y2)为目标点，D(x3,y3)。求OCBA，
设为L。
AO?a a=OD?b b=AD?c c?(x2?x)+(y2?y)2112
(x3?x)+(y3?y)2112?x3?x2???y3?y2?
22
第 5 页