A non-retraction path planning approach for extrusion-based additive manufacturing

Notwithstanding the widespread use and large number of advantages over traditional subtractive manufacturing techniques, the application of additive manufacturing technologies is currently limited by the undesirable fabricating efficiency, which has attracted attentions from a wide range of areas, such as fabrication method, material improvement, and algorithm optimization. As a critical step in the process planning of additive manufacturing, path planning plays a significant role in affecting the build time by means of determining the paths for the printing head's movement. So a novel path filling pattern for the deposition of extrusion–based additive manufacturing is developed in this paper, mainly to avoid the retraction during the deposition process, and hence the time moving along these retracting paths can be saved and the discontinuous deposition can be avoided as well. On the basis of analysis and discussion of the reason behind the occurrence of retraction in the deposition process, a path planning strategy called “go and back” is presented to avoid the retraction issue. The “go and back” strategy can be adopted to generate a continuous extruder path for simple areas with the start point being connected to the end point. So a sliced layer can be decomposed into several simple areas and the sub-paths for each area are generated based on the proposed strategy. All of these obtainable sub-paths can be connected into a continuous path with proper selection of the start point. By doing this, separated sub-paths are joined with each other to decrease the number of the startup and shutdown process for the extruder, which is beneficial for the enhancement of the deposition quality and the efficiency. Additionally, some methodologies are proposed to further optimize the generated non-retraction paths. At last, several cases are used to test and verify the developed methodology and the comparisons with conventional path filling patterns are conducted. The results show that the proposed approach can effectively reduce the retraction motions and is especially beneficial for the high efficient additive manufacturing without compromise on the part resistance.     

面向串扰时延效应的时序分析方法及在集成电路测试中的应用

随着特征尺寸进入纳米尺度,相邻连线之间的电容耦合对电路时序的影响越来越大,并可能使得电路在运行时失效.准确和快速地估计电路中的串扰效应影响,找到电路中潜在的串扰时延故障目标,并针对这些故障进行测试是非常必要的.文中提出了一种基于通路的考虑多串扰引起的时延效应的静态时序分析方法,该方法通过同时考虑临界通路及为其所有相关侵略线传播信号的子通路来分析多串扰耦合效应.该方法引入了新的数据结构"跳变图"来记录所有可能的信号跳变时间,能够精确地找到潜在的串扰噪声源,并在考虑串扰时延的情况下有效找到临界通路及引起其最大串扰减速效应的侵略子通路集.这种方法可以通过控制跳变图中时间槽的大小来平衡计算精度和运行时间.最后,文中介绍了在基于精确源串扰通路时延故障模型的测试技术中,该静态时序分析方法在耦合线对选择和故障敏化中的应用.针对ISCAS89电路的实验结果显示,文中提出的技术能够适应于大电路的串扰效应分析和测试,并且具有可接受的运行时间.     

Probabilistic Connections for Bidirectional Path Tracing

Bidirectional path tracing (BDPT) with Multiple Importance Sampling is one of the most versatile unbiased rendering algorithms today. BDPT repeatedly generates sub‐paths from the eye and the lights, which are connected for each pixel and then discarded. Unfortunately, many such bidirectional connections turn out to have low contribution to the solution. Our key observation is that we can importance sample connections to an eye sub‐path by considering multiple light sub‐paths at once and creating connections probabilistically. We do this by storing light paths, and estimating probability mass functions of the discrete set of possible connections to all light paths. This has two key advantages: we efficiently create connections with low variance by Monte Carlo sampling, and we reuse light paths across different eye paths. We also introduce a caching scheme by deriving an approximation to sub‐path contribution which avoids high‐dimensional path distance computations. Our approach builds on caching methods developed in the different context of VPLs. Our Probabilistic Connections for Bidirectional Path Tracing approach raises a major challenge, since reuse results in high variance due to correlation between paths. We analyze the problem of path correlation and derive a conservative upper bound of the variance, with computationally tractable sample weights. We present results of our method which shows significant improvement over previous unbiased global illumination methods, and evaluate our algorithmic choices.     

Spectral Mollification for Bidirectional Fluorescence

Fluorescent materials can shift energy between wavelengths, thereby creating bright and saturated colors both in natural and artificial materials. However, rendering fluorescence for continuous wavelengths or combined with wavelength dependent path configurations so far has only been feasible using spectral unidirectional methods. We present a regularization-based approach for supporting fluorescence in a spectral bidirectional path tracer. Our algorithm samples camera and light sub-paths with independent wavelengths, and when connecting them mollifies the BSDF at one of the connecting vertices such that it reradiates light across multiple wavelengths. We discuss arising issues such as color bias in early iterations, consistency of the method and MIS weights in the presence of spectral mollification. We demonstrate our method in scenes combining fluorescence and transport phenomena that are difficult to render with unidirectional or spectrally discrete methods.     

Stratified Markov Chain Monte Carlo Light Transport

Markov chain Monte Carlo (MCMC) sampling is a powerful approach to generate samples from an arbitrary distribution. The application to light transport simulation allows us to efficiently handle complex light transport such as highly occluded scenes. Since light transport paths in MCMC methods are sampled according to the path contributions over the sampling domain covering the whole image, bright pixels receive more samples than dark pixels to represent differences in the brightness. This variation in the number of samples per pixel is a fundamental property of MCMC methods. This property often leads to uneven convergence over the image, which is a notorious and fundamental issue of any MCMC method to date. We present a novel stratification method of MCMC light transport methods. Our stratification method, for the first time, breaks the fundamental limitation that the number of samples per pixel is uncontrollable. Our method guarantees that every pixel receives a specified number of samples by running a single Markov chain per pixel. We rely on the fact that different MCMC processes should converge to the same result when the sampling domain and the integrand are the same. We thus subdivide an image into multiple overlapping tiles associated with each pixel, run an independent MCMC process in each of them, and then align all of the tiles such that overlapping regions match. This can be formulated as an optimization problem similar to the reconstruction step for gradient-domain rendering. Further, our method can exploit the coherency of integrands among neighboring pixels via coherent Markov chains and replica exchange. Images rendered with our method exhibit much more predictable convergence compared to existing MCMC methods.     

ALGORITHMIC CHALLENGES IN LEARNING PATH METRICS FROM OBSERVED CHOICES

In many systems it is an essential part of the operation to find optimal paths in large graphs. In order to understand the system, we need to know the path metric under which the optimal paths are chosen. In many cases, however, no explicite knowledge of the metric is available, we can only observe the path choices that are made. Our goal is to learn the unknown metric, as accurately as possible, from the observed path choices. We present a mathematical model and method to handle this problem. Our main result is that the unknonw path metric can be optimally learned by a polynomial time algorithm, if we assume an additive (but unknown) metric over the graph edges. We also consider the case when the path metric is general, that is, not necessarily additive.     

软件测试路径选择优化模型及其进化求解

路径测试是一种非常重要且应用广泛的结构测试方法, 已有路径生成方法的测试效率不高、测试开销较大, 且易生成冗余测试路径. 针对以上问题, 主要研究路径选择问题的优化模型及其进化求解方法, 目的在于: 在不降低测试覆盖率的前提下, 减少冗余路径的数量, 降低测试消耗. 首先, 以多条路径作为决策变量, 基于该决策变量包含的边数和路径数, 建立多目标优化模型; 然后, 采用多目标进化算法求解该模型, 得到目标路径集. 将所提方法应用于7个基准测试程序, 并与其他算法比较. 实验结果表明, 相比其他算法, 所提方法能够在保证测试充分性的条件下, 降低测试消耗, 从而提高测试效率.     

从Web日志中挖掘用户浏览偏爱路径

Web日志中包含了大量的用户浏览信息，如何有效地从其中挖掘出用户浏览兴趣模式是一个重要的研究课题．作者在分析目前用户浏览模式挖掘算法存在的问题的基础上，利用提出的支持一偏爱度的概念，设计了网站访问矩阵，并基于这个矩阵提出了用户浏览偏爱路径挖掘算法：先利用Web日志建立以引用网页URL为行、浏览网页URL为列、路径访问频度为元素值的网站访问矩阵．该矩阵为稀疏矩阵，将该矩阵用三元组法来进行表示．然后，通过对该矩阵进行支持一偏爱度计算得到偏爱子路径．最后进行合并生成浏览偏爱路径．实验表明该算法能准确地反映用户浏览兴趣，而且系统可扩展性较好．这可以应用于电子商务网站的站点优化和个性化服务等．     

Skeleton based Vertex Connection Resampling for Bidirectional Path Tracing

Bidirectional path tracing is known to perform poorly for the rendering of highly occluded scenes. Indeed, the connection strategy between light and eye subpaths does not take into account the visibility factor, presenting no contribution for many sampled paths. To improve the efficiency of bidirectional path tracing, we propose a new method for adaptive resampling of connections between light and eye subpaths. Aiming for this objective, we build discrete probability distributions of light subpaths based on a skeleton of the empty space of the scene. In order to demonstrate the efficiency of our algorithm, we compare our method to both standard bidirectional path tracing and a recent important caching method.     

结构测试中的可达路径选择方法

在简单介绍了传统的不可达路径的排除方法后，主要介绍能有效改善其缺陷的可达路径选择方法，基于最少谓词思想的路径生成方法得到广泛的认可，但其实现方法的不同同样会影响路径的可达效果，文中介绍的综合利用控制流信息和数据流信息的方法较之单纯地利用控制流或数据流信息会生成更好的路径。     

基于时间窗的改进两阶段AGV路径规划研究

针对自动导引车(AGV)在仓储物流搬运系统中的路径冲突问题,提出了一种基于时间窗的改进两阶段动态路径规划方法.对原有两阶段路径规划方法进行改进,在离线情况下,将时间窗原理和Di-jkstra算法相结合,顺序规划出各个AGV的路径,采用改变AGV优先级的方法在线进行路径动态规划.通过仿真实验证明了改进后算法可以减少冲突的概率,有效地避免了AGV之间的碰撞,不仅具有很好的鲁棒性和柔性,而且可以提高系统效率.     

多无人机协同航路规划的共同进化方法

面向多无人机协同作战的航路设计问题,提出了一种较新颖的多无人机协同航路规划共同进化方法.将航路映射到进化计算个体建立了基于共同进化计算的航路规划问题模型,以此为基础重点讨论了个体适应度设计等关键问题.以SEAD任务为想定,对多无人机协同航路规划共同进化方法进行了仿真.仿真结果表明该方法能够快速为多无人机找到协同航路,能够综合考虑无人机航路的燃油、安全、避碰以及任务协同等指标,可以解决多无人机协同执行任务的航路设计问题,且具有较好的收敛性和线性时间性.     

Transient chaotic neural network-based disjoint multipath routing for mobile ad-hoc networks

Due to mobility of wireless hosts, routing in mobile ad-hoc networks (MANETs) is a challenging task. Multipath routing is employed to provide reliable communication, load balancing, and improving quality of service of MANETs. Multiple paths are selected to be node-disjoint or link-disjoint to improve transmission reliability. However, selecting an optimal disjoint multipath set is an NP-complete problem. Neural networks are powerful tools for a wide variety of combinatorial optimization problems. In this study, a transient chaotic neural network (TCNN) is presented as multipath routing algorithm in MANETs. Each node in the network can be equipped with a neural network, and all the network nodes can be trained and used to obtain optimal or sub-optimal high reliable disjoint paths. This algorithm can find both node-disjoint and link-disjoint paths with no extra overhead. The simulation results show that the proposed method can find the high reliable disjoint path set in MANETs. In this paper, the performance of the proposed algorithm is compared to the shortest path algorithm, disjoint path set selection protocol algorithm, and Hopfield neural network (HNN)-based model. Experimental results show that the disjoint path set reliability of the proposed algorithm is up to 4.5 times more than the shortest path reliability. Also, the proposed algorithm has better performance in both reliability and the number of paths and shows up to 56% improvement in path set reliability and up to 20% improvement in the number of paths in the path set. The proposed TCNN-based algorithm also selects more reliable paths as compared to HNN-based algorithm in less number of iterations.     

Dense Reconstruction of Transparent Objects by Altering Incident Light Paths Through Refraction

This paper addresses the problem of reconstructing the surface shape of transparent objects. The difficulty of this problem originates from the viewpoint dependent appearance of a transparent object, which quickly makes reconstruction methods tailored for diffuse surfaces fail disgracefully. In this paper, we introduce a fixed viewpoint approach to dense surface reconstruction of transparent objects based on refraction of light. We present a simple setup that allows us to alter the incident light paths before light rays enter the object by immersing the object partially in a liquid, and develop a method for recovering the object surface through reconstructing and triangulating such incident light paths. Our proposed approach does not need to model the complex interactions of light as it travels through the object, neither does it assume any parametric form for the object shape nor the exact number of refractions and reflections taken place along the light paths. It can therefore handle transparent objects with a relatively complex shape and structure, with unknown and inhomogeneous refractive index. We also show that for thin transparent objects, our proposed acquisition setup can be further simplified by adopting a single refraction approximation. Experimental results on both synthetic and real data demonstrate the feasibility and accuracy of our proposed approach.     

An Integrated Path and Timing Analysis Method based on Cycle-Level Symbolic Execution

Previously published methods for estimation of the worst-case execution time on high-performance processors with complex pipelines and multi-level memory hierarchies result in overestimations owing to insufficient path and/or timing analysis. This does not only give rise to poor utilization of processing resources but also reduces the schedulability in real-time systems. This paper presents a method that integrates path and timing analysis to accurately predict the worst-case execution time for real-time programs on high-performance processors. The unique feature of the method is that it extends cycle-level architectural simulation techniques to enable symbolic execution with unknown input data values; it uses alternative instruction semantics to handle unknown operands. We show that the method can exclude many infeasible (or non-executable) program paths and can calculate path information, such as bounds on number of loop iterations, without the need for manual annotations of programs. Moreover, the method is shown to accurately analyze timing properties of complex features in high-performance processors using multiple-issue pipelines and instruction and data caches. The combined path and timing analysis capability is shown to derive exact estimates of the worst-case execution time for six out of seven programs in our benchmark suite.     

均匀参与介质的渲染方法研究

参与介质在现实世界中广泛存在,光线在参与介质中的传播过程比在表面上的传播过程更加复杂,比如在高度散射参与介质中会发生成千上万次反射、在低散射参与介质中由于表面聚集出现体焦散效果,从而使得光线的模拟过程非常耗时。目前常用的方法包括点、光束和路径统一模型法（unifying points,beams and paths,UPBP）以及流型探索梅特罗波利斯光线传递方法（manifold exploration Metropolis light transport,MEMLT）等,这些方法在一定程度上改进了原有方法,但是在一些特殊情况下仍然需要很长时间才能收敛。本文介绍几种针对均匀参与介质的高效渲染方法。1）基于点的参与介质渲染方法,主要通过在参与介质内分布一些点来分别加速单次、二次和多次散射的计算,在GPU （graphics processing unit）实现的基础上,最终达到可交互的效率,并且支持对任意的均匀参与介质的编辑。2）基于多次反射的预计算模型,预计算出无限参与介质中的多次散射分布,通过分析光照分布的对称性,将该分布的维度从4维减低为3维,并且将该分布应用到多种蒙特卡洛渲染方法中,比如MEMLT、UPBP等,从而提高效率。3）参与介质中的路径指导方法,通过学习光线在参与介质中的分布,该分布用SD-tree （spatial-directional tree）来表示,与相位函数进行重采样来产生出射方向。以上3种方法分别从不同角度加快了参与介质的渲染效率。     

基于Web数据挖掘的用户浏览兴趣路径研究

使用Web日志与用户浏览行为相结合的方式对用户浏览兴趣模式进行挖掘。分别建立以访问次数、平均到网页中字符数的访问时间和拉动滑动条次数为元素值的矩阵,通过对矩阵进行路径兴趣度的计算得到兴趣子路径,进行合并生成用户兴趣路径集。实例分析表明该算法是可行和有效的,对于电子商务网站的优化和实施个性化服务具有意义。     

Approximating Wardrop equilibria with finitely many agents

We present efficient algorithms for computing approximate Wardrop equilibria in a distributed and concurrent fashion. Our algorithms are exexuted by a finite number of agents each of which controls the flow of one commodity striving to balance the induced latency over all utilised paths. The set of allowed paths is represented by a DAG. Our algorithms are based on previous work on policies for infinite populations of agents. These policies achieve a convergence time which is independent of the underlying network and depends mildly on the latency functions. These policies can neither be applied to a finite set of agents nor can they be simulated directly due to the exponential number of paths. Our algorithms circumvent these problems by computing a randomised path decomposition in every communication round. Based on this decomposition, flow is shifted from overloaded to underloaded paths. This way, our algorithm can handle exponentially large path collections in polynomial time. Our algorithms are stateless, and the number of communication rounds depends polynomially on the approximation quality and is independent of the topology and size of the network. Supported by DFG grant Vo889/1–3 and by DFG through German excellence cluster UMIC at RWTH Aachen. Supported by the DFG GK/1298 “AlgoSyn”. Supported in part by the the EU within the 6th Framework Programme under contract 001907 (DELIS) and by DFG through German excellence cluster UMIC at RWTH Aachen. A preliminary version of this work has appeared in [14].     

A mapping-based approach to eliminating self-intersection of offset paths on mesh surfaces for CNC machining

Geometrically, a tool path can be generated by successively offsetting its adjacent path on the surface with a given path interval, which preferably starts from one of the surface boundaries or a primary curve. The key issues involved in offset path planning are the generation of raw offset paths and the elimination of the self-intersection of raw offset paths. Most researches available in this area are focused on how to generate the raw offset paths, however, the latter, especially how to eliminate the self-intersection of the offset paths on mesh surfaces, has not been sufficiently addressed. In this paper, a mapping-based approach to eliminating the self-intersection of offset paths is proposed for the CNC machining of mesh surfaces. The method first flattens the mesh surface onto a predefined plane by using a mesh mapping technique, and then taking the mapping as a guide, the offset paths are also naturally mapped onto the plane, from which those invalid self-intersection loops can be effectively identified and eliminated. To handle the issue of self-intersection for all types of offset path, a notion of local loop is introduced to detect and eliminate the invalid self-intersection loops. After that the planar paths are inversely mapped into the physical space and the final tool paths used for the machining of mesh surface are obtained. Meanwhile, in order to improve the kinematic and dynamic performance of the machine tool when machining along the generated offset paths, a method for rounding the sharp corners of tool paths, which result from the process of eliminating the self-intersection of raw offset paths, is also preliminarily investigated. Finally, the proposed method is validated by the results of simulations and machining experiments.     

重采样在微博机器人识别中的应用研究

随着微博机器人账户的不断增多,对其识别检测已成为当前数据挖掘领域的热点问题。已有的微博机器人识别研究多使用爬取搜集的相关数据,在小规模平衡分布的机器人与普通用户数据集上训练并验证算法模型, 在样本分布不平衡的真实情况下存在局限性。重采样是一种针对不平衡数据集分类的常用技术,为探究重采样对 相关监督学习机器人识别算法的影响,该文以微热点数据挖掘竞赛的真实数据为基础,提出一种结合重采样的微 博机器人识别框架,在5种不同采样方式的基础上使用多种评价指标,综合评估了7种监督学习算法在不平衡验 证集上的分类性能。实验结果表明,以往基于小规模平衡样本数据训练的模型在真实情况下的Recall有较大降低,而结合重采样的算法框架能够大幅提高机器人账户的识别率,其中使用 NearMiss欠采样会让算法的 Recall大幅提升,而使用 ADASYN 过采样会让算法的 G_mean有所提高。一般而言,微博用户的发布时间、发布地域以及 发布时间间隔等属性是区分正常用户和机器人的重要特征属性。重采样调整了机器学习算法所依赖的特征属性, 从而获得更好的预测性能。