Autonomous navigation through unstructured terrains has been most effectively demonstrated by animals, who utilize a large set of locomotive styles to move through their native habitats. While legged robots have recently demonstrated several of these locomotion modalities (such as walking, running, jumping, and climbing vertical walls), motion planners have yet to be able to leverage these unique mobility characteristics. In this article, we outline some of the specific motion planning challenges faced when attempting to plan for legged systems with dynamic gaits, with specific instances of these demonstrated by the dynamic climbing platform TAILS. Using a unique implementation of sampling-based model predictive optimization, we demonstrate the ability to motion plan around obstacles on vertical walls and experimentally demonstrate this on TAILS by navigating through traditionally difficult narrow gap problems.

Energy-efficient navigation is an important technology for mobile robots because of its potential to increase the operation time of the robot. In particular, when coupled with a dynamic legged quadruped, the need for energy savings is made more apparent as payloads are limited. Due to the complexity in modeling motion and power models of these robots, a new approach is necessary to effectively motion plan for these complex robots. We accomplish this by using Sampling-Based Model Predictive optimization (SBMPO) which was extended for use on the LLAMA quadrupedal platform in simulation. SBMPO allows for direct generation of trajectories while using a heuristic-based search to speed up computations. This approach is shown to effectively motion plan while optimizing for energy consumption and maintaining the natural dynamics of the robot in a simulated environment.

Most wheelchairs have low directional stability due to their wheel-drive system configurations. Hence, when a wheelchair experiences excessive slip, it will create an uncontrollable moment that changes its heading direction, endangering the safety of the wheelchair user. This paper presents an approach to longitudinal slip reduction (or traction control) for an Electric Powered Wheelchair that uses a variable reference model, which is a mass-damper system. The position of a joystick is mapped to force and torque values, which are the input to this model. The output is the desired trajectory, which is fed to a trajectory tracking controller. The key idea is that if slip occurs, the applied torque to the wheels is reduced by decreasing the desired acceleration, which is achieved by changing the parameters of the reference model. In this study, the mass of the reference model is changed. The proposed slip reduction approach is validated via experiments.

For efficient and safe locomotion the gaits of legged robots should vary with the type of terrain. Hence, terrain surface classification is an important problem for this class of mobile robots. Prior research has developed approaches to proprioceptive terrain classification for both wheeled and limbed robots that use sensor measurements dependent upon the dynamics of the robot, which ultimately requires the classification system to be trained at a large number of operating conditions (e.g., vehicle speeds and loads). This research develops an approach to terrain identification based on pressure images generated through direct surface contact using a robot skin constructed around a high-resolution pressure sensing array. Terrain signatures for classification are formulated from the magnitude frequency responses of the pressure images. The methodology is used to train and test a classifier using dynamically measured pressure images from a one-legged hopping robot. Experimental tests yield high classification accuracies, which are independent with respect to changing robot dynamics (i.e., different leg gaits). The findings of this paper suggest the methodology can be extended to autonomous field robots, providing the robot with crucial information about the environment that can be used to aid stability over rough terrains and enhance motion planning over varying terrains.

An important application of neural networks is the identification of the dynamics of a nonlinear system with no known closed-form model, especially a system whose dynamic behavior may change with time. When this is done quickly and robustly, the model may be used for closed-loop Nonlinear Model Predictive Control (NMPC). NMPC methods that rely on linearization about an equilibrium point or excessive parameter tuning require a priori information that limits the robustness of those methods for a system with changing dynamic behavior. This paper presents a novel method for adaptive NMPC of multiple input, multiple output (MIMO) systems, called Sampling Based Model Predictive Control (SBMPC) that, like most MPC approaches, has the ability to enforce hard constraints on the system inputs and states. However, unlike other NMPC methods, it does not rely on linearizing the system or gradient based optimization. Instead, it discretizes the input space to the model via pseudo-random sampling and feeds the sampled inputs through the nonlinear plant, hence producing a graph for which an optimal path can be found using an efficient graph search method such as A* optimization. Although SBMPC can be applied to any form of a nonlinear model, here a radial basis function neural network is used to model the nonlinear system due to its ability to represent a very general class of nonlinear systems. Using the Minimal Resource Allocation Network (MRAN) learning algorithm, the neural network size and parameter values may be adjusted even while the controller is active. After presenting the general methodology, Adaptive SBMPC is used in simulation to control the chemical concentrations of flue gas exiting a steam boiler's combustion chamber, represented by a 3-state time-varying nonlinear model with two inputs and three outputs.

In real world motion planning tasks, autonomous vehicles can easily deviate away from their planned trajectories due to external disturbances, uncertain wheel/leg-terrain interaction, and other errors in the model used for planning. A possible solution to this problem consists in the continuous usage of replanning strategies. However, replanning is in general computationally intensive and its use should be minimized when possible. In this paper, a new methodology for robust trajectory tracking is proposed. The method generates, via sampling, correcting control inputs to drive the vehicle back to the desired trajectory. Due to the use of sampling, the methodology easily incorporates nonlinear planning models and integrates seamlessly with sampling-based motion planners. The paper presents simulation and preliminary experimental results showing the efficacy of the proposed approach and thus its potential application to motion planning tasks with real-time constraints.

Autonomous ground vehicles operating in the field are likely to be faced with several mobility challenges such as piles of rubble, water crossings, steep hills, mud, and stiff vegetation patches. These scenarios are particularly critical for smaller robots with torque and power limited actuators, which as experimentally shown in this work can easily fail to accomplish their tasks in these environments. This paper motivates and provides a methodology that integrates the robot, actuator and terrain models with an efficient motion planner to exploit the vehicle momentum as a way to successfully traverse these difficult terrains. In particular, experimental results showing the efficacy of the proposed methodology are presented for a vegetation patch and a steep hill. Finally, a discussion of the necessary perception work to fully automate the process is included.

Stochastic Clustering Auctions (SCAs) constitute a class of cooperative auction methods that enable improvement of the global cost of the task allocations obtained with fast greedy algorithms. Prior research had developed Contracts Sequencing Algorithms (CSAs) that are deterministic and enable transfers, swaps, and other types of contracts between team members. In contrast to CSAs, SCAs use stochastic transfers or swaps between the task clusters assigned to each team member and have algorithm parameters that can enable tradeoffs between optimality and computational and communication requirements. The first SCA was based on a “Gibbs Sampler” and constrained the stochastic cluster reallocations to simple single transfers or swaps; it is applicable to heterogeneous teams. Subsequently, a more efficient SCA was developed, based on the generalized Swendsen-Wang method; it achieves the increased efficiency by connecting tasks that appear to be synergistic and then stochastically reassigning these connected tasks, hence enabling more complex and efficient movements between clusters than the first SCA. However, its application was limited to homogeneous teams. The contribution of this work is to present an efficient SCA for heterogeneous teams; it is based on a modified Swendsen-Wang method. For centralized auctioning and homogeneous teams, extensive numerical experiments were used to provide a comparison in terms of costs and computational and communication requirements of the three SCAs and a baseline CSA. It was seen that the new SCA maintains the efficiency of the second SCA and can yield similar performance to the baseline CSA in far fewer iterations. The same metrics were used to evaluate the performance of the new SCA for heterogeneous teams. A distributed version of the new SCA was also evaluated in numerical experiments. The results show that, as expected, the distributed SCA continually improves the global performance with each iteration, but converges to a lower cost solution than the centralized SCA.

This article considers the problem of optimal task allocation for heterogeneous teams, for example, teams of heterogeneous robots or human-robot teams. It is well-known that this problem is NP-hard and hence computationally feasible approaches must develop an approximate solution. Here, we propose a solution via a Stochastic Clustering Auction (SCA) that uses a Markov chain search process along with simulated annealing. This is the first stochastic auction method used in conjunction with global optimization. It is based on stochastic transfer and swap moves between the clusters of tasks assigned to the various robots and considers not only downhill movements, but also uphill movements, which can avoid local minima. A novel feature of this algorithm is that, by tuning the annealing suite and turning the uphill movements on and off, the global team performance after algorithm convergence can slide in the region between the global optimal performance and the performance associated with a random allocation. Extensive numerical experiments are used to evaluate the performance of SCA in terms of costs and computational and communication requirements. For centralized auctioning, the SCA algorithm is compared to fast greedy auction algorithms. Distributed auctioning is then compared with centralized SCA.

Terrain classification is key to using terrain dependent control modes to improve performance of autonomous ground vehicles (AGVs). One of the most viable forms of terrain classification, reaction-based terrain classification, is subject to the problem of speed and load dependency, which requires collecting large data sets for algorithm training. The research presented here presents a method of interpolating point clouds called Singular Value Decomposition Interpolation or SVDI, which uses singular value decomposition, matrix logarithms and Catmull-Rom splines. The estimated point clouds can then substitute for empirical training data, thereby reducing the need to collect large data sets for algorithm training. Here, SVDI is applied to the problem of speed dependency using a mobile robot. Although it is seen that interpolated point clouds are not as effective as real data, interpolated point clouds are seen to be more effective than known point clouds that do not correspond to the desired vehicle speed. Therefore it is concluded that SVDI can effectively reduce the speed and load dependence of reaction-based terrain classification.

The motors or engines of an autonomous ground vehicles (AGV) have torque and power limitations, which limit their abilities to climb steep hills, which are defined to be hills that have high grade sections in which the vehicle is forced to decelerate. Traversal of a steep hill requires the vehicle to have sufficient momentum before entering the hill. This problem is part of a larger class of momentum-based motion planning problems such as the problem of lifting heavy objects with manipulators. Hence, solutions to the steep hill climbing problem have much wider applicability. The motion planning here is accomplished using a dynamic model of the skid-steered AGV used in the experiments along with Sampling Based Model Predictive Control (SBMPC), a recently developed input sampling planning algorithm that may be viewed as a generalization of LPA* to the direct use of kinodynamic models. The motion planning is demonstrated experimentally using two scenarios, one in which the robot starts at rest at the bottom of a hill and one in which the robot starts at rest a distance from the hill. The first scenario requires the AGV to first reverse direction so that the vehicle can gather enough momentum before reaching the hill. This corresponds to having the vehicle begin at a local minimum, which results in a problem that many traditional model predictive control methods cannot solve. It is seen that, whereas open loop trajectories can lead to vehicle immobilization, SBMPC successfully uses the information provided by the dynamic model to ensure that the AGV has the requisite momentum.

This paper presents an efficient algorithm to achieve accurate subpixel matchings for calculating correspondences between stereo images based on a path-based matching algorithm. Compared with point-by-point stereo-matching algorithms, path-based algorithms resolve local ambiguities by maximizing the cross correlation (or other measurements) along a path, which can be implemented efficiently using dynamic programming. An effect of the global matching criterion is that cross correlations at all pixels contribute to the criterion; since cross correlation can change significantly even with subpixel changes, to achieve subpixel accuracy, it is no longer sufficient to first find the path that maximizes the criterion at integer pixel locations and then refine to subpixel accuracy. In this paper, by writing bilinear interpolation using integral images, we show that cross correlations at all subpixel locations can be computed efficiently and, thus, lead to a subpixel accuracy path-based matching algorithm. Our results show the feasibility of the method and illustrate significant improvement over existing path-based matching methods.

The need for terrain-dependent control systems on AGVs is evident when considering the variety of outdoor terrains many AGVs encounter. Although the idea of using terrain classification algorithms to identify the terrain and then update the control modes is well-established, the problem of how to intelligently update the control modes based on classifications has been left relatively unaddressed. This paper presents a simplistic rule, called the update rule, which decides when to change control modes based on past and present terrain classifications and is tuned using empirical data. Using experimental data from the experimental Unmanned Vehicle (XUV) mobile robot, this update rule is shown here to be both robust to misclassiflcations as well as sensitive to terrain transitions. This paper also develops and implements a sliding horizon approach to reaction-based terrain classification for improved sensitivity to terrain transitions. The update rule structure presented here is applicable to reaction and vision based terrain classification of individual terrains.

It will be shown that the global cost of the task allocations obtained with fast greedy algorithms can be improved upon by using a class of auction methods called Stochastic Clustering Auctions (SCAs). SCAs use stochastic transfers or swaps between the task clusters assigned to each team member, allow both uphill and downhill cost movements, and rely on simulated annealing. The choice of a key annealing parameter and turning the uphill movements on and off enables the converged solution of a SCA to slide in the region between the global optimal performance and the performance associated with a random allocation. The first SCA, called GSSCA, was based on a Gibbs Sampler, which constrained the stochastic cluster reallocations to simple single transfers or swaps. This paper presents a new and more efficient SCA, called SWSCA, based on the generalized Swendsen-Wang method that enables more complex and efficient movements between clusters by connecting tasks that appear to be synergistic and then stochastically reassigning these connected tasks. For centralized auctioning, extensive numerical experiments are used to compare the performance of SWSCA with GSSCA in terms of costs and computational and communication requirements. Distributed SWSCA is then compared with centralized SWSCA using communication links between robots that were motivated by a generic topology called a “scale free network”.

Skid-steered vehicles are often used as outdoor mobile robots due to their robust mechanical structure and high maneuverability. Sliding, along with rolling, is inherent to general curvilinear motion, which makes both kinematic and dynamic modeling difficult. For the purpose of motion planning, this paper develops and experimentally verifies dynamic models of a skid-steered wheeled vehicle for general planar (2-D) motion and for linear 3-D motion. These models are characterized by the coefficient of rolling resistance, the coefficient of friction, and the shear deformation modulus, which have terrain-dependent values. The dynamic models also include motor saturation and motor power limitations, which enable correct prediction of vehicle velocities when traversing on hills. It is shown that the closed-loop system that results from inclusion of the dynamics of the [proportional--integral--derivative (PID)] speed controllers for each set of wheels does a much better job than the open-loop model of predicting the vehicle linear and angular velocities. For a vehicle turning with small linear and angular accelerations, the model provides accurate predictions of velocities and reasonable predictions of torques. Hence, the closed-loop model is recommended for motion planning.

Analysis of the power consumption of a robotic ground vehicle (RGV) is important for planning since it enables motion plans that do not violate the power limitations of the motors, energy efficient path planning, prediction of the ability to complete a task based upon the vehicle's current energy supply, and estimation of when the vehicle will need to refuel or recharge. Power modeling is particularly difficult for skid steered vehicles because of the complexities of properly taking into account the skidding that is used for vehicle turning. This paper begins with a 2-dimensional, second order differential equation of a skid steered, wheeled RGV and shows that the power model is terrain dependent and is a function of both the turning radius and linear velocity of the vehicle. This model was verified experimentally, and a comprehensive set of experiments was performed to describe the power consumption of a skid steered RGV on asphalt.

To increase autonomous ground vehicle (AGV) safety and efficiency on outdoor terrains the vehicle's control system should have settings for individual terrain surfaces. A first step in such a terrain-dependent control system is classification of the surface upon which the AGV is traversing. This paper considers vision-based terrain surface classification for the path directly in front of the vehicle (¿ 1 m). Most visionbased terrain classification has focused on terrain traversability and not on terrain surface classification. The few approaches to classifying traversable terrain surfaces, with the exception of the use of infrared cameras to classify mud, have relied on stand-alone cameras that are designed for daytime use and are not expected to perform well in the dark. In contrast, this research uses a laser stripe-based structured light sensor, which uses a laser in conjunction with a camera, and hence can work at night. Also, unlike most previous results, the classification here does not rely on color since color changes with illumination and weather, and certain terrains have multiple colors (e.g., sand may be red or white). Instead, it relies only on spatial relationships, specifically spatial frequency response and texture, which captures spatial relationships between different gray levels. Terrain surface classification using each of these features separately is conducted by using a probabilistic neural network. Experimental results based on classifying four outdoor terrains demonstrate the effectiveness of the proposed methods.

Skid-steered vehicles are often used as outdoor mobile robots due to their robust mechanical structure and high maneuverability. Sliding along with rolling is inherent to general curvilinear motion, which makes both kinematic and dynamic modeling difficult. For the purpose of motion planning this paper develops and experimentally verifies dynamic models of a skid-steered wheeled vehicle for general planar (2D) motion and for linear 3D motion. These models are characterized by the coefficient of rolling resistance, the coefficient of friction, and the shear deformation modulus, which have terrain-dependent values. The dynamic models also include motor saturation and motor power limitations, which enable correct prediction of vehicle velocities when traversing hills. It is shown that the closed-loop system that results from inclusion of the dynamics of the (PID) speed controllers for each set of wheels does a much better job than the open loop model of predicting the vehicle linear and angular velocities. Hence, the closed-loop model is recommended for motion planning.

Ruts formed as a result of vehicle traversal on soft ground are used by expert off road drivers because they can improve vehicle safety on turns and slopes thanks to the extra lateral force they provide to the vehicle. In this paper we propose a rut detection and tracking algorithm for autonomous ground vehicles (AGVs) equipped with a laser range finder. The proposed algorithm utilizes an extended Kalman filter (EKF) to recursively estimate the parameters of the rut and the relative position and orientation of the vehicle with respect to the ruts. Simulation results show that the approach is promising for future implementation.

This paper presents an efficient algorithm to achieve accurate subpixel matchings for calculating correspondences between stereo images based on a path-based matching algorithm. Compared to point-by-point stereo matching algorithms, path-based algorithms resolve local ambiguities by maximizing the cross correlation (or other measurements) along a path, which can be implemented efficiently using dynamic programming. An effect of the global matching criterion is that the cross correlation at all pixels can contribute to the criterion; since cross correlation can change significantly even with subpixel changes, to achieve subpixel accuracy, it is no longer sufficient to first find the path that maximizes the criterion and then refine to subpixel accuracy. In this paper, by writing bilinear interpolation using integral images, we show that cross correlations at all subpixel locations can be computed efficiently and thus lead to a subpixel accuracy path based matching algorithm. Our results show the feasibility of the method and illustrate the significant improvements over the original path-based matching method.

Terrain variations can greatly influence autonomous ground vehicle (AGV) performance. However, if the terrain is properly identified, the AGV control systems can be adjusted to better suit the terrain. Current terrain classification techniques are largely based on vision and terrain dependent vehicle reactions. But at this time both methods have limitations. Visual methods can easily be fooled by fallen leaves or other superficial ground coverings, whereas response-based methods yield poor results when the AGV speed is significantly different from the training speeds. In addition, current response-based methods are not capable of identifying the multiple terrains that a vehicle may simultaneously traverse, e.g., when one subset of wheels is on-road and one is off-road. This paper proposes a response-based method called terrain input classification to solve the issue of speed dependency and multiple terrain traversal. This method is dependent upon knowing the vibration transfer function of the AGV. The method has been verified through terrain-based simulation results and is ready for experimental testing.

Autonomous navigation systems for mobile robots have been successfully deployed for a wide range of planar ground-based tasks. However, very few counterparts of previous planar navigation systems were developed for 3-D motion, which is needed for both unmanned aerial and underwater vehicles. A novel fuzzy behavioral scheme for navigating an unmanned helicopter in cluttered 3-D spaces is developed. The 3-D navigation problem is decomposed into several identical 2-D navigation subproblems, each of which is solved by using preference-based fuzzy behaviors. Due to the shortcomings of vector summation during the fusion of the 2-D subproblems, instead of directly outputting steering subdirections by their own defuzzification processes, the intermediate preferences of the subproblems are fused to create a 3-D solution region, representing degrees of preference for the robot movement. A new defuzzification algorithm that steers the robot by finding the centroid of a 3-D convex region of maximum volume in the 3-D solution region is developed. A fuzzy speed-control system is also developed to ensure efficient and safe navigation. Substantial simulations have been carried out to demonstrate that the proposed algorithm can smoothly and effectively guide an unmanned helicopter through unknown and cluttered urban and forest environments.

Navigation in environments that are densely cluttered with obstacles is still a challenge for Autonomous Ground Vehicles (AGVs), especially when the configuration of obstacles is not known a priori. Reactive local navigation schemes that tightly couple the robot actions to the sensor information have proved to be effective in these environments, and because of the environmental uncertainties, fuzzy behavior systems have been proposed. The most difficult problem in applying these systems is that of arbitrating or fusing the reactions of the individual behaviors. This paper presents an architectural design of a fuzzy behavior based system for navigation control of robotic vehicles using multivalued reactive fuzzy behaviors. This design allows the robot to thoroughly use the available sensor information when choosing the control action to be taken. Experimental results show that the proposed method can smoothly and effectively guide a robot through cluttered environments such as dense forests.

Aerial missions that require unmanned aerial vehicles (UAVs) to fly autonomously in unknown and hostile environments are inevitable. These UAVs must be equipped with a fully autonomous navigation system. Many methods that have been proposed for navigation of autonomous systems either lack the necessary intelligence or are not responsive enough to cope with the flying speeds of UAVs. This paper presents a new method for autonomous navigation of UAVs using reactive fuzzy behaviors. It extends a 2D fuzzy behavior navigation system used in unmanned ground vehicles to a 3D navigation system suitable for UAVs. The research is based on a range finding sensor system by judicious use of a 2D range finder. A novel defuzzification method for 3D navigation systems is developed to generate the most desired flying orientation. Simulation results carried out using MATLAB's Virtual Reality Toolbox show that the proposed system works very well to avoid static obstacles.

An industrial weigh belt feeder is used to transport solid materials into a manufacturing process at a constant feedrate. It exhibits nonlinear behavior because of motor friction, saturation, and quantization noise in the sensors, which makes standard autotuning methods difficult to implement. The paper proposes and experimentally demonstrates two types of fuzzy logic controllers for an industrial weigh belt feeder. The first type is a PI-like fuzzy logic controller (FLC). A gain scheduled PI-like FLC and a self-tuning PI-like FLC are presented. For the gain scheduled PI-like FLC the output scaling factor of the controller is gain scheduled with the change of setpoint. For the self-tuning PI-like FLC, the output scaling factor of the controller is modified online by an updating factor whose value is determined by a rule base with the error and change of error of the controlled variable as the inputs. A fuzzy PI controller is also presented, where the proportional and integral gains are tuned online based on fuzzy inference rules. Experimental results show the effectiveness of the proposed fuzzy logic controllers. A performance comparison of the three controllers is also given.