机器人避障问题.doc

--
机器人避障问题
摘要：本文研究了机器人避障最短路径与最短时间路径的问题。
问题（1）：首先利用几何知识证明了机器人在两个定点间绕一个障碍物的最短路径是由直线和圆弧组成的，并可将这种线弧结构应用所有路径之中，根据这个结论建立了机器人从区域中一点到达另一点的避障最短路径的最短路问题数学模型，此模型可用中的算法求解。在此基础之上，过原线弧结构中的圆弧中点，作与圆弧内切、半径为的圆，得到新的线弧结构，用规划的方法求出最短时间路径，此时圆的半径为11.97。将新线弧结构应用所有路径之中建立最短时间路径的最短路问题数学模型。
问题（2）：该题是研究机器人由原点到达目标点所用最短时间的问题。根据所设的转弯圆弧半径以及所转弯圆弧的圆心坐标，先计算出机器人在该区域行进中所用时间的方程一般通式，然后考虑到的特殊路径，通过软件求出所用时间的最小值。
关键词：线弧最短路径软件规划
1、问题的重述
1.1问题的重述
一个800×800的平面场景图，在原点O(0,0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表：
编号障碍物名称左下顶点坐标其它特性描述1正方形(300,400)边长2002圆形圆心坐标(550,450)，半径703平行四边形(360,240)底边长140，左上顶点坐标(400,330)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的平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过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的最短时间路径。
注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。
2、模型的假设与符号说明
2.1模型的假设
（1）假设机器人看作是质点；
（2）假设机器人由直线运动到圆弧的过程中没有加速度；
（3）假设机器人正常运行。
2.2符号的约定
：机器人所走路径的总长度；
：障碍物上任意点与行走路径之间的最短距离；
：转弯圆弧的半径。
3、模型的准备
3.1模型准备一
假设在平面中有任意与两点，中间的半圆是躲避障碍物时的不可接触区域，其中圆心为障碍物的顶点。

、为圆弧的两条切线，相交于。、为圆弧的两条切线。显而易见从到的路径中，圆弧半径越小所走的路径最短。因此，机器人在躲避障碍物时，沿半径最小的弧线路径走（即），所用的路程最短。
最短路径为：
，（其中是机器人走圆弧所对的圆心角）
区域中无论障碍物有多少，路径是由若干个线弧结构组成的，转弯半径最小时路径才能达到总路程最短。
3.2模型准备二
由于机器人需要躲避的障碍物形状不同，运动路线路较多，必然遇到两个线弧结构相连的情况。
情况1：

设出发点，目标点，圆心坐标，半径为，为到经过弧的路程长。
由上图可以得到：

在中，

在中，

在中，

所以，

所以可以得出：

情况2：

针对上面的问题，设圆心坐标分别为和,半径均为，这样我们可以得到：

因为与平行，故设CD的直线方程可以表示为：

由点到直线的距离公式求得

将的直线方程分别与圆、的方程联立，求得切点与和的坐标。这样用、任意一点作为分割点都可以将上图分割成两个线弧结构，这样就可以对其进行求解。
情况3:

假设两圆心坐标分别为和,半径均为，点坐标为，那么根据欧氏几何知识求得:

先