Recursive formulations for multibody systems with frictional joints based on the interaction between bodies

In practice, the clearances of joints in a great number of mechanical systems are well under control. In these cases, some of the existing methods become unpractical because of the little differences in the order of magnitude between relative movements and computational errors. Assuming that the effects of impacts are negligible, we proved that both locations and forces of contacts in joints can be fully determined by parts of joint reaction forces. Based on this fact, a method particularly suited for multibody systems possessing frictional joints with tiny clearances is presented. In order to improve the efficiency of computation, recursive formulations are proposed based on the interactions between bodies. The proposed recursive formulations can improve the computation of joint reaction forces. With the methodology presented in this paper, not only the motion of bodies in a multibody system but also the details about the contacts in joints, such as forces of contacts and locations of contact points, can be obtained. Even with the assumption of impact free, the instants of possible impacts can be detected without relying upon any ambiguous parameters, as indicated by numerical examples in this paper.     

Vesicles and Amoebae: On Globally Constrained Shape Deformation

Modeling the deformation of shapes under constraints on both perimeter and area is a challenging task due to the highly nontrivial interaction between the need for flexible local rules for manipulating the boundary and the global constraints. We propose several methods to address this problem and generate “random walks” in the space of shapes obeying quite general possibly time varying constraints on their perimeter and area. Design of perimeter and area preserving deformations are an interesting and useful special case of this problem. The resulting deformation models are employed in annealing processes that evolve original shapes toward shapes that are optimal in terms of boundary bending-energy or other functionals. Furthermore, such models may find applications in the analysis of sequences of real images of deforming objects obeying global constraints as building blocks for registration and tracking algorithms.     

Lattice Boltzmann Model Based on the Rebuilding-Divergency Method for the Laplace Equation and the Poisson Equation

In this paper, a new lattice Boltzmann model based on the rebuilding-divergency method for the Poisson equation is proposed. In order to translate the Poisson equation into a conservation law equation, the source term and diffusion term are changed into divergence forms. By using the Chapman-Enskog expansion and the multi-scale time expansion, a series of partial differential equations in different time scales and several higher-order moments of equilibrium distribution functions are obtained. Thus, by rebuilding the divergence of the source and diffusion terms, the Laplace equation and the Poisson equation with the second accuracy of the truncation errors are recovered. In the numerical examples, we compare the numerical results of this scheme with those obtained by other classical method for the Green-Taylor vortex flow, numerical results agree well with the classical ones.     

Pivoting based manipulation by a humanoid robot

In this paper we address whole-body manipulation of bulky objects by a humanoid robot. We adopt a “pivoting” manipulation method that allows the humanoid to displace an object without lifting, but by the support of the ground contact. First, the small-time controllability of pivoting is demonstrated. On its basis, an algorithm for collision-free pivoting motion planning is established taking into account the naturalness of motion as nonholonomic constraints. Finally, we present a whole-body motion generation method by a humanoid robot, which is verified by experiments.     

On Hierarchical Diameter-Clustering and the Supplier Problem

Given a data set in a metric space, we study the problem of hierarchical clustering to minimize the maximum cluster diameter, and the hierarchical k-supplier problem with customers arriving online. We prove that two previously known algorithms for hierarchical clustering, one (offline) due to Dasgupta and Long and the other (online) due to Charikar, Chekuri, Feder and Motwani, output essentially the same result when points are considered in the same order. We show that the analyses of both algorithms are tight and exhibit a new lower bound for hierarchical clustering. Finally we present the first constant factor approximation algorithm for the online hierarchical k-supplier problem.     

A High Order Compact Scheme for the Pure-Streamfunction Formulation of the Navier-Stokes Equations

In this paper we continue the study, which was initiated in (Ben-Artzi et al. in Math. Model. Numer. Anal. 35(2):313–303, 2001; Fishelov et al. in Lecture Notes in Computer Science, vol. 2667, pp. 809–817, 2003; Ben-Artzi et al. in J. Comput. Phys. 205(2):640–664, 2005 and SIAM J. Numer. Anal. 44(5):1997–2024, 2006) of the numerical resolution of the pure streamfunction formulation of the time-dependent two-dimensional Navier-Stokes equation. Here we focus on enhancing our second-order scheme, introduced in the last three afore-mentioned articles, to fourth order accuracy. We construct fourth order approximations for the Laplacian, the biharmonic and the nonlinear convective operators. The scheme is compact (nine-point stencil) for the Laplacian and the biharmonic operators, which are both treated implicitly in the time-stepping scheme. The approximation of the convective term is compact in the no-leak boundary conditions case and is nearly compact (thirteen points stencil) in the case of general boundary conditions. However, we stress that in any case no unphysical boundary condition was applied to our scheme. Numerical results demonstrate that the fourth order accuracy is actually obtained for several test-cases.     

On the application of the minimum polynomial extrapolation method to incompressible flows with heat transfer

In this paper, the Minimum Polynomial Extrapolation method (MPE) is used to accelerate the convergence of the Characteristic–Based–Split (CBS) scheme for the numerical solution of steady state incompressible flows with heat transfer. The CBS scheme is a fractional step method for the solution of the Navier–Stokes equations while the MPE method is a vector extrapolation method which transforms the original sequence into another sequence converging to the same limit faster then the original one without the explicit knowledge of the sequence generator. The developed algorithm is tested on a two-dimensional benchmark problem (buoyancy–driven convection problem) where the Navier–Stokes equations are coupled with the temperature equation. The obtained results show the feature of the extrapolation procedure to the CBS scheme and the reduction of the computational time of the simulation.     

Lower Bounds for Kernelizations and Other Preprocessing Procedures

We first present a method to rule out the existence of parameter non-increasing polynomial kernelizations of parameterized problems under the hypothesis P≠NP. This method is applicable, for example, to the problem Sat parameterized by the number of variables of the input formula. Then we obtain further improvements of corresponding results in (Bodlaender et al. in Lecture Notes in Computer Science, vol. 5125, pp. 563–574, Springer, Berlin, 2008; Fortnow and Santhanam in Proceedings of the 40th ACM Symposium on the Theory of Computing (STOC’08), ACM, New York, pp. 133–142, 2008) by refining the central lemma of their proof method, a lemma due to Fortnow and Santhanam. In particular, assuming that the polynomial hierarchy does not collapse to its third level, we show that every parameterized problem with a “linear OR” and with NP-hard underlying classical problem does not have polynomial self-reductions that assign to every instance x with parameter k an instance y with |y|=k ^O(1)⋅|x|^1−ε (here ε is any given real number greater than zero). We give various applications of these results. On the structural side we prove several results clarifying the relationship between the different notions of preprocessing procedures, namely the various notions of kernelizations, self-reductions and compressions.     

Evaluation of gang scheduling performance and cost in a cloud computing system

Cloud Computing refers to the notion of outsourcing on-site available services, computational facilities, or data storage to an off-site, location-transparent centralized facility or “Cloud.” Gang Scheduling is an efficient job scheduling algorithm for time sharing, already applied in parallel and distributed systems. This paper studies the performance of a distributed Cloud Computing model, based on the Amazon Elastic Compute Cloud (EC2) architecture that implements a Gang Scheduling scheme. Our model utilizes the concept of Virtual Machines (or VMs) which act as the computational units of the system. Initially, the system includes no VMs, but depending on the computational needs of the jobs being serviced new VMs can be leased and later released dynamically. A simulation of the aforementioned model is used to study, analyze, and evaluate both the performance and the overall cost of two major gang scheduling algorithms. Results reveal that Gang Scheduling can be effectively applied in a Cloud Computing environment both performance-wise and cost-wise.     

A recursive genetic framework for evolutionary decision-making in problems with high dynamism

Communication and coordination are the main cores for reaching a constructive agreement among multi-agent systems (MASs). Dividing the overall performance of MAS to individual agents may lead to group learning as opposed to individual learning, which is one of the weak points of MASs. This paper proposes a recursive genetic framework for solving problems with high dynamism. In this framework, a combination of genetic algorithm and multi-agent capabilities is utilised to accelerate team learning and accurate credit assignment. The argumentation feature is used to accomplish agent learning and the negotiation features of MASs are used to achieve a credit assignment. The proposed framework is quite general and its recursive hierarchical structure could be extended. We have dedicated one special controlling module for increasing convergence time. Due to the complexity of blackjack, we have applied it as a possible test bed to evaluate the system’s performance. The learning rate of agents is measured as well as their credit assignment. The analysis of the obtained results led us to believe that our robust framework with the proposed negotiation operator is a promising methodology to solve similar problems in other areas with high dynamism.     

An Efficient Newton-Krylov Implementation of the Constrained Runs Scheme for Initializing on a Slow Manifold

The long-term dynamic behavior of many dynamical systems evolves on a low-dimensional, attracting, invariant slow manifold, which can be parameterized by only a few variables (“observables”). The explicit derivation of such a slow manifold (and thus, the reduction of the long-term system dynamics) is often extremely difficult or practically impossible. For this class of problems, the equation-free framework has been developed to enable performing coarse-grained computations, based on short full model simulations. Each full model simulation should be initialized so that the full model state is consistent with the values of the observables and close to the slow manifold. To compute such an initial full model state, a class of constrained runs functional iterations was proposed (Gear and Kevrekidis, J. Sci. Comput. 25(1), 17–28, 2005; Gear et al., SIAM J. Appl. Dyn. Syst. 4(3), 711–732, 2005). The schemes in this class only use the full model simulator and converge, under certain conditions, to an approximation of the desired state on the slow manifold. In this article, we develop an implementation of the constrained runs scheme that is based on a (preconditioned) Newton-Krylov method rather than on a simple functional iteration. The functional iteration and the Newton-Krylov method are compared in detail using a lattice Boltzmann model for one-dimensional reaction-diffusion as the full model simulator. Depending on the parameters of the lattice Boltzmann model, the functional iteration may converge slowly or even diverge. We show that both issues are largely resolved by using the Newton-Krylov method, especially when a coarse grid correction preconditioner is incorporated.     

Optimal and online preemptive scheduling on uniformly related machines

We consider the problem of preemptive scheduling on uniformly related machines. We present a semi-online algorithm which, if the optimal makespan is given in advance, produces an optimal schedule. Using the standard doubling technique, this yields a 4-competitive deterministic and an e≈2.71-competitive randomized online algorithm. In addition, it matches the performance of the previously known algorithms for the offline case, with a considerably simpler proof. Finally, we study the performance of greedy heuristics for the same problem.     

An Almost Quadratic Time Algorithm for Sparse Spliced Alignment

The sparse spliced alignment problem consists of finding a chain of zero or more exons from O(n) prescribed candidate exons of a DNA sequence of length O(n) that is most similar to a known related gene sequence of length n. This study improves the running time of the fastest known algorithm for this problem to date, which executes in O(n ^2.25) time, or very recently, in O(n ²log ² n) time, by proposing an O(n ²log n)-time algorithm.     

Biologically-inspired robot spatial cognition based on rat neurophysiological studies

This paper presents a robot architecture with spatial cognition and navigation capabilities that captures some properties of the rat brain structures involved in learning and memory. This architecture relies on the integration of kinesthetic and visual information derived from artificial landmarks, as well as on Hebbian learning, to build a holistic topological-metric spatial representation during exploration, and employs reinforcement learning by means of an Actor-Critic architecture to enable learning and unlearning of goal locations. From a robotics perspective, this work can be placed in the gap between mapping and map exploitation currently existent in the SLAM literature. The exploitation of the cognitive map allows the robot to recognize places already visited and to find a target from any given departure location, thus enabling goal-directed navigation. From a biological perspective, this study aims at initiating a contribution to experimental neuroscience by providing the system as a tool to test with robots hypotheses concerned with the underlying mechanisms of rats’ spatial cognition. Results from different experiments with a mobile AIBO robot inspired on classical spatial tasks with rats are described, and a comparative analysis is provided in reference to the reversal task devised by O’Keefe in 1983.     

Business process management with the user requirements notation

A number of recent initiatives in both academia and industry have sought to achieve improvements in e-businesses through the utilization of Business Process Management (BPM) methodologies and tools. However there are still some inadequacies that need to be addressed when it comes to achieving alignment between business goals and business processes. The User Requirements Notation (URN), recently standardized by ITU-T, has some unique features and capabilities beyond what is available in other notations that can help address alignment issues. In this paper, a URN-based framework and its supporting toolset are introduced which provide business process monitoring and performance management capabilities integrated across the BPM lifecycle. The framework extends the URN notation with Key Performance Indicators (KPIs) and other concepts to measure and align processes and goals. An example process for controlling access to a healthcare data warehouse is used to illustrate and evaluate the framework. Early results indicate the feasibility of the approach.     

A new model for the integrated vehicle-crew-rostering problem and a computational study on rosters

Operational planning within public transit companies has been extensively tackled but still remains a challenging area for operations research models and techniques. This phase of the planning process comprises vehicle-scheduling, crew-scheduling and rostering problems. In this paper, a new integer mathematical formulation to describe the integrated vehicle-crew-rostering problem is presented. The method proposed to obtain feasible solutions for this binary non-linear multi-objective optimization problem is a sequential algorithm considered within a preemptive goal programming framework that gives a higher priority to the integrated vehicle-crew-scheduling goal and a lower priority to the driver rostering goals. A heuristic approach is developed where the decision maker can choose from different vehicle-crew schedules and rosters, while respecting as much as possible management’s interests and drivers’ preferences. An application to real data of a Portuguese bus company shows the influence of vehicle-crew-scheduling optimization on rostering solutions.     

Improvement of Convergence to Steady State Solutions of Euler Equations with the WENO Schemes

The convergence to steady state solutions of the Euler equations for high order weighted essentially non-oscillatory (WENO) finite difference schemes with the Lax-Friedrichs flux splitting (Jiang and Shu, in J. Comput. Phys. 126:202–228, 1996) is investigated. Numerical evidence in Zhang and Shu (J. Sci. Comput. 31:273–305, 2007) indicates that there exist slight post-shock oscillations when we use high order WENO schemes to solve problems containing shock waves. Even though these oscillations are small in their magnitude and do not affect the “essentially non-oscillatory” property of the WENO schemes, they are indeed responsible for the numerical residue to hang at the truncation error level of the scheme instead of settling down to machine zero. Differently from the strategy adopted in Zhang and Shu (J. Sci. Comput. 31:273–305, 2007), in which a new smoothness indicator was introduced to facilitate convergence to steady states, in this paper we study the effect of the local characteristic decomposition on steady state convergence. Numerical tests indicate that the slight post-shock oscillation has a close relationship with the local characteristic decomposition process. When this process is based on an average Jacobian at the cell interface using the Roe average, as is the standard procedure for WENO schemes, such post-shock oscillation appears. If we instead use upwind-biased interpolation to approximate the physical variables including the velocity and enthalpy on the cell interface to compute the left and right eigenvectors of the Jacobian for the local characteristic decomposition, the slight post-shock oscillation can be removed or reduced significantly and the numerical residue settles down to lower values than other WENO schemes and can reach machine zero for many test cases. This new procedure is also effective for higher order WENO schemes and for WENO schemes with different smoothness indicators.     

Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats

Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n ⁵) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n ¹¹) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case. Part of work was done during a Z.-Z. Chen visit at City University of Hong Kong.     

Spherical Correlation of Visual Representations for 3D Model Retrieval

In recent years we have seen a tremendous growth in the amount of freely available 3D content, in part due to breakthroughs for 3D model design and acquisition. For example, advances in range sensor technology and design software have dramatically reduced the manual labor required to construct 3D models. As collections of 3D content continue to grow rapidly, the ability to perform fast and accurate retrieval from a database of models has become a necessity. At the core of this retrieval task is the fundamental challenge of defining and evaluating similarity between 3D shapes. Some effective methods dealing with this challenge consider similarity measures based on the visual appearance of models. While collections of rendered images are discriminative for retrieval tasks, such representations come with a few inherent limitations such as restrictions in the image viewpoint sampling and high computational costs. In this paper we present a novel algorithm for model similarity that addresses these issues. Our proposed method exploits techniques from spherical signal processing to efficiently evaluate a visual similarity measure between models. Extensive evaluations on multiple datasets are provided.     

Searching for Complex Human Activities with No Visual Examples

We describe a method of representing human activities that allows a collection of motions to be queried without examples, using a simple and effective query language. Our approach is based on units of activity at segments of the body, that can be composed across space and across the body to produce complex queries. The presence of search units is inferred automatically by tracking the body, lifting the tracks to 3D and comparing to models trained using motion capture data. Our models of short time scale limb behaviour are built using labelled motion capture set. We show results for a large range of queries applied to a collection of complex motion and activity. We compare with discriminative methods applied to tracker data; our method offers significantly improved performance. We show experimental evidence that our method is robust to view direction and is unaffected by some important changes of clothing.