Search

This paper considers an assembly problem. Let there be two interlocking parts, only one of which may be cut into pieces. How many pieces should we cut the divisible part into to separate the parts using a sequence of rigid-body motions? In this initial exploration, we primarily consider 2-D polygonal parts. This paper presents an algorithm that computes a lower bound on the number of pieces that the divisible part must be cut into. This paper also presents a complete algorithm that constructs a set of cuts and a motion plan for disassembly, yielding an upper bound on the required number of pieces. Applications of the future extension of this paper to 3-D may include robot self-assembly, interlocking 3-D model design, search-and-rescue, packaging, and robotic surgery. Note to Practitioners—This paper presents an opposite problem of immobilization or caging. Given two interlocking parts, only one of which may be cut into pieces. How can we unimmobilize or uncage one from another? We explore this problem in two aspects: the lower bound and the upper bound on the number of pieces that the divisible part must be cut into. This paper is an early theoretical exploration of this problem. We verified our methods in a virtual 2-D environment instead of building physical structures. Extension of this paper to 3-D could have many applications, including robot self-assembly, 3-D fabrication model design, search-and-rescue, packaging, and robotic surgery. [ABSTRACT FROM AUTHOR]

In many applications, top-k query is an important operation to return a set of interesting points in a potentially huge data space. It is analyzed in this paper that the existing algorithms cannot process top- k query on massive data efficiently. This paper proposes a novel table-scan-based T2S algorithm to efficiently compute top-k results on massive data. T2S first constructs the presorted table, whose tuples are arranged in the order of the round-robin retrieval on the sorted lists. T2S maintains only fixed number of tuples to compute results. The early termination checking for T2S is presented in this paper, along with the analysis of scan depth. The selective retrieval is devised to skip the tuples in the presorted table which are not top-k results. The theoretical analysis proves that selective retrieval can reduce the number of the retrieved tuples significantly. The construction and incremental-update/batch-processing methods for the used structures are proposed in this paper. The extensive experimental results, conducted on synthetic and real-life data sets, show that T2S has a significant advantage over the existing algorithms. [ABSTRACT FROM AUTHOR]

This article discusses how a hybrid algorithm based on a genetic algorithm (GA) and linear programming helps minimize distribution costs for the Scandinavian pulp producer Sodra Cell. The GA considers a planner's perspective by defining an individual schedule as the sequences of routes for all ships in a fixed fleet. Because the GA operates on a pool of potential solutions, constantly adjusting them to better fit the requirements, it can suggest multiple solutions. Furthermore, it can serve as a core algorithm in a support system where one can apply small changes to the set of constraints without a cold start. Applying the GA to Sodra Cell's real-world case and comparing it to mixed-integer-programming approach revealed competitive results. INSET: Related Work in Genetic Algorithms..

Intra prediction algorithm used in High Efficiency Video Coding (HEVC) standard has very high computational complexity. Therefore, in this paper, a novel technique is proposed for reducing amount of computations performed by HEVC intra prediction algorithm and, therefore, reducing energy consumption of HEVC intra prediction hardware. The proposed technique significantly reduced the amount of computations performed by 4x4, 8x8, 16x16 and 32x32 luminance angular prediction modes. The proposed technique does not affect the PSNR and bit rate. In this paper, a low energy HEVC intra prediction hardware for 4x4, 8x8, 16x16 and 32x32 angular prediction modes is also designed and implemented using Verilog HDL. The proposed technique significantly reduced the energy consumption of the HEVC intra prediction hardware. Therefore, it can be used in portable consumer electronics products that require a real-time HEVC encoder. [ABSTRACT FROM PUBLISHER]

Home healthcare (HHC) is a service that dispatches caregivers to people in need of healthcare who live in the home. The task assignment and route generation for caregivers can be formulated as an extension of the well-known vehicle routing problem with time windows (VRPTW). Currently, the most successful exact algorithms for VRPTW are based on a framework combining column generation (CG) and branching. Although such methods could be successful for HHC routing and scheduling problem (HHCRSP) as well, fast approximate algorithms are appealing, especially for large problems. In an early version of this paper, we employed a heuristic distributed gossip algorithm to solve HHCRSP. In this paper, we integrate the gossip algorithm with a local solver based on CG, which makes it an effective algorithm for larger problem instances. As it will be shown with extensive numerical experiments, for large problem instances, gossip-CG performs better than the pure CG. Note to Practitioners—The task of routing and scheduling caregivers for HHC providers can be formulated as a mathematical problem that is theoretically challenging to solve to optimality for large-scale problems involving many clients and caregivers. Although extensive research and tools for tackling this problem already exist, in practice, even in developed countries, it is still common to rely on schedules generated manually by staff. What we present in this paper is the summary of our theoretical work on tackling such problems. The benefit of the framework that we propose, the CG-based gossip method, is that it can be preempted at any time if the staff requires to obtain a good schedule as soon as possible. If ample time is available, one can let our algorithm to run for a longer period of time to generate even shorter routes. [ABSTRACT FROM AUTHOR]

This work investigates energy-optimal motion planning for a class of multiaxis motion systems where the system dynamics are linear time-invariant and decoupled in each axis. Solving the problem in a reliable and efficient manner remains challenging owing to the presence of various constraints on control and states, nonconvexity in its cost function, and obstacles. This paper shows how the cost function can be convexified by considering the system dynamics, while decomposing decision variables to obtain a convex representation of collision avoidance constraints. With the convexified cost function and constraints, the original problem is decomposed into two quadratic programming (QP) problems. An alternating quadratic programming (AQP) algorithm is proposed to solve both the QP problems alternatingly and iteratively till convergence. Requiring an initial feasible trajectory as a guess, AQP necessarily converges to an energy-efficient solution that is homotopic to the initial guess. Under certain circumstances, AQP is guaranteed to produce a local optimum. Simulation demonstrates that AQP is computationally efficient and reliable while claiming comparable energy saving as the mixed-integer QP approach. Note to Practitioners—This paper presents an energy-optimal motion planning algorithm that can be easily implemented on a class of multiaxis motion systems. Main advantages of the proposed algorithm are: 1) it produces a trajectory resulting in lower but comparable energy efficiency as the global optimum; 2) it is guaranteed to provide an energy-efficient and constraint-compliant trajectory, and thus is reliable; 3) it requires a low computational load and can be deployed on a wide range of applications; and 4) its implementation is straightforward to any engineer with basic knowledge of numerical methods. [ABSTRACT FROM AUTHOR]

This paper addresses the issue of placing a simple polygon (upon translation and rotation) on an isometric triangular grid such that the polygon contains the maximum number of triangles in its closure. This solves the problem left open in two recent papers titled “On the problem of the automated design of large-scale robot skin” and “An improved algorithm for the automated design of large scale robot skin” published in the IEEE Transactions on Automation Science and Engineering . Based on the properties of the grid, an improved algorithm is also presented. We also present some experimental results describing the use of this algorithm. [ABSTRACT FROM AUTHOR]

Foreground moving object segmentation is a fundamental problem in many computer vision applications. As a solution for foreground segmentation, background modeling has been intensively studied over past years and many effective algorithms have been developed. However, accurate foreground segmentation is still a difficult problem. Currently, most of the algorithms work solely within the color space, in which the segmentation performance is prone to be degraded by a multitude of challenges, such as illumination changes, shadows, automatic camera adjustments, and color camouflage. RGB-D cameras are active visual sensors that provide depth measurements along with color images. We present in this paper an innovative background modeling method by using both the color and depth information from an RGB-D camera. The proposed method is evaluated using a public RGB-D data set. Various experiments confirm that our method is able to achieve superior performance compared with existing well-known methods. Note to Practitioners—This paper investigates background modeling for foreground segmentation with active perception. Recent RGB-D cameras that leverage the active perception technology have advanced many computer vision algorithms. In this paper, we develop a background modeling method to achieve superior performance by using an RGB-D camera instead of a color camera. Due to the use of the active sensing technology, the proposed method is characterized by its robustness to common challenges. Our method could be used for improving existing infrastructures, such as visual surveillance systems for parking spaces. Moreover, the simple design of our method allows it to be easily deployed on various computing platforms, which facilitates many practical applications that usually require embedded computing devices. However, our method cannot run real timely at the current status. We believe that it can be further improved using parallel programming techniques to meet the real-time requirement. [ABSTRACT FROM AUTHOR]

In this paper, we study a simplified affine motion model-based coding framework to overcome the limitation of a translational motion model and maintain low-computational complexity. The proposed framework mainly has three key contributions. First, we propose to reduce the number of affine motion parameters from 6 to 4. The proposed four-parameter affine motion model can not only handle most of the complex motions in natural videos, but also save the bits for two parameters. Second, to efficiently encode the affine motion parameters, we propose two motion prediction modes, i.e., an advanced affine motion vector prediction scheme combined with a gradient-based fast affine motion estimation algorithm and an affine model merge scheme, where the latter attempts to reuse the affine motion parameters (instead of the motion vectors) of neighboring blocks. Third, we propose two fast affine motion compensation algorithms. One is the one-step sub-pixel interpolation that reduces the computations of each interpolation. The other is the interpolation-precision-based adaptive block size motion compensation that performs motion compensation at the block level rather than the pixel level to reduce the number of interpolation. Our proposed techniques have been implemented based on the state-of-the-art high-efficiency video coding standard, and the experimental results show that the proposed techniques altogether achieve, on average, 11.1% and 19.3% bits saving for random access and low-delay configurations, respectively, on typical video sequences that have rich rotation or zooming motions. Meanwhile, the computational complexity increases of both the encoder and the decoder are within an acceptable range. [ABSTRACT FROM AUTHOR]

This paper presents a DC coefficient estimation algorithm for intra-predicted residual blocks in the High-Efficiency Video Coding (HEVC) standard. Discarding the DC coefficient directly in each transform block leads to substantial bit-saving, but at the same time produces strong discontinuities between neighboring blocks. To overcome this problem, we propose an estimation algorithm for the DC coefficient, which solves an optimal offset in a closed-form to recover the corresponding block edges. Then, we embed this algorithm into HEVC in its rate-distortion optimized quantization and sign bit hiding steps. Furthermore, a flag is signaled to decide whether the DC estimation strategy is used for each transform block. Test results under the common test condition show that our algorithm achieves 1.5% and 1.6% BD-rate reduction on average for luma and chroma, respectively, under all intra configuration. In the meantime, our simulation results show that both encoding time and decoding time increase only slightly (about 10%, without any special optimization on programming our proposed algorithm). When testing the proposed DC estimation algorithm on inter coding configurations, including low delay with P pictures, low delay with B pictures, and random access, we can also achieve 0.5%–1.1% bit-rate savings on average, while nearly no extra encoding and decoding time is needed. [ABSTRACT FROM AUTHOR]

We present a novel approach to perform probabilistic collision detection between a high-DOF robot and imperfect obstacle representations in dynamic and uncertain environments. Our formulation is designed for high-DOF robot trajectory planning in dynamic scenes, where the uncertainties are modeled using Gaussian distributions. We present an efficient algorithm to compute collision probabilities between the robot and the obstacles. Furthermore, we present a prediction algorithm for obstacle positions that takes into account spatial and temporal uncertainties and uses that for trajectory optimization. We highlight the performance of our trajectory planning algorithm in challenging simulated and real-world environments with robot arms operating next to dynamically moving human obstacles. Note to Practitioners—This paper suggests a novel trajectory planning approach for dynamic and uncertain environments. Existing planning approaches generally deal with uncertainties by performing collision checks using enlarged bounding shapes for the given confidence levels, which are conservative and tend to compute less optimal trajectories or fail to find feasible trajectories. In this paper, we suggest a new collision probability approximation of a robot and obstacles. Our approach guarantees that the computed probability is an upper bound on the actual probability. We then present a trajectory planning algorithm based on our probabilistic collision detection, and a practical belief space estimation algorithm. In our experimental results, we demonstrate that our approach can compute more efficient trajectories than the prior approaches, while our approach has a similar level of safety. Our experiments assume Gaussian distributions for the environment uncertainties, and we will extend our algorithm to non-Gaussian distributions in future research. Recently, we have extended our approach to general convex polytopes and improved the speed and accuracy of the collision probability computation using bounding volume hierarchies. [ABSTRACT FROM AUTHOR]

In this paper, we define a novel census signal temporal logic (CensusSTL) that focuses on the number of agents in different subsets of a group that complete a certain task specified by the STL. CensusSTL consists of an “inner logic” STL formula and an “outer logic” STL formula. We present a new inference algorithm to infer CensusSTL formulas from the trajectory data of a group of agents. We first identify the “inner logic” STL formula and then infer the subgroups based on whether the agents’ behaviors satisfy the “inner logic” formula at each time point. We use two different approaches to infer the subgroups based on similarity and complementarity, respectively. The “outer logic” CensusSTL formula is inferred from the census trajectories of different subgroups. We apply the algorithm in analyzing data from a soccer match by inferring the CensusSTL formula for different subgroups of a soccer team.

Note to Practitioners—The method described in this paper can be used to discover subgroups of agents and their behavior patterns based on spatial–temporal data of all agents in the group. The subgroups are formed by agents that behave similarly or complementarily for a certain task. The behavior patterns of the subgroups are expressed in the form of signal temporal logic statements. These are logical statements about the number of agents in the subgroups that are in certain states during a certain time interval. For example, if there are more than two blue agents in the region, then within 2 h, there will be more than three red agents in the same region. The behavior patterns inferred using this method can be used in: 1) analysis of group behavior while performing a task, e.g., in sports tactical analysis and 2) prediction of future group behavior under similar situations. [ABSTRACT FROM AUTHOR]

In dipole-antenna array signal-processing algorithm development, research has focused on “short dipoles” whose physical length ( $L$ ) is under (1/10) of a wavelength \lambda $ . Such electrically “short” dipoles have very small input impedances, rendering such “short” dipoles to be inefficient radiators. Practical dipoles, with an electrical length of ({L}/{\lambda }) \in [{0.1, 1}] , have notably larger input impedance, hence making them better radiators. Of such practical dipoles, this paper investigates their use for azimuth-polar direction finding and for polarization estimation. This paper will first present the measurement model (i.e., array manifold) of a triad of such practical dipoles, collocated in space and orthogonally oriented. This paper will then develop the corresponding closed-form algorithms to estimate the bivariate azimuth–elevation direction-of-arrival or the bivariate polarization. Such closed-form algorithms previously have been unavailable in the existing literature for such a triad of electrically “long” dipoles of pragmatic radiation efficiency. [ABSTRACT FROM AUTHOR]

Nuclear power plants (NPPs) are composed of very large complex systems. During transient occurrences in NPPs, operators determine the transients of the NPP through information acquired from various measuring instruments. A support vector machine (SVM) based on serial and parallel connections, termed as a multiconnected SVM, is introduced in this paper. The loss of coolant accidents (LOCAs) was identified and their break sizes are estimated using the multiconnected SVM model. The optimal parameter values of the multiconnected SVM models are obtained using a genetic algorithm. In this paper, the modular accident analysis program code was used to simulate the severe accidents occurring due to a variety of design basis accidents. The proposed algorithm uses the short time-integrated simulated sensor signals just after the reactor trip. The results show that the multiconnected SVM model can identify LOCAs and estimate their break sizes accurately. It is expected that the LOCA identification and the accurate estimation of the break size are useful for NPP operators when they try to manage severe accidents. [ABSTRACT FROM PUBLISHER]

Cryptographic architectures provide different security properties to sensitive usage models. However, unless reliability of architectures is guaranteed, such security properties can be undermined through natural or malicious faults. In this paper, two underlying block ciphers which can be used in authenticated encryption algorithms are considered, i.e., light encryption device and high security and lightweight block ciphers. The former is of the Advanced Encryption Standard type and has been considered area-efficient, while the latter constitutes a Feistel network structure and is suitable for low-complexity and low-power embedded security applications. In this paper, we propose efficient error detection architectures including variants of recomputing with encoded operands and signature-based schemes to detect both transient and permanent faults. Authenticated encryption is applied in cryptography to provide confidentiality, integrity, and authenticity simultaneously to the message sent in a communication channel. In this paper, we show that the proposed schemes are applicable to the case study of simple lightweight CFB for providing authenticated encryption with associated data. The error simulations are performed using Xilinx Integrated Synthesis Environment tool and the results are benchmarked for the Xilinx FPGA family Virtex-7 to assess the reliability capability and efficiency of the proposed architectures. [ABSTRACT FROM PUBLISHER]

This paper proposes a new reentry trajectory generation method, which mainly comprises two parts: reentry profile design and trajectory optimization. Different from conventional methods that design angle-of-attack (AOA) and bank-angle profiles, a height-range profile is proposed in this paper. Using this profile, the AOA can be directly derived and the quasi-equilibrium glide condition is easily satisfied. In addition, the bank angle is analytically derived with the heading error, with only one reversal. Finally, the original problem is transformed into a parameter optimization problem and solved by an improved particle swarm optimization (PSO) method. In PSO, a comparison principle is proposed to tackle constraints and three modifications are applied to the swarm evolution to enhance the searching capacity. To conquer disturbances, an online profile updating strategy is developed based on the nominal profile, so complicated work of designing a trajectory tracker is avoided. Simulation validates the effectiveness of the proposed method and demonstrates that the improved PSO is comparable to the pseudospectral method and is better than the basic PSO. [ABSTRACT FROM AUTHOR]

The goal of this paper is to localize a resident in indoor environments by using motion information from distributed environmental sensors and body activity information from wearable sensors. The passive infrared sensor nodes distributed in a home provide binary information about human motion in their field of views, while the wearable inertial measurement unit sensor node collects motion data that can be used in body activity recognition, walking velocity, and heading estimation. Basic human activities such as sitting, sleeping, standing, and walking are recognized. We proposed a particle filter-based sensor fusion algorithm that takes advantage of the human location/activity correlation in indoor environments to increase the localization accuracy. Experiments were conducted in a mock apartment testbed. We used the ground truth data obtained from a motion capture system to evaluate the results. Note to Practitioners—This paper is motivated by a goal to realize various home automation applications through human localization. For example, with the knowledge of human location, lighting, and air conditioning systems can be more efficiently managed, or a home service robot can provide better service to the resident. There currently lacks an accurate human localization method in indoor environments. The theoretical framework proposed in this paper aims to combine simple environmental sensors (passive infrared sensors) and a single wearable motion sensor to accurately track human locations. This method reduces the intrusiveness to the human, while keeping the cost of the infrastructure low. The theoretical framework has been tested and evaluated in a mock apartment environment as a proof of concept. For deployment into real homes, we need to conduct more realistic tests and thorough evaluation of the system. It is also necessary to reduce the size and weight of the wearable motion sensor and simplify the installation of the environmental sensors. [ABSTRACT FROM AUTHOR]

The prediction accuracy of the traditional kernel with data-driven regression methods strongly depends on the appropriate selection of the kernel function and aims at solving the nonlinearity of the input space. In this paper, a self-learning kernel regression model is proposed. A special kernel space from the measured data is learned and designed, so that combined with dimension reductions on the input variables, the regression behavior between the projected input variables and the output variable is found. The model is posed as a semidefinite programming problem with the objective function to find the maximum variance between the learned manifolds. The kernel is data dependent and can be generated online whenever a new data point is available. The effectiveness of the proposed algorithm is demonstrated through the case studies on a simple nonlinear system and a real semiconductor process. Note to Practitioners—Virtual sensing of quality/key variables is critical for the control and optimization of industrial processes. Traditional data-driven kernel regression methods cannot achieve guaranteed high prediction accuracy. This paper aims to develop a high-accuracy virtual sensor based on the self-learning kernel regression (SLKR) model, which simultaneously constructs the relationship between the input and the output data as well as represents the data in a low-dimensional manifold. For practical implementation, the following are necessary to: 1) select a historical data set with abundant information of the process; 2) preprocess industrial data well and eliminate irregular entries; 3) establish a self-learning regression kernel based on local manifold structure and regression relationship; 4) approximate the explicit data-dependent kernel function and determine suitable parameter; and 5) extract regression coefficients from the learned kernel matrix. [ABSTRACT FROM AUTHOR]

Rigid registration is a fundamental process in many applications that require alignment of different datasets. Iterative closest point (ICP) is a widely used algorithm that iteratively finds point correspondences and updates the rigid transformation. One of the key variants of ICP to its success is the selection of points, which is directly related to the convergence and robustness of the ICP algorithm. Besides uniform sampling, there are a number of normal-based and feature-based approaches that consider normal, curvature, and/or other signals in the point selection. Among them, normal-space sampling (NSS) is one of the most popular techniques due to its simplicity and low computational cost. The rationale of NSS is to sample enough constraints to determine all the components of transformation, but this paper finds that NSS actually can constrain the translational normal space only. This paper extends the fundamental idea of NSS and proposes Dual NSS (DNSS) to sample points in both translational and rotational normal spaces. Compared with NSS, this approach has similar simplicity and efficiency without any need of additional information, but has a much better effectiveness. Experimental results show that DNSS can outperform the normal-based and feature-based methods in terms of convergence and robustness. For example, DNSS can achieve convergence from an orthogonal initial position while no other methods can achieve. Note to Practitioners—ICP is commonly used to align different data to a same coordination system. While NSS is often used to speed up the alignment process by down-sampling the data uniformly in the normal space. The implementation of NSS only has three steps: 1) construct a set of buckets in the normal-space; 2) put all points of the data into buckets based on their normal direction; and 3) uniformly pick points from all the buckets until the desired number of points is selected. The algorithm is simple and fast, so that it is still the common practice. However, the weakness of NSS comes from the reason that it cannot handle rotational uncertainties. In this paper, a new algorithm called DNSS is developed to constrain both translation and rotation at the same time by introducing a dual-normal space. With a new definition of the normal space, the algorithm complexity of DNSS is the same as that of NSS, and it can be readily implemented in all types of application that are currently using ICP. The experimental results show that DNSS has better efficiency, quality, and reliability than both normal-based and feature-based methods have. [ABSTRACT FROM AUTHOR]

The 3-phase windings of interior permanent magnet synchronous machines (IPMSMs) used in electric vehicles (EVs) for traction can also be utilized for charging a battery. This integrated charging technology eliminates the on-board charger, leading to a significant reduction in the overall weight and cost of the EV. However, during integrated charging, the induced magnetic fields across the IPMSM windings are unbalanced, which could lead to addition of harmonic current components at the battery side, demagnetization, noise, and vibrations. This paper provides a novel design solution by implementing asymmetrical damper bars in the IPMSM rotor to mitigate unbalanced magnetic fields during integrated charging, and, thus, overcome the aforementioned issues. However, the bars introduced could affect the useful torque production of the machine during traction. Therefore, a magnetic equivalent circuit model based differential evolutionary algorithm is proposed and implemented to optimize the IPMSM rotor structure with dampers to achieve balanced magnetic fields during integrated charging operation and satisfactory traction performance. A comprehensive performance analysis of the optimally designed traction IPMSM equipped with integrated charging capability under both operating conditions is presented in this paper using finite element analysis. [ABSTRACT FROM AUTHOR]

The energy and cooling costs of Web server farms are among their main financial expenditures. This paper explores the benefits of dynamic voltage scaling (DVS) for power management in server farms. Unlike previous work, which addressed DVS on individual servers and on load-balanced server replicas, this paper addresses DVS in multistage service pipelines. Contemporary Web server installations typically adopt a three-tier architecture in which the first tier presents a Web interface, the second executes scripts that implement business logic, and the third serves database accesses. From a user's perspective, only the end-to-end response across the entire pipeline is relevant. This paper presents a rigorous optimization methodology and an algorithm for minimizing the total energy expenditure of the multistage pipeline subject to soft end-to-end response-time constraints. A distributed power management service is designed and evaluated on a real three-tier server prototype for coordinating DVS settings in a way that minimizes global energy consumption while meeting end-to-end delay constraints. The service is shown to consume as much as 30 percent less energy compared to the default (Linux) energy saving policy. [ABSTRACT FROM AUTHOR]

While the detection of the interesting regions in images has been extensively studied, relatively few papers have addressed surfaces. This paper proposes an algorithm for detecting the regions of interest of surfaces. It looks for regions that are distinct both locally and globally and accounts for the distance to the foci of attention. It is also shown how this algorithm can be adopted to saliency detection in point clouds. Many applications can utilize these regions. In this paper we explore one such application—viewpoint selection. The most informative views are those that collectively provide the most descriptive presentation of the surface. We show that our results compete favorably with the state-of-the-art results. [ABSTRACT FROM AUTHOR]

Recursion is one of the most difficult programming topics for students. In this paper, an instructional method is proposed to enhance students' understanding of recursion tracing. The proposal is based on the use of rules to translate linear recursion algorithms into equivalent, iterative ones. The paper has two main contributions: the instructional method itself, and its evaluation, which is based on previous works of other authors on mental models of recursion. As a result, an enhancement was measured in the viability of mental models exhibited by students (both for linear and multiple recursion), but no significant improvement was detected in their skills for designing recursive algorithms. Evidence was also obtained of the fact that many students with (relatively) viable mental models for linear recursion have unviable mental models for multiple recursion. Finally, it was noticed that many students adopt inaccurate mental models if those models are adequate to handle the given algorithm. [ABSTRACT FROM PUBLISHER]

Index coding studies multiterminal source-coding problems where a set of receivers are required to decode multiple (possibly different) messages from a common broadcast, and they each know some messages a priori. In this paper, at the receiver end, we consider a special setting where each receiver knows only one message a priori, and each message is known to only one receiver. At the broadcasting end, we consider a generalized setting where there could be multiple senders, and each sender knows a subset of the messages. The senders collaborate to transmit an index code. This paper looks at minimizing the number of total coded bits the senders are required to transmit. When there is only one sender, we propose a pruning algorithm to find a lower bound on the optimal (i.e., the shortest) index codelength, and show that it is achievable by linear index codes. When there are two or more senders, we propose an appending technique to be used in conjunction with the pruning technique to give a lower bound on the optimal index codelength; we also derive an upper bound based on cyclic codes. While the two bounds do not match in general, for the special case where no two distinct senders know any message in common, the bounds match, giving the optimal index codelength. The results are expressed in terms of strongly connected components in directed graphs that represent the index-coding problems. [ABSTRACT FROM AUTHOR]

This paper studies the problem of detecting the information source in a network in which the spread of information follows the popular Susceptible-Infected-Recovered (SIR) model. We assume all nodes in the network are in the susceptible state initially, except one single information source that is in the infected state. Susceptible nodes may then be infected by infected nodes, and infected nodes may recover and will not be infected again after recovery. Given a snapshot of the network, from which we know the graph topology and all infected nodes but cannot distinguish susceptible nodes and recovered nodes, the problem is to find the information source based on the snapshot and the network topology. We develop a sample-path-based approach where the estimator of the information source is chosen to be the root node associated with the sample path that most likely leads to the observed snapshot. We prove for infinite-trees, the estimator is a node that minimizes the maximum distance to the infected nodes. A reverse-infection algorithm is proposed to find such an estimator in general graphs. We prove that for g+1-regular trees such that gq>1, where g+1 is the node degree and q is the infection probability, the estimator is within a constant distance from the actual source with a high probability, independent of the number of infected nodes and the time the snapshot is taken. Our simulation results show that for tree networks, the estimator produced by the reverse-infection algorithm is closer to the actual source than the one identified by the closeness centrality heuristic. We then further evaluate the performance of the reverse infection algorithm on several real-world networks. [ABSTRACT FROM AUTHOR]

Downsampling and the computation of the bandlimited interpolation of discrete-time signals are two important concepts in signal processing. In this paper we analyze the downsampling operation regarding its impact on the existence and computability of the bounded bandlimited interpolation. We assume that the discrete-time signal is obtained by downsampling the samples of a bounded bandlimited signal that vanishes at infinity, and we study two problems. First, we investigate the existence of the bounded bandlimited interpolation for such discrete-time signals from a signal theoretic perspective and show that there exist signals for which the bounded bandlimited interpolation does not exist. Second, we analyze the algorithmic generation of the bounded bandlimited interpolation, using the concept of Turing computability. Turing computability models what is theoretically implementable on a digital computer. Interestingly, it turns out that even if the bounded bandlimited interpolation exists analytically, it is not always computable, which implies that there exists no algorithm on a digital computer that can always compute it. Computability is important in order that the approximation error be controlled. If a signal is not computable, we cannot ascertain whether the computed signal is sufficiently close to the true signal, i.e., we cannot verify every approximation accuracy. [ABSTRACT FROM AUTHOR]

Normally, modeling 3D face is an effective way for pose-invariant recognition, yet its expensive computation significantly discourages potential applications. In this paper, a simple and fully automatic panoramic image-based pose-invariant face recognition method is proposed to present excellent accuracy with low complexity. In this paper, a face shape model with local morphing treatment is first constructed and considered as the alignment standard to deal with all of the possible geometric distortion problems. During the recognition phase, a proposed systematically designed algorithm with morphing and the selection function are both utilized to significantly ease the negative effects of various poses within ±45° in yaw and ±22.5° in pitch. As demonstrated in experimental results, a similar accuracy as that of the 3D start-of-the-arts is achieved with much less computational complexity. [ABSTRACT FROM AUTHOR]

Transform, as one of the most important modules of mainstream video coding systems, seems very stable over the past several decades. However, recent developments indicate that bringing more options for transform can lead to coding efficiency benefits. In this paper, we go further to investigate how the coding efficiency can be improved over the state-of-the-art method by adapting a transform for each block. We present a variable block-sized signal-dependent transforms (SDTs) design based on the High Efficiency Video Coding (HEVC) framework. For a coding block ranged from $4\times4$ to $32\times32$ , we collect a quantity of similar blocks from the reconstructed area and use them to derive the Karhunen–Loève transform. We avoid sending overhead bits to denote the transform by performing the same procedure at the decoder. In this way, the transform for every block is tailored according to its statistics, to be signal-dependent. To make the large block-sized SDTs feasible, we present a fast algorithm for transform derivation. Experimental results show the effectiveness of the SDTs for different block sizes, which leads to up to 23.3% bit-saving. On average, we achieve BD-rate saving of 2.2%, 2.4%, 3.3%, and 7.1% under AI-Main10, RA-Main10, RA-Main10, and LP-Main10 configurations, respectively, compared with the test model HM-12 of HEVC. The proposed scheme has also been adopted into the joint exploration test model for the exploration of potential future video coding standard. [ABSTRACT FROM AUTHOR]

Field programmable gate array (FPGA) packing and placement without routability consideration could lead to unroutable results for high-utilization designs. Conventional FPGA packing and placement approaches are shown to have severe difficulties to yield good routability. In this paper, we propose an FPGA packing and placement engine called UTPlaceF that simultaneously optimizes wirelength and routability. A novel physical and congestion aware packing algorithm and a hierarchical detailed placement technique are proposed. UTPlaceF outperforms state-of-the-art FPGA placers simultaneously in runtime and solution quality on International Symposium on Physical Design (ISPD) 2016 benchmark suite. Compared with the top three winners of ISPD’16 FPGA placement contest, UTPlaceF can deliver 6.2%, 11.6%, and 29.1% better routed wirelength with shorter runtime. [ABSTRACT FROM AUTHOR]

This paper analyzes the asymptotic performances of fully distributed sequential hypothesis testing procedures as the type-I and type-II error rates approach zero, in the context of a sensor network without a fusion center. In particular, the sensor network is defined by an undirected graph, where each sensor can observe samples over time, access the information from the adjacent sensors, and perform the sequential test based on its own decision statistic. Different from most literature, the sampling process and the information exchange process in our framework take place simultaneously (or, at least in comparable time-scales), thus cannot be decoupled from one another. Our goal is to achieve second-order asymptotically optimal performance at every sensor, i.e., the average detection delay is within a constant gap from the centralized optimal sequential test as the error rates approach zero for the fixed number of sensors. To that end, a type of test procedure that resembles the well-known sequential probability ratio test (SPRT), termed as distributed SPRT (DSPRT) in this paper, is studied based on two message-passing schemes, respectively. The first scheme features the dissemination of the raw samples. In specific, every sample propagates over the network by being relayed from one sensor to another until it reaches all the sensors in the network. Although the sample propagation-based DSPRT is shown to yield the asymptotically optimal performance at each sensor, it incurs excessive inter-sensor communication overhead due to the exchange of raw samples with index information. The second scheme adopts the consensus algorithm, where the local decision statistic is exchanged between sensors instead of the raw samples, thus significantly lowering the communication requirement compared with the first scheme. In particular, the decision statistic for DSPRT at each sensor is updated by the weighted average of the decision statistics in the neighborhood at every message-passing step. We show that, under certain regularity conditions, the consensus algorithm-based DSPRT also yields the second-order asymptotically optimal performance at all sensors given a fixed number of sensors. Our asymptotic analyses of the two message-passing-based DSPRTs are then corroborated by simulations using the Gaussian and Laplacian samples. [ABSTRACT FROM AUTHOR]

Advances in semiconductor technology enable integrating tens of cores on a single chip. Providing quality-of-service (QoS) for communication flows in complex embedded applications is critical. In this paper, we present a new approach for designing guaranteed service (GS) networks-on-chip by introducing a new arbitration algorithm and differentiating high and low priority traffic flows in best-effort (BE) networks. An analytical model is provided to compute accurate performance bound parameters in the network with the new arbitration. When the flows have the same priorities in a switch, the new algorithm acts exactly the same as the basic round robin arbitration. It works as a superset of the basic algorithm, when the flows have different priorities. The proposed method helps designers to easily equip traditional BE networks with effective hard QoS, changing it to a GS network. This is done without the need to get involved in the designing complexity of traditional GS networks and still benefit from the superior properties of BE networks. We show substantial improvement in performance bounds for high priority flows (more than 40% in delay and 80% in bandwidth, on average) compared to the known approaches. [ABSTRACT FROM PUBLISHER]

It is a well-known fact that the Discrete Fourier Transform (DFT) \vec X of an arbitrary n -length input signal \vec {x} , can be computed from all the n time-domain samples in O( n\log n) operations via a Fast Fourier Transform (FFT) algorithm. If the spectrum k -sparse (where k\ll n ), can we do better? We show that asymptotically in k and n , when k ), where 0 \leq \delta <1 ), and the support of the non-zero DFT coefficients is uniformly random, the fast fourier aliasing-based sparse transform (FFAST) algorithm, proposed in this paper, computes, with asymptotically high probability, the k non-zero DFT coefficients of from O( k) samples of \vec x in O( k\log k) arithmetic operations. Further, the constants in the big Oh notation for both sample and computational cost are small, e.g., when \delta < 0.99 , which essentially covers a wide range of sub-linear sparsity cases, the sample cost is less than 4 k . Although, in this paper we assume that the samples of the signal \vec x observed by the FFAST are noise-free, a noise-robust extension of the FFAST is provided in a companion (Part II) paper [1]. Our approach is based on filter-less sub-sampling of the input signal using a set of carefully chosen uniform sub-sampling patterns guided by the Chinese Remainder Theorem (CRT). The idea is to cleverly exploit, rather than avoid, the resulting aliasing artifacts induced by sub-sampling. Specifically, the sub-sampling operation on the time-domain signal \vec x is designed to create aliasing patterns of the non-zero coefficients of the spectrum \vec X to “look like” parity-check constraints of a good erasure-correcting sparse-graph code. Next, we show that computing the sparse DFT \vec X is equivalent to decoding of an appropriate sparse-graph code. The sparse-graph codes further permit a fast peeling-style decoding. Consequently, the resulting DFT computation is low in both the sample and the decoding complexity. We analytically connect our proposed CRT-based aliasing framework to random sparse-graph codes, and analyze the performance of our algorithm using density evolution techniques from coding theory. We provide extensive simulation results, that are in tight agreement with our theoretical findings. [ABSTRACT FROM PUBLISHER]

Low-light images suffer from low contrast and unclear details, which not only reduces the available information for humans but limits the application of computer vision algorithms. Among the existing enhancement techniques, Retinex-based and learning-based methods are under the spotlight today. In this paper, we bridge the gap between the two methods. First, we propose a novel “generative” strategy for Retinex decomposition, by which the decomposition is cast as a generative problem. Second, based on the strategy, a unified deep framework is proposed to estimate the latent components and perform low-light image enhancement. Third, our method can weaken the coupling relationship between the two components while performing Retinex decomposition. Finally, the RetinexDIP performs Retinex decomposition without any external images, and the estimated illumination can be easily adjusted and is used to perform enhancement. The proposed method is compared with ten state-of-the-art algorithms on seven public datasets, and the experimental results demonstrate the superiority of our method. Code is available at: https://github.com/zhaozunjin/RetinexDIP. [ABSTRACT FROM AUTHOR]

Genetic programming approaches have been employed in the literature to automatically design constructive heuristics for cutting and packing problems. These heuristics obtain results superior to human-created constructive heuristics, but they do not generally obtain results of the same quality as local search heuristics, which start from an initial solution and iteratively improve it. If local search heuristics can be successfully designed through evolution, in addition to a constructive heuristic which initializes the solution, then the quality of results which can be obtained by automatically generated algorithms can be significantly improved. This paper presents a grammatical evolution methodology which automatically designs good quality local search heuristics that maintain their performance on new problem instances. [ABSTRACT FROM PUBLISHER]

In this paper, a strategy for controlling a group of agents to achieve positional consensus is presented. The problem is constrained by the requirement that every agent must be given the same control input through a broadcast communication mechanism. Although the control command is computed using state information in a global framework, the control input is implemented by the agents in a local coordinate frame. We propose a novel linear programming (LP) formulation that is computationally less intensive than earlier proposed methods. Moreover, a random perturbation input in the control command that helps the agents to come close to each other even for a large number of agents, which was not possible with an existing strategy in the literature, is introduced. The method is extended to achieve positional consensus at a prespecified location. The effectiveness of the approach is illustrated through simulation results. A comparison between the LP approach and the existing second-order cone programming-based approach is also presented. The algorithm was successfully implemented on a robotic platform with three robots. [ABSTRACT FROM PUBLISHER]

This paper proposes a diagnosis technique algorithm for a brushless dc motors under a stator inter-turn fault (ITF) condition using input impedance. The algorithm has early detection and various speed-range detection advantages. To early and accurately detect the ITF, the rotating speed, input current, voltage, resistance, and inductance must be analyzed. Therefore, we choose the input impedance as the detection factor because it includes all these factors. In this paper, the fault-detection system works without requiring a fast Fourier transform and the calculation of the negative-sequence impedance from the comparison of the measured impedance with the database impedance. The proposed technique was verified by the simulation and experiment. [ABSTRACT FROM AUTHOR]

Coupling cyber and physical systems gives rise to numerous engineering challenges and opportunities. An important challenge is the contagion of failure from one system to another, which can lead to large-scale cascading failures. However, the self-healing ability emerges as a valuable opportunity where the overlaying cyber network can cure failures in the underlying physical network. To capture both self-healing and contagion, this paper considers a graphical model representation of an interdependent cyber-physical system, in which nodes represent various cyber or physical functionalities, and edges capture the interactions between the nodes. A message-passing algorithm is proposed for this representation to study the dynamics of failure propagation and healing. By conducting a density evolution analysis for this algorithm, network reaction to initial disruptions is investigated. It is proved that as the number of message-passing iterations increases, the network reaches a steady-state condition that would be either a complete healing or a complete collapse. Then, a sufficient condition is derived to select the network parameters to guarantee the complete healing of the system. The result of the density evolution analysis is further employed to jointly optimize the design of cyber and physical networks for maximum resiliency. This analytical framework is then extended to the cases where the propagation of failures in the physical network is faster than the healing responses of the cyber network. Such scenarios are of interest in many real-life applications such as smart grid. Finally, extensive numerical results are presented to verify the analysis and investigate the impact of the network parameters on the resiliency of the network. [ABSTRACT FROM PUBLISHER]

Localization technologies play an increasingly important role in pervasive applications of wireless sensor networks. Since the number of targets is usually limited, localization benefits from compressed sensing (CS): measurements number can be greatly reduced. Despite many CS-based localization schemes, existing solutions implicitly assume that all targets fall on a fixed grid exactly. When the assumption is violated, the mismatch between the assumed and actual sparsifying dictionaries can deteriorate the localization performance significantly. To address such a problem, in this paper, we propose a novel and iterative multiple target counting and localization framework. The key idea behind the framework is to dynamically adjust the grid to alleviate or even eliminate dictionary mismatch. The contribution of this paper is twofold. First, we consider the off-grid target issue in CS-based localization and formulate multiple target counting and localization as a joint sparse signal recovery and parameter estimation problem. Second, we solve the joint optimization problem using a variational Bayesian expectation-maximization algorithm where the sparse signal and parameter are iteratively updated in the variational Bayesian expectation-step and variational Bayesian maximization-step, respectively. Extensive simulation results highlight the superior performance of the proposed framework in terms of probability of correct counting and average localization error. [ABSTRACT FROM PUBLISHER]

Proper generalized decomposition (PGD) is a recently developed model-order reduction method based on the use of variable-separated representations. In this paper, space variable-separated PGD is applied on the 3-D capacitance extraction of interconnects in integrated circuits to reduce its computational complexity. To make the PGD solver feasible, the complex boundary conditions are simplified by a characteristic function technique. 3-D singular-value decomposition of the coefficient functions is avoided by using a reformulated PGD algorithm, and therefore, the proposed method can effectively deal with problems with inhomogeneous dielectric layers and dummy fills. Numerical examples are given to verify the method. [ABSTRACT FROM AUTHOR]

Control applications are often implemented on highly cost-sensitive and resource-constrained embedded platforms, such as microcontrollers with a small on-chip memory. Typically, control algorithms are designed using model-based approaches, where the details of the implementation platform are completely ignored. As a result, optimizations that integrate platform-level characteristics into the control algorithms design are largely missing. With the emergence of cyber-physical systems (CPS)-oriented thinking, there has lately been a strong interest in co-design of control algorithms and their implementation platforms, leading to work on networked control systems and computation-aware control algorithms design. However, there has so far been no work on integrating the characteristics of a memory architecture into the design of control algorithms. In this paper we, for the first time, show that accounting for the impact of on-chip memory (or cache) reuse on the performance of control applications motivates new techniques for control algorithms design. This leads to significant improvement in quality of control for given resource availability, or more efficient implementations of embedded control applications. We believe that this paper opens up a variety of possibilities for memory-related optimizations of embedded control systems, that will be pursued by researchers working on computer-aided design for CPS. [ABSTRACT FROM PUBLISHER]

In the past decade, many numerical algorithms for the Eikonal equation have been proposed. Recently, the research of Eikonal equation solver has focused more on developing efficient parallel algorithms in order to leverage the computing power of parallel systems, such as multi-core CPUs and GPUs (Graphics Processing Units). In this paper, we introduce an efficient parallel algorithm that extends Jeong et al.’s FIM (Fast Iterative Method, [1] ), originally developed for the GPU, for multi-core shared memory systems. First, we propose a parallel implementation of FIM using a lock-free local queue approach and provide an in-depth analysis of the parallel performance of the method. Second, we propose a new parallel algorithm, Group-Ordered Fast Iterative Method (GO-FIM), that exploits causality of grid blocks to reduce redundant computations, which was the main drawback of the original FIM. In addition, the proposed GO-FIM method employs clustering of blocks based on the updating order where each cluster can be updated in parallel using multi-core parallel architectures. We discuss the performance of GO-FIM and compare with the state-of-the-art parallel Eikonal equation solvers. [ABSTRACT FROM AUTHOR]

In two-tier femtocell networks, adjusting the transmission power values of femtocell base stations (BSs) such that indoor users receive high signal quality while limiting leakage to outdoor users is an important problem. This paper proposes a novel distributed and self-optimized power adjustment algorithm for two-tier femtocell networks, in which a BS adjusts the transmission power based on the signal quality of neighboring BSs. Achieving fairness among users with minimal information exchange is desired. There are no predefined target parameters used to adjust transmission power, contrary to existing approaches in the literature. The convergence properties of the algorithm under fixed and time-varying communication infrastructures are investigated. The performance is further verified by simulations and comparisons with other algorithms for the coverage problem. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a new method for estimating the visual focus of attention (VFOA) in a video stream captured by a single distant camera and showing several persons sitting around a table, like in formal meeting or video conferencing settings. The visual targets for a given person are automatically extracted online using an unsupervised algorithm that incrementally learns the different appearance clusters from low-level visual features computed from face patches provided by a face tracker without the need of an intermediate error-prone step of head pose estimation as in classical approaches. The clusters learned in that way can then be used to classify the different visual attention targets of the person during a tracking run, without any prior knowledge on the environment and the configuration of the room or the visible persons. The experiments on public datasets containing almost 2 h of annotated videos from meetings and video conferencing show that the proposed algorithm produces state-of-the-art results and even outperforms a traditional supervised method that is based on head orientation estimation and that classifies VFOA using Gaussian mixture models. [ABSTRACT FROM AUTHOR]

Given a network with groups, such as a contact-network grouped by ages, which are the best groups to immunize to control the epidemic? Equivalently, how to choose best communities in social media like Facebook to stop rumors from spreading? Immunization is an important problem in multiple different domains like epidemiology, public health, cyber security, and social media. Additionally, clearly immunization at group scale (like schools and communities) is more realistic due to constraints in implementations and compliance (e.g., it is hard to ensure specific individuals take the adequate vaccine). Hence, efficient algorithms for such a “group-based” problem can help public-health experts take more practical decisions. However, most prior work has looked into individual-scale immunization. In this paper, we study the problem of controlling propagation at group scale. We formulate a set of novel Group Immunization problems for multiple natural settings (for both threshold and cascade-based contagion models under both node-level and edge-level interventions) and develop multiple efficient algorithms, including provably approximate solutions. Finally, we show the effectiveness of our methods via extensive experiments on real and synthetic datasets. [ABSTRACT FROM PUBLISHER]