异构群体队形光滑变换控制方法

针对现有群体队形控制方法在队形变换异构性、光滑性、条理性等方面的不足,提出一种基于几何约束机制的受限异构群体队形控制方法.首先采用Morphing方法生成由初始形状平滑变换到目标形状的一系列中间约束形状;然后引入基于质心的容量限制Power图对个体在约束形状中的内部布局进行建模,产生所需的异构分布;最后提出面向Power图的Lloyd导航算法,以控制个体进行无碰撞的光滑移动.实验结果表明,该方法稳定可靠,队形变换平滑流畅,非均匀人群分布可用于制作自然的群组动画和仿真真实场景,适用于不同规模、不同队形的异构群体队形控制.     

群组动画中的队形约束与控制方法

针对影视制作中对大规模虚拟群体运动控制的需求,提出一种基于队形约束的群体运动编辑与控制方法.首先利用贪心算法构建从初始队形到目标队形中个体位置的配对关系;然后对其进行优化,在保持个体相对位置的同时尽可能减少路线交叉;最后通过匹配虚拟角色的运动来合成流畅、逼真的群组动画.采用文中方法用户只需输入群体规模以及群体队形轮廓,即可实现对群体运动的编辑与控制.实验结果表明,该方法能够对不同规模、不同队形间的群体运动实现有效控制,从而提高群组动画制作的效率.     

可变形网格引导的群体队形仿真

目的 许多群体运动仿真算法侧重于模拟由大量自由移动个体所组成的群体行为,而针对具有特定队形的群体运动仿真算法较少。为解决这一问题,采用改进的网格引导方法,利用可变形网格对群体运动进行控制。方法 首先,对群体队形进行三角划分,建立一个连接所有智能体的队形网格。然后,利用障碍势场法在群体运动的过程中对队形网格进行变形,使智能体在避免与障碍物发生穿透的同时尽可能保持整体队形稳定。最后,针对障碍物穿过队形网格时可能造成的局部智能体 “错位现象”,提出了基于吸引点的网格引导方法,使群体绕过障碍物后能迅速恢复原来队形。结果 使用Unity软件对军队行进、动态车流、群体表演等场景中的智能体编队移动进行仿真,并设置了不同规模的群组交换实验进行对比。本文算法的实时计算花销主要集中在网格变形阶段：在队形网格顶点总数为1 000时,单位仿真步内网格变形阶段的平均运行时间为20.15 ms。队形网格划分阶段是一个预先进行的过程,不影响算法实时性。基于吸引点的网格引导方法提高了智能体的全局移动效率,使队形变化更加自然流畅。结论 实验结果表明,可变形网格引导的群体队形仿真算法在群体运动过程中能有效维持队形稳定,无论障碍环境是静态的还是动态的都能实现良好的群体避障,说明算法的有效性。     

不确定环境下多机器人编队控制研究

针对多机器人在不确定环境下难以保持某种队形到达预定目标等问题,提出了一种无须全局坐标的多机器人编队控制算法。该算法通过Reynolds类鸟群模拟方法设计了“分离”“对齐”“队形”三规则的控制器来实现多机器人任意队形保持控制,并增加切换规则来实现多机器人队形变换。在不同场景及复杂环境下进行仿真实验,验证了提出方法的优越性。该算法能够使多机器人在不确定环境下保持队形到达目标,对于救援、救灾下多机器人的运用具有重要意义。     

基于几何约束机制的团体操队形辅助设计平台

大型团体演出,如团体操,往往涉及到快速、平滑、流畅、整齐的群体队形变换问题.基于虚拟人群仿真技术,通过引入几何约束方法,结合Morphing,CVT和Lloyd技术,从团体操队形约束、个体分布布局、个体配对、个体运动路径规划、群体碰撞避免等方面,综合提出一种新颖的团体操群体队形变换解决方案.首先采用Morphing生成从源队形到目标体操队形的一系列中间约束形状,保证变化的平滑性;然后利用CVT技术实现群体在约束形状中的分布布局;由于约束形状变化,个体的运动路径规划和碰撞避免均采用改进的Lloyd下降法,即变空间域下的Lloyd下降法来实现;最终搭建系统平台,有效地提高了团体操队形设计质量和效率.     

广义Voronoi图求解多机器人运动规划

在拥挤环境中,由于障碍物的边界形状比较复杂,需要使用广义Voronoi图表示空间环境。且在多移动机器人的运动规划过程中,需要协调多个机器人的运动,必须得到Voronoi图通道的宽度。为此提出了一种计算拥挤障碍物环境中生成的广义Voronoi图及其通道宽度的算法。并在生成的Voronoi图上利用A*算法对多个机器人进行路径规划,并利用分布式方法协调多个机器人运动。对协调两个机器人运动的过程进行了仿真,仿真结果表明利用提出的算法生成的具有通道宽度信息的Voronoi图能够满足多移动机器人运动规划的需要。     

基于改进的领导-跟随者编队算法研究

针对领导-跟随者算法的不足,提出了基于先驱者的多机器人编队控制方法.先驱者采用SLAM方法规划编队行进轨迹的关键点,领导者则根据关键点和环境信息,调整运动轨迹,并计算与跟随者间的相互距离和夹角,决定跟随者的实时位姿.当编队队形遇障不能通过时,采用基于逻辑层次的变换策略进行队形变换.同时在Player-Stage仿真平台上,对算法进行了比较和分析,实验结果表明,改进的领导-跟随者算法能更好的保证编队队形的完整性和编队系统的稳定性,控制效果较好.     

基于行为的多机器人任意队形的控制

针对多机器人队形优化控制任务,提出一种快速收敛的机器人任意队形的控制算法。各机器人在奔向目标的过程中以队形的几何中心为参考点,自主地确定队形向量。在保持队形的过程中,采用动态死区法,通过对各个区域大小的控制达到对机器人速度的控制,维持规定队形。采用反向避碰、切线避障,根据各机器人间的位置,引入整体队形向量约束机器人的方向,达到机器人整体队形的方向与机器人运动方向一致。实验结果表明该算法可以快速、有效地完成各种编队任务。     

多智能体系统的队形控制方法及应用综述

多智能体系统队形控制的研究主要集中于队形形成、队形保持和队形变换3个方面;首先,介绍、分析了多种队形控制方法,包括轨迹跟踪法、行动选择法、假想刚体法、网络关系图分析法、动态编队法、虚拟势场法、学习控制法和混合控制法等;其次,对移动机器人、无人机、水下机器人等多智能体系统的队形控制应用进行研究;然后,给出了近年来多智能体系统队形控制的研究进展,包括基于复Laplacian矩阵的多维空间队形控制方法,其它领域技术(云计算、图像处理等)用于队形控制的研究成果,并对基于队形控制的多移动机器人和无人机搬运作了介绍;最后,给出了当前队形控制研究中尚未解决的问题,包括队形扩展,队形稳定性,通信、传感器功能,异构多智能体系统队形控制和机械臂编队等。     

移动机器人编队的运动控制策略

为实现移动机器人编队的多样性、稳定性和队形变换连续性,并解决移动机器人编队运动中的避障、避碰、到达目标的问题,对基本队形进行分析,提出队形参数化的思路,建立基本队形虚结构的参数化数学模型,通过调整参数使队形在基本队形及其衍生的队形间进行变换;机器人在运行的过程中,利用行为融合方法、跟随领航者法、人工势场法和虚结构法对机器人进行运动控制,实现了机器人的避障、避碰、队形归建等目标。对上述策略进行了仿真实验,实验结果表明,使用本策略既保留了虚结构法队形稳定、队形归建迅速的优点,又改进了其灵活性差的不足。     

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

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

Voronoi图算法及其在混合电路的衬底耦合研究中的应用

提出了对版图进行划分的Ｖｏｒｏｎｏｉ图的算法：将Ｖｏｒｏｎｏｉ图进行变换,通过扫描技术,从下到上对每个点与交点进行处理,从而形成变换后的Ｖｏｒｏｎｏｉ图,最后将此图转换为Ｖｏｒｏｎｏｉ图．在计算中,针对集成电路的物理特性,改进了阱区附近的Ｖ图的生成以及多个水平位置点和兼并问题．算法时间复杂度为Ｏ（ｎｌｏｇｎ）,空间复杂度为Ｏ（ｎ）．     

三维点集Voronoi图的算法实现

对现有三维点集Voronoi图的生成算法进行深入研究,提出并实现由Delaunay三角剖分构建Voronoi图的算法．首先采用随机增量局部转换计算Delaunay三角剖分,然后再根据对偶特性构建Voronoi图．该算法健壮性很高,适用于处理各种非完全共面三维点集．     

改进的限定Voronoi图梯形检测带细分算法

针对已有的限定Voronoi图生成算法在一些复杂约束条件下不能收敛的问题,通过引入控制因子,给出一种 改进的限定Voronoi图梯形检测带细分算法。在计算初始Voronoi生长元的过程中,引入外部和内部限定线段端点 保护圆半径控制因子,控制限定线段两端点附近的Voronoi边的尺寸;在细分梯形检测带的过程中,引入外部和内部 限定线段尺寸控制因子,控制位于限定线段上的Voronoi边的尺寸。实验结果表明,本算法对于内部边界约束、线束 约束条件以及不规则区域均可以得到质量较好、满足约束条件的限定Voronoi图。     

Representation of segment Voronoi diagram by Bezier curves

A new method for representing the Voronoi diagram of a set of line segments in a plane in the form of a flat straight-line graph is proposed. The graph is composed of control polygons of linear and quadratic Bezier curves. The radial function of the Voronoi diagram, which defines distance from the Voronoi edges to the generator sites, is described similarly with the help of the Bezier curves. The method allows one to construct an explicit medial representation of polygonal figures for the image shape analysis and transformation.

     

障碍空间中基于Voronoi图的k最近邻查询

为了提升障碍空间中k最近邻查询的效率,研究了障碍空间中基于Voronoi图的k最近邻查询方法,提出了在障碍空间基于Voronoi图的kNN-Obs算法。该算法采用了两个过程:过滤过程和精炼过程。过滤过程主要是利用Voronoi图的过滤功能,较大程度地减少了被查询点的个数。精炼过程主要根据障碍距离和邻接生成点对候选集内对象进行第二次筛选。进一步给出了处理新增加点的ADDkNN-Obs算法和处理删除点的DENkNN-Obs算法。实验表明该算法在处理障碍空间中的k最近邻问题时具有优势。     

一种平面点集Voronoi 图的细分算法

Voronoi 图是计算几何中的重要概念之一,在计算机图形学、计算几何、 计算机辅助几何设计、有限元网格划分、机器人轨迹控制、模式识别、气象学和地质学研究 中得到广泛应用。借助于四叉树和区间算术,提出了一种新的构造平面点集Voronoi 图的细 分算法, 并且和经典的增量算法、栅格扩张法进行了比较, 结果显示新细分算法更为有效。 最重要的是细分算法原理简单,很容易编程实现。     

基于Voronoi图的定性路径推理

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

基于各向异性质心Voronoi图的网络异常检测技术

网络异常检测技术是入侵检测研究领域中的重要内容,但在检测率和误报率上存在相互制约的问题,导致实际应用中性能不高。基于各向异性质心Voronoi图,提出一种新的网络异常检测算法。在新算法中,首先对数据集用各向异性质心Voronoi图进行聚类,然后计算每个数据点的点密度,判断数据点是否正常。通过KDD Cup1999数据集的实验测试表明,新算法具有较高的检测率和较低的误报率。     

A parallel algorithm for constructing Voronoi diagrams based on point‐set adaptive grouping

This paper presents a parallel algorithm for constructing Voronoi diagrams based on point‐set adaptive grouping. The binary tree splitting method is used to adaptively group the point set in the plane and construct sub‐Voronoi diagrams for each group. Given that the construction of Voronoi diagrams in each group consumes the majority of time and that construction within one group does not affect that in other groups, the use of a parallel algorithm is suitable. After constructing the sub‐Voronoi diagrams, we extracted the boundary points of the four sides of each sub‐group and used to construct boundary site Voronoi diagrams. Finally, the sub‐Voronoi diagrams containing each boundary point are merged with the corresponding boundary site Voronoi diagrams. This produces the desired Voronoi diagram. Experiments demonstrate the efficiency of this parallel algorithm, and its time complexity is calculated as a function of the size of the point set, the number of processors, the average number of points in each block, and the number of boundary points. Copyright © 2013 John Wiley & Sons, Ltd.