We present a general search strategy called SANDROS for motion planning, and its applications to motion planning for three types of robots: (1) manipulator; (2) rigid object; and (3) multiple rigid objects. SANDROS is a dynamic-graph search algorithm, and can be described as a hierarchical, nonuniform-multiresolution, best-first search to find a heuristically short motion in the configuration space. The SANDROS planner is resolution complete, and its computation time is commensurate with the problem difficulty measured empirically by the solution-path complexity. For many realistic problems involving a manipulator or a rigid object with six degrees of freedom, its computation times are under 1 minute for easy problems involving wide free space, and several minutes for relatively hard problems.

We describe a learning user interface (LUI) for robot task planning and programming. A robot operator interacts with LUI with commands in a natural-language-like form, and teaches LUI new commands necessary to perform assigned tasks using the programming by demonstration paradigm. LUI has a basic set of commands for moving a robot. When a new form of a command is given along with a demonstration of how to execute the command in terms of a sequence of known commands, LUI abstracts and stores the demonstration sequence. The abstraction involves qualitative reasoning about spatial relationships of the robot and objects involved during the demonstration. LUI allows robot operators to teach and subsequently issue high-level, natural-language-like motion commands rather than precise numeric commands involving coordinate specifications. This capability can speed up robotic operations in many applications in which similar tasks must be carried out repetitively.

This paper presents a complete motion planner in three-dimensional changing environment. The robot is either a manipulator or a rigid object that translates and rotates, while obstacles are polyhedra translating and rotating along known trajectories. The motion planner is based on the SANDROS search strategy, which uses a hierarchical, multi-resolution representation of the product space of the time and the configuration space. A solution is found by generating a candidate sequence of subgoals and subsequently computing collision-free path along the sequence. For changing environments it is the first planner for non-point robots that is efficient and guarantees a solution. This planner can control the trade-offs between the computation resource and algorithmic completeness/solution path quality, and thus can fully utilize the available computing power. This algorithm is useful for navigation of mobile robots and submarines, or motion planning of multiple robots by regarding other robots as moving obstacles.

We present a learning algorithm that improves path planning by using past experience to enhance future performance. The algorithm relies on an existing path planner to provide solutions to difficult tasks. From these solutions, an evolving sparse network of useful robot configurations is learned to support faster planning. More generally, the algorithm provides a framework in which a slow but effective planner may be improved both cost-wise and capability-wise by a faster but less effective planner coupled with experience. We analyze the algorithm by formalizing the concept of improvability and deriving conditions under which a planner can be improved within the framework. The analysis is based on two stochastic models, one pessimistic (on task complexity), the other randomized (on experience utility). Using these models, we derive quantitative bounds to predict the learning behavior. We use these estimation tools to characterize the situations in which the algorithm is useful and to provide bounds on the training time. In particular, we show how to predict the maximum achievable speedup.

We present a motion planner for the classical mover's problem in three dimensions that is both resolution-complete and efficient in that it has performance commensurate with task difficulty. It is based on the SANDROS search strategy, which uses a hierarchical, multi-resolution representation of the configuration space along with a generate-and-test paradigm for solution paths. This planner can control the trade-offs between the computation resource and algorithmic completeness/solution path quality, and thus can fully utilize the available computing power. It is useful for navigation of mobile robots, submarines and spacecraft, or part motion feasibility in assembly planning.

In this paper, we present a new hybrid motion planner that is capable of exploiting previous planning episodes when confronted with new planning problems. Our approach is applicable when several (similar) problems are successively posed for the same static environment, or when the environment changes incrementally between planning episodes. At the heart of our system lie two low-level motion planners: a fast, but incomplete planner LOCAL, and a computationally costly (possibly resolution) complete planner GLOBAL. When a new planning problem is presented to our planner, an efficient meta-level planner MANAGER decomposes the problem into segments that are amenable to solution by LOCAL. This decomposition is made by exploiting a task graph, in which successful planning episodes have been recorded. In cases where the decomposition fails, GLOBAL is invoked. The key to our planner's success is a novel representation of solution trajectories, in which segments of collision-free paths are associated with the boundary of nearby obstacles. Thus we effectively combine the efficiency of one planner with the completeness of another to obtain a more efficient complete planner.>

We present a global motion planner for tracing curves in three dimensions with robot manipulator tool frames. This planner generates an efficient motion satisfying three types of constraints: constraints on the tool tip for curve tracing, robot kinematic constraints and robot link collision constraints. Motions are planned using a global search algorithm and a local planner based on a potential-field approach. This planner can be used with any robots including redundant manipulators and can control the trade-offs between its algorithmic completeness and computation time. It can be applied in many robotic tasks such as seam welding, caulking, edge deburring and chamfering, and is expected to reduce motion programming times from days to minutes.>

Path planning needs to be fast to facilitate real-time robot programming. Unfortunately, current planning techniques are still too slow to be effective, as they often require several minutes, if not hours of computation. To overcome this difficulty, we present an adaptive algorithm that uses past experience to speed up future performance. It is a learning algorithm suitable for incrementally-changing environments such as those encountered in manufacturing of evolving products and waste-site remediation. The algorithm allows the robot to adapt to its environment by having two experience manipulation schemes: for minor environmental change, we use an object-attached experience abstraction scheme to increase the flexibility of the learned experience; for major environmental change, we use an on-demand experience repair scheme to retain those experiences that remain valid and useful. Using this algorithm, we can effectively reduce the overall robot planning time by re-using the computation result for one task to plan a path for another.>

To address the need of a practical motion planner for manipulators, the authors present an efficient and resolution-complete algorithm that has performance commensurate with task difficulty. The algorithm uses SANDROS, a search strategy that combines hierarchical, nonuniform multiresolution, and best-first search to find a near-optimal solution in the configuration space. This algorithm can be applied to any manipulator, and has been tested with five- and six-degree-of-freedom robots, with execution times ranging from 20 seconds to 10 minutes on a 16 MIPS workstation.>

Determining the feasibility of a particular search program is important in practical situations, especially when the computation involved can easily require days, or even years. To help make such predictions, a simple procedure based on a stratified sampling approach is presented. This new method, which is called heuristic sampling, is a generalization of Knuth’s original algorithm for estimating the efficiency of backtrack programs. With the aid of simple heuristics, this method can produce significantly more accurate cost estimates for commonly used tree search algorithms such as depth-first, breadth-first, best-first, and iterative-deepening.

Path planning among movable obstacles is a practical problem that is in need of a solution. An efficient heuristic algorithm is presented that uses a generate-and-test paradigm: a good candidate path is hypothesized by a global planner and subsequently verified by a local planner. In the process of formalizing the problem, a technique for modeling object interactions through contact is presented. The algorithm has been tested on a variety of examples, and was able to generate solutions within 10 s on a 17-MIPS Sun Sparc workstation.>