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.

This paper presents a compliant control method for insertion of complex objects with concavities. Most work on robot assembly using compliant motion control focuses on overcoming jamming conditions for simple peg-in-hole problems, and cannot be used for complex shapes frequently encountered in assembly applications. When an object is being inserted into a hole or slot with a small clearance, a contact path issued to compensate for uncertainties. When the object shape is complex, however, the contact state changes several times and severely, making compliant control difficult. Our algorithm is capable of controlling compliant motion in spite of changing contact states. During the execution of a nominal motion plan, it computes the actual position of the contact point from the force/torque sensor reading using a contact localization algorithm. It then dynamically updates the center of compliance to the computed contact point, and minimizes the chance of jamming and unwanted collisions. The control scheme has been implemented on hardware and tested on the task of inserting a T-shape into a C-shape involving a very tight tolerance. The insertion motion was accomplished by a sequence of 2 translational and 1 rotational compliant motions, and successfully executed by the proposed compliant motion controller.

We discuss the integration of the SANDROS path planner into a general robot simulation and control package with the inclusion of a fast geometry engine for distance calculations. This creates a single system that allows the path to be computed, simulated, and then executed on the physical robot. The architecture and application procedures are presented. Also, we present examples of its usage in typical environments found in our organization. The resulting system is as easy to use as the general simulation system and is fast enough to be used interactively on an everyday basis.

This paper presents a motion planner for robots in a game situation, in which the agents involved have conflicting goals. More specifically, a human-computer boxing game system is developed in a graphical environment. One boxer is controlled by a human through a motion tracking system, while the other is controlled by a motion planning algorithm. The planner has a defensive and an offensive strategies. The defensive strategy tries to move one of the forearms between the opponent's fist and its body, while the offensive strategy locates an exposed part of the opponent's body and throws a punch at it. To achieve an interactive operation, the motion planner considers only kinematic and geometric constraints during the search. This project is also aimed at integrating a planner with all actual robot, and investigating associated technological bottlenecks.

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 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.

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.>

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.>

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.>

A method is described for obtaining the boundary equations of configuration obstacles for stick-figure manipulators in three-dimensional environments. Polyhedral obstacles are represented as a collection of planar triangular patches, and the intersection conditions between a line segment and a triangular patch are used to derive boundary equations. It is shown that the boundary equation for the nth joint variable can be solved explicitly in terms of the 0th, 1st, . . ., (n-1)th joint variables. The expressions can be used to compute configuration obstacles or to analyze the geometry of contacts between manipulators and obstacles.>