距离几何约束

距离几何约束（精选6篇）

距离几何约束 篇1

无线传感器网络是一种全新的信息获取和处理方式, 是由部署在感兴趣区域的大量低成本、低功耗的微型无线传感器网络节点组成。作为无线传感器网络的基本组成部分, 节点的位置信息对整个无线传感器网络是非常重要的。节点收集感知数据时, 如果不知道其感知对象位置, 所感知的信息往往是毫无意义的[1,2]。目前定位算法主要分两大类, 基于测距算法 (range-based) 和无需测距算法 (range-free) 。基于测距算法通过测量节点间的距离和角度信息, 使用三边测量、三角测量或最大似然估计等定位算法。常用的测距技术有RSSI (接收信号的强度指示) 、TOA、TDOA和AOA等。无需测距定位算法则不需要距离和角度信息, 算法根据网络连通性等信息来实现节点定位。基于测距的定位算法由于实际测量节点间的距离或角度, 通常定位精度较高, 比较各种基于距离的测距方法, 基于RSSI的定位无需额外硬件, 而无线通信芯片本身具有计算收发信号强度的功能, 定位不需要增加额外的硬件, 不会增加节点的硬件成本和尺寸, 所以基于RSSI的测距是无线传感器网络定位比较常用的方法。在实际的应用中由于反射、多径传播、非视距、天线增益等问题都会对RSSI的测距产生误差, 从而引起较大的定位误差。本文利用二维空间的Cayley-Menger行列式[2,3]提供的几何约束对RSSI的测距误差进行优化修正, 结合三角形质心计算, 提出了一种基于RSSI测距和距离几何约束结合三角形质心定位算法 (RDGC-TCL) 。仿真表明, 该算法与基于RSSI和三角形质心定位算法 (R_TCL) 相比, 提高了定位精度。

RDGC-TCL算法

RSSI测距

RSSI利用已知发射信号强度, 接收点根据收到的信号强度, 计算信号在传播过程中的损耗, 使用理论或经验的信号传播模型将传播损耗转化为距离。常用的传播路径损耗模型有[4,5]:自由空间传播模型、对数距离路径损耗模型、哈它模型、对数-常态分布模型等。文中采用自由空间传播模型和对数-常态分布模型, 用于分析和仿真。自由空间无线电传播路径损耗模型如下式:

式中:d为距信源的距离 (km) , f为频率 (MHz) , k为路径衰减因子。

在实际应用环境中, 由于多径、绕射、障碍物等因素, 无线电传播路径损耗与理论值相比有些变化。采用对数-常态分布模型将更加合理, 式 (2) 计算节点收到锚节点信息的路径损耗。

式中:为经过距离d后的路径损耗 (dB) ;Xσ为平均值为0的高斯分布随机变数, 其标准差范围为4~10。式中k的范围在2至5之间。取d=1m, 带入式 (1) , 可得到, 即的值。这样根据上式可得各未知节点接收锚节点信号时的信号强度为:

RSSI=发射功率+天线增益-路径损耗 () 。

Cayley-Menger行列式及距离几何约束

距离几何理论中, Cayley-Menger行列式可以被用来处理不变空间的欧拉距离几何问题[6,7]。两个n点序列{p1, …, pn}和{q1, …, qn}∈Rm组成Cayley-Menger矩阵, 且定义为:

其中d (pi, qj) , (i, j∈{1, …, n}为点pi和qj之间的欧式距离。两个n点序列的Cayley-Menger行列式定义为:

当两个序列相同时, M (p1, …, pn;q1, …, qn) 和D (p1, …, pn;q1, …, qn) 可简化为M (p1, …, np) 和D (p1, …, pn) , D (p1, …, pn) 被称为Cayley-Menger行列式。在RSSI测距过程中, 由于多径、绕射、障碍物等因素, 不可避免出现测距误差ε, 设未知节点与锚节点p1, …, pr之间的真实距离d0i与测量距离d0i。设未知节点p0接收到锚节点的测量信息, 根据节点集合{p0, p1, p2, p3}, {p0, p1, p2, p4}, …, {p0, p1, p2, pr}, 结合[3]利用Cayley-Menger行列式的经典理论的推导, 可得到r-2个独立的二次距离约束等式, fi (ε1, ε2, εi) =, 0 (i=, 3, 4…, r) 。ε1, ε2, …, εr作为未知节点与锚节点在测量过程中出现的误差, 在距离约束限制下形成平方误差最小化非线性问题:minJ=ε12+ε22+…+εr2

运用数值分析方法, 求得最优解ε1*, ε2*, …, εr*, 进而得到未知节点与锚节点位置估计值:

三角形质心定位算法模型

本文研究了未知节点与其无线射程范围内的三个锚节点之间的通信约束和几何关系得出了未知节点所在三角区域, 将三角形的质心作为未知节点的估计位置[8,9]。这里的三角形质心定位算法的基本思想是:三个锚节点A、B、C, 未知节点D, 利用RSSI和距离几何约束算出节点A和D的距离为rA;节点B和D的距离为rB;节点C和D的距离为rC。分别以A、B、C为圆心, rA, rB, rC为半径画圆, 可得锚圆交叠区域, 通过计算三个锚圆交叠区域的三个特征点的坐标, 以这三个点为三角形的顶点, 未知点即为三角形的质心 (如图1所示) 。

假设已知3个锚节点的坐标分别为A (xa, ya) 、B (xb, yb) 、C (xc, yc) , 与未知节点的距离分别为rA, rB, rC, 通过下面的公式求出。

同理, 可以求出F点和G点的坐标, 假设未知节点M的坐标 (xm, ym) , 利用质心算法得到未知节点M的估计坐标为:

RDGC-TCL算法过程

RDGC-TCL算法包括使用CayleyMenger行列式给出的距离几何约束条件对RSSI测量值进行处理来减小测量误差和利用三角形质心定位算法进行定位。

(1) 锚节点周期性发送自身的信息, 信息中包括自身节点ID和自身位置坐标。

(2) 未知节点p0收到来自锚节点 (p1, …, pr) 信息时, 根据RSSI由强到弱对锚节点进行排序, 并建立RSSI与节点到锚节点距离的映射。建立三个集合:

锚节点集合:Beacon_set= (p1, …, pr) ;

未知节点到锚节点距离集合:

(3) 选取RSSI值大的前几个锚节点进行计算, 并采用距离几何约束来求得未知节点与锚节点距离的估计值。

(4) 在Beacon_set中选择RSSI值大的锚节点组合成下面的三角形集合, 这是提高定位的关键。对Triangle_set中任一个三角形根据 (7) 式算出三个交点的坐标, 最后由质心算法, 得到未知节点坐标。

(5) 对求出的未知节点坐标集合取平均值, 得未知节点坐标。

仿真分析

为了验证算法的有效性, 对定位算法进行仿真。仿真场景为一个120×120的矩形区域, 100个节点被随机放在区域内, 其中30个锚节点, 70个未知节点。

采用距离几何约束来减少RSSI测距误差并结合采用三角形质心定位算法 (RDGC-TCL算法) , 算法性能主要从定位误差和定位覆盖率两方面进行考虑。仿真结果如图2、图3所示。

RDGC-TCL算法在测距校正的过程总增加了计算量和计算时间, 但对定位误差的减小和定位覆盖率的增加都有了较大的提高。由图2所示, 在锚节点较少的情况下, 本文算法的性能提高不大, 因为提供校正的测量数据较少, 随着锚节点数目增加, 用于校正的测量数据的增加, 使得测量的距离更加的准确, 使得定位的精度有了较大的提高。图3表明本文算法相对于R_TCL算法在节点的覆盖率方面有较大的提高。

结语

本文针对RSSI测距误差, 提出了基于RSSI和距离几何约束并结合三角形质心定位算法, 仿真结果表明, 本文算法比传统的RSSI定位算法有更好的定位性能, 能够减小定位误差并提高节点定位覆盖率, 同时本定位算法对硬件的要求不高, 能够降低无线传感器网络的成本, 能够满足大多数无线传感器网络的应用要求, 是无线传感器网络节点定位一种可选方案。

摘要：节点定位是无线传感器网络的基础问题之一, 基于RSSI测距技术被广泛应用到节点定位中。由于RSSI测距受到环境影响而产生测距误差, 进而影响节点定位的精度。本文利用距离几何约束来减小RSSI测距误差, 并结合三角形质心定位算法。仿真结果表明该算法比基于RSSI三角质心定位算法的定位精度有较大提高。

关键词：无线传感器网络,RSSI,节点定位,距离几何约束,三角质心定位

参考文献

[1]李建中, 高宏.无线传感器网络的研究进展[J].计算机研究与发展, 2008, 45 (1) :63-72.

[2]Akyildiz I F, Su W.Sankarasubramaniam Y, et al.Wireless sensor network:a survey[J], Computer Networks (Elesvier) (2002, 38 (4) :393-422)

[3]MING C.Sensor network localization with in precise distance[J].System and control letters, 2006, 55 (5) :887-893

[4]陈维克, 李文锋.基于RSSI的无线传感器网络加权质心定位算法[J].武汉理工大学学报, 2006, 30 (2) :265-268

[5]Su F, Ren W.Jin H.Localization alogrithm based on difference estimation for wireless sensor networks[c], Communication Software and Networks, 2009, ICCSN’09, International Conference on, 27-28Feb.2009Page (s) :499-503

[6]朱建新, 高蕾娜, 张新访.基于距离几何约束的二次加权质心定位算法[J].计算机应用, 2009, 29 (2) :480-483

[7]Mao G, Fidan B, et al.Wireless sensor network localization techniques[J].computer networks, 2007, 51 (10) :2529-2553

[8]林玮, 陈传峰.基于RSSI的无线传感器网络三角形质心定位算法[J].现代电子技术, 2009 (12) :180-183.

[9]李娟, 王珂, 李莉.基于锚圆交点加权质心的无线传感器网络定位算法[J].吉林大学学报 (工学版) , 2009, 39 (6) :1649-1653

基于交互方式的几何约束求解 篇2

计算机辅助设计 (Computer Aided Design, CAD) 是使用计算机来帮助人们进行产品设计的一项技术。在计算机辅助设计中, 几何约束求解是一项关键性技术, 能够缩短设计周期, 降低设计劳动和提高设计质量。目前, 几何约束求解方法主要包括:基于代数的求解方法、基于几何约束图的求解方法和基于规则推理的求解方法。在基于代数的求解方法中, 将几何约束问题转化为非线性方程组, 然后求解非线性方程组获取模型参数的数值[1]。在基于几何约束图的求解方法中, 使用无向图来表达几何约束关系。分析几何约束图, 形成一系列可求解的子问题, 组合子问题的解以获取整个问题的解[2]。在基于规则推理的求解方法中, 使用规则来建立模型构造步骤[3]。在二维绘图过程中, 复杂的图形可以利用简单的直线、圆弧和曲线合成, 比较适于使用这种求解方法。

2 交互方式几何约束求解框架

本文给出了一种基于交互方式的几何约束求解框架, 如图1所示。通过用户编辑界面, 绘图者输入建模命令。模型构建器对用户输入的建模命令进行分解, 建立若干个几何约束方程来实现建模命令。调用约束求解器对几何约束方程组进行求解, 获得模型的参数数值。模型构建器将该模型的几何约束方程存储在几何约束方程列表之中, 将模型参数数值存储在模型数据列表之中。在求得模型的几何参数数值之后, 约束求解器调用图形绘制器在图形显示界面中画出用户所需要的几何模型。

用户可以通过绘图系统画出所需要的目标模型。但是, 用户建模不是一次就能完成的。在建模过程中, 需要对模型参数进行多次修改。在每一次修改参数的过程中, 模型的约束关系都要发生改变, 诸如:模型元素之间的边界超出、边界交叠和边界错位等。这些问题会造成建模错误, 其具体反映形式为模型的几何约束方程组出现矛盾和无解的情况。单纯利用模型构建器来调整几何约束方程组是不能解决建模过程中出现的错误与矛盾。很多模型元素之间的冲突必须通过人机交互的方式来解决。

用户可以通过调整几何约束方程来解决建模过程中的矛盾。对于用户而言, 这种方式比较直接, 但是系统实现起来是比较复杂的而且也经常会出现问题。几何约束关系中的矛盾可以表现为模型参数之间的冲突。用户通过操作界面可以调整模型参数, 来解决几何约束关系中的冲突问题。这种约束关系的调整方式, 对于系统实现而言是比较容易的。但是, 需要用户计算模型元素的参数数值。例如:两个圆相切, 若其中一个圆的圆心发生变化, 则另一个圆的圆心坐标也要发生变化。在几何约束关系调整的过程中, 用户通过人机界面调整某一个模型元素的参数数值, 模型构建器调用约束求解器来计算几何约束方程组的解, 以获得其它模型元素的参数数值。

在模型建立和修改过程中, 用户需要与系统进行人机交互。几何约束关系的调整是以模型参数修改为基础的。在修改几何约束关系时, 用户应该分析约束方程之间的关系, 找出所涉及的最小约束方程组。在最小约束方程组中, 计算模型参数的关联度。按照关联度, 对模型参数进行排序。选取关联度最大的模型参数, 通过设定参数的数值来调节几何约束方程, 以消除约束关系中的冲突。若最小约束方程组依然存在矛盾, 则需要继续执行以上步骤, 直到所有的冲突消除为止。在消除了最小约束方程组的矛盾之后, 一部分参数数值由用户确定, 其余的需要调用约束求解器来进行求解。

用户编辑界面的设计应该便于模型参数的修改和几何约束关系的调整。在用户编辑界面中, 应该列出该模型的所有几何元素和几何约束方程。在系统实现时, 采用列表控件来显示几何约束方程。针对每一个模型元素, 应该列出它的所有模型参数。在系统实现时, 采用列表控件来显示模型参数。在设定模型参数数值时, 采用编辑框来实现。在用户界面中, 可以从列表控件中选择要修改的模型参数。在编辑框中, 可以设定模型参数的数值。在用户编辑界面中, 采用编辑框来实现几何约束方程的输入。在初始建立模型的过程中, 用户通过编辑框输入几何约束方程。在几何约束方程的编辑过程中, 用户从列表控件中选择目标约束方程。然后, 在编辑框中修改几何约束方程。在存储过程中, 按照模型元素来存储对应的参数信息, 按照模型来存储对应的几何约束方程。其目的是便于实现几何约束方程和模型参数的定位。采用CDC类来绘制目标模型。

采用了人机交互的方式来调整几何约束关系, 可以方便灵活地实现模型建立与修改, 降低了系统实现的难度, 具有较好的用户可操作性。

3 结论

本文给出了一种基于人机交互的几何约束求解方法。通过修改模型元素的参数数值来调整模型的几何约束关系, 将约束方程的调整归结为参数信息的修改。按照模型元素来存储参数信息以提高定位的效率。采用人机交互的方式来修改模型参数数值来降低建模和模型修改的难度。

摘要：本文提出了一种利用人机交互方式来实现几何约束求解的框架。用户通过CAD建模系统界面来改变模型参数的数值。系统的约束求解器对模型的几何约束方程进行求解, 获取约束方程的解。图形绘制器利用约束方程的解来绘制几何模型。

关键词：人机交互,几何约束求解,图形绘制器,几何模型

参考文献

[1]Gao X S, Lei D and Liao Q.Generalized stewart platforms and their direct kinematics.IEEE Transactions on Robotics, 2005, 21 (2) :141-151.

[2]黄学良, 李娜, 陈立平.三维装配几何约束闭环系统的递归分解方法[J].计算机辅助设计与图形学学报, 2013, 25 (9) :1296-1303.

距离几何约束 篇3

被动传感器的测量一般包括方位角和俯仰角。由于被动传感器在搜索目标时不发射信号, 不容易被敌方目标发现, 因此被动传感器在军事防空领域获得了广泛的应用。被动传感器所涉及的一个重要研究内容是如何利用多个被动传感器对目标进行精确交叉定位。在过去的研究过程中, 人们提出了最大似然估计算法 (Maximum Likelihood Estimate, MLE) 、Stansfield算法、伪线性估计 (Pseudolinear Estimate, PLE) 和修正辅助变量估计 (Modified-Instrumental Variable estimate, MIV) 等算法[1,2,3]。文献[4]在目标的被动定位过程中, 采用了加权最小二乘估计方法, 也取得了较好的效果。针对被动传感器在机动目标跟踪的情况, 文献[5]应用自适应最小二乘方法, 取得了较好的跟踪结果。文献[6]利用被动定位所得的目标位置, 对运动目标采用不同滤波算法进行滤波, 并对比了不同滤波算法的跟踪性能。最近, 文献[7-9]又提出了一种几何约束最小二乘 (Geometric Constraint Least Square, GCLS) 测向交叉定位算法, 并给出了详细的数学推导和仿真实验。该算法巧妙地将传感器几何位置信息融入到提高测量数据的准确程度过程中, 在默认各个测向传感器误差相同的条件下, 取得了良好的实验效果。文献[7-9]也提到可以采用几何约束加权最小二乘法 (Geometric Constraint Weighted Least Square, GCWLS) 构造目标函数, 使之适用于多个传感器量测误差不同甚至相关的情况。但是, 在实验过程中发现, 直接采用GCWLS算法效果并不理想。究其原因, 是该算法没有考虑各个传感器的测角误差和径向距离对定位精度的影响, 本文从该问题出发, 提出了一种计算交叉点权值的方法, 在交叉定位过程中对不同交叉点进行加权处理, 能够较大幅度提高定位性能。本文算法是在GCWLS算法基础上的改进算法, 称之为改进的基于几何约束的加权被动定位算法 (Geometric Constraint Weighted Least Square Plus, GCWLS+) 。新算法在相同的优化函数以及相同的参数设置条件下, 具有更好的定位性能, 而且时间复杂度增加量较小。

1 基于几何约束的被动定位算法

在利用测向传感器进行目标定位的过程中, 如果只有两个传感器, 并且和目标不在一条直线上, 那么方位角测量值所指示直线的交叉点就是目标的估计位置。如果多个测向传感器进行交叉定位, 则会出现多个交叉点的情况, 如图1所示, 这就是交叉定位不一致现象。从多传感器融合的角度来看, 多个传感器融合之后的数据应该能够获得更精确的定位结果。几何约束最小二乘算法就是利用多个传感器自身的位置信息通过优化算法计算每个传感器观测值可能出现的偏差, 并以此修正各个传感器的观测值, 从而提高测量值的准确程度。

假定有三个测向传感器, 并以x轴为零点和顺时针旋转为正方向进行测量。测量值分别为和由于每个传感器存在量测误差, 因此测量值存在误差设测量值和精确值之间的关系为

假定各个传感器的位置事先知道, 传感器i到传感器j的角度θij通过计算可以得到。为了计算方便, 我们取θiT, θij∈[, 02π) 。下面定义角度

并将其限制在 (-π, π]。φijT其实就是传感器i和传感器j之间线段和传感器i和目标T之间线段的夹角。由式 (1) 、式 (2) 易知:

定理1:假设有三个传感器对同一目标进行观测, 如图2, 其中任意两个传感器和目标不在同一条直线上, 即θiT≠θij, i, j∈1{, , 2}3andi≠j, 若θˆijT已知, 则下式成立:

定理2:假设有三个传感器对目标进行观测, 其中任意两个传感器和目标不在同一条直线上, 即θiT≠θij, i, j∈1{, , 2}3andi≠j, 若传感器i和j之间的距离dij及相应的夹角θˆijT已知, 则下式成立:

定理1和定理2的详细证明参见文献[7]。

将式 (4) 或者式 (5) 作为约束条件, 并记为

则对于具有k>3个传感器的测向定位系统, 可以得到 (k-2) 个约束条件, 即:

下面讨论三维空间中的被动定位情况。在三维空间中, 被动传感器通常通过测量目标的俯仰角θ和偏转角φ对目标进行定位, 如图3所示。

定理3:假定有两个传感器分别处于不同位置, 并且两个传感器和目标三者不共线。两个传感器和点A在同一个平面上, AT是该平面的法线方向。则:

其中:i, j∈1{, 2}, i≠j;θij T和φij T是真实角度;θˆij T和φˆij T是包含量测值的角度;eθij T和eφij T是角度误差。

假定传感器都位于坐标系中的x-y平面上, 则:

其中:φij是第i个传感器和第j个传感器之间的角度。则下式成立:

定理3的证明过程参见文献[7]。与二维情况类似, 如果传感器多于两个, 此时可以获得多个与式 (11) 类似的约束条件。

在上面的讨论中, 利用三角函数获得了二维和三维空间中测向角度、传感器间角度以及传感器间距离三者的约束关系。下面我们利用加权最小二乘方法获得最小的测角误差, 如果令传感器之间的测角协方差矩阵为∑, 而e=[e1e2e3...]T则有

将式 (12) 作为目标函数, 式 (4) 和 (5) 作为非线性约束函数, 利用最优化方法求解各个测量值的测角误差ei并对测量值进行修正, 修正公式为

2 改进的基于几何约束的加权定位算法

在求交叉定位点的过程中, 两个测向传感器确定一个目标位置, 所以k个传感器可以确定Ck2个交叉点。由于优化算法的精度问题, 这些交叉点并不重合, 目标位置要进一步计算。文献[7]采用的计算办法是直接求多个交叉点的重心, 但是在实验中发现这种计算方式误差较大。原因是每一个交叉点的精度不相同, 对最终估计位置的贡献不一样。为了能够进一步的提高定位性能, 对交叉点误差的影响因素进行分析, 计算第i和第j个传感器交叉点的权值wij。此时目标的位置计算如下:

考虑到影响交叉点误差的因素有两个, 即:传感器的测角误差标准差σi和传感器到目标的距离ir。在计算权值的时候应该把这两个因素对定位精度的影响都考虑进去。由于目标的误差范围可以近似的计算为εi≈sin (σi) ri, 在标准差非常小的情况下再进一步近似, 从而获得第i个传感器的误差度量:

其中:ir表示第i个传感器到目标的径向距离, σi表示传感器i的误差标准差。由于目标位置此时尚未确定, 因此并不能得到ir的精确值, 只能通过估算得到其近似值, 例如通过计算各个交叉点的重心获得目标位置近似值。

由式 (15) 可知, 定位误差与测角标准差和径向距离成正比。为了计算每个交叉点的权值, 首先对每个传感器的误差度量值εi进行归一化, 即:

然后再计算每个交叉点的权值:

其中M (εˆi, εˆj) 是一个求均值的函数, 例如几何均值或者算术均值函数。

最后对所有交叉点权值wij进行归一化, 即:

由wij的定义可知, 当确定交叉点Pij的两个传感器测角误差较大时, 权值wij较小, 反之权值则较大;当确定交叉点的传感器与目标之间的距离ri和rj较大时, 权值wij较小, 反之权值则较大。交叉点权值计算方法步骤总结如下:

Step 1:利用式 (15) 计算每个传感器的误差度量;

Step 2:利用式 (16) 对每个传感器的误差度量进行归一化;

Step 3:利用式 (17) 计算各个交叉点的权值;

Step 4:利用式 (18) 对各个交叉点权值归一化。

对于二维空间三个传感器的被动定位问题, 改进后的基于几何约束的二维被动定位算法步骤如下:

Step 1:把定理1或定理2作为约束条件, 把式 (12) 作为目标函数, 利用最优化方法计算每个传感器的测量误差ie;

Step 2:利用式 (13) 计算修正过的量测值;

Step 3:传感器量测值两两结合, 再加上传感器的坐标, 计算出所有交叉点Pij;

Step 4:利用交叉点权值计算方法获得各个交叉点的权值wij;

Step 5:利用式 (14) 计算出目标位置。

对于三维空间的改进算法与上述算法类似, 不再赘述。

3 仿真实验及结果分析

为了验证改进算法的有效性, 从定位误差和时间复杂度两个方面入手, 分别对二维和三维情况进行仿真实验, 并对实验结果进行分析。其中, GCLS、GCWLS算法来自文献[7], GCWLS+是本文提出的改进算法。

3.1 实验1:二维空间中三个测向传感器交叉定位

传感器的位置分别是 (0, 0) 、 (100, 30) 和 (250, 0) , 目标的位置是 (100, 100) 。考虑到不同性能传感器组合可能会对算法结果产生影响, 因此实验中设置了6种不同情况的测量误差标准差组合。三个传感器的测角误差标准差 (Standard deviation) 如表1前3行所示, 单位为度。每一种情况都重复观测10 000次, 分别采用GCLS、GCWLS、GCWLS+三种方法进行目标定位, 并求取不同方法的定位误差。

表1表明, 本文算法与GCWLS算法和GCLS算法相比, 误差性能有较大提高。不论是采用定理1还是采用定理2都能取得几乎相同的误差结果。此外, 在各个传感器测量标准差相互差别较大的情况下, GCWLS的误差性能甚至比GCLS的误差性能差, 而本文算法由于考虑了径向距离对误差性能的影响, 因而误差在各种情况下都低于GCLS和GCWLS, 如表1第4、5列数据所示。这种情况在各个传感器测量误差完全相同但是都非常小的情况下也会出现, 如表1中第6列数据所示。

3.2 实验2:三维空间中三个测向传感器交叉定位

传感器的位置分别为 (0, 0, 0) 、 (200, 200, 0) 和 (100, 0, 0) , 目标的位置为 (250, 500, 100) 。由于不同性能传感器组合对算法误差性能有所影响, 因此设定了6种组合, 然后计算在不同组合条件下的误差性能。其中, 传感器的测角误差标准差设定如表2前6行所示, 单位为度。分别对目标重复观测10 000次。采用GCLS、GCWLS、GCWLS+三种方法对目标定位, 并求取不同方法的定位误差。

表2表明实验结果同二维空间中情况类似, 本文算法能够较大幅度提高目标定位性能。同样, GCWLS并不能很好处理在误差不相同情况下的定位问题, 如表2中第3、5列数据所示。甚至在传感器误差性能相同情况下, 定位效果也不理想, 如表2中第1列数据所示。但是采用本文算法能够有效改善这种状况, 在各种情况下误差都能大幅度降低, 能够提高定位的准确性。

3.3 实验3:时间复杂度分析

实验一和实验二运行1 000次所需要的时间如表3所示。表3表明, 改进算法与GCWLS算法时间复杂度基本相当, 而GCLS算法时间复杂度表现不稳定, 有时比GCWLS+大, 有时比GCWLS+小, 这是由于加权矩阵会影响优化过程所需要的时间。在实验一中, GCLS、GCWLS和GCWLS+三种算法时间复杂度依次增大的, 但是使用定理1或者定理2需要的时间复杂度则各有伯仲。

s

结束语

本文在GCWLS算法的基础上, 给出了一种交叉点权值的计算方法, 在传感器量测标准误差不相同的情况下, 取得了较好的定位性能。值得注意的是, 该算法与优化算法的精确程度息息相关。理想情况下, 利用优化算法得到的测量偏差值对各个测量值进行修正之后, 所有这些量测值计算出来的交叉点是重合的, 并不需要对各个交叉点进行加权。但是, 由于优化算法并不能保证每次都能得到精确解, 往往得到近似解或者是局部最优解。此时, 就需要采用本文提出的计算交叉点权值的办法进行加权, 从而获得更为精确的定位结果。

参考文献

[1]Gavish M, Weiss A J.Performance of analysis of bearing-only target location algorithms[J].IEEE Trans.on Aerospace and Electronic Systems (S0018-9251) , 1992, 28 (3) :817-827.

[2]Nardone S C, Lindgren A G, Gong K F.Fundamental properties and performance of conventional bearings-only target motion analysis[J].IEEE Trans.on Automatic Control (S0018-9286) , 1984, 29 (9) :775-787.

[3]Dogangay K, Ibal G.Instrumental variable estimator for3D bearings-only emitter localization[C]//Proceedings of the2nd International Conference on Intelligent Sensors, Sensor Networks and Information Processing, Melbourne, Australia, Dec5-8, 2005:63-68.

[4]刘宗香, 谢维信, 杨煊.网状被动传感器系统视线交叉目标定位方法[J].电子与信息学报, 2005, 27 (1) :17-20.LIU Zong-xiang, XIE Wei-xin, YANG Xuan.Target location method based on intersection of lines of sight in the netted passive sensor system[J].Journal of Electronics&Information Technology, 2005, 27 (1) :17-20.

[5]宋骊平, 姬红兵, 高新波.多站测角的机动目标最小二乘自适应跟踪算法[J].电子与信息学报, 2005, 27 (5) :793-796.SONG Li-ping, JI Hong-bing, GAO Xin-bo.Least-squares adaptive algorithm for bearings-only multi-sensor maneuvering target passive tracking[J].Journal of Electronics&Information Technology, 2005, 27 (5) :793-796.

[6]后小明.三站目标被动定位数据处理算法研究[J].电子与信息学报, 2007, 29 (3) :565-569.HOU Xiao-ming.Algorithm research for passive locating processing of three station target data[J].Journal of Electronics&Information Technology, 2007, 29 (3) :565-569.

[7]Bishop A N, Anderson B D O, Fidan B, et al.Bearing-only localization using geometrically constrained optimization[J].IEEE Trans.on Aerospace and Electronic Systems (S0018-9251) , 2009, 45 (1) :308-320.

[8]Bishop A N, Fidan B, Anderson B D O, et al.Optimality analysis of sensor-target geometries in passive localization:Part1–Bearing-only localization[C]//Proceedings of the3rd International Conference on Intelligent Sensors, Sensor Networks, and Information Processing, Melbourne, Australia, Dec3-6, 2007:7-12.

参数化造型中的几何约束求解方法 篇4

传统CAD系统无法很好的支持功能设计、概念设计等操作, 为了弥补传统CAD系统的不足, 更好地满足概念化设计的要求、提高设计效率, 在20世纪70年代, CAD系统首次引入了人工智能的思想, 其主要特征和标志为参数化和变量化技术。

参数化技术与变量化技术的核心是:当设计者指定了草图的尺寸和拓扑关系后, 系统能够自动生成相应的结果图形。这一求解过程称为几何约束求解。几何约束求解对CAD系统的性能起着至关重要的作用, 并可应用于其他众多的工程领域。

几何约束求解的数学思想是:将几何约束转化为代数方程组, 然后对方程组进行求解, 得到问题的解。几何约束涉及大量几何元素, 在转化为代数方程组时会产生大型非线性方程组。目前还没有求解大型非线性方程组的稳定方法, 为了提高求解效率、减小求解复杂度, 一个基本思想是将大型系统分解为若干个较小规模的子系统, 分别求解, 然后将各个求解结果组装为整个系统的最终解。几何约束的求解方法融合了很多领域的知识, 如几何、图论、矩阵、组合优化、人工智能和离散数学等, 根据不同的求解方式, 可将几何约束求解方法分为:基于代数的求解方法、基于几何约束图的求解方法和基于人工智能的规则推理法。

2 约束求解方法

2.1 基于代数的求解方法

基于代数的求解方法是将几何约束问题转化为非线性方程组来进行求解。这种方法利用变量和方程表达几何约束系统, 具有很强的通用性和直观性。代数求解法中常用的方法是数值法和符号法。

数值法是直接将几何约束转化为非线性方程组, 然后采用整体数值迭代求解。Newton-Raphson迭代法是使用最多的一种数值计算方法, 通过迭代过程Xk+1=Xk-J (Xk) -1F (Xk) 逐渐逼近方程组的解, 这里J (Xk) 是F (Xk) 在点Xk的Jacobi矩阵, F= (f1, f2, …, fm) T:是方程组向量, X= (x1, x2, …, xm) T是变元向量。这种方法的求解速度快, 使用范围广, 但只能求得一个解。为了求得问题的全部解, 可以将几何约束满足问题转化为优化问题进行求解。Joan利用遗传算法来求解几何约束问题, 但是这种方法只能处理规模较小的问题。欧阳应秀提出将混沌方法嵌入BFGS算法的混合求解方法, 能求解欠约束和过约束情况。

用符号法求解几何约束时, 首先将几何约束映射为代数方程组, 然后利用消元法化简代数方程组, 并采用数值回代的方法进行求解。符号法主要可以分为Grobner基法、吴方法以及结式法。高小山将吴方法应用于几何约束求解。这种方法可以判断完备约束、欠约束和过约束的情况, 但是时间复杂度和空间复杂度都较大。

2.2 基于几何约束图的求解方法

基于几何约束图的方法是对几何约束图进行分析, 将问题分解为可分别求解的子问题, 然后将各个子问题的解合并为最终问题的解。根据分析策略的不同, 可将基于几何约束图的方法分为构造法和自由度分析法。

在构造法中, 根据几何约束图的不同分解形式, 可以将构造法分为递归分割法和递归装配法。递归分割法是通过一定的规则, 将几何约束系统分割为若干子系统, 再继续递归分割各个子系统。Owen首次提出递归分割法, 该方法以图论中的关节点、双连通和三连通等概念为基础, 与深度优先搜索和广度优先搜索算法相结合, 自顶向下分割几何约束图。Joan提出了Deficit的概念, 在保持约束图的Deficit不变的条件下, 分解二叉树s-tree。张桂芳将三维完备几何约束图分解为k-连通子图, 如果其中一个子图是完备约束的, 则求解该子图后, 可以将这些子图的解合并为原问题的解。递归装配法以迭代的方式将刚性体组合成更大的刚性体。如果约束系统中包含完备约束和欠约束子系统, 则递归装配法返回一个完备约束组件的最大集合。Podgorelec通过变换点和直线之间的角度和距离约束, 将复杂约束转化为简单约束;将复杂几何元素映射为辅助线和辅助点, 来处理复杂几何元素。

Kramer以刚体运动学为基础提出了几何约束系统的自由度分析法, 给出了链路搜索和环路搜索算法, 并提出:“几何约束满足问题的核心是实现约束的最大分解”。

彭小波分析了几何约束系统的奇异性, 提出了一种基于有向约束图的欠约束系统的求解的方法, 通过分解几何约束来减小约束求解的规模。蒋丹东引入了点簇的概念, 综合了基于图和基于规则的约束求解方法, 运用图论的原理建立了基于点簇的图形约束模型。李彦涛引入形状自由度的概念, 将剪枝和凝聚相结合, 实现欠约束和完备约束系统的分解, 并使用解析法和数值法对约束进行求解。在欠约束系统分解方面, Lee将非尺规可构造构型分离出来并利用数值计算法进行求解, 利用分类规则找出欠约束子图, 并得到求解序列。Joan通过添加几何约束, 将欠约束转化为可求解的完备几何约束问题。高小山以D-Tree的分解方法为基础, 通过自动添加几何约束, 将欠约束问题转化为可求解的完备几何约束问题, 使分解后的几何约束问题具有最小的规模。

2.3 基于人工智能的规则推理法

基于人工智能的规则推理法利用谓词和一系列重写规则来构造几何元素, 从而将几何约束问题转化为可构造的形式。

Aldefeld采用基于符号推理和操作的专家系统来建立规则体系, 用一阶谓词描述几何约束关系, 然后利用推理机对知识库进行规则匹配, 从而构造出整个图形。

日本东京大学Kimura的研究小组提出了基于规则的构造方法, 通过两种方法得到约束:一种是由系统模型自动生成, 另一种是由用户交互定义。这种方法考虑了系统的多解情况, 但没有考虑约束的一致性检验问题。Verroust提出了面向规则的平行四边形变换方法, 该方法能够解决多边形的所有完备约束问题, 但应用范围有限。高曙明引入已知元素和已知约束的概念, 利用普通算法实现几何推理。Dufourd采用延拓法对几何约束系统进行自动符号推理, 并提出以树的形式表达解空间, 通过剪枝法处理多解性问题。Schreck利用距离比率约束来替换距离约束, 将几何约束问题转变为相似群中的不变形式, 并进行构造求解。Podgorelec给出了分析几何约束是否可解的规则, 并提出了简化几何约束和冗余校验的方法。Fabre将符号法和数值法相结合来简化几何约束, 但该方法仍然以牛顿迭代法为基础, 求解的稳定性和效率有待进一步提高。

3 结论

本文分析介绍了国内外现有的几何约束求解方法。几何约束求解是CAD造型系统的关键技术, 对CAD系统的性能起着至关重要的作用。在造型系统中, 合理有效的几何约束求解机制将会有效地提高造型效率。因此, 研究几何约束求解方法具有重要的现实意义。

摘要：本文介绍了参数化造型中的几何约束求解方法的发展状况, 从基于代数的求解方法、基于几何约束图的求解方法和基于人工智能的规则推理法等方面分析了目前造型系统中采用的几何约束求解方法。

关键词：约束求解,几何约束图,人工智能

参考文献

解析几何中的最值距离探析 篇5

关键词：数学,解析几何,求线段最值,曲化直

解析几何中的最值问题是高考中的热点问题, 既有选择题又有填空题、解答题, 难度中等偏高.考查上述问题时, 通常考查函数与方程、转化与化归及分类讨论等思想方法.这就要求同学们对最值问题要做到心中有数, 运算准确, 争取在此类问题上能够脱颖而出.下面, 就常常出现的几类题型介绍一下自己的看法.

例1已知点A (-3, 8) , B (2, 2) , 点P是x轴上的点, 求当|AP|+|PB|最小时点P的坐标.

【解析】设点B关于x轴的对称点为B1, 连AB1交x轴于点P, 则易知点P满足|AP|+|PB|最小.可求得直线AB1的方程2x+y-2=0.令y=0, 则x=1.故所求点P的坐标为 (1, 0) .

点评:此题考查直线上一点到直线同侧的两点距离和的最小值, 往往转化为对称问题, 用直线方程的方法求解.很好地把直线问题与几何问题结合到了一起, 难度不大, 属于易得分题.

例2若实数x, y满足x2+y2+8x-6y+16=0, 则x+y+1的最大值为________.

点评:此题考查直线与圆位置关系问题.解法一考虑用圆心到直线距离与半径比较大小, 同学们容易想到但要注意计算准确.解法二则巧妙地运用了三角代换方法, 简化了运算步骤, 是较好的选择.

例3如图, 已知B, C为椭圆的两个焦点, 为定点, M是椭圆上一动点, 求的最小值.

【解析】根据椭圆定义, 有|MA|+|MC|=|MA|+ (8-|MB|) =8- (|MB|-|MA|) .为使|MA|+|MC|取得最小值, 只需|MB|-|MA|取得最大值, A、B、M三点共线时才可以取得, 此时, 故所求最小值为.

点评:此题考查椭圆第一定义的灵活运用, 要熟练掌握转化变形, 同时应用了三点共线原理, 难度稍大, 属于拉分题.

例4 P为双曲线的右支上一点, M、N分别是圆 (x+5) 2+y2=4和 (x-5) 2+y2=4上的点, 求|PM|-|PN|的最大值.

【解析】根据题意, 作出右图.显然, O1, O2为双曲线的两个焦点.要使|PM|-|PN|最大, 即要使|PM|最大, |PN|最小, 以此作出M, N具体位置如右图, 则容易得出|PM|-|PN|最大值为:|PM|-|PN|= (|PO1|+2) - (|PO2|-1) =3+|PO1|-|PO2=3+6=9.

点评:此题属于综合性较强的题型, 既考查了圆的方程, 又考查了双曲线的性质.但最终还是回归到双曲线的定义上, 充分体现了回归课本的指导思想.

例5点A (3, 2) 为定点, 点F是抛物线y2=4x的焦点, 点P在抛物线y2=4x上移动, 则当|PA|+|PF|取得最小值时, 点P的坐标是____.

【解析】抛物线y2=4x的准线方程为x=-1, 设P到准线的距离为d, 则|PA|+|PF|=|PA|+d.要使|PA|+|PF|取得最小值, 由右图可知过A点的直线与准线垂直时, |PA|+|PF|取得最小值, 把y=2代入y2=4x, 得P (1, 2) .

点评:此题求取最值时, 没有上来后先设点, 而是首先观察点的位置, 看能否借助概念, 巧妙进行转化, 于是考虑抛物线的定义, 顺利解决了此题.

距离几何约束 篇6

关键词：重定位,几何约束分枝定界算法,同时定位与地图创建,联合相容

0 引言

当环境未知时,为使移动机器人实现自主行走,必须同时解决定位和地图创建问题,也称SLAM问题(Si⁃multaneous Localization and Mapping)[1]。而其中的重定位则是研究在缺乏初始位姿等先验知识的前提下,使机器人根据其所携带的传感器测量值,确定自身在给定地图中的位置及姿态,此后可重新开始进行同时定位与地图创建。当无法获得GPS信号时,重定位是惟一有效的方法,适用于以下三种场合:在定位误差较大时自行恢复;在机器人“迷失”时重新启动SLAM过程;在循环较大时使其能够安全地结束。

要处理重定位问题,目前主要有两种不同的思路[2]:以最大团[3]、假设检验[4]与联合相容分枝定界(JCBB)[5,6]等方法为代表,其实质是在地图中寻找与传感器探测信息相一致的特征,再参照机器人与这些特征之间的相对距离与方位,最终确定机器人在地图中的位置;以蒙特卡洛定位[7]和马尔可夫定位[8]等方法为代表,其实质是在机器人可能所处的各位置,分别对传感器探测信息与地图间的一致性进行检验。第一种思路的关键是数据关联,数据关联[9,10]可在传感器观测与地图特征之间建立对应的关系,并直接影响到SLAM中的状态估计,而实际中各种不确定性与干扰因素的作用使得数据关联更为复杂与困难。

为解决数据关联问题,研究者们提出多种不同的算法[11,12,13,14]。其中,最邻近(NN)算法是最早提出的,其算法简单、易于实现,但对传感器测量精度要求较高,且不适用于干扰程度较严重的环境。文献[15]将分枝定界和几何约束相结合,提出了一种性能较好的几何约束分枝定界(GCBB)算法,然而当观测数目增大时计算量也呈指数关系增加,使得实时性变差,限制了其实际应用。鉴于此,本文将从两个方面对GCBB算法进行改进:在观测数目较多时,分组进行关联,以降低计算量;利用机器人传感器的测量范围将数据关联的范围限制在局部可能区域内,以减少数据关联时的搜索空间,从而进一步降低计算量。在此基础上,设计了一种快速几何约束分枝定界(Fast Geometric Constrains Branch and Bound,FGCBB)算法,并利用悉尼大学提供的“Victoria Park”数据集[16]对FGCBB算法进行验证,以期为重定位问题提供一种新的解决思路。

1 SLAM问题的一般数学模型

SLAM问题中,利用状态向量及其协方差矩阵可将地图信息表示为Map={Xk,Pk}。系统的状态向量可表示为:

式中:Xvk=[xvkyvkΦvk]T,(xvk,yvk)是机器人的位置坐标,Φvk是机器人的姿态角;M=[x1y1x2y2⋯xnyn]T表示各个地图特征的位置坐标,对于静止特征,位置坐标是不随时间变化的。

协方差矩阵的表达式为:

式中:Pvv是机器人位姿估计协方差;Pmm是特征位置估计协方差;Pvm是交叉协方差。

设k时刻,机器人所带传感器获得环境特征Ei的观测为zk,i(i=1,2,⋯,m),以Fj={xj,yj}(j=1,2,⋯,n)表示地图中的已有特征,为建立zk,i和Fj之间的关系,需要通过数据关联将地图特征Fji与每一观测zk,i进行对应,进而得到关联假设:

当Hm中存在某个ji=0,则表明观测zk,i可能是虚假观测或新特征,故无法与已有特征相匹配。数据关联本质上是一个搜索解空间的过程。设观测数为m,可能与第i个观测相匹配的特征数为(n+1),那么可知需搜索的空间大小为(n+1)m,与观测数m成指数关系。

2 GCBB算法

2.1 几何约束

几何约束包括一元(unary)几何约束与二元(bina⁃ry)几何约束,当缺少位置估计时,可以利用几何约束实现数据关联。

(1)一元几何约束

设pij=(Ei,Fj)为所给定的“观测⁃特征”配对,以分别代表Ei与Fj的某几何特性参数,如长度、半径和角度等。pij=(Ei,Fj)满足一元几何约束的条件是:

式中:d=dim(ui);1-α是给定的置信水平,通常取95%。χ2d,1-α的值可在卡方分布表中依据自由度d与置信水平1-α查表得到。若观测数目为m,则对应有m个一元几何约束。

(2)二元几何约束

设pij=(Ei,Fj)与pkl=(Ek,Fl)为所给定“观测⁃特征”配对,则二元几何约束是指Ei,Ek间的几何关系与Fj,Fl间的几何关系必须一致。以fb(·)表示两者间的几何关系函数,则Fj,Fl之间的几何关系估计值与方差的表达式分别为:

式中:均为雅可比矩阵。

同理,可得到观测Ei,Ek之间的几何关系估计值与方差Pik。若有:

则认为pij=(Ei,Fj)与pkl=(Ek,Fl)满足二元几何约束。若观测数目为m,则对应有m⋅(m-1)/2个二元几何约束。

2.2 联合相容检验

利用2.1节中的几何约束将观测和特征配对后,还需通过联合相容(Joint Compatibility,JC)检验所得配对的一致性,并获得一致性最佳的配对。在进行检验时,联合相容所采用的依据是特征间的相对误差,随着配对数目的增加,单个错误配对与其余配对联合相容的概率将降低。目前,大部分的重定位算法都是基于联合相容来检验关联的一致性,其效果差别较小,但计算效率却存在较大差异。

机器人的观测方程可写为:

式中:h(·)为非线性函数;nk是方差为Rk的高斯白噪声。

设关联假设Hm={j1,j2,⋯,jm},则可列出联合观测方程:

联合新息vHm与协方差SHm的表达式为:

式中:zk=[zk,1⋯zk,m]′表示k时刻的所有观测值;分别表示k时刻机器人的预测位姿及其预测方差;为雅可比矩阵。

而观测zk与Hm中相应的地图特征满足联合相容的条件为联合马氏距离:

式中d=dim(zk)。

将几何约束和分枝定界法两者进行结合,便形成了几何约束分枝定界(GCBB)重定位算法,具体的推导过程可参见文献[15]。

3 改进的GCBB重定位算法

由于GCBB算法的计算复杂度与观测数目m成指数关系,当m较大时,算法的执行速度将大幅度降低,直接影响到算法的实际应用。下面将从两个方面对GCBB算法进行改进。

3.1 数据关联的分组处理

当观测数目较大时,先将所有观测进行分组,再对各组进行数据关联。设每组观测数目的上限为N,此时搜索空间的大小由(n+1)m变为m N⋅(n+1)N,相应地,计算复杂度与观测数目m之间也从指数关系变成线性关系,计算效率得到了较大提高。按分组方式进行数据关联时,配对出错的概率随着N的增加而降低,为有效地防止错误关联,一般要求N6,考虑到随着N的增大,计算量也会迅速增加,故N通常在6~10之间选取。

3.2 关联特征的局部化选取

在进行数据关联时,所采用的地图特征数目越多,计算量越大。考虑到任一时刻机器人所携带的传感器的探测范围是有限的,为减少计算量,可根据传感器的探测范围选取相应的局部区域内的地图特征,实施数据关联。

首先,假设地图中有n个特征,定义n×n维矩阵C,则:

式中:(xi,yi),(xj,yj)分别表示地图中第i,j个特征的位置;R由传感器探测范围确定。只有满足Cij=1,才能执行下一层的联合相容配对。

3.3 快速几何约束分枝定界算法(FGCBB)

综合第3.1,3.2节所提出的改进,便可得到FGCBB算法,其处理流程的伪代码如下所示。需要注意的是,与常规GCBB伪代码相比,在分枝判定中增加了Cij==1,以考虑特征的区域性。

FGCBB处理流程伪代码:

GCBB处理流程伪代码:

4 算例仿真与分析

由于“Victoria Park”数据集提供了丰富的GPS数据、激光雷达数据与DR数据,为了对FGCBB算法进行验证,本节利用该数据集进行仿真。设置传感器探测范围为R=16 m,N=6。计算平台CPU为IntelⓇCoreTMi5⁃3210M,主频为2.5 GHz,算法通过Matlab R2013a实现。

将EKF⁃SLAM算法[2]执行1 000步以获得环境地图,其中含有99个树特征。设一元、二元几何约束分别取为树干半径与树间距离。继续执行EKF⁃SLAM算法,在第1 001~2 500步对重定位算法进行验证,而每一步计算所得的机器人位姿则为重定位结果提供参考。

1 001步时激光雷达测量中提取的树特征分布如图1所示,此时观测数目为m=7。图2给出了此时快速几何约束分枝定界算法重定位的结果。从图2知,所有的观测与地图特征进行了正确关联,重定位位姿与参考位姿相差很小。

1 001~2 500步中快速几何约束分枝定界算法(FGCBB)的重定位结果见图3。在此过程中,有737步机器人是位于地图中的,其中的74步观测数小于6,而地图之外的其余各点均没有获得定位。

图4给出了1 001~2 500步中不同观测数目条件下FGCBB与GCBB的平均执行时间对比曲线。可以看出,当观测数目大于6时,FGCBB比GCBB的执行时间要少,且观测数目越大,两者的差距越大。

5 结语