A method for computing the distance between two mobile objects following linear or arc-like motions with constant accelerations is introduced in this paper. This distance is obtained without stepping or discretizing any object's motion. Objects are modeled by bi-dimensional convex hulls. The distance- computation algorithm obtains the instant in time when two mobile objects are at their minimum translational distance of separation or penetration. The distance and the instant in time are parallely computed. This method is so fast that can be run as frequent as new information from the world is received.

A fast and complete collision-detection procedure is presented in this paper. Given a straight-line path for a mobile robot, the current instant of time, and estimations of the obstacles motions, a set of speeds is obtained in real time with neither space nor time discretization. The mobile-robot path together with each one of these speeds, if they exist, states a different collision-free trajectory. All these trajectories verify that the minimum distance between the mobile robot and the obstacles at anytime is greater than or equal to a configurable parameter. This set of speeds is fast updated when a change in the original mobile-robot path is considered. If the current mobile-robot speed does not belong to the mentioned set of speeds, then the mobile robot will collide with at least one obstacle and, in this case, a set of accelerations is fast-tuned to avoid all the obstacles. Collision-free trajectories that do not verify the dynamic constraints of the mobile robot are simply rejected.

A new technique for computing the minimum translational distance between two moving objects with rotational motions is presented in this paper. Separation or penetration distance is computed with no space and time discretization for constant-speed motions. Motions are constrained to two degrees of freedom. Objects and their motions are modeled by 3D spherically-extended polytopes. The distance-computation algorithm returns a set of parameters that characterizes the maximum approach positions and the corresponding instant of time. Additionally, this set of parameters also characterizes a new motion for one of the objects to come into contact with the other moving object.

A new and fast technique for generating collision-free paths for a mobile sphere, whose size (radius) dynamically changes, is introduced in this paper. A collision between the mobile-sphere motion and an obstacle is predicted by computing its minimum translational distance. This distance parameterizes an intermediate configuration for the sphere, which is in contact with the obstacle or separated a configurable distance. Collision with a given obstacle is then avoided by forcing the mobile sphere to pass through a selected intermediate configuration. This paper describes a technique to reduce or to grow this configuration (sphere) in order to bring it into contact (or as close as desired) with a second obstacle. This fact provides the path planner some remarkable properties like it really generates a set of homotopic paths in narrow environments for not only a sphere but any other mobile object which always keeps inside the volume represented by the generated path.

This paper presents a fast technique for obtaining a set of collision-free trajectories for a mobile robot under a continuous time approach. Given a mobile-robot path, a set of speeds for the mobile robot is generated with the constraint of avoiding collision with the moving obstacles in sight. Afterwards, this set of speeds is easily updated, when a change in the original mobile-robot path is applied. Collision-free trajectories that do not verify the dynamic constraints of the mobile robot are simply rejected

In this paper, a new method for generating a set of collision-free maneuvers for unmanned vehicles in automated highway systems is introduced. The low computational cost of the proposed maneuver planner allows its execution as frequent as the new positions and speeds of vehicles (obstacles) in sight are received. This planner is based on the computation of the minimum translational distance between two mobile objects. This distance is then used for predicting and avoiding a collision, generating (if it is possible and safe), overtaking (changing to the left and right lane), braking and keeping-the-lane maneuvers. These maneuvers can be provided to a decision-making process for selecting the most suitable one.

A new technique for collision detection based on the application of the Hough transform is presented in this paper. As a consequence of applying this technique, a method for computing the minimum translational distance (MTD) between two spherically extended polytopes is introduced. This distance algorithm is based on the Gilbert-Johnson-Keerthi (GJK) algorithm. Parameters returned by the MTD algorithm hold collision-free configurations that avoid a predicted collision.

A methodology for computing a collision-free trajectory for mobile robots amidst moving objects is presented. This planner is based on a technique for computing the minimum translational distance between two mobile objects. This distance is then used for predicting and avoiding a collision. The computation of this distance is based on the application of the GJK algorithm to a particular subset of the Minkowski difference set of the involved objects. This subset states the separation or penetration distance between two objects along their given motions. When a collision is predicted, a collision-free intermediate temporal-position is generated avoiding such a collision.

A novel and fast technique for solving the basic motion-planning problem is introduced. Obstacle avoidance is based on the computation of minimum translational distances that allows one to obtain collision-free intermediate configurations. When path planning is constrained to two degrees of freedom, Hough transform is applied to such configurations. After that, several collision-free paths are generating by joining different sets of selected intermediate configurations. These selections are obtained by applying the technique called minimum volume locus. Complexity of this path planner is linear with the number of obstacles. Object representation is based on spherically extended polytopes.