Research Projects
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.
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:
- Robot Motion Planning: A
Distributed Representation Approach. J. Barraquand and J.C. Latombe.
International Journal of Robotics Research, 10(6):628-649, 1991.
- On Computing Multi-Arm
Manipulation Trajectories. Y. Koga. PhD Thesis, Mechanical Engineering
Dept., Stanford University, August 1994.
- Random Networks in
Configuration Space for Fast Path Planning. L.E. Kavraki. PhD Thesis,
Computer Science Dept., Tech. Rep. STAN-CS-TR-95-1535, Stanford
University, January 1995.
- Probabilistic
Roadmaps for Path Planning in High-Dimensional Configuration Spaces.
L.E. Kavraki, P. Svestka, J.C. Latombe, and M. Overmars. IEEE Transactions
on Robotics and Automation, 12(4):566-580, 1996.
- Analysis of Probabilistic Roadmaps
for Path Planning. L.E. Kavraki, M. Kolountzakis, and J.C. Latombe.
Proc. of the IEEE International Conference on Robotics and Automation, pp.
3020-3025, 1996. Also in IEEE Tr.~on Robotics and Automation,
14(1):166-171, Feb.~1998.
- A
Random Sampling Scheme for Path Planning. J. Barraquand, L.E. Kavraki,
J.C. Latombe, T.Y. Li, R. Motwani, and P. Raghavan. International Journal
of Robotics Research, 16(6):759-774, 1997.
- Randomized
Query Processing in Robot Motion Planning. L.E. Kavraki, J.C. Latombe,
R. Motwani, and P. Raghavan. Journal
of Computer and System Sciences, 57(1):50-60, August 1998.
- Path
Planning in Expansive Configuration Spaces. D. Hsu, J.C. Latombe, and
R. Motwani. Proc. 1997 IEEE International Conference on Robotics and
Automation. A revised
version of this paper appeared in International Journal of
Computational Geometry and Applications, 9(4-5):495-512, 1999.
- On
Finding Narrow Passages with Probabilistic Roadmap Planners. D. Hsu,
L.E. Kavraki, J.C. Latombe, R. Motwani, and S. Sorkin. In Robotics: The
Algorithmic Perspective, Workshop on Algorithmic Foundations of
Robotics, P.K. Agarwal, L.E. Kavraki, and M.T. Mason (eds.), A K Peters,
Natick, MA, pp. 141-153, 1998.
- Capturing
the Connectivity of High-Dimensional Geometric Spaces by Parallelizable
Random Sampling Techniques. In Advances in Randomized Parallel
Computing, P.M. Pardalos and S. Rajasekaran (eds.), Combinatorial
Optimization Series, Kluwer Academic Publishers, Boston, MA, 159-182,
1999.
- Probabilistic
Roadmaps for Robot Path Planning. L.E. Kavraki and J.C. Latombe. In Practical
Motion Planning in Robotics: Current Approaches and Future Directions,
K. Gupta and A. del Pobil (eds), John Wiley, pp. 33-53, 1998.
- Randomized
Kinodynamic Planning. Steve Lavalle and James Kuffner, Proc. IEEE Int.
Conf. on Robotics and Automation, 1999.
- Randomized
Kinodynamic Motion Planning with Moving Obstacles. D. Hsu, R. Kindel,
J.C. Latombe, S. Rock. Proc. Workshop on Algorithmic Foundations of
Robotics (WAFR'00), Hanover, NH, March 2000.
- Kinodynamic
Motion Planning Amidst Moving Obstacles.R. Kindel, D. Hsu, J.C.
Latombe, S. Rock. Proc. IEEE Int. Conf. on Robotics and Automation,
San Francisco, CA, 2000.
- Randomized
Kinodynamic Motion Planning with Moving Obstacles. D. Hsu, R. Kindel,
J.C. Latombe, S. Rock. Int. J. of Robotics Research, 21(3):233-255,
March 2002.
- A
Single-Query Bi-Directional Probabilistic Roadmap Planner with Lazy
Collision Checking. G. Sanchez and J.C. Latombe. Int. Symposium on
Robotics Research (ISRR'01), Lorne, Victoria, Australia, November
2001. Published in Robotics
Research: The Tenth Int. Symp., R.A. Jarvis and A. Zelinsky (eds.),
Springer Tracts in Advanced Robotics, Springer, pp. 403-417, 2003.
- On
Delaying Collision Checking in PRM Planning -- Application to Multi-Robot
Coordination. G. Sanchez and J.C. Latombe. Int. J. of Robotics
Research, 21(1):5-26, January 2002.
- Using
a PRM Planner to Compare Centralized and Decoupled Planning for
Multi-Robot Systems. G. Sanchez and J.C. Latombe. IEEE Int. Conf.
on Robotics and Automation, 2002.
- Exact
Collision Checking of Robot Paths. F. Schwarzer, M. Saha, and J.C.
Latombe, In Algorithmic Foundations of Robotics V, J.D. Boissonnat, J. Burdick, K. Goldberg,
and S. Hutchinson (eds.), Springer Tracts in Advanced Robotics, Springer,
pp. 25-41, 2004.
- Adaptive
Dynamic Collision Checking for Single and Multiple Articulated Robots in
Complex Environments, F. Schwarzer, M. Saha, and J.C. Latombe,
2003.
- Dynamic
Networks for Motion Planning in Multi-Robot Space Systems. C.M. Clark,
S.M. Rock, and J.C. Latombe, 7th
International Symposium on Artificial Intelligence, Robotics and
Automation in Space,
Nara, Japan, May 2003.
- Motion Planning for Multiple
Mobile Robot Systems Using Dynamic Networks. C.M. Clark, S.M. Rock,
and J.C. Latombe, IEEE Int. Conference on Robotics and Automation,
Taipei, Taiwan, 2003.
- Planning Multi-Goal Tours for Robot
Arms. M. Saha, G. Sanchez, and J.C. Latombe. IEEE Int. Conference
on Robotics and Automation, Taipei, Taiwan, 2003.
Slides: For slides on the probabilistic roadmap
approach click here.
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:
- On Geometric Assembly
Planning. R.H. Wilson. PhD Thesis. Computer Science Dept., Stanford
University, 1992.
- Geometric
Reasoning about Mechanical Assembly. R.H. Wilson and J.C. Latombe.
Artificial Intelligence, 71(2):371-396, 1995.
- Two-Handed
Assembly Sequencing. R.H. Wilson, L.E Kavraki, J.C. Latombe, and T.
Lozano-Perez. The International Journal of Robotics Research,
14(4):335-350, 1995.
- A
General Framework for Assembly Planning: The Motion Space Approach. D.
Halperin, J.C. Latombe, and R.H. Wilson. To appear in Algorithmica,
Special issue on Robot Algorithms. A shorter version
will also appear in the Proc. of the ACM Symp. on Computational Geometry.
- An
Efficient System for Geometric Assembly Sequence Generation and
Evaluation. B. Romney, C. Godard, M. Goldwasser, and G. Ramkumar,
Proc. ASME International Computers in Engineering Conference, Boston, pp.
699-712, 1995.
- Complexity
Measures for Assembly Sequences. M. Goldwasser, J.C. Latombe, and R.
Motwani, Proc. of the IEEE International Conference on Robotics and
Automation, pp. 1851-1857, 1996.
- Assembly
Sequencing with Toleranced Parts. J.C. Latombe, R.H. Wilson, and F.
Cazals. Computer-Aided Design, 29(2):159-174, 1997.
- On
the Concurrent Design of Assembly Sequences and Fixtures. B. Romney.
PhD Thesis, Electrical Engineering Dept., Stanford University, 1997.
- Atlas:
An Automatic Assembly Sequencing and Fixturing System. B. Romney.
Proc. Int. Conf. on the Theory and Practice of Geometric Modelling, W.
Strasser, R. Klein, and R. Rau (eds.), Springer-Verlag, 1997, pp. 397-415.
- Polyhedral
Assembly Partitioning Using Maximally Covered Cells in Arrangements of
Convex Polygons. L.J. Guibas, D. Halperin, H. Hirukawa, J.C. Latombe,
and R.H. Wilson. International Journal of Computational Geometry and its
Application, 8(2):179-199, 1998.
- On-Line Robot Motion Planning
in a Dynamic Environment. T.Y. Li. PhD Thesis, Mechanical Engineering
Dept., Stanford University, 1995.
- On-Line
Manipulation Planning for Two Robot Arms in a Dynamic Environment.
T.Y. Li and J.C. Latombe. International Journal of Robotics Research,
16(2):144-167, 1997.
- Assembly
Maintainability Study with Motion Planning. H. Chang and T.Y. Li, Proc.
of the IEEE International Conference on Robotics and Automation, pp.
1012-1019, 1995.
- Placing
a Robot Manipulator Amid Obstacles for Optimized Execution. D. Hsu,
J.C. Latombe, and S. Sorkin, Proc. IEEE Int. Symp. on Assembly and Task
Planning (ISATP'99), 1999 Porto, Portugal, pp. 280-285, 1999.
Slides: For slides on Motion Support for Virtual
Prototyping click here.
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
- Motion Planning in
Stereotaxic Radiosurgery. A. Schweikard, J.R. Adler, and J.C. Latombe.
IEEE Transactions on Robotics and Automation, 9(6):764-774, 1993.
- Treatment
Planning for a Radiosurgical System with General Kinematics. A.
Schweikard, R. Tombropoulos, L.E Kavraki, J.R. Adler, and J.C. Latombe.
Proc. IEEE International Conference on Robotics and Automation, pp.
1720-1727, 1994.
- Treatment
Planning for Image-Guided Robotics Radiosurgery. R. Tombropoulos, A.
Schweikard, J.C. Latombe, and J.R. Adler. In Lecture Notes in Computer
Science 905, N. Ayache (ed.) Springer, New York, NY, pp. 131-137, 1995.
- A
General Algorithm for Beam Selection in Radiosurgery. R. Tombropoulos,
J.C. Latombe, and J.R. Adler. Preprints of the IARP Workshop on Medical
Robotics, Vienna, pp. 91-98, 1996.
- Treatment planning for
Image-Guided Robotic Radiosurgery. R. Tombropoulos. PhD Thesis, Medical
Information Sciences, Stanford University, 1997.
- Inverse Treatment Planning
for the Cyberknife. R.
Tombropoulos, J.C. Latombe, and J.R. Adler. Radiosurgery,
2:236-250, Karger, Basel, 1998.
- CARABEAMER:
A Treatment Planner for a Robotic Radiosurgical System with General
Kinematics. R. Tombropoulos, J.R. Adler, and J.C. Latombe. Medical
Image Analysis, 3(3):237-264, 1999.
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
- An Intelligent Observer. C.
Becker, H. Gonzalez-Banos, J.C. Latombe, and C. Tomasi. In Lecture Notes
in Control and Information Sciences 223, O. Khatib and J.K. Salisbury
(eds.), Springer, New York, NY, pp. 153-160, 1997
- Finding
an Unpredictable Target in a Workspace with Obstacles. S.M. LaValle,
D. Lin, L.J. Guibas, J.C. Latombe, and R. Motwani. Proc. 1997 IEEE
International Conference on Robotics and Automation.
- Motion
Strategies for Maintaining Visibility of a Moving Target. S.M.
LaValle, H. Gonzalez-Banos, C. Becker, and J.C. Latombe. Proc. 1997 IEEE
International Conference on Robotics and Automation.
- Visibility-Based
Pursuit-Evasion in a Polygonal Environment. L.J. Guibas, J.C. Latombe,
S.M. LaValle, D. Lin, and R. Motwani. Proc. 5th Int. Workshop on
Algorithms and Data Structures (WADS'97), Halifax, Nova Scotia, Canada;
published as Lecture Notes in Computer Science 1272, F. Dehne, A.
Rau-Chaplin, J.R. Sack, and R. Tamassia (eds.), pp. 17-30, 1997.
- Motion
Planning with Visibility Constraints: Building Autonomous Observers.
H.H. Gonzalez-Banos, L.J. Guibas, J.C. Latombe, S.M. LaValle, D. Lin, R.
Motwani, and C. Tomasi. In Robotics Research - The Eighth International
Symposium, Y. Shirai and S. Hirose (eds.) Springer, pp. 95-101, 1998.
- A
Visibility-Based Pursuit-Evasion Problem. L.J. Guibas, J.C. Latombe,
S.M. LaValle, D. Lin, and R. Motwani. International Journal of
Computational Geometry and Applications, 9(5):471-194, Oct. 1999.
- Planning
Robot Motions for Range-Image Acquisition and Automatic 3D Model
Construction. H.H. Gonzalez-Banos and J.C. Latombe, AAAI Fall
Symposium, 1998.
- Dealing with Geometric
Constraints in Game-Theoretic Planning. P. Fabiani and J.C. Latombe. Proc. IJCAI'99, 1999.
- The
Autonomous Observer: A Tool for Remote Experimentation in Robotics.
H.H. Gonzalez-Banos, J.L. Gordillo, D. Lin, J.C. Latombe, A. Sarmiento,
and C. Tomasi. Proc. SPIE Conf. on Telemanipulator and Telepresence
Technologies, Sept. 1999 (to appear). (html
file.)
- Planning
Robot Motion Strategies for Efficient Model Construction. H.H.
Gonzalez-Banos, E. Mao, J.C. Latombe, T.M. Murali, and A. Efrat. Robotics
Research -- The 9th Int. Symposium, J.M. Hollerbach and D.E.
Koditschek (eds.), Springer, pp. 345-352, 2000.
- Robot
Navigation for Automatic Model Construction Using Safe Regions. H.H.
Gonzalez-Banos and J.C. Latombe. Experimental Robotics VII. D. Russ
and S. Singh (eds.), Lecture Notes in Control and Information Sciences,
271, Springer, pp. 405-415, 2001. (Proc. of Int. Symposium on Experimental
Robotics (ISER'01), Waikiki, HI, December 2000.)
- A
Randomized Art-Gallery Algorithm for Sensor Placement. H.H. Gonzalez-Banos
and J.C. Latombe. ACM Symp. on Computational Geometry (SoCG'01),
2001.
- Tracking a
Partially Predictable Target with Uncertainties and Visibility
Constraints. P. Fabiani. H.H. Gonzalez-Banos, J.C. Latombe, and D.
Lin. J. of Robotics and Autonomous Systems, 38(1):31-48, 2002.
- Real-Time
Combinatorial Tracking of a Target Moving Unpredictably Among Obstacles.
H.H. Gonzalez-Banos, C.Y. Lee, and J.C. Latombe. Proc. IEEE Int. Conf.
on Robotics and Automation, Washington D.C., May 2002.
- Real-Time
Tracking of an Unpredictable Target Amidst Unknown Obstacles. C.Y.
Lee, H.H. Gonzalez-Banos, and J.C. Latombe. To appear in Proc. Int.
Conf. on Control, Automation, Robotics and Vision (ICARCV'02),
Singapore, Dec. 2002.
- Navigation
Strategies for Exploring Indoor Environments. H.H. Gonzalez-Banos and
J.C. Latombe. International Journal of Robotics Research.
21(10-11):829-848, Oct-Nov. 2002.
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
- Planning
Motions with Intentions. Y. Koga, K. Kondo, J. Kuffner, and J.C.
Latombe. Proc. SIGGRAPH'94, pp. 395-408, 1995.
- Goal-Directed
Navigation for Animated Characters Using Real-Time Path Planning and
Control". J. Kuffner. Proc. CAPTECH '98: Workshop
on Modelling and Motion Capture Techniques for Virtual Environments,,
Geneva, Switzerland, Nov. 26-28, 1998.
- Perception-Based
Navigation for Animated Characters in Real-Time Virtual Environments".
J. Kuffner and J.C. Latombe. 1999.
- Fast
Synthetic Vision, Memory, and Learning for Virtual Humans. J. Kuffner
and J.C. Latombe. Proc. of Computer Animation, IEEE, pp. 118-127,
May 1999.
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
- Geometric
Manipulation of Flexible Molecules. P.W. Finn, D. Halperin, L.E.
Kavraki, J.C. Latombe, R. Motwani, C. Shelton, and S. Venkatasubramanian.
In Lecture Notes in Computer Science 1148, M.C. Lin and D. Manocha (eds.),
Springer, New York, NY, pp. 67-78, 1996.
- RAPID:
Randomized Pharmacophore Identification for Drug Design. P.W. Finn,
L.E. Kavraki, J.C. Latombe, R. Motwani, C. Shelton, S. Venkatasubramanian,
and A. Yao. Proc. of 13th ACM Symp. on Computational Geometry (SoCG'97),
pp. 324-333, 1997. A revised
version of this paper also appeared in Computational Geometry:
Theory and Applications, 10, pp. 263-272, 1998.
- A
Perturbation Scheme for Spherical Arrangements with Application to
Molecular Modeling D. Halperin and C. Shelton, Proc. of 13th ACM Symp.
on Computational Geometry (SoCG'97), 1997.
- Search
Techniques for Rational Drug Design. P.W. Finn, L.E. Kavraki, J.C.
Latombe, R. Motwani, and S. Venkatasubramanian. Proc. of IASTED Int. Conf.
on Intelligent Information Systems, Bahamas, pp. 2-6, Dec. 8-10, 1997.
- Efficient
Database Screening for Rational Drug Design Using
Pharmacophore-Constrained Conformational Search. S.M. LaValle, P.W.
Finn, L.E. Kavraki, and J.C. Latombe. Proc. 3rd Int. Conf. on
Computational Biology (RECOMB'99), pp.~250-259, 1999.
- A
Motion Planning Approach to Flexible Ligand Binding. A.P. Singh, J.C.
Latombe, and D.J. Brutlag. Proc. 7th Int. Conf. on Intelligent Systems
for Molecular Biology (ISMB), AAAI Press, Menlo Park, CA, pp. 252-261,
1999.
- A
Randomized Kinematics-Based Approach to Pharmacophore-Constrained
Conformational Search and Database Screening. S.M. LaValle, P.W. Finn,
L.E. Kavraki, and J.C. Latombe. J. of Computational Chemistry,
21(9):731-747, July 2000.
- Capturing
Molecular Energy Landscapes with Probabilistic Conformational Roadmaps.
M.S. Apaydin, A.P. Singh, D.L. Brutlag, and J.C. Latombe. IEEE Int.
Conf. on Robotics and Automation, Seoul, Korea, April 2001.
- Stochastic
Roadmap Simulation: An Efficient Representation and Algorithm for
Analyzing Molecular Motion.. M.S. Apaydin, D.L. Brutlag, C. Guestrin,
D. Hsu. and J.C. Latombe. Proc. RECOMB'02, Washington D.C., pp.
12-21, 2002.
- Studying
Protein-Ligand Interactions with Stochastic Roadmap Simulaton.. M.S.
Apaydin, C. Guestrin, C. Varma, D.L. Brutlag, and J.C. Latombe. Bioinformatics,
Vol. 18, Suppl. 2, pp. 18-26, Oct. 2002. (Proc. European Conf. on
Computational Biology, ECCB 2002, Saarbrucken, Germany.)
- Stochastic
Conformational Roadmaps for Computing Ensemble Properties of Molecular
Motion M.S. Apaydin, D.L. Brutlag, C. Guestrin, D. Hsu, J.C. Latombe.
In Algorithmic Foundations of Robotics V, J.D. Boissonnat, J. Burdick, K. Goldberg, and S. Hutchinson
(eds.), Springer Tracts in Advanced Robotics, Springer, pp.
131-147, 2004.
- Identifying
Structural Motifs in Proteins R. Singh and M. Saha. Pacific Symp.
on Biocomputing (PSB), Lihue, Kauai, Hawaii, Jan. 2003.
- Approximation
of Protein Structure for Fast Similarity Measures. F. Schwarzer and I.
Lotan, Proc. RECOMB’03,
Berlin, Germany, April 2003.
- Stochastic
Roadmap Simulation: An Efficient Representation and Algorithm for
Analyzing Molecular Motion. M.S. Apaydin, D.L. Brutlag, C. Guestrin,
D. Hsu, J.C. Latombe, and C. Varma. J.
Computational Biology, 10(3-4):257-281, 2003.
- Efficient
Energy Computation for Monte Carlo Simulation of Proteins. I. Lotan,
F. Schwarzer, J.C. Latombe, 3rd Workshop on Algorithms in Bioinformatics (WABI),
Budapest, Hungary, Sept., 2003.
- Algorithm
and Data Structures for Efficient Energy Maintenance During Monte Carlo
Simulation of Proteins. I. Lotan, F. Schwarzer, D. Halperin, J.C.
Latombe, J. Computational Biology,
11(5):902-932, 2004.
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
- Efficient
Distance Computation and Collision Detection Between Deformable Objects.
S. Sorkin. Honors Undergraduate Thesis, Computer Science Department,
Stanford University, June 2000.
- A
Microsurgery Simulation System. J. Brown, K. Montgomery, J.C. Latombe,
and M. Stephanides. 4th Int. Conf. on Medical Image Computing and
Computer-Assisted Intervention, Utrecht, The Netherlands, October
2001.
- Real-Time
Simulation of Deformable Objects: Tools and Application. J. Brown, S.
Sorkin, C. Bruyns, J.C. Latombe, K. Montgomery, and M. Stephanides. Computer
Animation, Seoul, Korea, November 2001.
- Algorithmic
Tools for Real-Time Microsurgery Simulation. J. Brown, S. Sorkin, J.C.
Latombe, K. Montgomery, and M. Stephanides. Medical Image Analysis,
Elsevier, 6(3):289-300, September 2002.
- Real-Time
Knot Tying Simulation. J. Brown, J.C. Latombe, and K. Montgomery. The Visual Computer J., 20(2-3):165-179, May 2004.
Rock-Climbing Robots and Knot Tying
click here for a video
- Motion
Planning for a Three-Limbed Climbing Robot in Vertical Natural Terrain.
T. Bretl, S.M. Rock, and J.C. Latombe, IEEE Int. Conf. on Robotics and
Automation, Taipei, Taiwan, 2003.
- Climbing
Robots in Natural Terrain. T. Bretl, T. Miller, S.M. Rock, and J.C.
Latombe, 7th Int. Symp.
on Artificial Intelligence, Robotics and Automation in Space, Nara, Japan, May 2003.
- Toward
Autonomous Free-Climbing Robots. T. Bretl, J.C. Latombe, and S. Rock, 11th Int. Symp. on Robotics
Research, Siena, Italy, Oct. 19-22, 2003. Published in P. Dario and R.
Chatila (eds.), Robotics Research, Springer, pp. 6-15, 2005.
- Real-Time
Knot Tying Simulation. J. Brown, J.C. Latombe, and K. Montgomery. The Visual Computer J.,
20(2-3):165-179, May 2004.
- Free-Climbing with a
Multi-Use Robot. T. Bretl, S.M. Rock, J.C. Latombe, B. Kennedy,
and H. Aghazarian. 9th
Int. Symp. on Experimental Robotics, Singapore, 18-21 June 2004.
Visit
the websites of Tim Bretl and Joel Brown.