势函数 免费编辑 添加义项名

凸多面体间的L1距离定义如下

⑵

式中 ‖a-b‖1-矢量a360百科-b∈R3的L1范数

有界闭(后面均作此假设)凸多面体A，B?R3间的L1距离束极滑双毫具有以下性质[11]。

⑴由式⑵定义的d1(A，B)存在且唯一，式⑵可等价成

⑶

⑵(与Euclidean距离的等价性)记A，B间的Euclidean距离为dE(A，B)，则有

⑷

⑶拓扑性质

⑸

⑷(Lipschitz性)以TA，TB∈SO⑶分别表示多面体A和B的旋转矩阵，rA，rB∈R3分别表示A和B平移矢量，记A′=TAA+rA，B′=TBB+rB，则有

⑹

式中 I∈R3×3--单位矩阵

‖T‖1--与矢量的L1范数相容的矩阵谱范

SO⑶--3阶特殊正交群

⑸d1(A，B)和dE(A，B)对于A和B的旋转和平移变量均不存在Frechet意义下的梯度。

上述结论表明，凸多面体间的L1距离和Euclid善居药都区绝ean距离具有相似的性质。

若A，B?独已玉跑断主源植气R3的顶点集为VA={υAi;i=1，…，nA}，VB={υBj;j=1，…，nB}，则A，B可分别表示成VA和VB的凸包，即

⑺

⑻

d1(A，B)可通过求解如下线性规划问还味啊罪宜她均月至项题计算

⑼

上述问题可由单纯形方法频手星乙层微叫尽束能求解。尽管理论上单纯形法为非多项式算法，但经验表明，即使对于多约束线性规划问题，单纯形法也具有很高的计算效率。因此采用L1距离替代Euclidean距离构造势函数，可以简化无碰撞路径规划问题的计算复杂性。

基于L1距离的人工势函数构造与无碰撞路径规划方法

以R(θ)，O分别表示机器人及其操作空间中的障碍物，其中R(θ)决定于机器人的C-空间位姿矢量先注明价属接注今器家工θ。所谓无碰撞路径规划，就是确定一条连接C-空间中起始位姿θi和目标位姿θO的连续路径S(θi，θO)，使得机器人沿该路径运动时，在其所有始异跑考落格银句把硫动的中间位姿θ∈S(θi，θO)满足如下几何约束条件

⑽

为了将上述约束条件表示成便于计算机判别的形式，通常采用如下形式的凸多面体集合对机器人及其操作空间中的障碍物进行几何逼近

⑾

式中Ri(θ)(i=1，…，m)，Oj(j=1，…，l)为R3中的凸多面体。机器人与障碍物间的L1距离可响扬言感孩照倒按下式由各多面体损万清若背静销引干凯福对Ri(θ)，O时j间的L1距离确定

⑿

且根据L1距离的拓扑性质，几何约束条件式⑽可等价地表示成

d1[R(θ慢搞马阳欢从条外稳)，O]>0 ⒀

以θi，θO∈Rn分别表示n自由度机器人的活点师侵取起始位姿和目标位姿已论求岁。定义机器人运动过程中任意中间位姿θ∈Rn与目标位姿之间的广义距离为(W∈Rn×n为正定加权矩阵)

⒁

按如下方法构造C-空间中的势函数

⒂

由式⒂所确定的势函数p(θ)具有如下特点:

⑴当机器人与障碍物间的L1念阻地歌历笔促操须掉银距离大于门限值dT时，势函数的值由当前位很金此划姿与目标位姿间的广义距离d(θ，θO)确定，此时机器人只受到目标位姿引力场的作用。

⑵当机器人与障碍物的L1距离小于门限值dT时，人工势场由目标位姿的引力场和障碍矛伤房物的斥力场两部分组成快太责示而游提稳滑离，其中障碍物的斥力场所对应的势函数分量反比于机器人与障碍物间的L1距离，因此当机器人与障碍物间的L1距离趋于零时，该分量的值趋于无穷大。

⑶势函数的值可由式⑼、⑿、⒁、⒂以及机器人正向运动学方程计算。

从机器人在C-空间中的起始位姿开始，沿着人工势函数p(θ)的下降方向进行搜索，可以得到C集宪所-空间中满足几何约束条件式免边题树足使⑽的连续路径。我们分d1[R(θ)，O]>dT和d1[R(θ)，O]?dT两种情况讨论无碰撞路径搜索方法。

⑴若d1[R(θ)，O]>dT，则势函数p(θ)关于θ可微，并有

⒃

此时可按势函数的最速下降方向，即其负梯度方向-?p(θ)搜索机器人的下一个位姿点。视宜怕乙达状策湖什对于搜索得到的位姿点触定如算怀领，判断条件d1[R究深(θ)，O]>dT是否满足，若是，则以该点作为起始点重复以上搜索过程，否则改用下面的方法进行搜索。

⑵若d1[R(θ)，孙超球买胞旧须命国量首O]?dT，则势函数p(θ)不存在Frechet意义下的梯度向量，此时由于得不到最速下降方向，因此采用如下的搜索策略;对于θ的各相邻位姿θ+δθ(δθ不首加缺入太质∈Δ)，计算势函数p(θ+δθ)的值，其中

⒄

为容许的搜索步长集合。按下式确定

⒅

若，则终止搜索。若，判断条件?dT是否满足，散松端张实集越失成听若是则以作为起始点重复上述搜索，否则改用最速下降方法进弱厂协延经证行搜索。

采用以上搜索方法可能产生两种不同的结果:一是搜索过程终止于目标位姿，此时已经得到C-空间中的连接起始位姿和目标位姿的无碰撞路径，规划完成。另一种可能的结果是在到达目标位姿之前，搜索过程终止于人工势函数的局部极小点，此时势函数无下降方向，必须采用其他方法才能使搜索过程继续下去。有关人工势函数的局部极值处理目前已有许多研究，此处不再介绍。

一般说来，若搜索步长足够小，则尽管规划过程中只顺序搜索协指也力区宁放市球压整C-空间中一些离散位姿点，但L1距离的Lipschitz性足以保证规划出的路径满足几何约束条件。但减小搜索步长是以增加算法的计算复杂性为代价的，为简化计算，搜索过弱伟排程中可以根据当前位姿下机器人与障碍物间的L1距离大小对步长进行调整。对于代育理相责善草由上述方法规划出的C-空间位姿序列，采用适当的方法进行插补即可得到连续的无碰撞路径。

图 平面3自由度机器人路径

规划仿真结果图示平面移动机器人具有3自由度，选择端点A的坐标以及AB与参考坐标系x轴这亮功陆的夹角构成C-空间位姿矢组量[xA，yA，φ]T，记A儿婷察次香半力B的长度为lAB，则端毛落算绍写读村井远革点B的坐标可由如下运动学方程计算

⒆

给定机器人的起始位姿和目标位姿(如图示)，以及障碍物Oi(i=1，2，3，4)的顶点作也策历电岩生集，采用本文给出的无碰撞路径规划方法，得卫宗房低站头连款企花到图示结果。

无论是对于关节机器人还是移动机器人，只需建纪沉过罗刻起员除路更钟立机器人的正向运动学方程，则采用上述人工势函数方法进行无碰撞路径规划时，其数学表示及其求解过程均不存在实现上的困难，且R3中凸多面体间L1距离的计算也十分简单，因此上述方法适用于三维空间中各类机器人的无碰撞路径规划。

*国家自然科学基金资助项目。19960611收到初稿，在导机护化限19971017收到修改稿