Two and Three Finger Caging of Polygons and Polyhedra

Multi-finger caging offers a rigorous and robust approach to robot grasping. This thesis provides several novel algorithms for caging polygons and polyhedra in two and three dimensions. Caging refers to a robotic grasp that does not necessarily immobilize an object, but prevents it from escaping to infinity. The first algorithm considers caging a polygon in two dimensions using two point fingers. The second algorithm extends the first to three dimensions. The third algorithm considers caging a convex polygon in two dimensions using three point fingers, and considers robustness of this cage to variations in the relative positions of the fingers.

This thesis describes an algorithm for finding all two-finger cage formations of planar polygonal objects based on a contact-space formulation. It shows that two-finger cages have several useful properties in contact space. First, the critical points of the cage representation in the hand’s configuration space appear as critical points of the inter-finger distance function in contact space. Second, these critical points can be graphically characterized directly on the object’s boundary. Third, contact space admits a natural rectangular decomposition such that all critical points lie on the rectangle boundaries, and the sublevel sets of contact space and free space are topologically equivalent. These properties lead to a caging graph that can be readily constructed in contact space. Starting from a desired immobilizing grasp of a polygonal object, the caging graph is searched for the minimal, intermediate, and maximal caging regions surrounding the immobilizing grasp. An example constructed from real-world data illustrates and validates the method.

A second algorithm is developed for finding caging formations of a 3D polyhedron for two point fingers using a lower dimensional contact-space formulation. Results from the two-dimensional algorithm are extended to three dimension. Critical points of the inter-finger distance function are shown to be identical to the critical points of the cage. A decomposition of contact space into 4D regions having useful properties is demonstrated. A geometric analysis of the critical points of the inter-finger distance function results in a catalog of grasps in which the cages change topology, leading to a simple test to classify critical points. With these properties established, the search algorithm from the two-dimensional case may be applied to the three-dimensional problem. An implemented example demonstrates the method.

This thesis also presents a study of cages of convex polygonal objects using three point fingers. It considers a three-parameter model of the relative position of the fingers, which gives complete generality for three point fingers in the plane. It analyzes robustness of caging grasps to variations in the relative position of the fingers without breaking the cage. Using a simple decomposition of free space around the polygon, we present an algorithm which gives all caging placements of the fingers and a characterization of the robustness of these cages.

Pitman-Yor Diffusion Trees

We introduce the Pitman Yor Diffusion Tree (PYDT) for hierarchical clustering, a generalization of the Dirichlet Diffusion Tree (Neal, 2001) which removes the restriction to binary branching structure. The generative process is described and shown to result in an exchangeable distribution over data points. We prove some theoretical properties of the model and then present two inference methods: a collapsed MCMC sampler which allows us to model uncertainty over tree structures, and a computationally efficient greedy Bayesian EM search algorithm. Both algorithms use message passing on the tree structure. The utility of the model and algorithms is demonstrated on synthetic and real world data, both continuous and binary.

Interaction between human interleukin-16 and CD4 receptor of HIV-1

AIM: To study the interaction between human interleukin-16 (IL-16) and the receptor CD4 (T-lymphocyte differentiation antigen) of human immunodeficiency virus type 1 (HIV-1). METHODS: Two structurally con served regions (SCRs) of human IL-16 were built by the SYBYL/Biopolymer module using the corresponding transmembrane (TM) domain of human interleukin-1 (HIL-4) and HIL-2 as the templates. The coordinates for amino-terminal residue sequence, carboxyl-terminal residue sequences, and cytoplasm loops were generated using Biopolymer's LOOP SEARCH algorithm. RESULTS: HIL-16 first formed a homodimer, then contacted with CD4 dimer further forming a dimeric complex. Subsequently, the dimeric complex constructed the tetrameric complex by two disulfide bridges between the cysteines of HIL-16 (Cys31-Cys31). CONCLUSION: The interaction model is useful to propose the action mechanism of HIL-16 and is beneficial for rational designing of novel anti-HIV drugs.

Molecular modeling on human CCR5 receptors and complex with CD4 antigens and HIV-1 envelope glycoprotein gp120

AIM: To investigate the interaction between human CCR5 receptors (CCR5) and HIV-1 envelope glycoprotein gp120 (HIV-1 gp120) and HIV-1 receptor CD4 antigens (CD4). METHODS: The structurally con served regions (SCR) of human CCR5 was built by the SYBYL/Biopolymer module using the corresponding transmembrane (TM) domain of bacteriorhodopsin (bR) as the template. The coordinates for amino-ter minal residue sequence, and carboxyl-terminal residue sequence, extracellular and cytoplasmic loops were generated using LOOP SEARCH algorithm. Subsequently the structural model was merged into the complex with HIV-1 gp120 and CD4. RESULTS: Human CCR5 interacted with both an HIV-1 gp120 and CD4. The N-terminal residues (especially Met1 and Gln4) of human CCR5, contacted with CD4 residues, mainly 7Nith one span (56 - 59) of CD4 in electrostatic interaction and hydrogen-bonds. The binding sites of human CCR5 were buried in a hydrophobic center surrounded by a highly basic periphery. On the other hand, direct interatomic contacts were made between ? CCR5 residues and 6 gp120 amino-acid residues, which included van der Waals contacts, hydrophobic interaction, and hydrogen bonds. CONCLUSION: The interaction model should be helpful for rational design of novel anti-HIV drugs.

An approach to multi-fidelity optimization of aeroengine compression systems

The aerodynamic design of turbomachinery presents the design optimisation community with a number of exquisite challenges. Chief among these are the size of the design space and the extent of discontinuity therein. This discontinuity can serve to limit the full exploitation of high-fidelity computational fluid dynamics (CFD): such codes require detailed geometric information often available only sometime after the basic configuration of the machine has been set by other means. The premise of this paper is that it should be possible to produce higher performing designs in less time by exploiting multi-fidelity techniques to effectively harness CFD earlier in the design process, specifically by facilitating its participation in configuration selection. The adopted strategy of local multi-fidelity correction, generated on demand, combined with a global search algorithm via an adaptive trust region is first tested on a modest, smooth external aerodynamic problem. Speed-up of an order of magnitude is demonstrated, comparable to established techniques applied to smooth problems. A number of enhancements aimed principally at effectively evaluating a wide range of configurations quickly is then applied to the basic strategy, and the emerging technique is tested on a generic aeroengine core compression system. A similar order of magnitude speed-up is achieved on this relatively large and highly discontinuous problem. A five-fold increase in the number of configurations assessed with CFD is observed. As the technique places constraints neither on the underlying physical modelling of the constituent analysis codes nor on first-order agreement between those codes, it has potential applicability to a range of multidisciplinary design challenges. © 2012 by Jerome Jarrett and Tiziano Ghisu.

Computational engineering design for micro-scale combustion devices: A thermally improved configuration

A multi-objective design optimisation study has been carried out with the objectives to improve the overall efficiency of the device and to reduce the fuel consumption for the proposed micro-scale combustor design configuration. In a previous study we identified the topology of the combustion chamber that produced improved behaviour of the device in terms of the above design criteria. We now extend our design approach, and we propose a new configuration by the addition of a micro-cooling channel that will improve the thermal behaviour of the design as previously suggested in literature. Our initial numerical results revealed an improvement of 2.6% in the combustion efficiency when we applied the micro-cooling channel to an optimum design configuration we identified from our earlier multi-objective optimisation study, and under the same operating conditions. The computational modelling of the combustion process is implemented in the commercial computational fluid dynamics package ANSYS-CFX using Finite Rate Chemistry and a single step hydrogen-air reaction. With this model we try to balance good accuracy of the combustion solution and at the same time practicality within the context of an optimisation process. The whole design system comprises also the ANSYS-ICEM CFD package for the automatic geometry and mesh generation and the Multi-Objective Tabu Search algorithm for the design space exploration. We model the design problem with 5 geometrical parameters and 3 operational parameters subject to 5 design constraints that secure practicality and feasibility of the new optimum design configurations. The final results demonstrate the reliability and efficiency of the developed computational design system and most importantly we assess the practicality and manufacturability of the revealed optimum design configurations of micro-combustor devices. Copyright © 2013 by ASME.

Quantum computing

Quantum computing is a quickly growing research field. This article introduces the basic concepts of quantum computing, recent developments in quantum searching, and decoherence in a possible quantum dot realization.

A Complex BPF with On Chip Auto-tuning Architecture for Wireless Receivers

A 3(rd) order complex band-pass filter (BPF) with auto-tuning architecture is proposed in this paper. It is implemented in 0.18um standard CMOS technology. The complex filter is centered at 4.092MHz with bandwidth of 2.4MHz. The in-band 3(rd) order harmonic input intercept point (IIP3) is larger than 16.2dBm, with 50 Omega as the source impedance. The input referred noise is about 80uV(rms). The RC tuning is based on Binary Search Algorithm (BSA) with tuning accuracy of 3%. The chip area of the tuning system is 0.28 x 0.22 mm(2), less than 1/8 of that of the main-filter which is 0.92 x 0.59 mm(2). After tuning is completed, the tuning system will be turned off automatically to save power and to avoid interference. The complex filter consumes 2.6mA with a 1.8V power supply.

A Complex BPF with On Chip Auto-tuning Architecture for Low-IF Receivers

A 3(rd) order complex band-pass filter (BPF) with auto-tuning architecture is proposed in this paper. It is implemented in 0.18 mu m standard CMOS technology. The complex filter is centered at 4.092MHz with bandwidth of 2.4MHz. The in-band 3(rd) order harmonic input intercept point (IIP3) is larger than 19dBm, with 50 Omega as the source impedance. The input referred noise is about 80 mu V-rms. The RC tuning is based on Binary Search Algorithm (BSA) with tuning accuracy of 3%. The chip area of the tuning system is 0.28x0.22mm(2), less than 1/8 of that of the main-filter which is 0.92x0.59mm(2). After tuning is completed, the tuning system will be turned off automatically to save power and to avoid interference. The complex filter consumes 2.6mA with a 1.8V power supply.

一种三维航迹快速搜索方法

本文提出了基于SAS的自动三维航迹规划方法。该方法通过把约束条件结合到搜索算法中去，有效地减小了搜索空间，缩短了搜索时间，从而使三维规划能够用于实时航迹规划。在搜索过程中地形信息得到了充分利用，使算法生成的航迹能够自动回避地形和威胁。实验证明，该方法能够快速有效地完成规划任务，获得满意的三维航迹。

Quantum computing

Quantum computing is a quickly growing research field. This article introduces the basic concepts of quantum computing, recent developments in quantum searching, and decoherence in a possible quantum dot realization.

一种基于神经网络的生产调度方法

提出解决具有开、完工期限制的约束Ｊｏｂ－ｓｈｏｐ生产调度问题的一种神经网络方法．该方法通过约束神经网络，描述各种加工约束条件，并对不满足约束的开工时间进行相应调节，得到可行调度方案；然后由梯度搜索算法优化可行调度方案，直至得到最终优化可行调度解．理论分析、仿真实验表明了方法的有效性。

延时过程纯滞后的一种降阶搜索算法

本文讨论了在特殊信号下,非真阶非真滞后模型参数的最小二乘估计与纯滞后之间的关系,提出了一种新的辨识纯滞后的方法——降阶搜索算法。

Systematic delay-driven power optimisation and power-driven delay optimisation of combinational circuits

With the proliferation of mobile wireless communication and embedded systems, the energy efficiency becomes a major design constraint. The dissipated energy is often referred as the product of power dissipation and the input-output delay. Most of electronic design automation techniques focus on optimising only one of these parameters either power or delay. Industry standard design flows integrate systematic methods of optimising either area or timing while for power consumption optimisation one often employs heuristics which are characteristic to a specific design. In this work we answer three questions in our quest to provide a systematic approach to joint power and delay Optimisation. The first question of our research is: How to build a design flow which incorporates academic and industry standard design flows for power optimisation? To address this question, we use a reference design flow provided by Synopsys and integrate in this flow academic tools and methodologies. The proposed design flow is used as a platform for analysing some novel algorithms and methodologies for optimisation in the context of digital circuits. The second question we answer is: Is possible to apply a systematic approach for power optimisation in the context of combinational digital circuits? The starting point is a selection of a suitable data structure which can easily incorporate information about delay, power, area and which then allows optimisation algorithms to be applied. In particular we address the implications of a systematic power optimisation methodologies and the potential degradation of other (often conflicting) parameters such as area or the delay of implementation. Finally, the third question which this thesis attempts to answer is: Is there a systematic approach for multi-objective optimisation of delay and power? A delay-driven power and power-driven delay optimisation is proposed in order to have balanced delay and power values. This implies that each power optimisation step is not only constrained by the decrease in power but also the increase in delay. Similarly, each delay optimisation step is not only governed with the decrease in delay but also the increase in power. The goal is to obtain multi-objective optimisation of digital circuits where the two conflicting objectives are power and delay. The logic synthesis and optimisation methodology is based on AND-Inverter Graphs (AIGs) which represent the functionality of the circuit. The switching activities and arrival times of circuit nodes are annotated onto an AND-Inverter Graph under the zero and a non-zero-delay model. We introduce then several reordering rules which are applied on the AIG nodes to minimise switching power or longest path delay of the circuit at the pre-technology mapping level. The academic Electronic Design Automation (EDA) tool ABC is used for the manipulation of AND-Inverter Graphs. We have implemented various combinatorial optimisation algorithms often used in Electronic Design Automation such as Simulated Annealing and Uniform Cost Search Algorithm. Simulated Annealing (SMA) is a probabilistic meta heuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. We used SMA to probabilistically decide between moving from one optimised solution to another such that the dynamic power is optimised under given delay constraints and the delay is optimised under given power constraints. A good approximation to the global optimum solution of energy constraint is obtained. Uniform Cost Search (UCS) is a tree search algorithm used for traversing or searching a weighted tree, tree structure, or graph. We have used Uniform Cost Search Algorithm to search within the AIG network, a specific AIG node order for the reordering rules application. After the reordering rules application, the AIG network is mapped to an AIG netlist using specific library cells. Our approach combines network re-structuring, AIG nodes reordering, dynamic power and longest path delay estimation and optimisation and finally technology mapping to an AIG netlist. A set of MCNC Benchmark circuits and large combinational circuits up to 100,000 gates have been used to validate our methodology. Comparisons for power and delay optimisation are made with the best synthesis scripts used in ABC. Reduction of 23% in power and 15% in delay with minimal overhead is achieved, compared to the best known ABC results. Also, our approach is also implemented on a number of processors with combinational and sequential components and significant savings are achieved.

A generational scheme for partitioning graphs

Graph partitioning divides a graph into several pieces by cutting edges. Very effective heuristic partitioning algorithms have been developed which run in real-time, but it is unknown how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. Distinctive features are the transmission and modification of whole subdomains (the partitioned units) that act as genes, and the use of a multilevel heuristic algorithm to effect the crossover and mutations. Its effectiveness is demonstrated by improvements on previously established benchmarks.