Using B<Superscript>+</Superscript>-trees for processing of line segments in large spatial databases

Points, lines, and regions are the three basic entities for constituting vector-based objects in spatial databases. Many indexing methods (G-tree, K-D-B tree, Quad-tree, PMR-tree, Grid-file, R-tree, and so on) have been widely discussed for handling point or region data. These traditional methods can efficiently organize point or region objects in a space into a hashing or hierarchical directory. They provide efficient access methods to meet the requirement of accurate retrievals. However, two problems are encountered when their techniques are applied to deal with line segments. The first is that representing line segments by means of point or region objects cannot exactly and properly preserve the spatial information about the proximities of line segments. The second problem is derived from the large dead space and overlapping areas in external and internal nodes of the hierarchical directory caused by the use of rectangles to enclose line objects. In this paper, we propose an indexing structure for line segments based on B ⁺ -tree to remedy these two problems. Through the experimental results, we demonstrate that our approach has significant improvement over the storage efficiency. In addition, the retrieval efficiency has also been significantly prompted as compared to the method using R-tree index scheme. These improvements derive mainly from the proposed data processing techniques and the new indexing method.     

基于多启发式信息融合的攻击路径发现算法研究

攻击路径发现对于提高信息系统安全具有重要意义,传统攻击路径发现技术存在考虑因素有限以及可扩展性不高的问题,导致其在网络攻击复杂化和网络规模扩大化的趋势下应用价值有限。针对该问题,本文提出一种基于多启发式信息融合的攻击路径发现算法,该算法结合攻击路径发现背景知识,将漏洞威胁程度,漏洞成功率以及主机资产作为启发式函数计算依据引导攻击路径搜索,达到减少搜索范围、提高路径可用性的目的;并且基于SMHA^*（Share Multi-Heuristic A^*,SMHA^*）框架实现多种启发式信息融合,共同引导攻击路径搜索。通过与现有规划算法进行对比实验,验证了本算法能够更加灵活而全面地考虑攻击路径发现中的现实因素,且规划效率也能够满足实际需求,能够有效提高规划结果的可行性以及应用价值。     

融合简化稀疏A*算法与模拟退火算法的无人机航迹规划

针对无人机航迹规划问题,提出了一种融合简化稀疏A^*算法与模拟退火算法（Fusion of Simplified Sparse A^* Algorithm and Simulated Annealing algorithm,简称FSSA-SA）的航迹规划方法.首先,在对威胁环境进行建模之后,将模拟退火思想与具体航迹规划问题求解相结合,给出了模拟退火算法求解航迹规划问题的具体设计与实现方法.其次,利用简化的稀疏A^*算法在规划起止点之间进行一次往返搜索,并将所得结果中较优的一条航迹作为模拟退火算法的初始解,实现了两种算法的融合.然后,当退火进行至低温区时,通过对位置存在冗余的航迹节点的剔除,进一步改善了算法的求解质量.最后为了验证算法的优越性,将本文算法与稀疏A^*算法、模拟退火算法进行了仿真对比试验.试验结果表明,本文提出的FSSA-SA算法相比于上述两种算法,具有较少的规划耗时;相比于稀疏A^*算法,在所得航迹的综合代价相差不大的情况下,内存占用量少了两个量级;相比与模拟退火算法,在相同的退火条件下,其规划所得航迹的综合代价平均减少了35%左右.     

基于A*算法的足球机器人路径规划

路径规划问题是足球机器人研究的一个重点. 以往的路径规划算法忽略了球员的移动对其周围区域产生的影响,导致实际所求得的最优安全路径并非那么安全. 为了解决这个问题,提出了一种对动态障碍物避障的A^*算法. 该方法根据带球球员以及对方防守球员的影响力对球场进行了区域划分,并为每个区域设置了风险值,再运用改进后的A^*算法规划路径. 实验结果表明,该方法能够有效减少带球球员被对方防守球员包围的可能性,并且综合考虑了路径的长度与安全性,规划出的路径性能更好.     

高密集度AGV快递包裹分拣系统的路径规划

基于自动引导小车（AGV）的快递包裹自动分拣系统是智能物流的研究热点,路径规划是其关键问题之一.在快递包裹分拣系统中,AGV具有高密集性和车辆数量较大的特点,这种情况极易造成AGV拥堵,使得整个系统的性能降低.针对此问题本文提出可避免拥挤的CAA^*（Congestion-avoidable A^*）算法,该算法以A^*算法为基础,引入动态属性节点,建立动态环境模型,对各个节点可能发生的拥挤情况进行预测,判断是否存在潜在的拥挤节点,在路径规划过程中绕过潜在的拥堵节点,避免发生拥堵现象.实验结果表明,本文所提的CAA^*路径规划方法在具有高密集度和较大规模的AGV场景中,能有效避免拥堵,从而提高场地AGV的密集度和系统的分拣效率.对实际应用场地的仿真表明,本文的算法比传统的A^*算法AGV密集度提高了28.57%,系统分拣效率提高了24.29%.     

The Number of Tree Stars Is <Emphasis Type="Italic">O</Emphasis><Superscript>*</Superscript>(1.357<Superscript><Emphasis Type="Italic">k</Emphasis></Superscript>)

Every rectilinear Steiner tree problem admits an optimal tree T ^* which is composed of tree stars. Moreover, the currently fastest algorithms for the rectilinear Steiner tree problem proceed by composing an optimum tree T ^* from tree star components in the cheapest way. The efficiency of such algorithms depends heavily on the number of tree stars (candidate components). Fößmeier and Kaufmann (Algorithmica 26, 68–99, 2000) showed that any problem instance with k terminals has a number of tree stars in between 1.32 ^k and 1.38 ^k (modulo polynomial factors) in the worst case. We determine the exact bound O ^*(ρ ^k ) where ρ≈1.357 and mention some consequences of this result.     

Solving Connected Dominating Set Faster than 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

In the connected dominating set problem we are given an n-node undirected graph, and we are asked to find a minimum cardinality connected subset S of nodes such that each node not in S is adjacent to some node in S. This problem is also equivalent to finding a spanning tree with maximum number of leaves. Despite its relevance in applications, the best known exact algorithm for the problem is the trivial Ω(2 ⁿ ) algorithm that enumerates all the subsets of nodes. This is not the case for the general (unconnected) version of the problem, for which much faster algorithms are available. Such a difference is not surprising, since connectivity is a global property, and non-local problems are typically much harder to solve exactly. In this paper we break the 2 ⁿ barrier, by presenting a simple O(1.9407 ⁿ ) algorithm for the connected dominating set problem. The algorithm makes use of new domination rules, and its analysis is based on the Measure and Conquer technique. An extended abstract of this paper appeared in the proceedings of FSTTCS’06. Fedor V. Fomin was additionally supported by the Research Council of Norway.     

On the strict logic foundation of fuzzy reasoning

This paper focuses on the logic foundation of fuzzy reasoning. At first, a new complete first-order fuzzy predicate calculus system K^* corresponding to the formal system L^* is built. Based on the many-sort system K_ms^* corresponding to K^*, the triple I methods of FMP and FMT for fuzzy reasoning and their consistency are formalized, thus fuzzy reasoning is put completely and rigorously into the logic framework of fuzzy logic.The author is indebted to anonymous referee for his useful comments which have helped to improve the paper.     

基于遗传算法的UAV自适应航迹规划

根据遗传算法与动态的稀疏A*搜索(Dynamic Sparse A*Search,DASA)算法各自的特点,提出一种组合优化算法来实现在不确定战场环境中自适应航迹规划.在无人机(UAV,Unmanned Aerial Vehicles)飞行前,采用全局搜索能力强的遗传算法进行全局搜索,对从起始点到目标点的飞行航线进行规划,生成全局最优或次优的可行参考飞行航线;在无人机任务执行阶段,以参考飞行航线为基准,采用DASA算法进行在线实时航迹再规划.仿真结果表明,与遗传算法相比,该组合算法不但能生成近似最优解,而且能够满足在线实时应用的要求.     

Tree Structure for Contractible Regions in ℝ<Superscript>3</Superscript>

For contractible regions ωin ℝ³ with generic smooth boundary, we determine the global structure of the Blum medial axis M. We give an algorithm for decomposing M into “irreducible components” which are attached to each other along “fin curves”. The attaching cannot be described by a tree structure as in the 2D case. However, a simplified but topologically equivalent medial structure ̂ M with the same irreducible components can be described by a two level tree structure. The top level describes the simplified form of the attaching, and the second level tree structure for each irreducible component specifies how to construct the component by attaching smooth medial sheets to the network of Y-branch curves. The conditions for these structures are complete in the sense that any region whose Blum medial axis satisfies the conditions is contractible.     

Microassembly path planning using reinforcement learning for improving positioning accuracy of a 1 cm<Superscript>3</Superscript> omni-directional mobile microrobot

This paper introduces the path planning of a 1 cm³ mobile microrobot that is designed for microassembly in a microfactory. Since the conventional path planning method can not achieve high microassembly positioning accuracy, a supervised learning assisted reinforcement learning (SL-RL) method has been developed. In this mixed learning method, the reinforcement learning (RL) is used to search a movement path in the normal learning area. But when the microrobot moves into the buffer area, the supervised learning (SL) is employed to prevent it from moving out of the boundary. The SL-RL uses a gradient descent algorithm based on uniform grid tile coding under SARSA(λ) to handle the large learning state space. In addition to the uniform grid tile model, two irregular tile models called an uneven grid tile model and a cobweb tile model are designed to partition the microrobot state space. The main conclusions demonstrated by simulations are as follows: First, the SL-RL method achieves higher positioning accuracy than the conventional path planning method; second, the SL-RL method achieves higher positioning accuracy and learning efficiency than the single RL method; and third, the irregular tile models show higher learning efficiency than the uniform tile model. The cobweb tile model performs especially well.     

A Framework for Evaluating Privacy Preserving Data Mining Algorithms<Superscript>*</Superscript>

Recently, a new class of data mining methods, known as privacy preserving data mining (PPDM) algorithms, has been developed by the research community working on security and knowledge discovery. The aim of these algorithms is the extraction of relevant knowledge from large amount of data, while protecting at the same time sensitive information. Several data mining techniques, incorporating privacy protection mechanisms, have been developed that allow one to hide sensitive itemsets or patterns, before the data mining process is executed. Privacy preserving classification methods, instead, prevent a miner from building a classifier which is able to predict sensitive data. Additionally, privacy preserving clustering techniques have been recently proposed, which distort sensitive numerical attributes, while preserving general features for clustering analysis. A crucial issue is to determine which ones among these privacy-preserving techniques better protect sensitive information. However, this is not the only criteria with respect to which these algorithms can be evaluated. It is also important to assess the quality of the data resulting from the modifications applied by each algorithm, as well as the performance of the algorithms. There is thus the need of identifying a comprehensive set of criteria with respect to which to assess the existing PPDM algorithms and determine which algorithm meets specific requirements. In this paper, we present a first evaluation framework for estimating and comparing different kinds of PPDM algorithms. Then, we apply our criteria to a specific set of algorithms and discuss the evaluation results we obtain. Finally, some considerations about future work and promising directions in the context of privacy preservation in data mining are discussed. ^*The work reported in this paper has been partially supported by the EU under the IST Project CODMINE and by the Sponsors of CERIAS. Editor:  Geoff Webb

---

Panconnectivity and edge-pancyclicity of 3-ary <Emphasis Type="Italic">N</Emphasis>-cubes

We study two topological properties of the 3-ary n-cube Q _n ³. Given two arbitrary distinct nodes x and y in Q _n ³, we prove that there exists an x–y path of every length ranging from d(x,y) to 3 ⁿ −1, where d(x,y) is the length of a shortest path between x and y. Based on this result, we prove that Q _n ³ is edge-pancyclic by showing that every edge in Q _n ³ lies on a cycle of every length ranging from 3 to 3 ⁿ .

Finding a Minimum-depth Embedding of a Planar Graph in <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>4</Superscript>) Time

Consider an n-vertex planar graph G. The depth of an embedding Γ of G is the maximum distance of its internal faces from the external one. Several researchers pointed out that the quality of a planar embedding can be measured in terms of its depth. We present an O(n ⁴)-time algorithm for computing an embedding of G with minimum depth. This bound improves on the best previous bound by an O(nlog n) factor. As a side effect, our algorithm improves the bounds of several algorithms that require the computation of a minimum-depth embedding.     

基于柱状空间和改进A*算法的无人机规避方法

针对无人机避障问题,提出了基于改进A~*算法和柱状空间的无人机规避方法。首先,根据无人机飞行区域的障碍物分布情况,建立飞行区域的柱状空间;然后将障碍物对无人机的影响引入到估价函数中,重新设计启发函数;最后将基于柱状空间和改进A~*算法的无人机规避方法应用于无人机的规避中,并对规划的路径进行平滑处理。仿真结果表明,该算法能够有效地实现无人机的规避。     

An O(2<Superscript>O(k)</Superscript>n<Superscript>3</Superscript>) FPT Algorithm for the Undirected Feedback Vertex Set Problem

We describe an algorithm for the Feedback Vertex Set problem on undirected graphs, parameterized by the size k of the feedback vertex set, that runs in time O(c^kn³) where c = 10.567 and n is the number of vertices in the graph. The best previous algorithms were based on the method of bounded search trees, branching on short cycles. The best previous running time of an FPT algorithm for this problem, due to Raman, Saurabh and Subramanian, has a parameter function of the form 2^{O(k log k /log log k)}. Whether an exponentially linear in k FPT algorithm for this problem is possible has been previously noted as a significant challenge. Our algorithm is based on the new FPT technique of iterative compression. Our result holds for a more general form of the problem, where a subset of the vertices may be marked as forbidden to belong to the feedback set. We also establish "exponential optimality" for our algorithm by proving that no FPT algorithm with a parameter function of the form O(2^o(k)) is possible, unless there is an unlikely collapse of parameterized complexity classes, namely FPT = M[1].     

一种基于A*算法的虚拟力场避障导航算法

针对传统A＊算法在实际应用中需要所有的节点信息,算法忽略车身实际宽度的问题,提出了基于A＊算法同时结合使用虚拟力场法的避障导航算法。该改进算法解决了 A＊算法在实际应用中存在的问题,也避免了单独使用虚拟力场法存在的容易陷入局部极小点、在目标点附近有障碍物时无法到达以及摆动剧烈的问题。仿真实验验证了新算法的有效性,实验结果表明该算法拓宽了原有算法的使用范围并且提高了无人车实时路径导航的能力。     

Augmenting the Rigidity of a Graph in <Emphasis Type="Italic">R</Emphasis><Superscript>2</Superscript>

Given a Laman graph G, i.e. a minimally rigid graph in R ², we provide a Θ(n ²) algorithm to augment G to a redundantly rigid graph, by adding a minimum number of edges. Moreover, we prove that this problem of augmenting is NP-hard for an arbitrary rigid graph G in R ².     

Reactive Local Search for the Maximum Clique Problem<Superscript><Emphasis Type="Italic">1</Emphasis></Superscript>

A new Reactive Local Search (\RLS ) algorithm is proposed for the solution of the Maximum-Clique problem. \RLS is based on local search complemented by a feedback (history-sensitive) scheme to determine the amount of diversification. The reaction acts on the single parameter that decides the temporary prohibition of selected moves in the neighborhood, in a manner inspired by Tabu Search. The performance obtained in computational tests appears to be significantly better with respect to all algorithms tested at the the second DIMACS implementation challenge. The worst-case complexity per iteration of the algorithm is O(max {n,m}) where n and m are the number of nodes and edges of the graph. In practice, when a vertex is moved, the number of operations tends to be proportional to its number of missing edges and therefore the iterations are particularly fast in dense graphs. Received September 11, 1997; revised February 5, 1998.     

Fault Identification in System-Level Diagnosis: a Logic-Based Framework and an <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>2</Superscript>\sqrt{τ}/{\log <Emphasis Type="Italic">n</Emphasis>}) Algorithm

Much research has been devoted to system-level diagnosis—SLD. Two issues have been addressed. The first of these is diagnosability, i.e., provide necessary and sufficient conditions for a system of n units to be diagnosable provided that the number of faulty units does not exceed τ . The second is the design of fault identification algorithms, assuming that the system being considered is diagnosable. This paper focuses on the second of these concerns, discussing several algorithms of which the most efficient runs in O(n ^2.5 ) . By considering a logical framework, this paper investigates the process of fault identification and proposes a fault identification algorithm which runs in O( n ² \sqrt τ / \sqrt log n ) , τ < n/2 . Received January 10, 2000; revised August 3, 2000.