An oblivious shortest-path routing algorithm for fully connected cubic networks

Fully connected cubic networks (FCCNs) are a class of newly proposed hierarchical interconnection networks for multicomputer systems, which enjoy the strengths of constant node degree and good expandability. The shortest path routing in FCCNs is an open problem. In this paper, we present an oblivious routing algorithm for n-level FCCN with N = 8(n) nodes, and prove that this algorithm creates a shortest path from the source to the destination. At the costs of both an O(N)-parallel-step off-line preprocessing phase and a list of size N stored at each node, the proposed algorithm is carried out at each related node in O(n) time. In some cases the proposed algorithm is superior to the one proposed by Chang and Wang in terms of the length of the routing path. This justifies the utility of our routing strategy. (C) 2006 Elsevier Inc. All rights reserved.

The locally twisted cubes

This paper introduces a new variant of the popular n-dimensional hypercube network Q(n), known as the n-dimensional locally twisted cube LTQ(n), which has the same number of nodes and the same number of connections per node as Q(n). Furthermore. LTQ(n) is similar to Q(n) in the sense that the nodes can be one-to-one labeled with 0-1 binary sequences of length n. so that the labels of any two adjacent nodes differ in at most two successive bits. One advantage of LTQ(n) is that the diameter is only about half of the diameter of Q(n) We develop a simple routing algorithm for LTQ(n), which creates a shortest path from the source to the destination in O(n) time. We find that LTQ(n) consists of two disjoint copies of Q(n) by adding a matching between their nodes. On this basis. we show that LTQ(n) has a connectivity of n.

Simultaneous mobile sink allocation in home environments with applications in mobile consumer robotics

This paper presents a novel mobile sink area allocation scheme for consumer based mobile robotic devices with a proven application to robotic vacuum cleaners. In the home or office environment, rooms are physically separated by walls and an automated robotic cleaner cannot make a decision about which room to move to and perform the cleaning task. Likewise, state of the art cleaning robots do not move to other rooms without direct human interference. In a smart home monitoring system, sensor nodes may be deployed to monitor each separate room. In this work, a quad tree based data gathering scheme is proposed whereby the mobile sink physically moves through every room and logically links all separated sub-networks together. The proposed scheme sequentially collects data from the monitoring environment and transmits the information back to a base station. According to the sensor nodes information, the base station can command a cleaning robot to move to a specific location in the home environment. The quad tree based data gathering scheme minimizes the data gathering tour length and time through the efficient allocation of data gathering areas. A calculated shortest path data gathering tour can efficiently be allocated to the robotic cleaner to complete the cleaning task within a minimum time period. Simulation results show that the proposed scheme can effectively allocate and control the cleaning area to the robot vacuum cleaner without any direct interference from the consumer. The performance of the proposed scheme is then validated with a set of practical sequential data gathering tours in a typical office/home environment.

Path dependence and Britain’s "coal wagon problem"

This article explores the nature and impact of path dependence in British rail coal haulage before 1939. It examines the factors which locked Britain's railways into a system of small coal wagons with highly fragmented ownership, the cost penalties of this system, and the reasons that attempts at modernization were unsuccessful. The analysis highlights the importance of decentralized ownership of a highly durable installed base of complementary infrastructure. Technical and institutional interrelatedness blocked incremental modernization, while the political requirement to compensate private wagon owners for the loss of their wagon stock made wholesale rationalization financially unattractive.

3D path planning with novel multiple 2D layered approach for complex human-robot interaction

Navigating cluttered indoor environments is a difficult problem in indoor service robotics. The Acroboter concept, a novel approach to indoor locomotion, represents unique opportunity to avoid obstacles in indoor environments by navigating the ceiling plane. This mode of locomotion requires the ability to accurately detect obstacles, and plan 3D trajectories through the environment. This paper presents the development of a resilient object tracking system, as well as a novel approach to generating 3D paths suitable for such robot configurations. Distributed human-machine interfacing allowing simulation previewing of actions is also considered in the developed system architecture.

Path planning of robots in noisy workspaces using learning automata

The problem of a manipulator operating in a noisy workspace and required to move from an initial fixed position P0 to a final position Pf is considered. However, Pf is corrupted by noise, giving rise to Pˆf, which may be obtained by sensors. The use of learning automata is proposed to tackle this problem. An automaton is placed at each joint of the manipulator which moves according to the action chosen by the automaton (forward, backward, stationary) at each instant. The simultaneous reward or penalty of the automata enables avoiding any inverse kinematics computations that would be necessary if the distance of each joint from the final position had to be calculated. Three variable-structure learning algorithms are used, i.e., the discretized linear reward-penalty (DLR-P, the linear reward-penalty (LR-P ) and a nonlinear scheme. Each algorithm is separately tested with two (forward, backward) and three forward, backward, stationary) actions.

The uniqueness of signature problem in the non-Markov setting

We establish a general framework for a class of multidimensional stochastic processes over [0,1] under which with probability one, the signature (the collection of iterated path integrals in the sense of rough paths) is well-defined and determines the sample paths of the process up to reparametrization. In particular, by using the Malliavin calculus we show that our method applies to a class of Gaussian processes including fractional Brownian motion with Hurst parameter H>1/4, the Ornstein–Uhlenbeck process and the Brownian bridge.

Large deviations of Rouse polymer chain: first passage problem

The purpose of this paper is to investigate several analytical methods of solving first passage (FP) problem for the Rouse model, a simplest model of a polymer chain. We show that this problem has to be treated as a multi-dimensional Kramers' problem, which presents rich and unexpected behavior. We first perform direct and forward-flux sampling (FFS) simulations, and measure the mean first-passage time $\tau(z)$ for the free end to reach a certain distance $z$ away from the origin. The results show that the mean FP time is getting faster if the Rouse chain is represented by more beads. Two scaling regimes of $\tau(z)$ are observed, with transition between them varying as a function of chain length. We use these simulations results to test two theoretical approaches. One is a well known asymptotic theory valid in the limit of zero temperature. We show that this limit corresponds to fully extended chain when each chain segment is stretched, which is not particularly realistic. A new theory based on the well known Freidlin-Wentzell theory is proposed, where dynamics is projected onto the minimal action path. The new theory predicts both scaling regimes correctly, but fails to get the correct numerical prefactor in the first regime. Combining our theory with the FFS simulations lead us to a simple analytical expression valid for all extensions and chain lengths. One of the applications of polymer FP problem occurs in the context of branched polymer rheology. In this paper, we consider the arm-retraction mechanism in the tube model, which maps exactly on the model we have solved. The results are compared to the Milner-McLeish theory without constraint release, which is found to overestimate FP time by a factor of 10 or more.