Synthesis of workspaces of planar manipulators with arbitrary topology using shape representation and simulated annealing

This paper presents a general methodology for the synthesis of the external boundary of the workspaces of a planar manipulator with arbitrary topology. Both the desired workspace and the manipulator workspaces are identified by their boundaries and are treated as simple closed polygons. The paper introduces the concept of best match configuration and shows that the corresponding transformation can be obtained by using the concept of shape normalization available in image processing literature. Introduction of the concept of shape in workspace synthesis allows highly accurate synthesis with fewer numbers of design variables. This paper uses a new global property based vector representation for the shape of the workspaces which is computationally efficient because six out of the seven elements of this vector are obtained as a by-product of the shape normalization procedure. The synthesis of workspaces is formulated as an optimization problem where the distance between the shape vector of the desired workspace and that of the workspace of the manipulator at hand are minimized by changing the dimensional parameters of the manipulator. In view of the irregular nature of the error manifold, the statistical optimization procedure of simulated annealing has been used. A number of worked-out examples illustrate the generality and efficiency of the present method. (C) 1998 Elsevier Science Ltd. All rights reserved.

Integer Sequence window based Reconfigurable FIR filters

Conventional hardware implementation techniques for FIR filters require the computation of filter coefficients in software and have them stored in memory. This approach is static in the sense that any further fine tuning of the filter requires computation of new coefficients in software. In this paper, we propose an alternate technique for implementing FIR filters in hardware. We store a considerably large number of impulse response coefficients of the ideal filter (having box type frequency response) in memory. We then do the windowing process, on these coefficients, in hardware using integer sequences as window functions. The integer sequences are also generated in hardware. This approach offers the flexibility in fine tuning the filter, like varying the transition bandwidth around a particular cutoff frequency.

Finding a Box Representation for a Graph in $O(n^2\Delta^2\ln n)$ time

An axis-parallel box in $b$-dimensional space is a Cartesian product $R_1 \times R_2 \times \cdots \times R_b$ where $R_i$ (for $1 \leq i \leq b$) is a closed interval of the form $[a_i, b_i]$ on the real line. For a graph $G$, its boxicity is the minimum dimension $b$, such that $G$ is representable as the intersection graph of (axis-parallel) boxes in $b$-dimensional space. The concept of boxicity finds application in various areas of research like ecology, operation research etc. Chandran, Francis and Sivadasan gave an $O(\Delta n^2 \ln^2 n)$ randomized algorithm to construct a box representation for any graph $G$ on $n$ vertices in $\lceil (\Delta + 2)\ln n \rceil$ dimensions, where $\Delta$ is the maximum degree of the graph. They also came up with a deterministic algorithm that runs in $O(n^4 \Delta )$ time. Here, we present an $O(n^2 \Delta^2 \ln n)$ deterministic algorithm that constructs the box representation for any graph in $\lceil (\Delta + 2)\ln n \rceil$ dimensions.

On a Novel Geometric Representation of Rotation

This paper presents a novel method of representing rotation and its application to representing the ranges of motion of coupled joints in the human body, using planar maps. The present work focuses on the viability of this representation for situations that relied on maps on a unit sphere. Maps on a unit sphere have been used in diverse applications such as Gauss map, visibility maps, axis-angle and Euler-angle representations of rotation etc. Computations on a spherical surface are difficult and computationally expensive; all the above applications suffer from problems associated with singularities at the poles. There are methods to represent the ranges of motion of such joints using two-dimensional spherical polygons. The present work proposes to use multiple planar domain “cube” instead of a single spherical domain, to achieve the above objective. The parameterization on the planar domains is easy to obtain and convert to spherical coordinates. Further, there is no localized and extreme distortion of the parameter space and it gives robustness to the computations. The representation has been compared with the spherical representation in terms of computational ease and issues related to singularities. Methods have been proposed to represent joint range of motion and coupled degrees of freedom for various joints in digital human models (such as shoulder, wrist and fingers). A novel method has been proposed to represent twist in addition to the existing swing-swivel representation.

Register Allocation and Optimal Spill code Scheduling in Software Pipelined Loops using 0-1 Integer Linear Programming Formulation

In achieving higher instruction level parallelism, software pipelining increases the register pressure in the loop. The usefulness of the generated schedule may be restricted to cases where the register pressure is less than the available number of registers. Spill instructions need to be introduced otherwise. But scheduling these spill instructions in the compact schedule is a difficult task. Several heuristics have been proposed to schedule spill code. These heuristics may generate more spill code than necessary, and scheduling them may necessitate increasing the initiation interval. We model the problem of register allocation with spill code generation and scheduling in software pipelined loops as a 0-1 integer linear program. The formulation minimizes the increase in initiation interval (II) by optimally placing spill code and simultaneously minimizes the amount of spill code produced. To the best of our knowledge, this is the first integrated formulation for register allocation, optimal spill code generation and scheduling for software pipelined loops. The proposed formulation performs better than the existing heuristics by preventing an increase in II in 11.11% of the loops and generating 18.48% less spill code on average among the loops extracted from Perfect Club and SPEC benchmarks with a moderate increase in compilation time.

Boxicity of Circular Arc Graphs

A k-dimensional box is a Cartesian product R(1)x...xR(k) where each R(i) is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. That is, two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. We show that if G is a circular arc graph which admits a circular arc representation in which no arc has length at least pi(alpha-1/alpha) for some alpha is an element of N(>= 2), then box(G) <= alpha (Here the arcs are considered with respect to a unit circle). From this result we show that if G has maximum degree Delta < [n(alpha-1)/2 alpha] for some alpha is an element of N(>= 2), then box(G) <= alpha. We also demonstrate a graph having box(G) > alpha but with Delta = n (alpha-1)/2 alpha + n/2 alpha(alpha+1) + (alpha+2). For a proper circular arc graph G, we show that if Delta < [n(alpha-1)/alpha] for some alpha is an element of N(>= 2), then box(G) <= alpha. Let r be the cardinality of the minimum overlap set, i.e. the minimum number of arcs passing through any point on the circle, with respect to some circular arc representation of G. We show that for any circular arc graph G, box(G) <= r + 1 and this bound is tight. We show that if G admits a circular arc representation in which no family of k <= 3 arcs covers the circle, then box(G) <= 3 and if G admits a circular arc representation in which no family of k <= 4 arcs covers the circle, then box(G) <= 2. We also show that both these bounds are tight.

mRegistry: a registry representation for fault diagnosis

Microsoft Windows uses the notion of registry to store all configuration information. The registry entries have associations and dependencies. For example, the paths to executables may be relative to some home directories. The registry being designed with faster access as one of the objectives does not explicitly capture these relations. In this paper, we explore a representation that captures the dependencies more explicitly using shared and unifying variables. This representation, called mRegistry exploits the tree-structured hierarchical nature of the registry, is concept-based and obtained in multiple stages. mRegistry captures intra-block, inter-block and ancestor-children dependencies (all leaf entries of a parent key in a registry put together as an entity constitute a block thereby making the block as the only child of the parent). In addition, it learns the generalized concepts of dependencies in the form of rules. We show that mRegistry has several applications: fault diagnosis, prediction, comparison, compression etc.

Representation of evidence: An approach to uncertainty handling in knowledge-based systems

Many knowledge based systems (KBS) transform a situation information into an appropriate decision using an in built knowledge base. As the knowledge in real world situation is often uncertain, the degree of truth of a proposition provides a measure of uncertainty in the underlying knowledge. This uncertainty can be evaluated by collecting `evidence' about the truth or falsehood of the proposition from multiple sources. In this paper we propose a simple framework for representing uncertainty in using the notion of an evidence space.

Location Area Planning Using Simulated Annealing With A New Solution Representation

Location area planning problem is to partition the cellular/mobile network into location areas with the objective of minimizing the total cost. This partitioning problem is a difficult combinatorial optimization problem. In this paper, we use the simulated annealing with a new solution representation. In our method, we can automatically generate different number of location areas using Compact Index (CI) to obtain the optimal/best partitions. We compare the results obtained in our method with the earlier results available in literature. We show that our methodology is able to perform better than earlier methods.

Influence fields: a quantitative framework for representation and analysis of active dendrites

Rathour RK, Narayanan R. Influence fields: a quantitative framework for representation and analysis of active dendrites. J Neurophysiol 107: 2313-2334, 2012. First published January 18, 2012; doi:10.1152/jn.00846.2011.-Neuronal dendrites express numerous voltage-gated ion channels (VGICs), typically with spatial gradients in their densities and properties. Dendritic VGICs, their gradients, and their plasticity endow neurons with information processing capabilities that are higher than those of neurons with passive dendrites. Despite this, frameworks that incorporate dendritic VGICs and their plasticity into neurophysiological and learning theory models have been far and few. Here, we develop a generalized quantitative framework to analyze the extent of influence of a spatially localized VGIC conductance on different physiological properties along the entire stretch of a neuron. Employing this framework, we show that the extent of influence of a VGIC conductance is largely independent of the conductance magnitude but is heavily dependent on the specific physiological property and background conductances. Morphologically, our analyses demonstrate that the influences of different VGIC conductances located on an oblique dendrite are confined within that oblique dendrite, thus providing further credence to the postulate that dendritic branches act as independent computational units. Furthermore, distinguishing between active and passive propagation of signals within a neuron, we demonstrate that the influence of a VGIC conductance is spatially confined only when propagation is active. Finally, we reconstruct functional gradients from VGIC conductance gradients using influence fields and demonstrate that the cumulative contribution of VGIC conductances in adjacent compartments plays a critical role in determining physiological properties at a given location. We suggest that our framework provides a quantitative basis for unraveling the roles of dendritic VGICs and their plasticity in neural coding, learning, and homeostasis.

On the structure of analytic vectors for the Schrodinger representation

This article deals with the structure of analytic and entire vectors for the Schrodinger representations of the Heisenberg group. Using refined versions of Hardy's theorem and their connection with Hermite expansions we obtain very precise representation theorems for analytic and entire vectors.

Under-representation of intrinsic terminators across bacterial genomic islands: Rho as a principal regulator of xenogenic DNA expression

Two transcription termination mechanisms - intrinsic and Rho-dependent - have evolved in bacteria. The Rho factor occurs in most bacterial lineages, and has been hypothesized to play a global regulatory role. Genome-wide studies using microarray, 2D-gel electrophoresis and ChIP-chip provided evidence that Rho serves to silence transcription from horizontally acquired genes and prophages in Escherichia coli K-12, implicating the factor to be a part of the ``cellular immune mechanism'' protecting against deleterious phages and aberrant gene expression from acquired xenogenic DNA. We have investigated this model by adopting an alternate in silico approach and have extended the study to other species. Our analysis shows that several genomic islands across diverse phyla have under-representation of intrinsic terminators, similar to that experimentally observed in E. coli K-12. This implies that Rho-dependent termination is the predominant process operational in these islands and that silencing of foreign DNA is a conserved function of Rho. From the present analysis, it is evident that horizontally acquired islands have lost intrinsic terminators to facilitate Rho-dependent termination. These results underscore the importance of Rho as a conserved, genome-wide sentinel that regulates potentially toxic xenogenic DNA. (C) 2012 Elsevier B.V. All rights reserved.

HUMAN DETECTION USING SPARSE REPRESENTATION

The problem of human detection is challenging, more so, when faced with adverse conditions such as occlusion and background clutter. This paper addresses the problem of human detection by representing an extracted feature of an image using a sparse linear combination of chosen dictionary atoms. The detection along with the scale finding, is done by using the coefficients obtained from sparse representation. This is of particular interest as we address the problem of scale using a scale-embedded dictionary where the conventional methods detect the object by running the detection window at all scales.

A constant factor approximation algorithm for boxicity of circular arc graphs

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional axis parallel boxes in Rk. Equivalently, it is the minimum number of interval graphs on the vertex set V such that the intersection of their edge sets is E. It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below O(n0.5-ε)-factor, for any ε > 0 in polynomial time unless NP = ZPP. Till date, there is no well known graph class of unbounded boxicity for which even an nε-factor approximation algorithm for computing boxicity is known, for any ε < 1. In this paper, we study the boxicity problem on Circular Arc graphs - intersection graphs of arcs of a circle. We give a (2+ 1/k)-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where k ≥ 1 is its boxicity. For Normal Circular Arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is O(mn+n2) in both these cases and in O(mn+kn2) which is at most O(n3) time we also get their corresponding box representations, where n is the number of vertices of the graph and m is its number of edges. The additive 2-factor algorithm directly works for any Proper Circular Arc graph, since computing an NCA model for it can be done in polynomial time.