周 玮， 王 栋

(济南工程职业技术学院基础部，山东济南250200)

1 引 言

随着科学技术的进步和计算机技术的发展，机器人的应用越来越广泛，在机器人的应用中如何使机器人在其工作范围内为完成一项特定的任务寻找一条安全高效的行走路径，是人工智能领域的一个重要问题.本文主要针对在一个场景中的各种静态障碍物，研究机器人绕过障碍物到达指定目的地的最短路径问题和最短时间问题.

本文以2012年“高教社”杯全国大学生数学建模竞赛D题“机器人避障问题”为例进行研究.假设机器人的工作范围为800×800的平面正方形区域，其中有12个不同形状的静态障碍物(具体几何信息可参见[1])，场景图中有4个目标点O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，在原点处有一机器人，下面我们将研究机器人从O(0, 0)出发，O→A、O→B、O→C和O→A→B→C→O的最短路径，以及机器人从O(0, 0)出发，到达A的最短时间路径问题.

2 静态避障问题中机器人行走最短路径的分析

2.1 行走路径的设计

图1 障碍物包络图

在本例中障碍物有4种不同形状：矩形、平行四边形、三角形和圆形.考虑到机器人本身的形状和大小，为研究方便起见，将机器人视为一个点.机器人与障碍物之间的距离至少为10个单位，因此可以先用包络线画出机器人行走的危险区域(如图1)，包络线内是机器人的禁入区.

图2 图3

根据以上分析，可以确定机器人的行走路径应为线圆结构. 那么是否是转弯半径越小，行走路径就越短呢？为此需要求在已知两个固定点和圆弧圆心坐标的情况下，圆弧半径r为何值，才能使机器人的行走路径最短.

L=AC+BD+rω

可以证明，L′>0，函数L为单调递增函数，因此当圆弧半径r逐渐增加时，机器人的行走路径会增大.根据以上分析，对于静态障碍物机器人的行走路径应遵循以下三个原则.

原则一：机器人的行走路径为线圆结构，由两条切线和一段圆弧组成；

原则二：每个路口至多发生一次转弯，并以障碍物顶点为转弯圆弧的中心；

原则三：机器人转弯圆弧半径为最小允许半径10个单位.

2.2 最短路径的选择

从起点到达目标点有多条路径，根据Dijkstra算法可以找出从起点到达每一个目标点的最短路径.本文采用带权的有向图表示机器人的行走路径，途中节点为障碍物的角点，边表示障碍物之间的联系，权表示线路的长度(节点之间的直线距离).从顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径就是所求最短路径，Dijkstra算法就是按路径的长度递增次序产生最短路径的算法[3].

图4

下面以O→B为例，确定O→B的最短路径.如图4所示，根据障碍物的形状和位置，本文给出了机器人从O(0,0)出发避过障碍物到达目标B点的4条较优路径.运用Dijkstra算法算出O→B的最短路径为O→B3→B5→B6→B7→B8→B.

O→B最短路算法如下：

1.起点O记为B0,终点B记为Bn；

2.从网络的终点Bn开始，令它的标号λn为零；

3.计算结点Bi的标号λi，设结点Bj已标号，

结点Bi指向Bj，则Bi的标号可按算式：

求出，其中λi是Bi的标号，li,j是结点Bi与Bj之间的直线距离；

4.重复上述计算，直到求得起点B0的标号λ0为止，此标号λ0即为最短路的长度；

5.确定最短路径，从起点开始，顺网络的箭线前进，若有几条箭线，则选取箭线所指标号最小且满足条件λj=λk+lj,k,k≥j+1的结点为最短路径所经过的结点.

应用上述算法可得到从O点出发，分别到达各目标点的最短路径.

3 最短路径长度的计算模型

机器人的行走路径由直线段和圆弧组成，只要知道直线段的起点和终点坐标，即切点坐标，就能计算出每段直线段的长度，再计算出各段弧长，即可得到每条路径的总长度.

3.1 切点坐标的计算模型

根据前面制定的行走路径原则，起点到目标点无论中间障碍物有多少，最短路径都是由若干个线圆结构所组成，圆弧中心为障碍物的顶点，半径为机器人转弯最小半径10个单位.观察这四条路径，发现所有线圆结构的切线都可以归结为两种类型，一种是两圆圆心连线与公切线相交(内公切线)，另一种是两圆圆心连线与公切线平行(外公切线).

图5 图6

3.1.1 第一种类型(内公切线)的切点

两圆圆心连线与公切线相交，则圆心连线的中点在切线上，可由两圆圆心坐标确定中点坐标，则问题转化为求圆弧外的点与障碍物的转弯圆弧形成的切线的切点(如图5的C点).设切点C(x,y),起点O(x1,y1),圆心M(x2,y2)，求切点C的坐标.

在Rt△OCM中OC2=OM2-CM2，又因为切点C在圆M上，故C点坐标满足以下方程，联立方程组

运用MATLAB解方程[4]，求出切点C(x,y)的坐标.类似地，要求D点坐标，只需求出DE中点的坐标，就可以利用上述模型计算出来.

3.1.2 第二种类型(外公切线)的切点

第二种类型的切点是两圆圆心连线与公切线平行(外公切线)的切点，如果能找到圆弧外一点的坐标，就可以利用第一种类型切点的模型计算[5].

两圆连线OO′与公切线DE平行(如图6)，切点为D.已知圆心O(x1,y1),圆心O′(x2,y2)，半径为r=10,求切点D的坐标.解法如下：

在两圆心连线上找出中点G(x3,y3)，过G作DE的垂线，交DE于Hx,y点.

根据中点坐标公式可得G点坐标

由于OD⊥DE,O′E⊥DE,故ODEO′为矩形,H为DE的中点，且GH=r，根据勾股定理，

由两点间距离公式，

因此，对于Hx,y点的坐标，有

利用MATLAB解方程,求出H点的坐标，就可以利用类型一求切点的方法，确定切点D和E的坐标.

3.2 弧长的计算模型

3.2.1 单个目标点的最短路径的弧长

机器人从O点出发，到达一个目标的的路径为单个目标的的路径，比如求O→A、O→B、和O→C的最短路径.观察机器人行走的所有路径中的圆弧，发现所有圆弧都可归结为以下三种类型：

图7 线圆结构1 图8 线圆结构2 图9 线圆结构3

设O(x1,y1)为起点，A(x2,y2)为目标点，C和D分别为直线与转弯圆弧的切点，障碍物的顶点M(x3,y3)(即转弯圆弧的圆心)，圆的半径为r，OA的长度为a，OM的长度为b，AM的长度为c，

∠OMA=φ, ∠OMC=α, ∠AMD=β, ∠CMD=θ,

对于这种线圆结构，需要做简单的变换，利用中点公式，确定切线的中点坐标，将类型二转换为类型一，才能求出A→B的路径中圆弧的长度.

假设两圆心坐标分别为O(x1,y1)和O′(x2,y2),M点为两圆心连线和两圆内公切线的交点，这样就可以利用类型一中的方法，分两段求解.同理如果有更多类似的转弯，同样可以按照此种方法分解.

已知起点、目标点、障碍物顶点坐标，可以用与类型一同样的方法计算出弧长.

3.2.2 多个目标点的最短路径

图10

机器人从起点出发，依次经过指定的中间目标点最后到达终点，是多个目标点的最短路径问题,比如O→A→B→C→O的最短路径的计算.由于机器人的行走路线为线圆结构，不能折线转弯，因此中间目标点应位于某个半径为r的圆周上. 这里我们仍按照最小允许半径为10个单位，则只需计算出过A,B,C三点的圆心位置即可，这样就将多目标点的最短路径问题转化成了单目标点的最短路径问题.求过A,B,C三点的圆心位置的问题可通过建立非线性规划模型求得.

(i) 过A点圆弧的圆心如图10，障碍物顶点O180,210,

建立非线性规划模型

图11

(ii)过B点圆弧的圆心如图11，障碍物顶点O1150,600,顶点O2270,680,B100,700,r=10，过B的圆弧圆心Om,n，最短路径为LB,则

LB=OO1+rθ+OO2.

建立非线性规划模型

图12

(iii)过C点圆弧的圆心(如图12)，障碍物顶点O1670,730,顶点O2720,600,C700,640,r=10，过C的圆弧圆心Om,n，圆O与圆O2的公切线为AB,切点Ax1,y1，Bx2,y2，圆O与圆O1的公切线为EF,切点Ex3,y3，Fx4,y4，最短路径为LC,则

LC=EF+AB+rθ，

其中

建立非线性规划模型

运用LINGO对模型求解，可得过A，B，C的圆弧圆心坐标计算结果. 根据以上模型可计算出O→A，O→B，O→C以及O→A→B→C→O的所有切点坐标，直线段长度和圆弧长度.

4 最短时间路径模型的建立和求解

机器人的行走速度与转弯半径有关，假设行走速度v与转弯半径ρ之间满足

图13

其中v0为直线行走速度，那么与最短路径问题不同，转弯半径不再是越小越好，转弯半径越小. 虽然行走的距离也越短，但是速度会变慢，这样行走速度反而可能会增加. 因此，应选择一个适当的转弯半径，使得行走时间最短[6].

以O→A为例，研究最短时间路径问题，建立非线性规划模型[7].如图13，起点O0,0，目标点A300,300，障碍物5的顶点M80,210，切点Cx1,y1,Dx2,y2，转弯圆弧的圆心M′m,n，圆心角∠CM′D为θ，半径为r，O→A的路径为L，时间为t，则

建立目标函数

编写LINGO程序求解，可求得圆弧圆心坐标和半径以及最短时间.

5 总结与讨论

本文将机器人避障行走路线设计为若干个线圆结构组成，通过建立数学模型计算出各切点坐标和各圆弧长度，用解析几何方法进行计算，精确度较高.但是在障碍物较多且形状不规则时，模型显得较为繁琐.如果障碍物较多，到达目标点的路径就较多，这时可应用网络模型计算最短路.本文给出的最优设计还可以应用于货物运输、管道输送等领域，应用此模型能较好地解决运输线路最短、输送管道最短等问题.

[参 考 文 献]

[1] 全国大学生数学建模竞赛组委会.2012高教社杯全国大学生数学建模竞赛赛题:[2012-09-07].http:∥www.mcm.edu.cn/problem/2012/cumcm2012problems.rar .

[2] 百度文库.行走机器人避障问题:[2012-09-08].http:∥/wenku.baidu.com/view/251ee65677232f60ddcca17b.html.

[3] 邦迪.图论及其应用[M].西安:西安科学出版社,1984.

[4] 章栋恩，马玉兰.MATLAB高等数学实验[M].北京：电子工业出版社，2010.

[5] 杜龙斌、杨亚运、付文，机器人避障问题. [2013-01-20].http:∥www.jpkc.sdu.edu.cn/sddxs/html/shuxuejianmoyouxiuzuopin/20130315/2495.html.

[6] 王琦.线性-二次双层规划的满意解与基于LP与NLP过程的算法[J].系统工程理论与践,2007,27(8)：84-91.

[7] 任竞争，谭世语，周志明.LINGO及其在化工过程优化中的应用[J].计算机与应用化学, 2010, 27(7)：975-977.