We present a novel algorithm for robot motion planning in dynamic environments. Our approach extends rapidly-exploring random trees (RRTs) in several ways. We assume the need to simultaneously plan and maintain paths for multiple tasks with respect to the current state of a moving robot in a dynamic environment. Our algorithm dynamically maintains a forest of trees by splitting, growing and merging them on the fly to adapt to moving obstacles and robot motion. In order to minimize tree maintenance, we only validate the task paths, rather than the entire forest. The root of the inhabited tree moves with the robot. Dynamic re-planning is integrated with tree and forest maintenance. Coupling the robot motion with the planner enables us to support multiple tasks, for example providing an "escape" path while moving to a goal. The robot is free to move along whichever task path it chooses. We highlight the work by showing fast results in simulated environments with moving obstacles.

The need for collision detection arises in several robotics areas, including motion-planning, online collision avoidance, and simulation. At the heart of most current methods are algorithms for interference detection and/or distance computation. We presented (1997) an implemented technique for doing exact numerical distance computation and interference detection for translationally-swept bodies and approximate techniques for bodies swept under finite screw motion. Here, we extend the enhanced GJK and Gilbert-Foo, algorithms to obtain exact numerical distance computation and interference detection between the convex hulls of the volumes swept by two convex polyhedra under finite screw motions. This algorithm enables conservative distance and collision computations that are both tighter and more efficient than the previous result. It has been integrated into a bounding-volume hierarchy distance/interference code to extend the result to facetted non-convex rigid bodies.

We consider the problem of planning shortest paths for a tethered robot with a finite length tether in a 2D environment with polygonal obstacles. We present an algorithm that runs in time O((k/sub l/+1)/sup 2/n/sup 4/) and finds the shortest path or correctly determines that none exists that obeys the constraints, where n is the number obstacle vertices, and k/sub l/ is the number loops in the initial configuration of the tether. The robot may cross its tether but nothing can cross obstacles, which cause the tether to bend. The algorithm can also be applied to planning a shortest path for the free end of an anchored cable.

The need for collision detection arises in several robotics areas, including motion-planning, online collision avoidance, and simulation. At the heart of most current methods are algorithms for interference detection and/or distance computation. A few recent algorithms and implementations are very fast, but to use them for accurate collision detection, very small step sizes can be necessary, reducing their effective efficiency. We present a fast, implemented technique for doing exact distance computation and interference detection for translationally-swept bodies. For rotationally swept bodies, we adapt this technique to improve accuracy, for any given step size, in distance computation and interference detection. We present preliminary experiments which show that the combination of basic and swept-body calculations holds much promise for faster accurate collision detection.

For a number of years, robotics researchers have exploited hierarchical representations of geometrical objects and scenes in motion-planning, collision-avoidance, and simulation. However, few general techniques exist for automatically constructing them. We present a generic, bottom-up algorithm that uses a heuristic clustering technique to produce balanced, coherent hierarchies. Its worst-case running time is O(N/sup 2/logN), but for non-pathological cases it is O(NlogN), where N is the number of input primitives. We have completed a preliminary C++ implementation for input collections of 3D convex polygons and 3D convex polyhedra and conducted simple experiments with scenes of up to 12,000 polygons, which take only a few minutes to process. We present examples using spheres and convex hulls as hierarchy primitives.

Kinodynamicplanmng attempts to solve a robot motion problem subject to simultaneous kinematic and dynamics constraints.In the general problem, ggven a robot system, we must find a minimal-time trajectory that goes from a start position and veloclty to a goal position and velocity while avoiding obstacles by a safety margur and respecting constraints cm velocity and acceleration.We consider the simplified case of a point mass under Newtoman mechanics.together with velocity and acceleration bounds.The point must be flown from a start to a goal, amidst polyhedral obstacles in 2D or 3D.Although exact sohztions to this problem are not known, we provide the first provably good approximation algorlthm, and show that it runs in polynomial time.

The kinodynamic planning problem is, given a robot system, to find a trajectory from a start state to a goal state, while avoiding obstacles by a safety margin delta (v) and respecting dynamics bounds. Provably good polynomial-time approximation algorithms for optimal kinodynamic planning find trajectories within in of optimal and have a time complexity polynomial in 1/ in and in the geometric complexity of the robot world. The authors obtain such algorithms to find near-optimal trajectories obeying piecewise constant extremal controls and bang-bang control. Previous provably good kinodynamic planning algorithms for robot arms produce nonextremal, and hence locally nonoptimal trajectories. Using parameters in /sub T/ and in /sub S/ and describe closeness to optimality in execution time and observance of the safety margin, the authors derive equicomplexity curves to show how their algorithms permit to tradeoffs between time and safety.>

We consider the following problem: given a robot system, find a minimal-time trajectory from a start state to a goal state, while avoiding obstacles by a speed-dependent safety margin and respecting dynamics bounds. In [CDRX] we developed a provably good approximation algorithm for the minimum-time trajectory problem for a robot system with decoupled dynamics bounds. This algorithm differed from previous work in three ways: it is possible (1) to bound the goodness of the approximation by an error term ε (2) to polynomially bound the running time (complexity) of our algorithm; and (3) to express the complexity as a polynomial function of the error term.

The authors describe the first implementation of a good polynomial-time approximation algorithm for kinodynamic planning. Attention is given to the following problem: given a robot system, find a minimal-time trajectory from a start position and velocity to a goal position and velocity, while avoiding obstacles and respecting dynamic constraints on velocity and acceleration. From the class of approximate minimal-time trajectories for a given problem instance that the theoretical algorithm would find, the proposed implementation will find a trajectory with minimal useless chattering. In addition, the authors present an improved analysis of the accuracy of the approximation strength of this approach. This analysis reveals that the algorithm produces approximations good to a small additive error in state space and exact in time while only sacrificing the epsilon -approximation factor in safety, where epsilon is an error term. In addition, the analysis halves the polynomial complexity of the algorithm in (1/ epsilon ), and it provides a simple characterization of when the algorithm will find a trajectory that is exact at the start and goal.>

The following problem, is considered: given a robot system find a minimal-time trajectory from a start position and velocity to a goal position and velocity, while avoiding obstacles and respecting dynamic constraints on velocity and acceleration. The simplified case of a point mass under Newtonian mechanics together with velocity and acceleration bounds is considered. The point must be flown from a start to a goal, amid 2-D or 3-D polyhedral obstacles. While exact solutions to this problem are not known, the first provably good approximation algorithm is given and shown to run in polynomial time.