Research Projects
Slides
on Computer Science
and the Physical World (ps format).
Slides
on Motion Planning (ppt format).
Slides
on Randomized Motion Planning (ppt format).
Slides
on SBL Planner (ppt format).
Slides
on Sampling and Connection Strategies for PRM Planners (ppt format).
Slides
on Exact Collision Checking of Robot Paths (ppt format).
Slides
on Motion Planning with Visibility Constraints (ppt format).
Slides
on Real-Time Tracking of an Unpredictable Target Amidst Unknown Obstacles (ppt format).
Slides
on Probabilistic Roadmaps: A Tool for Computing Ensemble Properties
of Molecular Motions (ppt format).
Slides
on Research Overview (ppt format).
Downloadable code of the SBL planner
(for Single-query, Bi-directional,
Lazy collision-checking), a very efficient PRM planner
developed by Gildardo Sánchez-Ante.
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.
- 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, Workshop on Algorithmic Foundations
of Robotics (WAFR), Nice, Dec. 2002.
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.
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.
Workshop on Algorithmic Foundations
of Robotics (WAFR), Nice, Dec. 2002.
- Identifying
Structural Motifs in Proteins
R. Singh and M. Saha.
Pacific Symp. on Biocomputing (PSB), Lihue, Kauai, Hawaii, Jan. 2003.
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 is being 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. Montgomcp weld1R.avi ~latery, 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.