Autonomous navigation has recently gained great interest in the field of reinforcement learning. However, little attention was given to the time optimal velocity control problem, i.e. controlling a vehicle such that it travels at the maximal speed without becoming dynamically unstable (roll-over or sliding). Time optimal velocity control can be solved numerically using existing methods that are based on optimal control and vehicle dynamics. In this paper, we use deep reinforcement learning to generate the time optimal velocity control. Furthermore, we use the numerical solution to further improve the performance of the reinforcement learner. It is shown that the reinforcement learner outperforms the numerically derived solution, and that the hybrid approach (combining learning with the numerical solution) speeds up the training process.

This paper offers a method to compute the control inputs for an all-wheel drive vehicle that moves along a specified path on rough terrain. The focus of this paper is on longitudinal motion only, using a half-car model with no suspensions. For a given path, we first compute the range of the admissible speeds and accelerations at every point along the path, subject to vehicle dynamics and constraints on the wheel/ground forces. A feasible velocity profile along the path is then computed to respect the admissible speeds and accelerations and satisfy given boundary conditions. While the velocity profile represents the accelerations of the center of mass, it remains to determine the control inputs (torques) for the two independent wheels. The challenge stems from the longitudinal model being an indeterminate system, having two control inputs but only one degree-of-freedom along the specified path. This inherent indeterminacy is resolved by adding a virtual suspension to the rigid vehicle model, which allows to explicitly compute the two individual wheel torques. The method is demonstrated for a vehicle moving at the time optimal speeds over a bump. A dynamic simulation of the vehicle with a stiff suspension shows that the two wheels maintain contact with the ground at all times, despite moving at the ultimate speeds. It is also shown that the all-wheel-drive model produces a larger set of admissible speeds and accelerations, and hence results in faster speeds and shorter motion times than the single drive (front or rear) model.

This paper presents an efficient algorithm for online obstacle avoidance that accounts for robot dynamics and actuator constraints. The robot trajectory (path and speed) is generated on-line by avoiding obstacles optimally one at a time. This reduces the original problem from one with m obstacles to m simpler problems with one obstacle each, thus resulting in a planner that is linear, instead of exponential, in the number of obstacles. While this approach is quite general and applicable to any cost function and to any robot dynamics, it is treated here for minimum time motions, a point mass robot, and planar circular obstacles.

This paper addresses the issue of motion planning in dynamic environments using Velocity Obstacles. Specifically, we propose an adaptive time horizon to truncate the velocity obstacle so that its boundary closely, yet conservatively, approximates the boundary of the set of states from which collision is unavoidable. We wish to develop a representation such that any velocity vector that does not penetrate the velocity obstacle is safe, i.e. an avoidance maneuver exists, and any that does is not. Such clear partitioning between safe and unsafe velocities would allow safe planning with only one step look ahead, and can produce faster trajectories than the conservative trajectories produced when using an infinite time horizon. The computation of the adaptive time horizon is formulated as a minimum time problem, which is solved numerically for each static or moving obstacle. It is used in an on-line planner that generates locally time optimal trajectories to the goal. The planner is demonstrated for static and moving obstacles, and for on-line motion planning in a crowded dynamic environment.

This paper presents a new on-line planner for dynamic environments that is based on the concept of velocity obstacles (VO). It addresses the issue of motion safety, i.e. avoiding states of inevitable collision, by selecting a proper time horizon for the velocity obstacle. The proper choice of the time horizon ensures that the boundary of the velocity obstacle coincides with the boundary of the set of inevitable collision states. This time horizon is determined by the minimum time it would take the robot to avoid collision, either by stopping or by passing the respective obstacle. The planner generates a near-time optimal trajectory to the goal by selecting at each time step the velocity that minimizes the time-to-go and is out of the velocity obstacle. The planner takes into account the shape, velocity, and path curvature of the obstacle's trajectory. It is demonstrated for on-line motion planning in very crowded static and dynamic environments.

This paper presents a method to determine the stability of off-road vehicles moving on rough terrain. The measures of stability are defined as the maximum speed and acceleration under which the vehicle does not slide or tip over. To compute these stability measures, we propose a quasi 3D analysis by decomposing the vehicle dynamics into three separate planes: the yaw, pitch, and roll planes. In each plane, we compute the set of admissible speeds and acceleration for the planar vehicle model, contact model, and ground force constraints. The intersection of the admissible sets provides the total range of feasible speeds and accelerations along the vehicle's path, from which we obtain the stability margins. Numerical results for a vehicle traversing a simulated terrain demonstrate the effectiveness of the approach.

This paper proposes a method for near-optimal navigation of high speed mobile robots on uneven terrain. The method relies on a layered control strategy. A high-level planning layer generates an optimal desired trajectory through uneven terrain. A low-level navigation layer guides a robot along the desired trajectory via a potential field-based control algorithm. The high-level planner is guaranteed to yield optimal trajectories but is computationally intensive. The low-level navigation layer is sub-optimal but computationally efficient. To guard against failures at the navigation layer, a model-based lookahead approach is employed that utilizes a reduced form of the optimal trajectory generation algorithm. Simulation results show that the proposed method can successfully navigate a mobile robot over uneven terrain while avoiding hazards. A comparison of the method’s performance to a similar algorithm is also presented.

Dynamic stability reflects the vehicle's ability to traverse uneven terrain at high speeds. It is determined from the set of admissible speeds and tangential accelerations of the center of mass along the path, subject to the ground force and geometric path constraints. This paper presents an analytical method for computing the stability margins of a planar all-wheel drive vehicle that accounts for soil parameters. It consists of mapping the ground force constraints to constraints on the vehicle's speeds and accelerations along the path. The boundaries of the set of admissible speeds and accelerations determine the static and dynamic stability margins, used to gage the traversability of the vehicle along the path. The first is the maximum feasible acceleration at zero speed, whereas the second is the maximum feasible speed. Both stability margins are demonstrated for a planar vehicle moving on a sinusoidal path.

Dynamic stability reflects the vehicle's ability to traverse uneven terrain at high speeds. It is determined from the set of admissible speeds and tangential accelerations of the center of mass along the path, subject to the ground force constraints and the geometric path constraints. This paper presents a geometric procedure for computing the set of admissible speeds and accelerations of a planar all-wheel drive vehicle. It first determines the boundaries of the set of resultant forces at the center of mass that satisfy the ground force constraints and the equations of motion along the path. This set is then mapped to the set of feasible speeds and accelerations along the path, from which the dynamic stability margin (DSM) is determined. A byproduct of this procedure is a static stability margin (SSM) that reflects the vehicle's ability to accelerate, or decelerate, at zero speed. Both stability margins are useful as cost measures for physics-based motion planning over rough terrain. The approach is demonstrated for a planar vehicle moving on a sinusoidal track

This paper describes a unified measure of stability of a Rocker Bogie vehicle that accounts for the tendency to slide, tipover, or lose contact with the ground considering both static equilibrium and dynamic effects. The measure of stability is computed by solving for the range of acceptable velocities and accelerations that satisfy a set of dynamic constraints. The maximum acceptable velocity serves as a dynamic stability measure, whereas the maximum acceptable acceleration at zero velocity serves as a static stability measure. The utility of the static and dynamic stability margins are demonstrated for both two dimensional and longitudinal quasi-3D motion in several examples.

This paper describes an efficient algorithm to generate a set of local optimal paths between two given end points in cluttered environments or over open terrain. The local optimal paths are selected from the set of shortest constrained paths through every node (one for each path) in the graph, generated by running twice a "single-source" search. The initial set of the shortest constrained paths spans the entire search space and includes local optimal paths with costs equal or better than the longest constrained path in the set. The search for the optimal path is transformed to a search for the best path in each homotopy class generated by this search. The initial search is of complexity O(nlogn), and the pruning procedure is O(nmlogm), where n is the number of nodes and m is the number of homotopy classes generated by this search. The algorithm is demonstrated for motion planning on rough terrain.

This paper offers a unified measure for dynamic stability of off-road vehicles that accounts for the tendency to tipover, slide, or loose contact with ground during static equilibrium and in motion. The contacts between the vehicle and ground are assumed rigid, and all wheels are assumed active. The dynamic stability measure is determined by computing the range of velocity and acceleration of the vehicle's center of mass that satisfies a set of dynamics constraints. The upper velocity limit serves as a dynamic stability measure, whereas the acceleration limit at zero speed serves as a static stability measure. In this paper, we demonstrate the approach for a four-wheel drive planar vehicle.

This paper describes a new search algorithm, the Dual Dijkstra Search. From a given initial and final configuration, Dual Dijkstra Search finds various paths which have different topologies simultaneously. This algorithm allows you to enumerate not only the optimal one but variety of meaningful candidates among local minimum paths. It is based on the algorithm of Dijkstra, which is popularly used to find an optimal solution. The method consists of two procedures: First computes local minima and ranks the paths in order of optimality. Then classify them with their topological properties and take out only the optimal paths in each groups. Computed examples include generating collision-free motion along 2D space and motion planning of 3-DOF robot. We also proposed the idea of motion compression, which simplifies the high dimensional motion planning problem. Together with this idea, we applied Dual Dijkstra Search to 7-DOF arm manipulation problem and succeeded in obtaining variety of motion candidates.

This paper focuses on real-time motion planning in a dynamic environment. Most of the global existing approaches cannot satisfy real-time due to heavy computation, while local methods don't guarantee reaching the goal. In this paper we present a novel global approach based on the non-linear velocity obstacle concept. We use the rich information on the velocities admissible for the robot to build a complete autonomous navigation module, composed of a local obstacle-avoidance system coupled with an incremental global motion planner. Real-time computation issues are discussed. Results obtained in simulation for dynamic environments are presented.

This paper focuses on real-time global motion planning in a dynamic environment. Most of the existing approaches suffer from heavy computation and cannot satisfy real-time constraints. In this paper we present a novel approach, based on the Non-Linear Velocity Obstacle Concept, that maps the positions of the obstacles and their known or estimated trajectories directly in the space of the velocities admissible by our robot, taking into account its kinematic and dynamics constraints. The result is a map of all the collision free velocities. We present a few improvements to this approach and introduce the notion of risk to perform local goal-oriented obstacle-avoidance. Combining it with graph-expansion techniques, we propose to extend the system to an incremental global motion planner in a dynamic environment.

This paper generalizes the concept of velocity obstacles given by Fiorini et al. (1998) to obstacles moving along arbitrary trajectories. We introduce the nonlinear velocity obstacle, which takes into account the shape, velocity and path curvature of the moving obstacle. The nonlinear v-obstacle allows selecting a single avoidance maneuver (if one exists) that avoids any number of obstacles moving on any known trajectories. For unknown trajectories, the nonlinear v-obstacles can be used to generate local avoidance maneuvers based on the current velocity and path curvature of the moving obstacle. This elevates the planning strategy to a second order method, compared to the first order avoidance using the linear v-obstacle, and zero order avoidance using only position information. Analytic expressions for the nonlinear v-obstacle are derived for general trajectories in the plane. The nonlinear v-obstacles are demonstrated in a complex traffic example.

Presents a practical motion planner for humanoids and animated human figures. Modeling human motions as a sum of rigid body and cyclic motions, we identify body postures that represent the rigid-body part of typical motion patterns. This leads to a model of the configuration space that consists of a multi-layered grid, each layer corresponding to a single posture. A global search through this reduced configuration space yields a feasible path and the corresponding postures along the path. A velocity profile is calculated along the optimal path, subject to the speed and acceleration limits assumed for each posture. Cyclic motions, generated from "primitive" cyclic motion patterns for each posture, are then added to the trajectory produced by the path planner. This "kinematic" motion is then modified by a dynamics filter to result in dynamically consistent behavior. Examples are presented which demonstrate the use of this planner in an office environment.

Obstacle traversal aims at selecting a feasible path through an obstacle field. It is different from obstacle avoidance in that the path selected might climb over some obstacles if this is "cheaper" than going around. Climbing over obstacles allows to generate shorter paths in the case of large concave obstacles. A planner is presented that produces traversable paths, taking into account terrain topography, robot parameters, and robot/ground interaction. This planner is applicable to outdoor applications, such as Mars exploration, where absolute avoidance of obstacles is not necessary. Examples for a Mars rover are presented.

This paper presents an online planner for suboptimal obstacle avoidance. It generates near-shortest paths incrementally by avoiding obstacles optimally one at a time. In known environments, the obstacles are avoided in an order determined by a global criterion, whereas in unknown environment, obstacles are avoided as they are detected by on-board sensors. This avoidance strategy converges globally to the goal, regardless of the order in which the obstacles are selected. The planner is demonstrated for a point robot moving amongst general planar polygonal obstacles.

This paper solves the online obstacle avoidance problem using the Hamilton-Jacobi-Bellman (HJB) theory. Formulating the shortest path problem as a time optimal control problem, the shortest paths are generated by following the negative gradient of the return function, which is the solution of the HJB equation. To account for multiple obstacles, we avoid obstacles optimally one at a time. This is equivalent to following the pseudo-return function, which is an approximation of the true return function for the multi-obstacle problem. Paths generated by this method are near-optimal and guaranteed to reach the goal, at which the pseudo-return function is shown to have a unique minimum. The proposed method is computationally very efficient, and applicable for online applications. Examples for circular obstacles demonstrate the advantages of the proposed approach over traditional path planning methods.

This paper presents a method for motion planning in dynamic environments, subject to robot dynamics and actuator constraints. The time optimal trajectory is computed by first generating an initial guess using the concept of velocity obstacle. The initial guess, computed by a global search over a tree of avoidance maneuvers, is then optimized using a dynamic optimization. This method is applicable to repetitive tasks in known dynamic environments, as is demonstrated for a planar robot manipulator.

This paper presents a method for generating near-time optimal trajectories in cluttered environments for manipulators with invariant inertia matrices. For one obstacle, the method generates the time-optimal trajectory by minimizing the time-derivative of the return (cost) function for this problem, satisfying the Hamilton-Jacobi-Bellman (HJB) equation. For multiple obstacles, the trajectory is generated using the pseudo return function, which is an approximation of the return function for the multi-obstacle problem. The pseudo return function avoids one obstacle at a time, producing near-optimal trajectories that are guaranteed to avoid the obstacles and satisfy the actuator constraints. An example with circular obstacles demonstrates close correlation between the near-optimal and optimal paths, requiring computational efforts that are suitable for on-line implementations.

A method is presented for optimizing the motions of articulated systems along specified paths, minimizing a time-energy cost function. Using a transformation to path variables, the optimization problem is formulated in a reduced two dimensional state space. The necessary conditions for optimality, stated for the reduced problem, lead to a compact two point boundary value problem that requires the iterations of only one boundary condition. The optimal control obtained for this problem is smooth, as opposed to the typically discontinuous time optimal control. The method is demonstrated numerically for a two link planar manipulator, and experimentally for the UCLA Direct Drive Arm. The smoother time-energy optimal trajectory is shown to result in smaller tracking errors than the time optimal trajectory.>

This paper presents a method for generating shortest paths in cluttered environments, based on the Hamilton-Jacobi-Bellman (HJB) equation. Formulating the shortest obstacle avoidance problem as a time optimal control problem, the shortest paths are generated by following the negative gradient of the return function, which satisfies the HJB equation. A method to generate near-optimal paths is also presented, based on a psuedo return function. Paths generated by this method are guaranteed to reach the goal, at which the psuedo return function is shown to have a unique minimum. The computation required to generate the near-optimal paths is substantially lower than those of traditional potential field methods, making it applicable to on-line obstacle avoidance. Examples with circular obstacles demonstrate close correlation between the near-optimal and optimal paths, and the advantages of the proposed approach over traditional potential field methods.>

This paper presents a general necessary condition for singular time optimal control of robotic manipulation moving along specified paths. Early work by Bobrow-Dubowsky (1985) and Shin-McKay (1985) ignored the issue of singular control, assuming bang-bang acceleration along the path. Recent work by Shiller-Lu (1992) has shown that the time optimal control can be singular if one of the equations of motion reduces to a velocity constraint. This paper derives a more general necessary condition for singular control. It is also proven that singular control cannot exist if the set of admissible controls is strictly convex, as is demonstrated for a two-link planar manipulator with elliptical actuator constraints.>

Design methods of robotic manipulators to select the link lengths and actuator sizes for minimum-time motions along specified paths are presented. An exact method is based on a parameter optimization, using the motion time along the path as the cost function. This method serves as a benchmark for a more efficient approximation which selects system parameters so as to maximize acceleration along the path. Examples of the design of a two-link manipulator are presented, demonstrating close correlation between the exact and the approximate methods.>

A potential based method for generating near time optimal paths of manipulators moving in the presence of obstacles is presented. The potential function consists of the navigation function for obstacle avoidance and acceleration potentials that force the path to maximize the acceleration and deceleration near the end points. The parameters of the potential functions are selected to guarantee a unique minimum that coincides with the destination point. The path of minimum potential from the initial point avoids obstacles as well as maximizes the initial acceleration and the final deceleration. The method is demonstrated for a two link planar manipulator, generating paths with optimal motion times substantially lower than those generated by the navigation function alone.>

A method for computing the time-optimal motions of robotic manipulators is presented that considers the nonlinear manipulator dynamics, actuator constraints, joint limits, and obstacles. The optimization problem is reduced to a search for the time-optimal path in the n-dimensional position space. A small set of near-optimal paths is first efficiently selected for a grid, using a branch and bound search and a series of lower bound estimates on the traveling time along a given path. These paths are further optimized with a local path optimization to yield the global optimal solution. Obstacles are considered by eliminating the collision points from the tessellated space and by adding a penalty function to the motion time in the local optimization. The computational efficiency of the method stems from the reduced dimensionality of the searched spaced and from combining the grid search with a local optimization. The method is demonstrated in several examples for two- and six-degree-of-freedom manipulators with obstacles.>

A method for planning the motions of autonomous vehicles moving on general terrains is presented that obtains the geometric path and vehicle speeds that minimize motion time considering vehicle dynamics, terrain topography, obstacles, and surface mobility. The terrain is represented by a smooth cubic B patch, and the geometric path consists of a B spline curve mapped to the surface. The time-optimal motions are computed by first obtaining the best obstacle-free path from all paths represented by a uniform grid. This path is further optimized using a local optimization procedure, using the optimal motion time along the path as the cost function and the control points of a B spline as the optimizing parameters. Examples are presented that demonstrate the method for a simple dynamic model of a vehicle moving on mountainous terrain.>

A method is presented for optimally planning the motions of autonomous vehicles, considering vehicle dynamics, terrain topography, obstacles, and surface mobility. The terrain is represented by a smooth cubic B patch, and the geometric path consists of a two dimensional B spline curve mapped to the three-dimensional surface. The path is optimized with a parameter optimization procedure, using motion time as the cost function. The optimal motion time along the path is computed by transforming the constraints between the vehicle and ground to limits on vehicle speeds. The optimal speeds which minimize motion time are then obtained below the velocity limits, using the maximum acceleration of deceleration at all times. Examples are presented which demonstrate the method for a simple dynamic model of a vehicle moving on mountainous terrain.>

An algorithm is presented for the computation of path-constrained time-optimal motions of robotic manipulators exploring the nature of so-called critical points and critical arcs. At critical points the reflected inertia at one of the joints is zero, and the feasible acceleration range at the velocity limit is not unique. Time-optimal motions along critical arcs may be singular in the sense that the acceleration is neither maximum nor minimum. This is in contrast to existing motion optimization methods along specified paths which assume maximum acceleration or deceleration at all times. The consideration of critical arcs makes this algorithm robust near the switching points, which are potential points of failure in the other methods. Critical points can be anticipated along the path by mapping the locus of critical arcs to the position space. Examples are presented to demonstrate the algorithm and the existence of singular critical arcs.>

The author presents an interactive motion planning system designed to obtain near-time-optimal and obstacle-free paths efficiently. A geometric representation of robot dynamics reduces the motion planning problem to a simple geometric task. A graphic display of the acceleration capabilities of the manipulator tip and the forbidden regions around the obstacles guides the user in interactively selecting a near-time-optimal and obstacle-free path. The selected path is evaluated by the time-optimal velocity profile along that path, obtained by online optimization. Using the interactive system, paths to within 3% of the optimal were computed in very short time compared to conventional optimization methods. Examples of planning the motions of a two-link manipulator operating in a cluttered environment are presented. Where the layout of the workcell makes the paths inefficient or prevents a movement altogether, the system can be used to redesign the cell layout.>

A practical method to obtain the global time optimal motions of robotic manipulators is presented. This method takes into account the nonlinear manipulator dynamics, actuator constraints, joint limits, and obstacles. Previously developed methods of optimizing manipulator motions along given paths and a local path optimization are utilized. A set of best paths is obtained first in a global search over the manipulator workspace, using graph search and hierarchical pruning techniques. These paths are used as initial conditions for a continuous path optimization to yield the global optimal motion. Examples of optimized motions of a six-degree-of-freedom manipulator, operating in a three-dimensional space with obstacles, are presented.>

A method is presented which finds the minimum time motions for a manipulator between given end states. The method considers the full nonlinear manipulator dynamics, actuator saturation characteristics, and accounts for both the presence of obstacles in the work space and restrictions on the motions of the manipulator's joints. The method is computationally practical and has been implemented in a Computer Aided Design (CAD) software package, OPTARM II, which facilitates its use. Examples of its application to a six degree-of-freedom articulated manipulator, performing tasks in a typical environment, are presented. The results show that substantial improvements in system performance can be achieved with the technique.

The motion of current industrial manipulators is typically controlled so that tasks are not done in a minimum time optimal manner. The result is substantially lower productivity than that potentially possible. Recently a computationally efficient algorithm has been developed to find the true minimum time optimal motion for a manipulator moving along a specified path in space that uses both the full nonlinear dynamic character of the manipulator and the constraints imposed by its actuators. A Computer Aided Design (CAD) implementation of the algorithm called OPTARM is described which can treat practically general six degree-of-freedom manipulators. Examples are presented which show OPTARM to be a useful design tool for manipulators, their tasks and work places. The algorithm is extended in OPTARM to include the constraints imposed by manipulator payloads and end-effectors.