基于Voronoi图的定性路径推理

动态空间知识的表示与推理是定性空间推理研究的重要内容.基于Voronoi图及其动态变化,提出运动路径定性表示与推理方法.先根据Voronoi图空间邻近关系定义Voronoi图生成子空间关系,进一步定义定性位置及概念邻域,并应用概念相邻的定性位置序列给出定性路径表示.再由动态Voronoi图的边集变化和给出的概念邻域中定性位置间最短路径的启发式算法,设计并实现具有观察者角度的定性路径推理算法.最后,实验分析并验证该方法的有效性.     

传感环境下基于局部Voronoi图的启发式反监控路径发现算法

针对移动对象通过传感区域时的安全问题,提出了一种基于局部Voronoi图(VT)的启发式反监控路径发现算法.首先,给出了一种基于局部Voronoi图的路径暴露风险近似估算模型.在该模型中,移动目标可依据当前探测到的传感器节点位置信息动态生成局部Voronoi图,并可依据定义的暴露风险计算公式近似估算出局部Voronoi图中各条边所对应路径的暴露风险.然后,在此基础上设计并实现了一种启发式的反监控路径发现算法.在该算法中,移动目标可首先基于局部Voronoi图确定自己的下一跳位置点候选集,然后再基于定义的启发式代价函数从候选集中选择一个风险代价最小的位置点作为其下一跳目标位置点.最后,沿着局部Voronoi图中对应的最小暴露风险路径移动到该目标位置点.理论分析和实验结果表明,所提算法具有良好的反监控性能,针对部署有n个传感器节点的区域,能够使得移动对象在不超过O(n log n)的时间内快速找到一条具有较低暴露风险的路径来穿越整个传感区域.     

用Voronoi多边形扩展的空间数据模型

Voronoi图是一种基本几何结构 ,也是解决相关几何问题的有效的工具 .为了有效地解决 GIS中的空间目标间关系的动态构建、显示等问题 ,首先重点探讨了用 Voronoi图扩展的空间数据模型 ,然后主要从空间数据建模语义的角度出发 ,在研究 GIS面向对象的空间数据模型的基础上 ,提出了用 Voronoi多边形来部分地代替面向对象的数据模型间的关系定义 ,并给出了一个基于 Voronoi多边形的面向对象数据模型的框架 .该模型由于利用了Voronoi图具有的能良好地表示空间目标邻近关系的特性 ,并且由于通过空间目标的位置 ,能动态地获取和显示空间目标间的邻接关系 ,因而可以有效地弥补目前拓扑数据模型中 ,计算更新复杂及不能表示空间上邻近 ,而几何上不相接目标间的空间关系和栅格数据模型中不能有效地表达目标间拓扑关系的不足的问题 ,实践证明 ,这是一种较为理想的表示复杂空间关系的数据模型 .     

一种动态定性空间关系自动规划方法

为解决定性空间关系的规划问题,在概念邻域图的基础上提出描述动作与定性空间关系交互的邻域划分图.基于邻域划分图,提出了定性空间关系自动规划的形式化表示和推理算法,证明了算法的可靠性,并举例说明了新方法的应用.该方法在处理单方面空间关系规划中具有用通用性,在机器人导航方面具有潜在的应用前景.     

方向关系的定性表示与推理

方向关系是GIS中的一个重要的理论问题。本文重点讨论方向关系的定性表示与推理。文章首先讨论了基于井字空间的方向关系定性表示,然后介绍了基于方向关系组合运算表的方向关系定性推理,最后对我们现在和将来的一些研究进行了叙述,并对我们的工作做了总结。     

基于Voronoi K阶邻近图的半监督学习自动图像标注

在为自动图像标注构建相似图的过程中,针对传统的方法是基于图像间的视觉相似性,其没有考虑到数据集中某个子数据集内的结构信息这一问题,提出一种基于Voronoi k阶邻近图的半监督学习自动图像标注方法。该方法充分考虑Voronoi k阶邻近图能很好地表达空间目标的影响区域以及可以方便地进行空间邻近的描述与推理的特性,将特征空间内的图像数据点分布信息融合到点对间的相似度量表示中,利用未标注样本挖掘图像特征的内在规律,然后把半监督学习的方法和多标记学习有效结合起来,从而达到对图像进行自动标注。实验结果表明,提出的标注方法可行,同时标注结果与传统的标注方法相比得到了明显改善。     

基于近似Voronoi图的移动机器人实时路径规划

运用Voronoi图理论及人工势场理论,研究了一种基于近似Voronoi图的移动机器人实时路径规划的方法,用来实现未知室内环境中移动机器人的自主导航。该方法朝向预先定义的目标点位置来探测室内环境,生成近似Voronoi图,同时利用人工势场法进行避障,生成一条能达到目标点的安全、光滑路径。仿真结果表明,该方法简单且易于实现,同时能够减少规划时间。     

基于方向关系组合运算表的定性推理

方向关系的定性推理是GIS中的一个重要的理论问题。本文介绍基于井字空间的方向关系定性表示。着重讨论基于方向关系组合运算表的定性推理，最后给出一个基于方向关系组合运算表的定性推理算法。     

带权定性影响图

定性影响图是具有精确概率和效用的影响图的定性抽象。在定性影响图中,节点之间的影响关系使用定性符号描述,这种符号描述简化了不确定知识的表示,降低了影响图建模的难度,加速了不确定知识的推理。但是,定性影响图在抽象过程中损失了部分信息,导致定性影响图在评价过程中会产生不确定结果,阻碍了定性影响图的广泛应用。以加权的思想扩展定性影响图,使扩展的定性影响图中每个定性影响都带有一个表示节点间影响强弱的数值权值,在评价过程中根据定性影响权值的比较来减少不确定结果的产生,从而扩大定性影响图的应用范围。     

基于Voronoi图的方向区域查询方法

针对空间中方向区域查询效率不高的问题,通过引入Voronoi图,利用其特性对数据空间进行划分,提出了基于Voronoi图的方向区域查询方法.该方法在基于Delaunay三角网生成的Voronoi图索引结构基础上,将首结点与查询对象连线形成有向线段,利用Voronoi图可以通过邻接生成点延展的特点确定查询对象的位置,通过...     

Path planning of wheeled mobile robot with simultaneous free space locating capability

This paper presents a hybrid path planning algorithm for the design of autonomous vehicles such as mobile robots. The hybrid planner is based on Potential Field method and Voronoi Diagram approach and is represented with the ability of concurrent navigation and map building. The system controller (Look-ahead Control) with the Potential Field method guarantees the robot generate a smooth and safe path to an expected position. The Voronoi Diagram approach is adopted for the purpose of helping the mobile robot to avoid being trapped by concave environment while exploring a route to a target. This approach allows the mobile robot to accomplish an autonomous navigation task with only an essential exploration between a start and goal position. Based on the existing topological map the mobile robot is able to construct sub-goals between predefined start and goal, and follows a smooth and safe trajectory in a flexible manner when stationary and moving obstacles co-exist.     

平面形状和布置的一种统一的定性表示方法

基于广义Ｖｏｒｏｎｏｉ图式，提出了Ｖｏｒｏｎｏｉ骨架边的跨度和势的概念，给出了保持连通性的层次骨架的建构算法。     

Voronoi图的生成及近邻关系查询方法

针对构建Voronoi图的方法的生成效率较低,构建复杂度较高的问题,提出了利用多方法交叉融合进行Voronoi图的构建与更新的方法。为了提高空间数据最近邻查询的效率,提出了基于Voronoi图和Voronoi多边形最小内切圆的最近邻查询方法;针对查询点位置频繁变化的情况,提出了基于Voronoi图和Voronoi多边形最小外接矩形的最近邻查询方法;为了提高对偶近邻对和最近对的查询效率,利用Voronoi多边形和对应的最小内切圆进行过滤和查询,提出了统一查询对偶近邻对和最近对的新方法。实验结果表明,所提方法解决了因数据分布不均导致的额外计算量的开销问题,在数据集规模较大和查询频率较高时具有一定的优势。     

基于Voronoi图理论的自由边界型腔加工路径规划

Ｖｏｒｏｎｏｉ图是计算几何研究中的一个有力工具。给出了基于Ｖｏｒｏｎｏｉ图和单调区划分的型腔数控加工环切轨迹规划算法,并首次将其应用于边界为自由曲线的型腔,提高了Ｖｏｒｏｎｏｉ图在该领域的应用价值。     

Voronoi diagrams with barriers and on polyhedra for minimal path planning

Two generalizations of the Voronoi diagram in two dimensions (E²) are presented in this paper. The first allows impenetrable barriers that the shortest path must go around. The barriers are straight line segments that may be combined into polygons and even mazes. Each region of the diagram delimits a set of points that have not only the same closest existing point, but have the same topology of shortest path. The edges of this diagram, which has linear complexity in the number of input points and barrier lines, may be hyperbolic sections as well as straight lines. The second construction considers the Voronoi diagram on the surface of a convex polyhedron, given a set of fixed source points on it. Each face is partitioned into regions, such that the shortest path to any goal point in a given region from the closest fixed source point travels over the same sequence of faces to the same closest point.     

Voronoi diagrams with barriers and on polyhedra for minimal path planning

Two generalizations of the Voronoi diagram in two dimensions (E²) are presented in this paper. The first allows impenetrable barriers that the shortest path must go around. The barriers are straight line segments that may be combined into polygons and even mazes. Each region of the diagram delimits a set of points that have not only the same closest existing point, but have the same topology of shortest path. The edges of this diagram, which has linear complexity in the number of input points and barrier lines, may be hyperbolic sections as well as straight lines. The second construction considers the Voronoi diagram on the surface of a convex polyhedron, given a set of fixed source points on it. Each face is partitioned into regions, such that the shortest path to any goal point in a given region from the closest fixed source point travels over the same sequence of faces to the same closest point.This material is based upon work supported by the National Science Foundation under grants ECS-8021504 and ECS-8351942. The second author is also supported in part by a Fulbright scholarship     

一种基于点集自适应分组构建Voronoi 图的并行算法

论文提出一种基于点集自适应分组构建Voronoi 图的并行算法,其基本思 路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成 Voronoi 图,称为Voronoi 子图;提取所有分组内位于四边的边界点,对边界点集构建Voronoi 图,称为边界点Voronoi 图;最后,针对每个边界点,提取其位于Voronoi 子图和边界点Voronoi 图内所对应的两个多边形,进行Voronoi 多边形的合并,最终实现子网的合并。考虑到算法 耗时主要在分组点集的Voronoi 图生成,而各分组的算法实现不受其他分组影响,采用并行 计算技术加速分组点集的Voronoi 图生成。理论分析和测试表明,该算法是一个效率较高的 Voronoi 图生成并行算法。     

Constructing the generalized local Voronoi diagram from laser rangescanner data

We consider the problem of building local free space representation by a circular-base robot, operating in an unknown bounded planar environment populated by obstacles of arbitrary shape. In the unknown environment, the robot depends on its sensors; in our case, this is the laser range scanner. A new structure is represented, termed the generalized local Voronoi diagram (GLVD), constructed directly from sensory data, obtained from an observation of the local environment, that is from the visible region, GLVD is obtained by deleting some edges from the ordinary Voronoi diagram, which is generated by the measured scanned points from the visible region. Crucial for the acquisition of the GLVD is the clusterization of the scanned points. Clusterization means grouping of the scanned points into distinct clusters, each having a specific property, e.g., for a particular point in the cluster, the nearest neighboring point should not lie further than a prescribed distance away. The relevant part of GLVD, the portion of GLVD which is in accordance with the generalized Voronoi diagram of the environment, is determined. Eventual differences between these two structures are discussed and experimental results are presented. With the superposition of several GLVDs we show that this structure can be used to construct a global map of the environment, for which the position and the orientation of the robot is needed