机器人绕过障碍物的数理性研究

吴生根

摘 要： 目前，机器人在我国得到了迅速健康的发展，并且为我国的科技产业发展作出了巨大贡献.本文针对机器人避障问题，根据选择不同的行走路线，使用设立权值方法，建立线圆结构模型，根据切点位置不同，做出不同的路线选择.

关键词： 障碍 路径 切点

下图1.5是一个800×800的平面场景图，在原点O（0，0）点处有一个机器人，它只能在该平面场景范围内活动.图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表：

在平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位），为此，需要确定机器人的最优行走路线——由直线段和圆弧线段组成的光滑曲线，其中圆弧线段是机器人转弯路线，机器人不能折线转弯，转弯路径是与直线相切的一条圆形曲线段，也可以是两条或多条相切的圆弧曲线段组成，但每个圆形路线的半径都必须大于某个最小转弯半径，假设为10个单位.另外，为了不与障碍物发生碰撞，要求机器人行走线路与障碍物间的最短距离为10个单位，越远越安全，否则将发生碰撞.若碰撞发生，则机器人无法到达目标点，行走失败.

建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型.对场景图中4个点O（0，0），A（300，300），B（100，700），C（700，640），具体计算：机器人从O（0，0）出发，到达每个点的最短路径和O→A，O→A→B的最短路径.

对该问题而言，要求求定点O（0，0）按照一定的行走规则绕过障碍物到达目标点的最短路径.机器人的行进线路必定由直线和与此直线相切的圆弧组成，可以先行求出所有的公切线，然后构造一个网络图，将这个问题转化为一个无约束的最短路径问题.若先画出机器人行走的危险区域，拐角处就是一个半径为10的圆弧.此时可采用拉绳子的方法寻找可能的最短路径（比如：求O点和A点之间的最短路径，我们就可以连接O点和A点之间的一段绳子，以拐角处的圆弧为支撑拉紧，那么这段绳子的长度便是O点到A点的一条可能的最短路径），然后采用穷举法列出O点到每个目标点A、B的可能路径，然后比较其大小便可得出O点到目标点的最短路径.而在计算总路径时，其关键在于机器人在经过A点走向B点的过程中要保证经过A点，与此同时，在A点附近转向时转弯半径及曲率圆心难以确定，B点到C点以此类推.

为了简化现实问题，现增加如下假设：（1）机器人能抽象成点来处理；（2）机器人行走过程中不出现故障等问题.我们将目标从起点到终点的路径看成是一条无限长的绳子，将禁区的圆角矩形看成支点，用绳子绕过禁区，拉绳子两端，当绳子绷到最紧时，路径最短.

以障碍物5为例，如图1.1因为机器人与障碍物间的距离最少为10，所以障碍物5外圈的圆角矩形内均为禁区.设OF、AE切于圆角矩形，点P为线段AE、OF延长线的焦点，如图所示在禁区外不管在何处转弯距离最短的肯定是d+l+d，以OGHPA线为例，线段OP的距离一定小于OGHP因为两点之间线段最短，而PA的距离一定大于EA，所以线路OGHA的长度一定大于线路OFEA.

1）切点坐标求解：在求弧的切点过程中将各顶点上的弧当做整个圆求解点到弧的切点坐标.如图1.2设A（x，y）为起点，点B（x，y）为线段AB与圆O的切点，O（x，y）为圆O的圆心，作过A点与x轴的平行线与过O点垂直x轴的线交于C（x，y），过B点与x轴的平行线与过O点垂直x轴的线交于D（x，y）.

设半径长为，OA长为a，AB长为b，∠BAO为α，∠AOC为β

则a=，b=，tanα=，α=arctan

tanβ=，β=arctan，cos（α+β）=，x=cos（α+β）×b+x

sin（α+β）=，y=sin（α+β）×b+y.

2）弧长求解：如图1.3，设圆O上两点A（x，y），B（x，y）所形成的弦AB长为a，与半径为ρ的圆O形成的圆心角∠AOB为α，弧AB长为l.则a=，α=2×arcsin，l=×2πρ.

3）与两圆圆心形成的线段不相交的切于两圆的切点坐标求解：（两圆心连成的直线不平行或垂直于x轴）如图1.4设圆O的圆心为O（x，y），圆O的圆心为O（x，y），作直线AB与直线OO不相交且切圆O于点A（x，y），切圆O于点B（x，y），过圆O作垂直于x轴的线与过圆O作平行于x轴的线交于C，过圆O作平行于x轴的线与过点A（x，y）作垂直于x轴的线交于点D，设圆O和圆O的半径都为ρ.因为直线AB与圆O圆O相切，所以∠OAB=∠ABO=90°，又因为AO与BO都为半径长度为ρ，所以四边形ABOO是矩形，所以∠AOO=90°.因为∠DOC=90°，所以∠AOD=∠COO，因为∠ADO=∠OCO=90°，所以△ADO与△OOC为相似三角形，

即=，OC=y-y，OC=x-x，即=

解方程组==ρ可得OD=xAD=y.

则点A的坐标为（x+x，y+y），同理可知B点坐标为（x+x，y+y）.

接下来我们给出了O到各目标点的可能路径的最短路径.

1）如图1.6，解决的就是从O（0，0）到A（300，300）目标点的最短路径问题，从O（0，0）到A（300，300）两条路径，经计算图中上面的路线为L=471.04，下面的路线为L=498.43.

2）如图1.7，解决的就是从O（0，0）到B（100，700）目标点的最短路径问题，从O（0，0）到B（100，700）两条路径，图中上面的路线经过计算距离更短为L=471.04.

针对机器人避障问题建立模型的方法有很多种，如：栅格法、精神网格法等，用这几种方法建立的模型在大多数情况下只能求出局部最优解，且时间和空间复杂度较大.本文中针对这个问题建立的线圆结构模型，适用性较强，大多情况下均能求出全局最优解.在障碍区间或障碍形状变化的情况下也适用.线圆结构模型的前提是线圆结构可求，求解速度与障碍区间的数量成反比，当障碍区间数量较大时求解速度会明显减小，求出的最佳解与实际优化解误差会随之增大.

参考文献：

[1]谭永基.数学模型.上海：复旦大学出版社，2011.

[2]尤承业.解析几何.北京：北京大学出版社，2004.

[3]赵静，但琦，主编.严尚安，等编.数学建模与数学实验.北京：高等教育出版社；海德堡：施普林格出版社，2000.11（2002重印）.

[4]算反三角函数http：//www.ab126.com/geometric/2080.html.