Vertex splitting and connectivity augmentation in hypergraphs

We consider problems of splitting and connectivity augmentation in hypergraphs. In a hypergraph G = (V +s, E), to split two edges su, sv, is to replace them with a single edge uv. We are interested in doing this in such a way as to preserve a defined level of connectivity in V . The splitting technique is often used as a way of adding new edges into a graph or hypergraph, so as to augment the connectivity to some prescribed level. We begin by providing a short history of work done in this area. Then several preliminary results are given in a general form so that they may be used to tackle several problems. We then analyse the hypergraphs G = (V + s, E) for which there is no split preserving the local-edge-connectivity present in V. We provide two structural theorems, one of which implies a slight extension to Mader’s classical splitting theorem. We also provide a characterisation of the hypergraphs for which there is no such “good” split and a splitting result concerned with a specialisation of the local-connectivity function. We then use our splitting results to provide an upper bound on the smallest number of size-two edges we must add to any given hypergraph to ensure that in the resulting hypergraph we have λ(x, y) ≥ r(x, y) for all x, y in V, where r is an integer valued, symmetric requirement function on V*V. This is the so called “local-edge-connectivity augmentation problem” for hypergraphs. We also provide an extension to a Theorem of Szigeti, about augmenting to satisfy a requirement r, but using hyperedges. Next, in a result born of collaborative work with Zoltán Király from Budapest, we show that the local-connectivity augmentation problem is NP-complete for hypergraphs. Lastly we concern ourselves with an augmentation problem that includes a locational constraint. The premise is that we are given a hypergraph H = (V,E) with a bipartition P = {P1, P2} of V and asked to augment it with size-two edges, so that the result is k-edge-connected, and has no new edge contained in some P(i). We consider the splitting technique and describe the obstacles that prevent us forming “good” splits. From this we deduce results about which hypergraphs have a complete Pk-split. This leads to a minimax result on the optimal number of edges required and a polynomial algorithm to provide an optimal augmentation.

Force distribution in manipulation by a robot hand with equality and inequality constraints

The problem of the appropriate distribution of forces among the fingers of a four-fingered robot hand is addressed. The finger-object interactions are modelled as point frictional contacts, hence the system is indeterminate and an optimal solution is required for controlling forces acting on an object. A fast and efficient method for computing the grasping and manipulation forces is presented, where computation has been based on using the true model of the nonlinear frictional cone of contact. Results are compared with previously employed methods of linearizing the cone constraints and minimizing the internal forces.

Speciation as an active force in promoting genetic evolution

There is a growing appreciation among evolutionary biologists that the rate and tempo of molecular evolution might often be altered at or near the time of speciation, i.e. that speciation is in some way a special time for genes. Molecular phylogenies frequently reveal increased rates of genetic evolution associated with speciation and other lines of investigation suggest that various types of abrupt genomic disruption can play an important role in promoting speciation via reproductive isolation. These phenomena are in conflict with the gradual view of molecular evolution that is implicit in much of our thinking about speciation and in the tools of modern biology. This raises the prospect of studying the molecular evolutionary consequences of speciation per se and studying the footprint of speciation as an active force in promoting genetic divergence. Here we discuss the reasons to believe that speciation can play such a role and elaborate on possible mechanisms for accelerated rates of evolution following speciation. We provide an example of how it is possible detect whether accelerated bursts of evolution occur in neutral and/or adaptive regions of genes and discuss the implications of rapid episodes of change for conventional models of molecular evolution. Speciation might often owe more to ephemeral and essentially arbitrary events that cause reproductive isolation than to the gradual and regular tug of natural selection that draws a species into a new niche.

Performance statistics of a head-operated force-reflecting rehabilitation robot system

Researchers in the rehabilitation engineering community have been designing and developing a variety of passive/active devices to help persons with limited upper extremity function to perform essential daily manipulations. Devices range from low-end tools such as head/mouth sticks to sophisticated robots using vision and speech input. While almost all of the high-end equipment developed to date relies on visual feedback alone to guide the user providing no tactile or proprioceptive cues, the “low-tech” head/mouth sticks deliver better “feel” because of the inherent force feedback through physical contact with the user's body. However, the disadvantage of a conventional head/mouth stick is that it can only function in a limited workspace and the performance is limited by the user's strength. It therefore seems reasonable to attempt to develop a system that exploits the advantages of the two approaches: the power and flexibility of robotic systems with the sensory feedback of a headstick. The system presented in this paper reflects the design philosophy stated above. This system contains a pair of master-slave robots with the master being operated by the user's head and the slave acting as a telestick. Described in this paper are the design, control strategies, implementation and performance evaluation of the head-controlled force-reflecting telestick system.

Calibration of closed loop controllers for setting impedances in force-reflecting systems

This paper discusses a new method of impedance control that has been successfully implemented on the master robot of a teleoperation system. The method involves calibrating the robot to quantify the effect of adjustable controller parameters on the impedances along its different axes. The empirical equations relating end-effector impedance to the controller's feedback gains are obtained by performing system identification tests along individual axes of the robot. With these equations, online control of end-effector stiffness and damping is possible without having to monitor joint torques or solving complex algorithms. Hard contact conditions and compliant interfaces have been effectively demonstrated on a telemanipulation test-bed using appropriate combinations of stiffness and damping settings obtained by this method.