Some experiments on the detection of three-dimensional motion of rigid objects in blocks world

The present paper describes some major steps in our experiment of a two-frame based approach analysis. Its application deals with 3-D time-varing scene analysis. The entire analysis process can be divided into several major steps. Here, we are concerned with four main steps: preprocessing, knowledge representation, features matching and motion estimation. The work is directly related to the problem encountered by researchers in machine intelligence area where a vision system is indispensable. For each step, experimental results are given to illustrate the performance of the algorithms of processing. Furthermore, the implemented algorithms provide somewhat versatility and flexibility in the sense that they can be applied to other tasks of scene analysis, such as: stereo vision, object recognition and dynamic scene segmentation since the problem in determining the movement of an object using successive images is similar in many ways to the problem met in optic flow analysis and stereopsis. Finally, it should be pointed out that a vision system can be easily built when combining all of these available algorithms.     

A Parallel Finite Element Method for 3D Two-Phase Moving Contact Line Problems in Complex Domains

Moving contact line problem plays an important role in fluid-fluid interface motion on solid surfaces. The problem can be described by a phase-field model consisting of the coupled Cahn–Hilliard and Navier–Stokes equations with the generalized Navier boundary condition (GNBC). Accurate simulation of the interface and contact line motion requires very fine meshes, and the computation in 3D is even more challenging. Thus, the use of high performance computers and scalable parallel algorithms are indispensable. In this paper, we generalize the GNBC to surfaces with complex geometry and introduce a finite element method on unstructured 3D meshes with a semi-implicit time integration scheme. A highly parallel solution strategy using different solvers for different components of the discretization is presented. More precisely, we apply a restricted additive Schwarz preconditioned GMRES method to solve the systems arising from implicit discretization of the Cahn–Hilliard equation and the velocity equation, and an algebraic multigrid preconditioned CG method to solve the pressure Poisson system. Numerical experiments show that the strategy is efficient and scalable for 3D problems with complex geometry and on a supercomputer with a large number of processors.     

Adaptive sampling for generalized probabilistic roadmaps

In this paper,an adaptive sampling strategy is presented for the generalized sampling-based motion planner,generalized probabilistic roadmap (GPRM).These planners are designed to account for stochastic...     

Solving problems with unilateral constraints by DAE methods

We study trajectories of mechanical systems with unilateral constraints under the additional assumption that always a given number of constraints is active. A reformulation as a problem with bilateral conditions yields a drastic reduction in the number of constraints, but in general, we are faced with regularity problems. We illustrate our approach in the special case of a dynamical rigid body contact problem. In particular, we present a regularization technique which leads to the definition of generalized solutions and a quite effective numerical method on the basis of algorithms for differential–algebraic systems. The results are applied to a wheel–rail contact problem of actual interest to railway engineers.     

Block-matching algorithm based on harmony search optimization for motion estimation

Motion estimation is one of the major problems in developing video coding applications. Among all motion estimation approaches, Block-matching (BM) algorithms are the most popular methods due to their effectiveness and simplicity for both software and hardware implementations. A BM approach assumes that the movement of pixels within a defined region of the current frame can be modeled as a translation of pixels contained in the previous frame. In this procedure, the motion vector is obtained by minimizing a certain matching metric that is produced for the current frame over a determined search window from the previous frame. Unfortunately, the evaluation of such matching measurement is computationally expensive and represents the most consuming operation in the BM process. Therefore, BM motion estimation can be viewed as an optimization problem whose goal is to find the best-matching block within a search space. The simplest available BM method is the Full Search Algorithm (FSA) which finds the most accurate motion vector through an exhaustive computation of all the elements of the search space. Recently, several fast BM algorithms have been proposed to reduce the search positions by calculating only a fixed subset of motion vectors despite lowering its accuracy. On the other hand, the Harmony Search (HS) algorithm is a population-based optimization method that is inspired by the music improvisation process in which a musician searches for harmony and continues to polish the pitches to obtain a better harmony. In this paper, a new BM algorithm that combines HS with a fitness approximation model is proposed. The approach uses motion vectors belonging to the search window as potential solutions. A fitness function evaluates the matching quality of each motion vector candidate. In order to save computational time, the approach incorporates a fitness calculation strategy to decide which motion vectors can be only estimated or actually evaluated. Guided by the values of such fitness calculation strategy, the set of motion vectors is evolved through HS operators until the best possible motion vector is identified. The proposed method has been compared to other BM algorithms in terms of velocity and coding quality. Experimental results demonstrate that the proposed algorithm exhibits the best balance between coding efficiency and computational complexity.     

A dynamic programming scheme with multidimensional step indexing

The classical dynamic programming scheme with computation for one sequence of steps is generalized to the case of several indexed sequences in which the solution at every step depends on the results found at preceding steps of each of these sequences. The Bellman equations are generalized and proved, the complexity of algorithms is estimated, computer-aided realization is described, and applied problems whose formalization leads to a dynamic programming problem with multidimensional step indexing are stated.     

Robust implementation of generalized impedance control for robot manipulators

Compliant manipulation requires the robot to follow a motion trajectory and to exert a force profile while making compliant contact with a dynamic environment. For this purpose, a generalized impedance in the task space consisting of a second-order function relating motion errors and interaction force errors is introduced such that force tracking can be achieved. Using variable structure model reaching control, the generalized impedance is realized in the presence of parametric uncertainties. The proposed control method is applied to a multi-d.o.f. robot for an assembly task of inserting a printed circuit board into an edge connector socket. It is suggested that an assembly strategy which involves a sequence of planned target generalized impedances can enable the task to be executed in a desirable manner. The effectiveness of this approach is illustrated through experiments by comparing the results with those obtained using a model-based control implementation.     

A Pseudo-Distance Algorithm for Collision Detection of Manipulators Using Convex-Plane-Polygons-based Representation

Robots have become indispensable parts for the industrial automated workshop. The distance calculation between the industrial robot and obstacles is a fundamental problem for the robotic collision-free motion control. But existing methods for this problem have the disadvantage that the accuracy and execution efficiency cannot be guaranteed at the same time. In this paper, a pseudo-distance algorithm is presented based on the convex-plane-polygons-based representation to solve this problem. In this algorithm, convex plane polygons (CPPs) and cylinders are utilized to represent obstacles and the manipulator, respectively. The spatial relationship between each CPP and each cylinder is discussed through defining condition parameters, and is divided into six conditions including three special conditions when the contact happens, and the other three conditions when there exists a certain distance between the CPP and the cylinder. The distance is modelled under different relations based on the theory of mathematics and geometry. The pseudo distance is determined through selecting the smallest value from distances between CPPs and cylinders. The numerical experiment is performed based on the proposed and two previous algorithms to estimate the shortest distance between an industrial robot and a groove-shape obstacle. And an application example is performed to show the significance of this work on the robotic motion control. Results indicate that the proposed algorithm is more efficient than previous algorithms under a certain precision requirement, and can be effectively applied in the robotic motion control.     

基于综合互信息的视觉SLAM主动探索

针对当前单目视觉同时定位与建图(SLAM)研究中基于互信息的主动探索方式存在忽略不同运动行为代价的缺陷,提出考虑运动代价的基于综合互信息的探索策略。运动行为的选择考虑摄像机平移一定距离、旋转一定角度所付出的代价,并根据不同类型的运动行为对路标匹配可靠性影响的大小为其设置相应的权重,然后选择单位代价下能够获得最大信息增益的行为。实验结果表明,基于这种探索策略的单目视觉SLAM可在不影响定位精度和实时性的情况下,科学地选择可行的运动行为,避免单纯追求信息收益的探索方式的不合理性。     

A cellular learning automata-based deployment strategy for mobile wireless sensor networks

One important problem which may arise in designing a deployment strategy for a wireless sensor network is how to deploy a specific number of sensor nodes throughout an unknown network area so that the covered section of the area is maximized. In a mobile sensor network, this problem can be addressed by first deploying sensor nodes randomly in some initial positions within the area of the network, and then letting sensor nodes to move around and find their best positions according to the positions of their neighboring nodes. The problem becomes more complicated if sensor nodes have no information about their positions or even their relative distances to each other. In this paper, we propose a cellular learning automata-based deployment strategy which guides the movements of sensor nodes within the area of the network without any sensor to know its position or its relative distance to other sensors. In the proposed algorithm, the learning automaton in each node in cooperation with the learning automata in the neighboring nodes controls the movements of the node in order to attain high coverage. Experimental results have shown that in noise-free environments, the proposed algorithm can compete with the existing algorithms such as PF, DSSA, IDCA, and VEC in terms of network coverage. It has also been shown that in noisy environments, where utilized location estimation techniques such as GPS-based devices and localization algorithms experience inaccuracies in their measurements, or the movements of sensor nodes are not perfect and follow a probabilistic motion model, the proposed algorithm outperforms the existing algorithms in terms of network coverage.     

Confidence interval estimation of partial area under curve based on combined biomarkers

In diagnostic studies, we often need to combine several markers to increase the diagnostic accuracy. This paper addresses the problem of confidence interval estimation of partial area under receiver-operating characteristic (ROC) curve for the combined marker based on the optimal linear combination proposed by Su and Liu (1993). The proposed approach is developed using the concepts of generalized inference. Numerical study demonstrates that the proposed approach generally can provide reasonable confidence intervals via a few straightforward simulation steps.     

A layered goal-oriented fuzzy motion planning strategy for mobile robot navigation.

Most conventional motion planning algorithms that are based on the model of the environment cannot perform well when dealing with the navigation problem for real-world mobile robots where the environment is unknown and can change dynamically. In this paper, a layered goal-oriented motion planning strategy using fuzzy logic is developed for a mobile robot navigating in an unknown environment. The information about the global goal and the long-range sensory data are used by the first layer of the planner to produce an intermediate goal, referred to as the way-point, that gives a favorable direction in terms of seeking the goal within the detected area. The second layer of the planner takes this way-point as a subgoal and, using short-range sensory data, guides the robot to reach the subgoal while avoiding collisions. The resulting path, connecting an initial point to a goal position, is similar to the path produced by the visibility graph motion planning method, but in this approach there is no assumption about the environment. Due to its simplicity and capability for real-time implementation, fuzzy logic has been used for the proposed motion planning strategy. The resulting navigation system is implemented on a real mobile robot, Koala, and tested in various environments. Experimental results are presented which demonstrate the effectiveness of the proposed fuzzy navigation system.     

Adaptive blocking in the QR factorization

On most high-performance architectures, data movement is slow compared to floating point (in particular, vector) performance. On these architectures block algorithms have been successful for matrix computations. By considering a matrix as a collection of submatrices (the so-called blocks), one naturally arrives at algorithms that require little data movement. The optimal blocking strategy, however, depends on the computing environment and on the problem parameters. On parallel machines, tradeoffs between individual floating point performance and overall system performance also come into play. Current approaches use fixed-width blocking strategies which are not optimal. This paper presents an adaptive blocking methodology for determining a good blocking strategy systematically. We demonstrate this technique on a block QR factorization routine on a distributed-memory machine. Using timing models for the high-level kernels of the algorithm, we can formulate in a recurrence relation a blocking strategy that avoids adding extra delays along the critical path of the algorithm. This recurrence relation predicts performance well since we base our timing models on observed data, not other simplistic measures. Experiments on the Intel iPSC/1 hypercube show that, in fact, the resulting blocking strategy is as good as any fixed-width blocking strategy, independent of problem size and the number of processors employed. So while we do not know the optimum fixed-width blocking strategy unless we rerun the same problem several times, adaptive blocking provides close to optimum performance in the first run. We also mention how adaptive blocking can result in performance portable code by automating the generation of the timing models.This work was partially performed when the author was a graduate student at Cornell University and was supported by the Office of Naval Research under contract N00014-83-K-0640 and by NSF contract DCR 86-02310. Support at Argonne was provided by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38. Computations were performed in part at the facilities of the Cornell Computational Optimization Project which is supported by the National Science Foundation under contract DMS 87-06133, at the Cornell National Supercomputer Facility, and at the Advanced Research Computing Facility at Argonne National Laboratory.     

基于背景配准的矿井危险区域视频目标检测算法

针对矿井危险区域视频监控视场背景复杂,难以实现视频目标精确提取的问题,提出了一种基于背景配准的视频目标检测算法。该算法实现步骤:提取SIFT特征点,计算特征点区域H-S光流矢量;通过区域运动特性分析提取出背景运动区域,对背景运动区域特征点做帧间匹配;计算仿射参数,配准差分后提取出精确的目标区域。实验结果表明,该算法能够去除前景目标特征点对背景配准的影响,可获得较为精确的目标区域。     

下肢康复机器人的自适应人机交互控制策略

针对康复机器人运动过程中的人机交互性问题,提出一种下肢康复机器人自适应人机交互控制策略.提取伸屈运动中下肢表面肌电信号（Surface electromyography,sEMG）和足底压力特征,分别用于表征下肢运动意图和人机交互力（Interaction force,IF）信息,建立基于sEMG-IF的人机交互信息融合模型,实现下肢康复机器人运动轨迹的在线规划;考虑主动康复运动过程中的人机交互作用,建立具有时变动态特性的人机系统动力学模型,设计间接模糊自适应控制器对期望轨迹进行跟踪控制,实现下肢康复机器人自适应人机交互控制.通过对5名被试者进行下肢康复机器人运动控制实验研究,验证所提方法的可行性和有效性.     

A Riccati-type algorithm for solving generalized Hermitian eigenvalue problems

The paper describes a heuristic algorithm for solving a generalized Hermitian eigenvalue problem fast. The algorithm searches a subspace for an approximate solution of the problem. If the approximate solution is unacceptable, the subspace is expanded to a larger one, and then, in the expanded subspace a possibly better approximated solution is computed. The algorithm iterates these two steps alternately. Thus, the speed of the convergence of the algorithm depends on how to generate a subspace. In this paper, we derive a Riccati equation whose solution can correct the approximate solution of a generalized Hermitian eigenvalue problem to the exact one. In other words, the solution of the eigenvalue problem can be found if a subspace is expanded by the solution of the Riccati equation. This is a feature the existing algorithms such as the Krylov subspace algorithm implemented in the MATLAB and the Jacobi–Davidson algorithm do not have. However, similar to solving the eigenvalue problem, solving the Riccati equation is time-consuming. We consider solving the Riccati equation with low accuracy and use its approximate solution to expand a subspace. The implementation of this heuristic algorithm is discussed so that the computational cost of the algorithm can be saved. Some experimental results show that the heuristic algorithm converges within fewer iterations and thus requires lesser computational time comparing with the existing algorithms.

     

Movement Planning in the Presence of Flows

This paper investigates the problem of time-optimum movement planning in two and three dimensions for a point robot which has bounded control velocity through a set of n polygonal regions of given translational flow velocities. This intriguing geometric problem has immediate applications to macro-scale motion planning for ships, submarines, and airplanes in the presence of significant flows of water or air. Also, it is a central motion planning problem for many of the meso-scale and micro-scale robots that have been constructed recently, that have environments with significant flows that affect their movement. In spite of these applications, there is very little literature on this problem, and prior work provided neither an upper bound on its computational complexity nor even a decision algorithm. It can easily be seen that an optimum path for the 2D version of this problem can consist of at least an exponential number of distinct segments through flow regions. We provide the first known computational complexity hardness result for the 3D version of this problem; we show the problem is PSPACE hard. We give the first known decision algorithm for the 2D flow path problem, but this decision algorithm has very high computational complexity. We also give the first known efficient approximation algorithms with bounded error.     

求解HP格点模型的最佳优先搜索算法

HP格点模型是目前预测蛋白质折叠结构的一种最简单和最流行的模型,该模型已被证明是NP完全问题。将问题的解空间组织成树型结构,利用启发式规则—k步探测法对结点的可能分支进行评估,采用最佳优先策略搜索解空间树。最后用最佳优先搜索算法(BF)对一组公认的算例进行了实算,计算结果表明,BF计算效率优于传统的遗传算法和Monte Carlo方法。     

Motion fairing using genetic algorithms

In this paper, we solve the motion smoothing problem using genetic algorithms. Smooth motion generation is essential in the computer animation and virtual reality area. The motion of a rigid body in general consists of translation and orientation. The former is described by a space curve in three-dimensional Euclidean space while the latter is represented by a curve in the unit quaternion space. By adopting the geometric approach, the smoothness of both translation data and orientation data is measured from the strain energy perspective and a nonlinear optimization problem is formulated that aims to minimize the weighted sum of the strain-energy and the sum of the squared errors. A hybrid algorithm that combines genetic algorithms and local search schemes is deployed to solve this optimization problem and the experiments show that both smoothness and shape preservation of the resulting motion can be achieved by the proposed algorithm.     

Block matching algorithm for motion estimation based on Artificial Bee Colony (ABC)

Block matching (BM) motion estimation plays a very important role in video coding. In a BM approach, image frames in a video sequence are divided into blocks. For each block in the current frame, the best matching block is identified inside a region of the previous frame, aiming to minimize the sum of absolute differences (SAD). Unfortunately, the SAD evaluation is computationally expensive and represents the most consuming operation in the BM process. Therefore, BM motion estimation can be approached as an optimization problem, where the goal is to find the best matching block within a search space. The simplest available BM method is the full search algorithm (FSA) which finds the most accurate motion vector through an exhaustive computation of SAD values for all elements of the search window. Recently, several fast BM algorithms have been proposed to reduce the number of SAD operations by calculating only a fixed subset of search locations at the price of poor accuracy. In this paper, a new algorithm based on Artificial Bee Colony (ABC) optimization is proposed to reduce the number of search locations in the BM process. In our algorithm, the computation of search locations is drastically reduced by considering a fitness calculation strategy which indicates when it is feasible to calculate or only estimate new search locations. Since the proposed algorithm does not consider any fixed search pattern or any other movement assumption as most of other BM approaches do, a high probability for finding the true minimum (accurate motion vector) is expected. Conducted simulations show that the proposed method achieves the best balance over other fast BM algorithms, in terms of both estimation accuracy and computational cost.