Research Projects

-----


Randomized Motion Planning

Design and Manufacturing

Robot-Assisted Surgery

Autonomous Observers

Digital Actors

Computational Biology

Tissue Modeling for Surgical Planning

Rock-Climbing Robots

Slides on Computer Science and the Physical World (ps).
Slides on Motion Planning (ppt).
Slides on Randomized Motion Planning (ppt).
Slides on SBL Planner (ppt).
Slides on Sampling and Connection Strategies for PRM Planners (ppt).
Slides on Exact Collision Checking of Robot Paths (ppt).
Slides on Motion Planning with Visibility Constraints (ppt).
Slides on Real-Time Tracking of an Unpredictable Target Amidst Unknown Obstacles (ppt).

Slides on Climbing Robot (ppt)
Slides on Probabilistic Roadmaps: A Tool for Computing Ensemble Properties of Molecular Motions (ppt).

Slides on Exploration of Molecular Conformational Spaces (ppt)

Slides on Robotics Algorithms for the Study of Protein Structure and Motion (ppt)
Slides on Research Overview (ppt format).

MPK: Downloadable Motion Planning Kit:

·         C++-library and workbench for motion planning

·         Allows arbitrary number of robots and obstacles

·         New robots can be added without recompiling

·         Arbitrary kinematics for 'hardwired' robots

·         Efficient and exact dynamic collision checker

·         Flexible definition of collision sets and clearances

·         Automatic pruning of object pairs that cannot possibly collide

·         Includes SBL, a single query path planner with lazy collision checking

 

-----

In addition to the sources of funding acknowledged below, these projects have benefited from donations from Honda R&D Americas, Intel, Silicon Graphics, SUN Microsystems, and Microsoft.

-----

Randomized Motion Planning

The path planning problem in robotics is to generate a continuous path for a given robot between an initial and a goal configuration (or placement) of the robot. Along this path, the robot must not intersect given forbidden regions (usually, obstacles). This problem is PSPACE-hard and all known complete planning algorithms take exponential time in the number of degrees of freedom of the robot. This led us to develop a new planning scheme that samples the robot's configuration space at random, retains the collision-free configurations (called milestones), and tries to connect them by simple paths. The result is a graph, called a roadmap, in which the nodes are the milestones and the edges the simple paths. The initial and goal configurations of the robot are connected to milestones of this roadmap. We have proven that specific algorithms based on this scheme are probabilistically complete, i.e., if there exists a solution path, these algorithms will find one with high probability 1-q if the number of milestones N is large enough. For a family of configuration spaces, which we call expansive spaces, we also have shown that N grows as log(1/q). We are currently extending this scheme to path planning for nonholonomic robots and to time-optimal motion planning with dynamic constraints.
This research has been funded by DARPA contracts N00014-88-K-0620 and N00014-92- J-1809, by Army ARO MURI grant DAAH04-96-1-0007. and by grants from the Stanford Integrated Manufacturing Association (
SIMA) and from the Center of Integrated Facility Engineering (CIFE).

References:

Slides: For slides on the probabilistic roadmap approach click here.

-----

Design and Manufacturing

The goal is to develop software tools to bridge the gap between the design and the manufacturing of assembly products. We have designed efficient planning algorithms that compute assembly sequences for a given product. These algorithms also evaluate various measures of the complexity of assembling this product, e.g., the number of hands required, the complexity of the motions, the length of assembly line, etc. One extension of these algorithms handles toleranced parts. Another selects fixturing points to keep the intermediate subassemblies stable. Our software is intended to run in the background of a CAD system, in order to automatically provide feedback to the designers and help them create products that are more cost-effective to manufacture. We also apply planning techniques to check that specified parts can easily be removed from a given assembly for inspection and repai, in order to help designers create products that are easier to maintain and service. We now address the problem of automatically designing optimized layouts of robotic workcells to assemble given products.
This research has been funded by NSF grant IRI-9306544-001, grants from the Stanford Integrated Manufacturing Association (SIMA), and gifts from General Electric, General Motors, ABB, and Renault. Matra-Datavision has provided a free license of the CAD system CAS.CADE.

Slides on Motion Support for Virtual Prototyping.

References:

Slides: For slides on Motion Support for Virtual Prototyping click here.

-----

Robot-Assisted Surgery

The goal is to develop integrated systems that allow for minimally invasive surgery procedures. So far, we have mainly worked on stereotaxic radiosurgery. A focus beam of radiation is used to destroy a brain tumor. To avoid damaging healthy tissue, the tumor is targeted from many different directions. Doses deposited along the various directions are additive, so that the tumor eventually receive a necrotic amount of radiation. Prof. John Adler, in the Neurosurgery Department at Stanford Medical School, has developed a new radiosurgical system (the Cyberknife). In this system, the radiation beam is produced by a light-weight linear accelerator that is moved by a general six-degree-of-freedom robot arm, which makes it possible to target the tumor from virtually any direction. Our contribution to this system has been in treatment planning: Given a 3-dimensional map of the brain tissues obtained through medical imaging, find the beam configurations that will destroy the tumor. The problem is made complicated by three factors: (i) Some healthy structures are critical and should receive very little dose, at most; (ii) Some tumors have complex shapes and grow close to critical structures; (iii) The number of beam configurations is limited, since it directly affects the duration of the treatment.
This research has been funded in part by the Sheik Enany Fund, Lorraine Ulshafer Fund, and by the Library of Medecine (LM-05305 and LM-07033). It also makes use of results in randomized motion planning obtained under DARPA contracts DAAA21-89-C0002 and N00014-92-J-1809, and Army ARO MURI grant DAAH04-96-1-0007.

References

-----

Autonomous Observers

We are building a system in which cooperative mobile robots equipped with cameras perform vision tasks with a high degree of autonomy in cluttered environments. We call these robots autonomous observers. Their design yields new challenging problems in motion planning, in which visibility and motion obstructions must be simultaneously taken into account. Currently, we consider three such problems: (i) model building, (ii) target finding, and (iii) target tracking. The need for autonomous observers arises in a variety of applications. For instance, medical surgeons often operate by watching graphic displays of key tissues; an autonomous observer could be used to maintain visibility of the tissues in spite of obstructions caused by people and complex mechanical instruments. Autonomous observers can also assist in distributed collaborations: researchers at one institution may want to conduct an experiment using robotic hardware at another institution; autonomous observers could then be used to gather and transmit crucial real-time information allowing the remote researchers to effectively monitor their experiment. Other applications include military surveillance and threat assessment, monitoring of manufacturing operations in an assembly plant, search/rescue in a potentially hostile environment, supervision of automated construction efforts in space, and television broadcast allowing each viewer to select his/her viewpoint. Many of these applications require several basic, high-level vision-oriented operations, such as locating and tracking moving targets, or automatic model construction. Although similar problems have been studied in other contexts, one distinguishing characteristic in our work is the satisfaction of geometric visibility constraints in the planning and execution of motion strategies.
Part of this project is done in collaboration with Prof. Ruzena Bajcsy at the University of Pennsylvania (GRASP Lab) and Prof. Jose Luis Gordillo-Moscoso at the ITESM institute (Monterrey, Mexico).
This research has been funded by DARPA grant N00014-94-1-0721, NSF grant IRI-9506064, and Army ARO MURI grant DAAH04-96-1-007.

Java Applet

For seeing a collection of animated examples computed by our target-finding planner, click here.

References

-----

Digital Actors

The goal is to create virtual actors modelling real or fictional humans that can move and act realistically on a graphic display. We equip these actors with capabilities that make it possible to direct them using high-level instructions. We use motion planning techniques to enable the actors to compute their own motions in order to achieve the goals stated in the high-level instructions. The core of the project is the design and implementation of a digital actor architecture that has many similarities with a robot control architecture. Each digital actor has an imperfect model of the world which it uses for planning. But, in order to generate realistic behaviors, execution occurs in another model, which represents the real world and is displayed. The actor accesses this second model though simulated sensors. For example, simulating vision requires computing the regions of the world that are actually visible by the actor at his/her current position. The digital actor is also equipped with both real-time motion control techniques to deal with small discrepancies between the planning and the world models and replanning capabilities to handle bigger differences. The actor also uses its sensory inputs to update his/her planning model. Applications of this research include movie generation, video games, and military simulation.
This research has been funded by Army ARO MURI grant DAAH04-96-1-007. It reuses results obtained under grants DARPA contracts DAAA21-89-C0002 and N00014-92-J-1809,

References

-----

Computational Biology

Pharmaceutical drug design is a long and expensive process. Early selection of promising molecules can dramatically improve this process. Pharmaceutical companies have access to large databases of molecules. Efficient database screening can therefore be a major tool for selecting the molecules on which the chemists will then focus their efforts. A major question, however, is the following: What should one be looking for? In many cases, chemists are looking for molecules that are likely to have a certain type of activity, which is usually the result of this molecule binding at a protein site. But, this activity is directly not encoded in the data base. Moreover, the protein structure and the binding site are often unknown. On the other hand, through experiments chemists can collect a small number of molecules (5 to 10) that exhibit the desired activity to some extent. It is then hypothesized that these molecules have a 3-dimensional atomic substructure in common, the substructure that is involved in the binding against the protein. The problem is to identify this substructure (called a pharmacophore). It is complicated by the fact that a drug molecule (which contains between 20 and 50 atoms) is highly flexible. The molecule can achieve many (on the order of several hundreds) low-energy states. We have developed software tools to solve the following subproblems:

(i) Conformational search: Given a candidate drug molecule, find all low-energy conformations of the molecule. Our software is based on sampling at random the conformation space of the molecule, using optimization techniques to minimize the energy of the sampled conformations, and on grouping the obtained low-energy conformations into clusters.

Different clusters found for the 1TLP molecule (see below):



(ii) Pharmacophore identification: Given a small collection of candidate drug molecules, find all 3-dimensional invariants that appear in at least one low-energy conformation of each molecule. Our software use an efficient randomized technique to extract all potential invariants from a pair of molecule. It then uses the same technique to compare these invariants with the other molecules.

Conformations of the 1TLP, 4TMN, 5TMN, and 6TMN molecules (inhibitors of thermolysin) :


The four conformations of the molecules in which the pharmacophore was found (the conformations overlap at the pharmacophore):



(iii) Database screening: Given a database of molecules and a pharmacophore, find all the molecules that admit a low-energy conformation that contains the pharmacophore. Here, we have adapted our conformational search software to take advantage of the fact that the given pharmacophore reduces the number of degrees of freedom of the molecules in the database.


(iv) Prediction of ligand-protein binding motions: Given a protein structure and a flexible ligand, find plausible binding motions. Our software uses a probabilistic roadmap technique, biased by the energy of the ligand, to generate low-energy binding motions.




A large fraction of this project has been conducted in collaboration with Dr. Paul Finn, who heads the Computational Chemistry group at Pfizer Pharmaceuticals in Sandwich, UK. We also work with Prof. Lydia Kavraki, in the Computer Science Department at Rice University, Houston, and with Prof. Doug Brutlag, in the Biochemistry Department at Stanford.
Part of this research was funded by a contract with Pfizer Pharmaceuticals. Tripos has provided a free license of the Sybyl software. Current research is being funded by a
National Science Foundation ITR grant CCR-0086013 and by a grant from the Stanford's BioX program.

References

-----

Tissue Modeling for Surgical Planning

This project ( research proposal) is aimed at developing efficient and realistic generic computer models of anisotropic, non-homogeneous, non-linear, visco-elastic tissues, to be used in virtual environments for surgical training and planning. Our models are mass-spring meshes. One specific application of this research is the development of a training tool for microvascular surgery (anastomosis of micro blood vessels). Another potential application is craniofacial surgical planning with the goal to show how the soft tissues would respond to underlying bone movements.




The following three figures illustrate pour virtual environment for blood vessel suturing. The surgical tools (e.g., the forceps, the needle) are attached to magnetically tracked devices.




An important goal of our research is to allow topological changes in the simulated tissue, such as those which are caused by new contacts or by cutting operations. The following two pictures illustrate the effect of a cutting operation:




Another of our goals is to automatically learn the parameters of a mesh representing a tissue structure by observing the deformations of this structure. A step toward this goal is to automatically build meshes from surfaces sensed with a laser range sensor. The following mesh was derives from the data provided by a laser scanner.




This research is conducted in collaboration with Prof. Michael Stephanides and Dr. Kevin Montgomery at the Stanford-NASA Biocomputation Center. It has been funded by a grant from the National Science Foundation (IIS-9907060-001). cp weld1R.avi ~latcp weld1R.avi ~latcp weld1R.avi ~latcp weld1R.avi ~latombe/laptop/weld1R.avi

References

-----

Rock-Climbing Robots and Knot Tying

 click here for a video


Visit the websites of Tim Bretl and Joel Brown.