In this paper we present the application of the Null-Space-based Behavioral (NSB) approach to the motion control of mobile robots with velocity saturated actuators. The NSB is a behavior-based robot control approach that uses a hierarchical organization of the tasks to guarantee that they are executed according to a desired priority: it uses a projection technique to avoid that, in the absence of actuator saturations, low-priority tasks could influence higher-priority tasks. The main contribution of this paper is the extension of the NSB approach to the case where actuator velocity saturation bounds are explicitly taken into account. The proposed solution dynamically scales task velocity commands so that the hierarchy of task priorities is preserved in spite of actuator velocity saturations. The approach has been validated on two specific case studies. In the first case, the NSB elaborates the motion directives for a single mobile robot that has to reach a target while avoiding a point obstacle; in this case, the mission is composed of two tasks. In the second case, the NSB elaborates the motion directives for a team of six mobile robots that has to entrap and escort a target; in this case the mission is composed of four tasks. The approach is validated by numerical simulations and by experiments with real mobile robots.

The inherent uncertainty associated with unstructured environments makes establishing a successful grasp difficult. Traditional approaches to this problem involve hands that are complex, fragile, require elaborate sensor suites, and are difficult to control. Alternatively, by carefully designing the mechanical structure of the hand to incorporate features such as compliance and adaptability, the uncertainty inherent in unstructured grasping tasks can be more easily accommodated. In this paper, we demonstrate a novel adaptive and compliant grasper that can grasp objects spanning a wide range of size, shape, mass, and position/orientation using only a single actuator. The hand is constructed using polymer-based Shape Deposition Manufacturing (SDM) and has superior robustness properties, making it able to withstand large impacts without damage. We also present the results of two experiments to demonstrate that the SDM Hand can reliably grasp objects in the presence of large positioning errors, while keeping acquisition contact forces low. In the first, we evaluate the amount of allowable manipulator positioning error that results in a successful grasp. In the second experiment, the hand autonomously grasps a wide range of spherical objects positioned randomly across the workspace, guided by only a single image from an overhead camera, using feed-forward control of the hand.

A survey of mining accidents has revealed that over 30% of all truck loading accidents can be addressed by providing dipper positioning feedback to the shovel operator. In this paper, a novel approach is presented for estimating a mining shovel's dipper pose to obtain its arm geometry in real-time utilizing a two-dimensional laser scanner. The low spatial resolution of laser scanners and the need for accurate initialization challenge the reliability and accuracy of most laser-scanner-based object tracking methods. This work addresses these issues by using the shovel dipper's kinematics model and position history, in conjunction with the dipper geometrical model, to track the dipper in space. The proposed method uses a bootstrap particle filter with a distance transformation in order to perform a global search in the workspace. The particle filter's result is then used as the initial pose for an Iterative Closest Point algorithm that increases the accuracy of the pose estimate. The proposed method can be applied to other laser scanner-based object tracking applications in outdoor environments. Experiments performed on a mining shovel demonstrate the reliability, accuracy, and computational efficiency of the proposed approach. Moreover, using a single proximal sensor can simplify mounting, reduce maintenance costs and machine down time, and enhance tracking reliability.

The growing interest in robot teams for surveillance or rescue missions entails new technological challenges. Robots have to move to complete their tasks while maintaining communication among themselves and with their human operators, in many cases without the aid of a communication infrastructure. Guaranteeing connectivity enables robots to explicitly exchange information needed in collaborative task execution, and allows operators to monitor or manually control any robot at all times. Network paths should be multi-hop, so as not to unnecessarily restrict the team's range. In this work we contribute a complete system which integrates three research aspects, usually studied separately, to achieve these characteristics: a multi-robot cooperative motion control technique based on a virtual spring–damper model which prevents communication network splits, a task allocation algorithm that takes advantage of network link information in order to ensure autonomous mission completion, and a network layer which works over wireless 802.11 devices, capable of sustaining hard real-time traffic and changing topologies. Link quality among peers is the key metric used to cooperatively move the robots and maintain uninterrupted connectivity, and the basis for novel ideas presented in each subsystem. Simulations and experimental results with real robots are presented and discussed.

In this paper we describe the design and control algorithms of Amour, a low-cost autonomous underwater vehicle (AUV) capable of missions of marine survey and monitoring. Amour is a highly maneuverable robot capable of hovering and carrying dynamic payloads during a single mission. The robot can carry a variety of payloads. It uses internal buoyancy and balance control mechanisms to achieve power efficient motions regardless of the payload size. Amour is designed to operate in synergy with a wireless underwater sensor network (WUSN) of static nodes. The robot's payload was designed in order to deploy, relocate and recover the static sensor nodes. It communicates with the network acoustically for signaling and localization and optically for data muling. We present control algorithms, navigation algorithms, and experimental data from pool and ocean trials with Amour that demonstrate its basic navigation capabilities, power efficiency, and ability to carry dynamic payloads.

Motion planning for spatially constrained robots is difficult due to additional constraints placed on the robot, such as closure constraints for closed chains or requirements on end-effector placement for articulated linkages. It is usually computationally too expensive to apply sampling-based planners to these problems since it is difficult to generate valid configurations. We overcome this challenge by redefining the robot's degrees of freedom and constraints into a new set of parameters, called reachable distance space (RD-space), in which all configurations lie in the set of constraint-satisfying subspaces. This enables us to directly sample the constrained subspaces with complexity linear in the number of the robot's degrees of freedom. In addition to supporting efficient sampling of configurations, we show that the RD-space formulation naturally supports planning and, in particular, we design a local planner suitable for use by sampling-based planners. We demonstrate the effectiveness and efficiency of our approach for several systems including closed chain planning with multiple loops, restricted end-effector sampling, and on-line planning for drawing/sculpting. We can sample single-loop closed chain systems with 1,000 links in time comparable to open chain sampling, and we can generate samples for 1,000-link multi-loop systems of varying topologies in less than a second.

We describe a practical path-planning algorithm for an autonomous vehicle operating in an unknown semi-structured (or unstructured) environment, where obstacles are detected online by the robot's sensors. This work was motivated by and experimentally validated in the 2007 DARPA Urban Challenge, where robotic vehicles had to autonomously navigate parking lots. The core of our approach to path planning consists of two phases. The first phase uses a variant of A* search (applied to the 3D kinematic state space of the vehicle) to obtain a kinematically feasible trajectory. The second phase then improves the quality of the solution via numeric non-linear optimization, leading to a local (and frequently global) optimum. Further, we extend our algorithm to use prior topological knowledge of the environment to guide path planning, leading to faster search and final trajectories better suited to the structure of the environment. We present experimental results from the DARPA Urban Challenge, where our robot demonstrated near-flawless performance in complex general path-planning tasks such as navigating parking lots and executing U-turns on blocked roads. We also present results on autonomous navigation of real parking lots. In those latter tasks, which are significantly more complex than the ones in the DARPA Urban Challenge, the time of a full replanning cycle of our planner is in the range of 50–300 ms.

This paper presents a new method for calculating operational-space inertia matrices, and other related quantities, for branched kinematic trees. It is based on the exploitation of branch-induced sparsity in the joint-space inertia matrix and the task Jacobian. Detailed cost figures are given for the new method, and its efficacy is demonstrated by means of a realistic example based on the ASIMO Next-Generation humanoid robot. In this example, the new method is shown to be 6.7 times faster than the basic matrix method, and 1.6 times faster than the efficient low-order algorithm of Rodriguez et al. Furthermore, cost savings of more than 50,000 arithmetic operations are obtained in the calculation of the inertia-weighted pseudoinverse of the task Jacobian and its null-space projection matrix. Additional examples are considered briefly, in order to further compare the new method with the algorithm of Rodriguez et al.

This paper is concerned with the problem of estimating the relative translation and orientation of an inertial measurement unit and a camera, which are rigidly connected. The key is to realize that this problem is in fact an instance of a standard problem within the area of system identification, referred to as a gray-box problem. We propose a new algorithm for estimating the relative translation and orientation, which does not require any additional hardware, except a piece of paper with a checkerboard pattern on it. The method is based on a physical model which can also be used in solving, for example, sensor fusion problems. The experimental results show that the method works well in practice, both for perspective and spherical cameras.

In this paper we describe a new image-based approach to tracking the six-degree-of-freedom trajectory of a stereo camera pair. The proposed technique estimates the pose and subsequently the dense pixel matching between temporal image pairs in a sequence by performing dense spatial matching between images of a stereo reference pair. In this way a minimization approach is employed which directly uses all grayscale information available within the stereo pair (or stereo region) leading to very robust and precise results. Metric 3D structure constraints are imposed by consistently warping corresponding stereo images to generate novel viewpoints at each stereo acquisition. An iterative non-linear trajectory estimation approach is formulated based on a quadrifocal relationship between the image intensities within adjacent views of the stereo pair. A robust M-estimation technique is used to reject outliers corresponding to moving objects within the scene or other outliers such as occlusions and illumination changes. The technique is applied to recovering the trajectory of a moving vehicle in long and difficult sequences of images.

In this paper we develop a new framework for path planning of flexible needles with bevel tips. Based on a stochastic model of needle steering, the probability density function for the needle-tip pose is approximated as a Gaussian. The means and covariances are estimated using an error propagation algorithm which has second-order accuracy. Then we adapt the path-of-probability (POP) algorithm to path planning of flexible needles with bevel tips. We demonstrate how our planning algorithm can be used for feedback control of flexible needles. We also derive a closed-form solution for the port placement problem for finding good insertion locations for flexible needles in the case when there are no obstacles. Furthermore, we propose a new method using reference splines with the POP algorithm to solve the path planning problem for flexible needles in more general cases that include obstacles.

A fundamental requirement of any autonomous robot system is the ability to predict the affordances of its environment. The set of affordances define the actions that are available to the agent given the robot's context. A standard approach to affordance learning is direct perception, which learns direct mappings from sensor measurements to affordance labels. For example, a robot designed for cross-country navigation could map stereo depth information and image features directly into predictions about the traversability of terrain regions. While this approach can succeed for a small number of affordances, it does not scale well as the number of affordances increases. In this paper, we show that visual object categories can be used as an intermediate representation that makes the affordance learning problem scalable. We develop a probabilistic graphical model which we call the Category–Affordance (CA) model, which describes the relationships between object categories, affordances, and appearance. This model casts visual object categorization as an intermediate inference step in affordance prediction. We describe several novel affordance learning and training strategies that are supported by our new model. Experimental results with indoor mobile robots evaluate these different strategies and demonstrate the advantages of the CA model in affordance learning, especially when learning from limited size data sets.

In this paper we explore a topological perspective of planning in the presence of uncertainty, focusing on tasks specified by goal states in discrete spaces. We introduce strategy complexes. A strategy complex is the collection of all plans for attaining all goals in a given space. Plans are like jigsaw pieces. Understanding how the pieces fit together in a strategy complex reveals structure. That structure characterizes the inherent capabilities of an uncertain system. By adjusting the jigsaw pieces in a design loop, one can build systems with desired competencies. The paper draws on representations from combinatorial topology, Markov chains, and polyhedral cones. Triangulating between these three perspectives produces a topological language for describing concisely the capabilities of uncertain systems, analogous to the concepts of reachability and controllability in other disciplines. The major nouns in this language are topological spaces. Three key theorems illustrate the sentences in this language. (a) Goal attainability: There exists a strategy for attaining a particular goal from anywhere in a system if and only if the strategy complex of a slightly modified system is homotopic to a sphere. (b) Full controllability: A system can move between any two states despite control uncertainty precisely when its strategy complex is homotopic to a sphere of dimension two less than the number of states. (c) General structure: Any system's strategy complex is homotopic to the product of a spherical part, modeling full controllability on subspaces, and a general part, modeling adversarial capabilities. This paper contains a number of additional results required as stepping stones, along with many examples. We provide algorithms for computing the key structures described. Finally, we show that some interesting questions are hard. For instance, it is NP-complete to determine the most precisely attainable goal of a system with perfect sensing, but uncertain control.

In this work, we study the inconsistency problem of extended Kalman filter (EKF)-based simultaneous localization and mapping (SLAM) from the perspective of observability. We analytically prove that when the Jacobians of the process and measurement models are evaluated at the latest state estimates during every time step, the linearized error-state system employed in the EKF has an observable subspace of dimension higher than that of the actual, non-linear, SLAM system. As a result, the covariance estimates of the EKF undergo reduction in directions of the state space where no information is available, which is a primary cause of the inconsistency. Based on these theoretical results, we propose a general framework for improving the consistency of EKF-based SLAM. In this framework, the EKF linearization points are selected in a way that ensures that the resulting linearized system model has an observable subspace of appropriate dimension. We describe two algorithms that are instances of this paradigm. In the first, termed observability constrained (OC)-EKF, the linearization points are selected so as to minimize their expected errors (i.e. the difference between the linearization point and the true state) under the observability constraints. In the second, the filter Jacobians are calculated using the first-ever available estimates for all state variables. This latter approach is termed first-estimates Jacobian (FEJ)-EKF. The proposed algorithms have been tested both in simulation and experimentally, and are shown to significantly outperform the standard EKF both in terms of accuracy and consistency.

Minimally invasive cardiac surgery offers important benefits for the patient but it also imposes several challenges for the surgeon. Robotic assistance has been proposed to overcome many of the difficulties inherent to the minimally invasive procedure, but so far no solutions for compensating physiological motion are present in the existing surgical robotic platforms. In beating heart surgery, cardiac and respiratory motions are important sources of disturbance, hindering the surgeon's gestures and limiting the types of procedures that can be performed in a minimally invasive fashion. In this context, computer vision techniques can be used for retrieving the heart motion for active motion stabilization, which improves the precision and repeatability of the surgical gestures. However, efficient tracking of the heart surface is a challenging problem due to the heart surface characteristics, large deformations and the complex illumination conditions. In this article, we present an efficient method for active cancellation of cardiac motion where we combine an efficient algorithm for 3D tracking of the heart surface based on a thin-plate spline deformable model and an illumination compensation algorithm able to cope with arbitrary illumination changes. The proposed method has two novelties: the thin-plate spline model for representing the heart surface deformations and an efficient parametrization for 3D tracking of the beating heart using stereo images from a calibrated stereo endoscope. The proposed tracking method has been evaluated offline on in vivo images acquired by a DaVinci surgical robotic platform.

In this paper, we present a game-theoretic analysis of a visibility-based pursuit–evasion game in a planar environment containing obstacles. The pursuer and the evader are holonomic having bounded speeds. Both players have a complete map of the environment. Both players have omnidirectional vision and have knowledge about each other's current position as long as they are visible to each other. The pursuer wants to maintain visibility of the evader for the maximum possible time and the evader wants to escape the pursuer's sight as soon as possible. Under this information structure, we present necessary and sufficient conditions for surveillance and escape. We present strategies for the players that are in Nash equilibrium. The strategies are a function of the value of the game. Using these strategies, we construct a value function by integrating the adjoint equations backward in time from the termination situations provided by the corners in the environment. From these value functions we recompute the control strategies for the players to obtain optimal trajectories for the players near the termination situation. This is the first work that presents the necessary and sufficient conditions for tracking for a visibility based pursuit–evasion game and presents the equilibrium strategies for the players.

Wide-angle images exhibit significant distortion for which existing scale-space detectors such as the scale-invariant feature transform (SIFT) are inappropriate. The required scale-space images for feature detection are correctly obtained through the convolution of the image, mapped to the sphere, with the spherical Gaussian. A new visual keypoint detector, based on this principle, is developed and several computational approaches to the convolution are investigated in both the spatial and frequency domain. In particular, a close approximation is developed that has comparable computation time to conventional SIFT but with improved matching performance. Results are presented for monocular wide-angle outdoor image sequences obtained using fisheye and equiangular catadioptric cameras. We evaluate the overall matching performance (recall versus 1-precision) of these methods compared to conventional SIFT. We also demonstrate the use of the technique for variable frame-rate visual odometry and its application to place recognition.

The ability to represent knowledge about space and its position therein is crucial for a mobile robot. To this end, topological and semantic descriptions are gaining popularity for augmenting purely metric space representations. In this paper we present a multi-modal place classification system that allows a mobile robot to identify places and recognize semantic categories in an indoor environment. The system effectively utilizes information from different robotic sensors by fusing multiple visual cues and laser range data. This is achieved using a high-level cue integration scheme based on a Support Vector Machine (SVM) that learns how to optimally combine and weight each cue. Our multi-modal place classification approach can be used to obtain a real-time semantic space labeling system which integrates information over time and space. We perform an extensive experimental evaluation of the method for two different platforms and environments, on a realistic off-line database and in a live experiment on an autonomous robot. The results clearly demonstrate the effectiveness of our cue integration scheme and its value for robust place classification under varying conditions.

In this paper, the roll and pitch dynamics of a biologically inspired quadruped water runner robot are analyzed, and a stable robot design is proposed and tested. The robot's foot–water interaction force is derived using drag equations. Roll direction instability is attributed to a small roll moment of inertia and large instantaneous roll moments generated by the foot–water interaction forces. Roll dynamics are modeled by approximating the water as a linear spring. Using this model, estimates on the roll moment of inertia that can endure moments generated by water interactions are derived. Instability in the pitch direction is caused by the thrust force the four feet exert on the water. To correct this, a circular tail which can negate the pitch moment around the center of mass is proposed. Both passive and active tail designs which can cope with disturbances are introduced. Based on these analyses, a stable water runner is designed, and built. Experimental high-speed video footage demonstrates the stable roll and pitch motion of the robot. Simulations are used to estimate robustness against disturbances, waves, and leg running frequency variations. It is found that roll motion is more sensitive to disturbances when compared with the pitch direction.

The increasing demand for physical interaction between humans and robots has led to an interest in robots that guarantee safe behavior when human contact occurs. However, attaining established levels of performance while ensuring safety creates formidable challenges in mechanical design, actuation, sensing and control. To promote safety without compromising performance, a human-friendly robotic arm has been developed using the concept of hybrid actuation. The new design employs high-power, low-impedance pneumatic artificial muscles augmented with small electrical actuators, distributed compact pressure regulators with proportional valves, and hollow plastic links. The experimental results show that significant performance improvement can be achieved with hybrid actuation over a system with pneumatic muscles alone. In this paper we evaluate the safety of the new robot arm through experiments and simulation, demonstrating that its inertia/power characteristics surpass those of previous human-friendly robots we have developed.