Decentralized Motion Planning for Multiple Mobile Robots: The Cocktail Party Model

This paper presents an approach for decentralized real-time motion planning for multiple mobile robots operating in a common 2-dimensional environment with unknown stationary obstacles. In our model, a robot can see (sense) the surrounding objects. It knows its current and its target's position, is able to distinguish a robot from an obstacle, and can assess the instantaneous motion of another robot. Other than this, a robot has no knowledge about the scene or of the paths and objectives of other robots. There is no mutual communication among the robots; no constraints are imposed on the paths or shapes of robots and obstacles. Each robot plans its path toward its target dynamically, based on its current position and the sensory feedback; only the translation component is considered for the planning purposes. With this model, it is clear that no provable motion planning strategy can be designed (a simple example with a dead-lock is discussed); this naturally points to heuristic algorithms. The suggested strategy is based on maze-searching techniques. Computer simulation results are provided that demonstrate good performance and a remarkable robustness of the algorithm (meaning by this a virtual impossibility to create a dead-lock in a random scene).     

Real-time Collision-free Path Planning of Robot Manipulators using Neural Network Approaches

In this paper, a novel neural network approach to real-time collision-free path planning of robot manipulators in a nonstationary environment is proposed, which is based on a biologically inspired neural network model for dynamic trajectory generation of a point mobile robot. The state space of the proposed neural network is the joint space of the robot manipulators, where the dynamics of each neuron is characterized by a shunting equation or an additive equation. The real-time robot path is planned through the varying neural activity landscape that represents the dynamic environment. The proposed model for robot path planning with safety consideration is capable of planning a real-time comfortable path without suffering from the too close nor too far problems. The model algorithm is computationally efficient. The computational complexity is linearly dependent on the neural network size. The effectiveness and efficiency are demonstrated through simulation studies.     

A Gesture Based Interface for Human-Robot Interaction

Service robotics is currently a highly active research area in robotics, with enormous societal potential. Since service robots directly interact with people, finding natural and easy-to-use user interfaces is of fundamental importance. While past work has predominately focussed on issues such as navigation and manipulation, relatively few robotic systems are equipped with flexible user interfaces that permit controlling the robot by natural means. This paper describes a gesture interface for the control of a mobile robot equipped with a manipulator. The interface uses a camera to track a person and recognize gestures involving arm motion. A fast, adaptive tracking algorithm enables the robot to track and follow a person reliably through office environments with changing lighting conditions. Two alternative methods for gesture recognition are compared: a template based approach and a neural network approach. Both are combined with the Viterbi algorithm for the recognition of gestures defined through arm motion (in addition to static arm poses). Results are reported in the context of an interactive clean-up task, where a person guides the robot to specific locations that need to be cleaned and instructs the robot to pick up trash.     

Robotic Tasks Using Path Control: Two Case Studies

Some robotic tasks usually achieved through motion control – trajectory tracking control – can be also well performed by resorting to path control philosophy. This is the case for applications where motion coordination among the robot joints is more important than joint tracking of a timed desired reference. This paper illustrates this concept by means of two academic case studies – theory and experiments – using a two degrees-of-freedom direct-drive revolute arm.     

Care-O-bot II—Development of a Next Generation Robotic Home Assistant

Technical aids allow elderly and handicapped people to live independently and supported in their private homes for a longer time. As a contribution to such technological solutions, two demonstrator platforms for a robotic home assistant—called Care-O-bot—were designed and implemented at Fraunhofer IPA, Stuttgart. Whereas Care-O-bot I is only a mobile platform with a touch screen, Care-O-bot II is additionally equipped with adjustable walking supporters and a manipulator arm. It has the capability to navigate autonomously in indoor environments, be used as an intelligent walking support, and execute manipulation tasks. The control software of Care-O-bot II runs on two industrial PCs and a hand-held control panel. The walking aid module is based on sensors in the walking aid handles and on a dynamic model of conventional walking aids. In direct mode, the user can move along freely with the robot whereas obstacles are detected and avoided. In planned mode, he can specify a target and be lead there by the robotic assistant. Autonomous planning and execution of complex manipulation tasks is based on a symbolic planner and environmental information provided in a database. The user input (graphical and speech input) is transferred to the task planner and adequate actions to solve the task (sequence of motion and manipulation commands) are created. A new method for sensor based manipulation using a tilting laser scanner and camera integrated in the head of the robot has been implemented. Additional sensors in the robot hand increase the grasping capabilities. The walking aid has been tested with elderly users from an assisted living facility and a nursery home. Furthermore, the execution of fetch and carry tasks has been implemented and tested in a sample home environment.     

Optimization Criteria and Geometric Algorithms for Motion and Structure Estimation

Prevailing efforts to study the standard formulation of motion and structure recovery have recently been focused on issues of sensitivity and robustness of existing techniques. While many cogent observations have been made and verified experimentally, many statements do not hold in general settings and make a comparison of existing techniques difficult. With an ultimate goal of clarifying these issues, we study the main aspects of motion and structure recovery: the choice of objective function, optimization techniques and sensitivity and robustness issues in the presence of noise.We clearly reveal the relationship among different objective functions, such as (normalized) epipolar constraints, reprojection error or triangulation, all of which can be unified in a new optimal triangulation procedure. Regardless of various choices of the objective function, the optimization problems all inherit the same unknown parameter space, the so-called essential manifold. Based on recent developments of optimization techniques on Riemannian manifolds, in particular on Stiefel or Grassmann manifolds, we propose a Riemannian Newton algorithm to solve the motion and structure recovery problem, making use of the natural differential geometric structure of the essential manifold.We provide a clear account of sensitivity and robustness of the proposed linear and nonlinear optimization techniques and study the analytical and practical equivalence of different objective functions. The geometric characterization of critical points and the simulation results clarify the difference between the effect of bas-relief ambiguity, rotation and translation confounding and other types of local minima. This leads to consistent interpretations of simulation results over a large range of signal-to-noise ratio and variety of configurations.     

Fast Local and Global Projection-Based Methods for Affine Motion Estimation

The demand for more effective compression, storage, and transmission of video data is ever increasing. To make the most effective use of bandwidth and memory, motion-compensated methods rely heavily on fast and accurate motion estimation from image sequences to compress not the full complement of frames, but rather a sequence of reference frames, along with differences between these frames which results from estimated frame-to-frame motion. Motivated by the need for fast and accurate motion estimation for compression, storage, and transmission of video as well as other applications of motion estimation, we present algorithms for estimating affine motion from video image sequences. Our methods utilize properties of the Radon transform to estimate image motion in a multiscale framework to achieve very accurate results. We develop statistical and computational models that motivate the use of such methods, and demonstrate that it is possible to improve the computational burden of motion estimation by more than an order of magnitude, while maintaining the degree of accuracy afforded by the more direct, and less efficient, 2-D methods.     

Coverage of Known Spaces: The Boustrophedon Cellular Decomposition

Coverage path planning is the determination of a path that a robot must take in order to pass over each point in an environment. Applications include de-mining, floor scrubbing, and inspection. We developed the boustrophedon cellular decomposition, which is an exact cellular decomposition approach, for the purposes of coverage. Essentially, the boustrophedon decomposition is a generalization of the trapezoidal decomposition that could allow for non-polygonalobstacles, but also has the side effect of having more efficient coverage paths than the trapezoidal decomposition. Each cell in the boustrophedon decomposition is covered with simple back and forth motions. Once each cell is covered, then the entire environment is covered. Therefore, coverage is reduced to finding an exhaustive path through a graph which represents the adjacency relationships of the cells in the boustrophedon decomposition. This approach is provably complete and experiments on a mobile robot validate this approach.     

Development of an autonomous underwater robot “Twin-Burger” for testing intelligent behaviors in realistic environments

An autonomous underwater robot named Twin-Burger was developed as a versatile test bed to establish the techniques which realize intelligent robot behaviors. The robot was designed to have necessary functions for complex tasks including cooperative task execution with other robots and divers. The first robot Twin-Burger I was completed and launched in November 1992. This paper describes hardware and software systems of the robot. Motion of the robot is controlled by sliding controllers based on simplified equations of motion which are derived from system identification experiments. Tank tests proved that the robot was able to cruise along a commanded path as a sequence of control actions generated by the sliding controllers. The Distributed Vehicle Management Architecture (DVMA) is applied to the robot as an architecture for the control software. Mission execution experiments shows that the Twin-Burger behaves appropriately according to the mission and environmental conditions.     

Piecewise Overactuation of Parallel Mechanisms Following Singular Trajectories: Modeling,Simulation and Control

The present approach aims at using the principle of redundant actuation for parallel robotic structures in order to follow complex trajectories in a so-called mechanically advantageous way, meaning that for any trajectory configuration the actuators can bear important loads (internal and/or external). Multibody system formalisms using relative coordinates and a robust technique to solve the closed-loop kinematic constraints, which are used for the purpose of modeling, are briefly reviewed. The notion of robot manipulability (and its relation to the velocity and force ellipsoids) is then recalled. As an initial step of the approach developed, suitable locations for the actuators of the non-overactuated system are proposed, the criteria being based on the theoretical concepts mentioned above. Then, according to some possible customer requirements, the number of actuators and their location are optimally specified on the basis of a piecewise trajectory planning. Both static and dynamic aspects are treated, depending on the application. Once the number and the locations of the actuators have been determined, a solution for the overdetermined inverse dynamics is proposed. Finally, the approach is validated via two examples of multibody parallel structures that are modeled, simulated and controlled in a suitable environment.     

Enhancing Randomized Motion Planners: Exploring with Haptic Hints

In this paper, we investigate methods for enabling a human operator and an automatic motion planner to cooperatively solve a motion planning query. Our work is motivated by our experience that automatic motion planners sometimes fail due to the difficulty of discovering critical configurations of the robot that are often naturally apparent to a human observer.Our goal is to develop techniques by which the automatic planner can utilize (easily generated) user-input, and determine natural ways to inform the user of the progress made by the motion planner. We show that simple randomized techniques inspired by probabilistic roadmap methods are quite useful for transforming approximate, user-generated paths into collision-free paths, and describe an iterative transformation method which enables one to transform a solution for an easier version of the problem into a solution for the original problem. We also illustrate that simple visualization techniques can provide meaningful representations of the planner's progress in a 6-dimensional C-space. We illustrate the utility of our methods on difficult problems involving complex 3D CAD Models.     

Supporting the sense of presence in control environments

This paper proposes a notion of presence which overcomes its strict interpretation in terms of physical projection and perception, and interprets the sense of being there as the understanding of the meaning of what is going on there. The domain of control environments is considered to illustrate this point and to propose technological solutions combining principles and techniques taken from Artificial Intelligence and Computer Supported Cooperative Work to enhance the interpretation and cooperation capabilities of the involved actors.     

Integration of 3-D shape construction and assembly to realize micro systems

In order to make micro 3-D structures, we are designing a table-sized factory, namely Nano Manufacturing World (NMW). In NMW, we challenged to use a new process fused by semiconductor process for preciseness and machine process for 3-dimensionality. In order to realize the new process, we designed three new mechanisms in this paper: multi-face shape making beam, co-focus rotational robot and micro mechanical tools. Through an evaluation to actually make a micro Gojunoto with the mechanisms, we confirmed their validities for functions of integration of 3-D shape construction and assembly.     

On the number of Eulerian orientations of a graph

An Eulerian orientation of an undirected Eulerian graph is an orientation of the edges of the graph such that for every vertex the in-degree is equal to the out-degree. Eulerian orientations are natural flow-like structures, and Welsh has pointed out that computing their number corresponds to evaluating the Tutte polynomial at the point (0, –2) [JVW], [Wl], and is further equivalent to evaluating ice-type partition functions in statistical physics [W2]. In this paper we resolve the complexity of counting the number of Eulerian orientations of an arbitrary Eulerian graph.We give an efficient randomized approximation algorithm for counting Eulerian orientations of any Eulerian graph. Our algorithm is based on a reduction to counting perfect matchings for a class of graphs for which the methods of Broder [B], Jerrum and Sinclair [JS1], and others [DL] [DS] apply. A crucial step of the reduction is the Monotonicity Lemma (Lemma 3.1) which is of independent combinatorial interest. Roughly speaking, the Monotonicity Lemma establishes the intuitive fact that increasing the number of constraints applied on a flow problem cannot increase the number of solutions. The proof of the lemma involves a new decomposition technique which decouples problematically overlapping structures (a recurrent obstacle in handling large combinatorial populations) and allows detailed enumeration arguments. As a by-product, we exhibit a class of graphs for which perfect and near-perfect matchings are polynomially related, and hence the permanent can be approximated, for reasons other than short augmenting paths (previously the only known approach).We also give the complementary hardness result, namely, that counting exactly Eulerian orientations is #P-complete. Finally, we provide some connections with counting Euler tours.     

Robot Homing by Exploiting Panoramic Vision

We propose a novel, vision-based method for robot homing, the problem of computing a route so that a robot can return to its initial home position after the execution of an arbitrary prior path. The method assumes that the robot tracks visual features in panoramic views of the environment that it acquires as it moves. By exploiting only angular information regarding the tracked features, a local control strategy moves the robot between two positions, provided that there are at least three features that can be matched in the panoramas acquired at these positions. The strategy is successful when certain geometric constraints on the configuration of the two positions relative to the features are fulfilled. In order to achieve long-range homing, the features trajectories are organized in a visual memory during the execution of the prior path. When homing is initiated, the robot selects Milestone Positions (MPs) on the prior path by exploiting information in its visual memory. The MP selection process aims at picking positions that guarantee the success of the local control strategy between two consecutive MPs. The sequential visit of successive MPs successfully guides the robot even if the visual context in the home position is radically different from the visual context at the position where homing was initiated. Experimental results from a prototype implementation of the method demonstrate that homing can be achieved with high accuracy, independent of the distance traveled by the robot. The contribution of this work is that it shows how a complex navigational task such as homing can be accomplished efficiently, robustly and in real-time by exploiting primitive visual cues. Such cues carry implicit information regarding the 3D structure of the environment. Thus, the computation of explicit range information and the existence of a geometric map are not required.     

Motion control of mechanical manipulators

The theory and implementation results of a recently developed class of adaptive and repetitive controllers used for motion control of robot manipulators are presented. The repetitive controller, which learns the input torque corresponding to a repetitive desired trajectory, requires no explicit knowledge of the manipulator equations of motion. The adaptive controller, on the other hand, which estimates the robot dynamic parameters on-line, may be used for more general trajectories but requires more detailed modeling information. Both schemes are computationally efficient and require no acceleration feedback of any kind; only standard position and velocity feedback information is utilized.The performance of both the adaptive and repetitive controllers was experimentally evaluated on an IBM 7545 robot. The experimental results of these controllers confirm a significant improvement in tracking accuracy over conventional Computed Torque and PD controllers.This work was supported by the National Science Foundation under grant MSS-8910427.     

A New Implementation of Automath

This paper presents aut, a modern Automath checker. It is a straightforward re-implementation of the Zandleven Automath checker from the seventies. It was implemented about five years ago, in the programming language C. It accepts both the AUT-68 and AUT-QE dialects of Automath. This program was written to restore a damaged version of Jutting's translation of Landau's Grundlagen. Some notable features: It is fast. On a 1 GHz machine it will check the full Jutting formalization (736 K of nonwhitespace Automath source) in 0.6 seconds. Its implementation of -terms does not use named variables or de Bruijn indices (the two common approaches) but instead uses a graph representation. In this representation variables are represented by pointers to a binder. The program can compile an Automath text into one big Automath single line-style -term. It outputs such a term using de Bruijn indices. (These -terms cannot be checked by modern systems like Coq or Agda, because the -typed -calculi of de Bruijn are different from the -typed -calculi of modern type theory.)The source of aut is freely available on the Web at the address .     

Cooperative Navigation of Micro-Rovers Using Color Segmentation

This paper addresses position estimation of a micro-rover mobile robot (called the daughter) as a larger robot (the mother) tracks it through large spaces with unstructured lighting. Position estimation is necessary for localization, where the mother extracts the relative position of the daughter for mapping purposes, and for cooperative navigation, where the mother controls the daughter in real-time. The approach taken is to employ the Spherical Coordinate Transform color segmenter developed for medical applications as a low computational and hardware cost solution. Data was collected from 50 images taken in five types of lighting: fluorescent, tungsten, daylight lamp, natural daylight indoors and outdoors. The results show that average pixel error was 1.5, with an average error in distance estimation of 6.3 cm. The size of the error did not vary greatly with the type of lighting. The segmentation and distance tracking have also been implemented as a real-time tracking system. Using this system, the mother robot is able to autonomously control the micro-rover and display a map of the daughter's path in real-time using only a Pentium class processor and no specialized hardware.     

End-to-end communications management using TMN “X” interfaces

The ongoing integration of LANs and WANs to support global communications and businesses and the emergence of integrated broadband communication services has created an increased demand for cooperation between customers, network and service providers to achieve end-to-end service management. Such a cooperation between autonomous authorities, each defining their own administrative management domains, requires the application of an open standardized framework to facilitate and regulate interworking. Such a framework is given by the ITU-T recommendations on TMN, where the so-called X interface is of particular importance for inter-domain management. In this paper, we explain the role of the TMN X interface within an inter-domain TMN architecture supporting end-to-end communications management. We identify the important issues that need to be addressed for the definition and realization of TMN X interfaces and report about our practical experiences with the implementation of TMN X interfaces in the PREPARE project.     

Observability of 3D Motion

This paper examines the inherent difficulties in observing 3D rigid motion from image sequences. It does so without considering a particular estimator. Instead, it presents a statistical analysis of all the possible computational models which can be used for estimating 3D motion from an image sequence. These computational models are classified according to the mathematical constraints that they employ and the characteristics of the imaging sensor (restricted field of view and full field of view). Regarding the mathematical constraints, there exist two principles relating a sequence of images taken by a moving camera. One is the epipolar constraint, applied to motion fields, and the other the positive depth constraint, applied to normal flow fields. 3D motion estimation amounts to optimizing these constraints over the image. A statistical modeling of these constraints leads to functions which are studied with regard to their topographic structure, specifically as regards the errors in the 3D motion parameters at the places representing the minima of the functions. For conventional video cameras possessing a restricted field of view, the analysis shows that for algorithms in both classes which estimate all motion parameters simultaneously, the obtained solution has an error such that the projections of the translational and rotational errors on the image plane are perpendicular to each other. Furthermore, the estimated projection of the translation on the image lies on a line through the origin and the projection of the real translation. The situation is different for a camera with a full (360 degree) field of view (achieved by a panoramic sensor or by a system of conventional cameras). In this case, at the locations of the minima of the above two functions, either the translational or the rotational error becomes zero, while in the case of a restricted field of view both errors are non-zero. Although some ambiguities still remain in the full field of view case, the implication is that visual navigation tasks, such as visual servoing, involving 3D motion estimation are easier to solve by employing panoramic vision. Also, the analysis makes it possible to compare properties of algorithms that first estimate the translation and on the basis of the translational result estimate the rotation, algorithms that do the opposite, and algorithms that estimate all motion parameters simultaneously, thus providing a sound framework for the observability of 3D motion. Finally, the introduced framework points to new avenues for studying the stability of image-based servoing schemes.