Moratz^[3]在直线段模型的基础上提出了一种具有可扩展粒度的相对方位关系模型OPRA_m, 使用一个方位点(有方向的点)表示空间对象。粒度参数m> 0∈ n决定方位点的区分粒度, m条线将二维平面划分为2m个线性区域和2m个平面区域。区域按逆时针方向从0到(4m-1)进行编号, 区域0和方位点的本质方向重合。图1给出了m=2(见图1(a))和m=4(见图1(b))时, 平面上不同位置方位点A和B的相对方位关系; 图1(c)给出了平面上两个相同位置方位点的相对方位关系。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 两个方位点之间的相对方位关系Fig.1 Relative directions between two oriented point

Freksa^[8]首次定义了概念邻域图(Conceptual neighborhoods graph, CNG), 并将概念邻域结构用于处理时间区间代数中时间区间连续变化的问题。宋小华等^[9]指出概念邻域图只给出了空间关系变化的结果, 没有给出空间关系变化的原因, 不知道是什么引起空间关系发生变化。宋小华在概念邻域图的基础上, 引入“ 动作” 的概念, 他认为空间关系的变化是因为在对象上施加了动作。

如果有动作关系集合A, 能够使互斥完备的基本关系集合B概念邻域图CNG(B)中的邻域关系相互转换, 则称集合A为完备动作关系集合。由完备动作关系集合A、基本关系集合B和B通过A转变的邻域关系集合» , 构造一个能表示基本关系随动作变化的图, 则称此图为邻域划分图(Neighborhood partition graph, NPG), 其形式表示如下:

NPG(B)={B, A, » }

对任意原子关系b∈ B, 其基于动作的邻域关系表示为np(b), 其形式表示如下:

np(b)={y|(x, y, a)∈ » , x, y∈ B, a∈ A}

三维空间中, 以点为空间变量, 方位点使用有序对S=(P_S, δ _S)表示, 其中P_S是方位点S的笛卡尔坐标P_S=(x_S, y_S, z_S); δ _S表示方位点的本质方向。δ _S平行于地面, 它所在的平面为xoy面, 垂直于xoy面的方向为z轴, 图2为3DOPRA_m模型参照系。

使用xoy面的相对方位和z轴的相对方位组合表示三维空间的相对方位关系。其中xoy面的方位划分如图3所示, 使用字母f、b、l、r、lf、rf、lb、rb代表front、back、left、right、leftfront、rightfront、leftback、rightback; z轴方位划分如图4所示, 使用字母U(up)、D(down)分别表示位于xoy面的上方和下方; E(equal)表示恰好在xoy平面上; 前两个“ * ” 表示xoy面上的方位关系, 第3个字母表示z轴方位关系。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 3DOPRAm模型参照系Fig.2 Reference system of the 3DOPRAm model

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 xoy面方位划分Fig.3 Directions in the xoy plane

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 z轴方位划分Fig.4 Directions of the z-axis

为了区分三维空间中的两个方位点A和B, 令A=(P_A, δ _A), 其中P_A=(x_A, y_A, z_A), 令B=(P_B, δ _B), 其中P_B=(x_B, y_B, z_B)。对二维OPRA_m模型相对角进行扩展, 引入两个相对角φ _AB和θ _AB, 如图5所示, 其定义如下:

φAB=arctan[2(yB-yA, xB-xA)]φAB∈[0, 2π], φBA=φAB+π

式中:φ _AB为方位点B在方位点A所确定的xoy面投影后, 两个方位点之间的反正切值。

θAB=arctan[2(zB-zA, (xB-xA)2+(yB-yA)2)]θAB∈[-π/2, π/2]

式中:θ _AB为方位点B和方位点A之间连线与xoy面所成的角。

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 三维空间中方位点A和B之间的相对角φ AB和θ ABFig.5 Relative angles φ AB and θ AB of two oriented points in the three dimensions

在三维空间中, φ _AB-δ _A表示方位点B在方位点A所确定的xoy面方位; φ _BA-δ _B表示方位点A在方位点B所确定的xoy面的方位。相对角θ _AB表示方位点B在方位点A的z轴方位。其中φ _AB-δ _A和θ _AB对应角度的变化构成方位点A所在的欧几里得空间的完备划分, 其所对应的方位和角度变化如表1所示, 方位点B所在欧几里得空间的划分和方位点A类似。

三维空间中, 使用三元组(Q_AB、Q_BA、Z_AB)表示空间中的两个方位点之间的方位关系。Q_AB表示xoy面上方位点A相对于方位点B的方位关系; Q_BA表示xoy面上方位点B相对于方位点A的方位关系; Z_AB表示方位点B相对于方位点A的z轴方位关系。

xoy面上, 两个方位点在不同位置时, 总共有8× 8=64种基本关系。当两个方位点在同一位置时, 有8种方位关系; 故xoy平面上共有72种原子方位关系。z轴有以下5种方位关系Z_AB={U¹、U²、D¹、D²、E}。可得出三维空间中总共有360种方位关系。

表1

Table 1

表1(Table 1)

表1 方位点A所在三维欧几里得空间划分 Table 1 A partition of oriented point A on the Euclidean plane xoy面方位关系 角度φ AB-δ A z轴方位关系 角度θ AB f 0 U2 (π /4, π /2] lf (0, π /2) U1 (0, π /4] l π /2 E 0 lb (π /2, π ) D1 [-π /4, 0) b π D2 [-π /2, -π /4) rb (π , 3π /2) - - r -3π /2 - - rf (3π /2, 2π ] - -

表1 方位点A所在三维欧几里得空间划分 Table 1 A partition of oriented point A on the Euclidean plane

空间演算的粒度和空间结果的数学特性是解决定性空间任务的主要问题^[10]。在实际应用中(如复杂导航任务), 依据所处的环境、机器人的处理能力、任务的要求, 需要不同粒度下的方位关系, 因此引入了可扩展粒度。选择合适的粒度参数可以忽略一些不能引起变化的推理步骤, 加快计算速度。

将上述粗粒度相对方位关系的设计准则扩展到多粒度的情况, 得到3DOPRA_m, 其中m为粒度参数, m> 0∈ n将二维平面划分为2m个线性区域和2m个平面区域。区域按逆时针方向从0到(4m-1)编号, 区域0和方位点的本质方向重合。m条线将z轴正半轴划分成m个方位, 从xoy面按逆时针编号; 将z轴负半轴划分成m个方位, 从xoy面按顺时针编号。

xoy面上, 可扩展粒度方位关系中每一个方向片i满足如下角度范围:

[i]m=]2πi-14m, 2πi+14m[, 当i为奇数时{2πi4m}, 当i为偶数时

方向片j的角度范围和方向片i相同。当P_A≠ P_B时, 使用关系A ∠jiB表示如下含义:给定粒度m, 以B为参照对象, A相对于B的位置用j描述, 以A为参照对象, B相对于A的位置用i描述。其中方向片i, j满足如下几何结构:

φAB-δA∈[i]m, φBA-δB∈[j]m

当P_A=P_B时, 使用关系A∠iB表示如下含义:给定粒度m, 以A为参照对象, B位于A的方位。方向片i满足如下几何结构:

δB-δA∈[i]m

在z轴上的方位, 可扩展粒度方位关系中方向片h满足如下角度范围:

[h]m=[h-12m, h2m], h> 00, h=0[h2m, h+12m], h< 0

A∠hB表示以A为参照对象, B相对于A的高度范围。方向片h满足如下几何结构:

θAB∈[h]m

三维空间中的相对方位关系用xoy面和z轴相对方位关系组合表示, 对三维空间中的方位点A和B, 当A和B的位置不同时, 使用A ∠jihB表示, 含义为:xoy面上, 对于B而言, B在A的方位用i表示。对于A而言, A在B的方位用j表示; z轴上, h表示以A为参照对象, B相对于A的高度。当A和B的位置相同时, 使用A∠ihB表示, 含义为:对于B而言, B在A的xoy面的方位用i表示, z轴的方位用h表示。图6和图7为粒度m=2的三维空间中方位点的相对方位关系:A₂ ∠622B表示角度范围为:φ _AB-δ _A=3π /2, φ _BA-δ _B=π /4, θ _AB∈ (π /4, π /2]。A₂∠40B表示角度范围为δ _B-δ _A=π , θ _AB=0。

图6

Fig.6

	Figure Option ViewDownloadNew Window
	图6 不同位置两个方位点的相对方位关系A2 ∠622BFig.6 Two o-point in relation relation A2 ∠622B at different position

2.4 3DOPRA_m相对方位关系的逆

方向关系取逆操作是方向关系的基本运算之一, 对于空间中的两个点对象A和B, 已知它们的关系为R=(A, B), 通过求逆操作可以得到R=(B, A)。在3DOPRA_m模型中, 通过简单的符号操作, 即可求得3DOPRA_m模型的逆操作。

当三维空间中方位点A和B在不同位置时, 方位点的逆为:

(m∠ijhB)-1=(m∠ji-hB)

当方位点A和B在相同位置时, 方位点的逆为:

(m∠ihB)-1=(m∠(4m-i)hB)

图7

Fig.7

	Figure Option ViewDownloadNew Window
	图7 相同位置方位点的相对方位关系A2∠40BFig.7 Two o-point in A2∠40B at the same position

3 3DOPRA_m概念邻域及定性空间导航问题

为了将3DOPRA_m模型用于描述定性空间导航问题, 本文给出了基于3DOPRA_m模型的概念邻域及导航问题形式化的表示。通过设定规则, 将动作引起邻域关系变化用于求解导航问题。

3.1 3DOPRA_m概念邻域

基于二维空间中OPRA_m模型的概念邻域, 给出了3DOPRA_m模型的概念邻域。由于在实际应用中, 不同空间对象所施加的动作是不同的, 或者是在研究空间关系时, 因为参照对象是较少发生变化或基本不发生变化, 只需要研究目标对象的动作即可, 因此针对3DOPRA_m模型, 需要根据实际应用场景和特定相对方位关系, 给出其引起关系变化的动作。

当三维空间中相对方位关系为A_m ∠ijhB时, 对A和B施加任意动作可得到如下概念邻域:

cn_s(_m ∠ijh)={_m ∠i-1j-1h, _m ∠i-1jh, _m ∠i-1jh, _m ∠ij-1h, _m ∠ij+1h, _m ∠i+1j-1h, _m ∠i+1jh, _m ∠i+1j+1h, _m∠(i-1)h, _m∠(i+1)h, _m∠(-j)h, _m∠(2m-j)h, _m∠ih, _m∠(2m-i)h, _m ∠ij(h-1), _m ∠ij(h+1)}

当三维空间中相对方位关系为A_m∠shB时, 对A和B施加任意动作可得到如下概念邻域:

cn_s(_m∠sh)={_m∠(s+1)h, _m∠(s-1)h, _m ∠* Sh, _m ∠* 2m-Sh, _m ∠S*h, _m ∠2m+S*h, _m∠s(h-1), _m∠s(h+1)}

宋小华等^[9]提出了定性空间关系自动规划的形式化表示和推理算法, 并证明此算法的可靠性, 同时指出其方法在处理单方面空间关系规划中具有通用性。基于此思想, 本文给出了定性空间导航问题的形式化表示和基本求解思路。

定性空间导航问题描述:直观上, 定性空间关系的导航就是给定初始状态对象间的空间关系和目标状态对象间的空间关系的表示, 求解从初始状态到目标状态的动作序列。

定义1 定性空间关系导航是一个动作序列π =< a₁, a₂, …, a_k> , 其中k≥ 0, 导航的长度是|π |=k, 即动作数目。

定义2 称N=(s, g)是一个定性空间关系导航问题, 其中s为定性空间关系初始状态; g为定性空间关系目标状态, 从s经过动作序列π 到达目标状态g, 则π 是N的一个解。

定性空间关系导航问题求解:

求解定性空间关系导航问题, 就是以N=(s, g)作为输入, 求解动作序列π 的过程。

使用递归回溯方法求解此类问题, 其基本思路为:对初始邻域状态分别按顺序施加动作, 到达下一个动作邻域状态。删除掉规则不允许和产生循环的动作邻域状态后, 对产生的动作邻域状态进行递归求解, 直至转换到目标状态。如果找不到目标状态, 返回失败。