自主吸尘机器人的研究现状

详细评述了自主吸尘机器人的研究特点和国内外的研究现状，分析了多传感器融合、环境建模、定位和路径规划等关键技术，指出了其中的难点和面临的问题．同时，探讨了自主吸尘机器人的发展趋势和未来的研究重点．     

并联机器人汉字球面雕刻刀路规划研究

目前，将并联机构应用于未来加工领域的研究已成为热点，并联机器人以其结构优势在高刚度、高强度和高精度等场合将得到广泛应用，但关于并联机器人在汉字雕刻领域的研究尚未展开。该文研究了并联机器人在球面雕刻汉字所遇到的若干问题，包括平面刀路向球面刀路的映射方法、圆弧插补及刀具姿态实时规划算法等，给出了算例并用实验室拥有的6—PURU并联机器人进行了验证，结果表明文中所提方法是有效和可行的，从而对扩大并联机器人的应用范围奠定了基础。     

On-line free-flight path optimization based on improved genetic algorithms

Free flight (FF) is the ideal strategy of current investigations on air traffic management systems, where an on-line flight path optimization algorithm is of top importance. This paper proposes an innovative algorithm with potential real-time properties for FF path optimization, by using an improved genetic algorithm (GA). Two kinds of mathematical models for the on-line flight path optimization problem are proposed to cover the near and far future applications. Several improvements are introduced to the GA to speed up its convergence as well as to improve performance. Simulation results show that the new algorithm is effective and has potential to solve the on-line FF path optimization problem in real time.     

Approximation Algorithms for Quickest Spanning Tree Problems

Let $G=(V,E)$ be an undirected multigraph with a special vertex ${\it root} \in V$, and where each edge $e \in E$ is endowed with a length $l(e) \geq 0$ and a capacity $c(e) > 0$. For a path $P$ that connects $u$ and $v$, the {\it transmission time} of $P$ is defined as $t(P)=\mbox{\large$\Sigma$}_{e \in P} l(e) + \max_{e \in P}\!{(1 / c(e))}$. For a spanning tree $T$, let $P_{u,v}^T$ be the unique $u$--$v$ path in $T$. The {\sc quickest radius spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max _{v \in V} t(P^T_{root,v})$ is minimized. In this paper we present a 2-approximation algorithm for this problem, and show that unless $P =NP$, there is no approximation algorithm with a performance guarantee of $2 - \epsilon$ for any $\epsilon >0$. The {\sc quickest diameter spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max_{u,v \in V} t(P^T_{u,v})$ is minimized. We present a ${3 \over 2}$-approximation to this problem, and prove that unless $P=NP$ there is no approximation algorithm with a performance guarantee of ${3 \over 2}-\epsilon$ for any $\epsilon >0$.     

A Branch-Checking Algorithm for All-Pairs Shortest Paths

We formulate and study an algorithm for all-pairs shortest paths in a network with $n $ nodes and $m $ arcs of positive length. Using the dynamic programming principle of optimality of subpaths the algorithm avoids redundant updates of distance labels. A shortest $v$--$w$ path, say $\langle v, r_{1} , r_{2} , \ldots , r_{k } = w \rangle$ with $k $ arcs ($k \geq 1$), is only then combined with an arc $(w,t) \in A$ to update the distance label of pair $v$--$t$, if $(w,t) $ is present on the shortest $r_{\ell } $--$ t$ path for each node $r_{\ell}$ $(\ell=k- 1 , k- 2, \ldots, 1) $. The algorithm extracts shortest paths in order of length from a data structure and builds two shortest path trees per node, an extra effort of $O(n^{2})$. This way it can execute efficiently only the aforementioned distance updates, by picking the arcs $(w,t)$ out of these trees. The time complexity order per distance update and path extraction is similar as in other algorithms. An implementation with a data structure of heaps is possible, but a bucket-type data structure may be more appropriate. The implied number of distance updates does not exceed $nm_{0}$ ($m_{0}$ being the total number of shortest path arcs), but is frequently much lower. In extreme cases the new algorithm applies $O(n^{2})$ distance updates, whereas known algorithms require $\Omega( n ^{3})$ updates. The algorithm is especially suited for undirected graphs; here the construction of one tree per node is sufficient and the computation times halve.     

一种改进的连续属性全局离散化算法

连续属性的离散化问题是粗糙集理论研究的一个重要内容,通过对一种局部离散化方法的改进,提出了全局的离散化算法。利用粗糙集理论,首先定义一致性的度量(辨别函数),修改了基于“最小描述长度准则”的离散化算法,实现了全局离散,弥补了前者引入不一致的缺陷;在保持数据一致性的前提下,进一步分析了离散中分割点的冗金并进行了约简。实验通过基于粗糙集的分类工具,在几组典型数据集上得到了预期的满意结果,验证了该算法的有效性。     

Research on Constructing Contours from Regular Terrain Grids Containing Invalid Data

A new method for constructing contours from complicated terrain elevation grids containing invalid data is put forward. By using this method, the topological consistency of contours in groups can be maintained effectively and the contours can be drawn smoothly based on boundaries pre-searching and local correction. An experimental example is given to demonstrate that the contours constructed by this method are of good quality.     

分层实体制造激光头切割路径的建模与优化

分层实体制造(LOM)技术中分层制造时间是由该层的切割速度与切割路径确定的，当切割工艺参数(如：切割功率、切割速度)确定之后，每一层制造的时间是由该层切割(扫描)路径确定的。因此优化切割(扫描)路径对提高成型效率有重要意义，而分层实体制造技术中激光切割路径优化的实质是空行程路径的优化。建立了切割路径空行程路径优化的数学模型。由于求解该模型的复杂性，采用了分级规划的两个分步算法：首先用改进的最近邻域算法求解轮廓边界线上的切割起点，然后当切割点确定后把路径优化问题归结为旅行售货员问题(TSP)，采用了高效的智能仿生算法一蚁群系统算法来求解。运行结果表明，该算法显著缩短了分层制造中的空行程，提高了快速原型制造的效率。     

共边排样件激光切割路径的规划

排样软件的应用使材料利用率得到了很大提高，然而后续切割软件若不能保证有效地切割零件、保证零件质量及提高生产率，则排样软件在材料利用率上获得的收益将丧失。基于图论学理论，建立了规则与非规则零件共边排样时激光切割路径规划的数学模型，给出了在充分考虑加工质量、加工效率、制造成本情况下的激光切割路径优化目标：打孔点最少以及切割中割嘴空行程最短。提出了满足激光切割工艺要求的三个切割路径优化算法：用于求解理想情况下共边切割路径优化问题的一个新的欧拉回路算法；基于奇度顶点完全图最小权最大匹配算法来求解一般情况下共边切割路径优化问题的算法；利用废料区域进一步减少打孔点的处理策略与求解算法。给出了各种算法的运行实例，验证了所提出的算法的有效性。     

一种新型的动态路由和波长分配综合算法

讨论了WDM光网中，在动态业务流量和有限范围波长变换情况下的动态路由和波长分配问题。基于Moone-Dijkstra算法，考虑到动态波长变换的可能和限制，提出了一种新型的、可实现动态最小代价路由和最佳虚波长通道的综合启发式算法(DMC-OVWP)。该算法对路由子问题和波长分配子问题既相互独立，又相互结合，优化了RWA。以中国教育和科研计算机网(CERNET)为拓扑背景，基于本算法进行了计算机仿真，并对实验结果进行了比较分析，证明本算法可充分利用网络信息获取较低的阻塞率。