势函数的构造是人工势场方法中的关键问题，典型的势函数构造方法如下
P(θ)=f{d(θ,θ0),d［R(θ),O］,dT}(1)
式中θ，θ0——机器人当前位姿与目标位姿矢量
d(θ,θ0)——θ与θ0间的某种广义距离函数
d［R(θ)，O］——当前位姿下机器人与障碍物间的最小距离
dT——给定的门限值
P(θ)分别为变量d(θ,θ0)和d［R(θ)，O］的单调递增函数和单调递减函数。从机器人的起始位姿开始沿着P(θ)的下降方向进行搜索可使机器人在避开障碍物的前提下向目标位姿运动。
机器人与障碍物间的距离计算是构造势函数的基础，通常采用的距离函数是Euclidean距离。若采用凸多面体集合对机器人连杆和障碍物进行几何模拟，则机器人与障碍物间的距离计算简化成凸多面体间的距离计算。凸多面体间的Euclidean距离是二次规划问题的解，计算比较复杂［8～10］。本文采用Euclidean距离的等价度量——L1距离，提出C-空间中人工势场的一种构造策略，并给出相应的机器人无碰撞路径规划方法。
考虑到机器人的实际操作空间为三维空间，因此有关讨论限制在R3中。
1凸多面体间的L1距离及其计算方法
凸多面体间的L1距离定义如下
(2)
式中‖a-b‖1—矢量a-b∈R3的L1范数
有界闭(后面均作此假设)凸多面体A，BR3间的L1距离具有以下性质［11］。
(1) 由式(2)定义的d1(A，B)存在且唯一，式(2)可等价成
(3)
(2) (与Euclidean距离的等价性)记A，B间的Euclidean距离为dE(A，B)，则有
(4)
(3) 拓扑性质
(5)
(4) (Lipschitz性)以TA，TB∈SO(3)分别表示多面体A和B的旋转矩阵，rA，rB∈R3分别表示A和B平移矢量，记A′=TAA+rA，B′=TBB+rB，则有
(6)
式中I∈R3×3——单位矩阵
‖T‖1——与矢量的L1范数相容的矩阵谱范
SO(3)——3阶特殊正交群
(5) d1(A，B)和dE(A，B)对于A和B的旋转和平移变量均不存在Frechet意义下的梯度。
上述结论表明，凸多面体间的L1距离和Euclidean距离具有相似的性质。
若A，BR3的顶点集为VA={υAi;i=1,…,nA}，VB={υBj;j=1,…,nB}，则A，B可分别表示成VA和VB的凸包，即
(7)
(8)
d1(A，B)可通过求解如下线性规划问题计算
(9)
上述问题可由单纯形方法求解。尽管理论上单纯形法为非多项式算法，但经验表明，即使对于多约束线性规划问题，单纯形法也具有很高的计算效率。因此采用L1距离替代Euclidean距离构造势函数，可以简化无碰撞路径规划问题的计算复杂性。
2基于L1距离的人工势函数构造与无碰撞路径规划方法
以R(θ)，O分别表示机器人及其操作空间中的障碍物，其中R(θ)决定于机器人的C-空间位姿矢量θ。所谓无碰撞路径规划，就是确定一条连接C-空间中起始位姿θi和目标位姿θO的连续路径S(θi，θO)，使得机器人沿该路径运动时，在其所有的中间位姿θ∈S(θi，θO)满足如下几何约束条件
(10)
为了将上述约束条件表示成便于计算机判别的形式，通常采用如下形式的凸多面体集合对机器人及其操作空间中的障碍物进行几何逼近
(11)
式中Ri(θ)(i=1,…，m)，Oj(j=1,…，l)为R3中的凸多面体。机器人与障碍物间的L1距离可按下式由各多面体对Ri(θ)，Oj间的L1距离确定
(12)
且根据L1距离的拓扑性质，几何约束条件式(10)可等价地表示成
d1［R(θ)，O］>0(13)
以θi，θO∈Rn分别表示n自由度机器人的起始位姿和目标位姿。定义机器人运动过程中任意中间位姿θ∈Rn与目标位姿之间的广义距离为(W∈Rn×n为正定加权矩阵)
(14)
按如下方法构造C-空间中的势函数
(15)
由式(15)所确定的势函数p(θ)具有如下特点：
(1) 当机器人与障碍物间的L1距离大于门限值dT时，势函数的值由当前位姿与目标位姿间的广义距离d(θ，θO)确定，此时机器人只受到目标位姿引力场的作用。
(2) 当机器人与障碍物的L1距离小于门限值dT时，人工势场由目标位姿的引力场和障碍物的斥力场两部分组成，其中障碍物的斥力场所对应的势函数分量反比于机器人与障碍物间的L1距离，因此当机器人与障碍物间的L1距离趋于零时，该分量的值趋于无穷大。
(3) 势函数的值可由式(9)、(12)、(14)、(15)以及机器人正向运动学方程计算。
从机器人在C-空间中的起始位姿开始，沿着人工势函数p(θ)的下降方向进行搜索，可以得到C-空间中满足几何约束条件式(10)的连续路径。我们分d1［R(θ)，O］>dT和d1［R(θ)，O］dT两种情况讨论无碰撞路径搜索方法。
(1) 若d1［R(θ)，O］>dT，则势函数p(θ)关于θ可微，并有
(16)
此时可按势函数的最速下降方向，即其负梯度方向-p(θ)搜索机器人的下一个位姿点。对于搜索得到的位姿点，判断条件d1［R(θ)，O］>dT是否满足，若是，则以该点作为起始点重复以上搜索过程，否则改用下面的方法进行搜索。
(2) 若d1［R(θ)，O］dT，则势函数p(θ)不存在Frechet意义下的梯度向量，此时由于得不到最速下降方向，因此采用如下的搜索策略；对于θ的各相邻位姿θ+δθ(δθ∈Δ)，计算势函数p(θ+δθ)的值，其中
(17)
为容许的搜索步长集合。按下式确定
(18)
若，则终止搜索。若，判断条件dT是否满足，若是则以作为起始点重复上述搜索，否则改用最速下降方法进行搜索。
采用以上搜索方法可能产生两种不同的结果：一是搜索过程终止于目标位姿，此时已经得到C-空间中的连接起始位姿和目标位姿的无碰撞路径，规划完成。另一种可能的结果是在到达目标位姿之前，搜索过程终止于人工势函数的局部极小点，此时势函数无下降方向，必须采用其他方法才能使搜索过程继续下去。有关人工势函数的局部极值处理目前已有许多研究，此处不再介绍。
一般说来，若搜索步长足够小，则尽管规划过程中只顺序搜索C-空间中一些离散位姿点，但L1距离的Lipschitz性足以保证规划出的路径满足几何约束条件。但减小搜索步长是以增加算法的计算复杂性为代价的，为简化计算，搜索过程中可以根据当前位姿下机器人与障碍物间的L1距离大小对步长进行调整。对于由上述方法规划出的C-空间位姿序列，采用适当的方法进行插补即可得到连续的无碰撞路径。
3平面移动机器人路径规划的图形仿真
图平面3自由度机器人路径
规划仿真结果图示平面移动机器人具有3自由度，选择端点A的坐标以及AB与参考坐标系x轴的夹角构成C-空间位姿矢量［xA，yA，φ］T，记AB的长度为lAB，则端点B的坐标可由如下运动学方程计算
(19)
给定机器人的起始位姿和目标位姿(如图示)，以及障碍物Oi(i=1，2，3，4)的顶点集，采用本文给出的无碰撞路径规划方法，得到图示结果。
4结论
无论是对于关节机器人还是移动机器人，只需建立机器人的正向运动学方程，则采用上述人工势函数方法进行无碰撞路径规划时，其数学表示及其求解过程均不存在实现上的困难，且R3中凸多面体间L1距离的计算也十分简单，因此上述方法适用于三维空间中各类机器人的无碰撞路径规划。
*国家自然科学基金资助项目。19960611收到初稿，19971017收到修改稿
