Research Projects
(Last updated, July 2006. For the
earlier “Research Projects” page see here.)
The
goal of our research is to design and test new algorithms and techniques to represent,
sense, plan, and control motions of physical objects. One key
underlying issue is to efficiently capture the connectivity of configuration or
state spaces that are both high-dimensional and geometrically complex. Current
projects aim at extending Probabilistic Road-Map (PRM) motion planners, sensing
and manipulating deformable objects, simulating large bio-molecules (proteins),
and designing new techniques to enable multi-limbed robots to navigate on
severely rough (broken, irregular, steep, non rigid) terrain.
Probabilistic
roadmaps are a key tool used (and for
a large part developed) in our group to represent the connectivity of complex,
high-dimensional motion spaces. There is an extensive literature on PRM. For an
introduction, see:
-
L.E. Kavraki, P. Svestka, J.C. Latombe, and M.
Overmars. Probabilistic
Roadmaps for Path Planning in High-Dimensional Configuration Spaces. IEEE
Transactions on Robotics and Automation, 12(4):566-580, 1996.
-
L.E. Kavraki. Sampling-Based Algorithms. In Principles
of Robot Motion: Theory, Algorithms, and Implementation, H. Choset et al.
(eds.), Chapter 7, 197-267, MIT Press, 2005.
Slides on PRM are also available here:
- Motion Planning (ppt).
- Randomized Motion Planning (ppt).
- SBL Planner (ppt).
-
Sampling and
Connection Strategies for PRM Planners (ppt).
-
On the Probabilistic
Foundations of Probabilistic Roadmaps (ppt) [Invited talk given at
WAFR’06]
A downloadable PRM toolkit (MPK: Motion Planning Kit) is available here.
Recent and current projects:
·
Adaptive dynamic collision
checking
·
Small-step retraction in PRM
planning
·
3-D Sensing of deformable objects
·
Humanoid robots on rough terrain
·
Modeling flexible protein loops
Adaptive dynamic collision checking
Static collision checking amounts to testing a given configuration of objects for overlaps. In contrast, the goal of dynamic checking is to determine whether all configurations along a continuous path are collision-free. While effective methods are available for static collision detection, dynamic checking still lacks methods that are both reliable and efficient. A common approach – frequently used in PRM planners – is to sample paths at some fixed, pre-specified resolution and statically test each sampled configuration. But this approach is not guaranteed to detect collision whenever one occurs, especially when objects are thin (Figure 1). One may increase the reliability of the approach by refining the sampling resolution along the entire path, but a finer resolution increases the running time of the collision checker. We introduce a new method for testing straight path segments in configuration space, or collections of such segments, which is both reliable and efficient. This method locally adjusts the sampling resolution by comparing lower bounds on distances between objects in relative motion with higher bounds on lengths of curves traced by points of these moving objects. Several additional techniques and heuristics further improve the checker’s efficiency in scenarios with many moving objects (e.g., articulated arms and/or multiple robots) and high geometric complexity. Our new method is general, but particularly well suited for use in PRM planners. Extensive tests, in particular on randomly generated path segments and on multi-segment paths produced by PRM planners, show that the new method compares favorably with a fixed-resolution approach at “suitable” resolution, with the enormous advantage that it never fails to detect collision.
Figure 1
Video clip
(2.59MB)
Slides (ppt)
Publications:
-
F. Schwarzer, M. Saha, and J.C. Latombe. Exact
Collision Checking of Robot Paths. In Algorithmic Foundations of
Robotics V, J.D. Boissonnat, J. Burdick, K. Goldberg, and
- F. Schwarzer, M. Saha, and J.C. Latombe. Adaptive Dynamic Collision Checking for Single and Multiple Articulated Robots in Complex Environments. IEEE Tr. on Robotics, 21(3):338-353, June 2005.
Funding: General Motors, NSF ACI-02-5671.
Any opinions, findings, and conclusions or recommendations expressed in the above material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
Multi-goal motion planning
We consider a motion planning problem that occurs in tasks, such as spot welding, car painting, inspection, and measurement, where the end-effector of a robotic arm must reach successive goal placements given as inputs (Figure 1). The problem is to compute a near-optimal path of the arm so that the end-effector visits each goal once. It combines two notoriously hard sub-problems – the collision-free shortest path and the traveling-salesman problems. It is further complicated by the fact that each goal placement of the end-effector may be achieved by several configurations of the arm – typically, distinct solutions of the arm’s inverse kinematics (Figure 2). This leads us to construct a set of goal configurations of the robot that are partitioned into groups. The planner must compute a robot path that visits one configuration in each group and is near optimal over all configurations in every goal group and over all group orderings (Figure 3). Our algorithm operates under the assumption that the computational cost of finding a good path between two goal configuration dominates that of finding a good tour in a graph of with edges of given costs. So, our algorithm tries to minimize the number of times it computes a path between two goal configurations. Although it still computes a quadratic number of such paths in the worst-case, experimental results show that it is much faster in practice. Our algorithm makes use of a recent approximation algorithm for the group Steiner tree problem [C. Chekuri, G. Even, and G. Kortsarz. A Greedy Approximation for the Group Steiner Problem. To appear in Discrete Applied Mathematics].
Figure 1 Figure
2
Figure 3
Publications:
-
M.
Saha, G. Sánchez-Ante, and J.C. Latombe. Planning
Multi-Goal Tours for Robot Arms. IEEE Int. Conference on Robotics and
Automation,
- M. Saha, G. Sánchez-Ante, J.C. Latombe, and T. Roughgarden. Planning Multi-Goal Tours for Robot Arms. Int. J. Robotics Research, 25(3):207-223, March 2006.
Funding: General Motors, ABB, NSF ACI-02-5671.
Any opinions, findings, and conclusions or recommendations expressed in the above material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
Small-step retraction in PRM planning
PRM planners have been successfully used to plan complex robot motions in configuration spaces of various dimensionalities. But their efficiency decreases dramatically in spaces with narrow passages. Here, we investigate a new method – which we call small-step retraction – that helps PRM planners find paths through such passages. The method relies on the empirical observation that widening narrow passages by only a small amount greatly facilitates the task of sampling configurations into them. So, it consists of slightly “fattening” the robot’s free space, constructing a roadmap in the fattened free space, and finally repairing portions of this roadmap by retracting them out of collision into the actual free space. The fattened free space is not explicitly computed. Instead, the geometric models of the workspace objects (robot links and/or obstacles) are “thinned” around their medial axis. A robot configuration lies in fattened free space if the thinned objects do not collide at this configuration. Two repair strategies are proposed. The “optimist” strategy waits until a complete path has been found in fattened free space before repairing it. Instead, the “pessimist” strategy repairs the roadmap as it is being built. The former is usually very fast, but may fail in some pathological cases where the computed path crosses “false” passages. The latter is more reliable, but not as fast. A simple combination of the two strategies yields an integrated planner that is both fast and reliable. This planner was implemented as an extension of a pre-existing single-query PRM planner, SBL (see MPK toolkit). Comparative tests on various examples (Figure 1) show that it is significantly faster (sometimes by several orders of magnitude) than SBL.
Figure 1
Video
clip (3.66MB)
Slides (ppt)
Publications:
-
M. Saha and J.C. Latombe. Finding Narrow
Passages with Probabilistic Roadmaps: The Small Step Retraction Method. IEEE/RSJ
Int. Conf. on Intelligent Robots and Systems,
- M. Saha, J.C. Latombe, Y.-C. Chang, F. Prinz. Finding Narrow Passages with Probabilistic Roadmaps: The Small-Step Retraction Method. Autonomous Robots, 19(3):301-319, Dec. 2005.
-
H.L.
Chen, D. Hsu, J.C. Latombe, G. Sanchez. Multi-Level
Free-Space Dilation for Sampling Narrow Passages in PRM Planning. To appear
in Proc. IEEE Int. Conf. on Robotics and Automation (ICRA),
Funding: General Motors, ABB, NSF ACI-02-5671.
Rope manipulation planning
The goal is to design motion planning methods to manipulate a rope (linear deformable object) and to perform tasks such as tying self-knots and/or knots around other objects (Figure 1). One possible application is robotized suturing in medical surgery. The goal configuration of the rope is defined topologically (Figure 2) by the crossings of the rope with itself and with other objects (“crossing configuration”). Our planner operates in two stages. First, assuming one end of the rope is fixed, the planner computes a path of the other end to achieve the successive crossings (Figure 3). Next, a sequence of paths is computed using a PRM planner for two manipulator arms to move the rope (Figure 4). The planner assumes the existence of removable static sliding supports (which we call “tri-fingers”) to provide structural support and keep “loops” wide enough to enable further manipulation (Figure 5, video). The behavior of the rope is defined by a “rope simulator”. The planner is independent of this simulator.
Figure 1
Figure 2 Figure 3
Figure 4
Figure 5
Video clip
(7.20MB)
Slides (ppt)
Publications:
- J. Brown, J.C. Latombe, and K. Montgomery. Real-Time Knot Tying Simulation. The Visual Computer J., 20(2-3):165-179, May 2004.
-
M. Saha and P. Isto. Motion Planning
for Robotic Manipulation of Deformable Linear Objects. Proc. IEEE Int.
Conf. on Robotics and Automation (ICRA),
-
P. Isto and M. Saha. A Slicing
Connection Strategy for Constructing PRMs in High-Dimensional Cspaces. Proc.
IEEE Int. Conf. on Robotics and Automation (ICRA),
-
M.
Saha, P. Isto, and J.C. Latombe. Motion Planning for Robotic Manipulation of
Deformable Linear Objects. Int. Symp. On
Experimental Robotics (ISER),
Funding: General Motors, ABB, NSF ACI-02-5671.
3-D Sensing of deformable objects
In applications like motion capture, high-speed crash tests, and robotic manipulation of deformable objects, there is a critical need for capturing 3-D videos of fast moving and/or deforming objects. A 3-D video is a sequence of 3-D representations at high time and space resolution. Although many 3-D sensing techniques are available, most cannot deal with dynamic scenes (e.g., laser scanning). Others, like stereovision, require that object surfaces be appropriately textured. Few, if any, build high-resolution 3-D models of dynamic scenes. We develop a sensor capable of generating high-resolution range maps from single images of moving and deforming objects. The method is based on observing the deformation of a projected light pattern that combines a set of parallel colored stripes and a perpendicular set of sinusoidal intensity stripes (Figure 1). While the colored stripes allow the sensor to compute absolute depths at coarse resolution, the sinusoidal intensity stripes give dense relative depths (Figure 2). This twofold pattern makes it possible to extract a high-resolution range map from each image in a video sequence (Figure 3). This approach is based on sound mathematical principles, but its implementation requires giving great care to a number of low-level details. In particular, the sensor has been implemented using commercial off the shelf hardware, which distorts sensed and transmitted signals in many ways. A novel method was developed to characterize and compensate for distortions due to chromatic aberrations. The sensor has been implemented and tested on several deforming objects (videos). This work is done in collaboration with Prof. Ken Salisbury (surgical simulation).
Figure 1
Figure 2
Figure 3
Video (2.6 MB) showing a water balloon bouncing around. It was shot at 100 fps but plays back at 15 fps so you can see what's happening.
Video (1.8 MB) showing a person moving a popcorn tin around.
Video (2.0 MB) showing a flag being waved side to side.
Video (2.0MB) showing sand being pushed with a wood stick.
Slides (pdf)
Publications:
-
P. Fong and F. Buron. High-Resolution
Three-Dimensional Sensing of Fast Deforming Objects. IEEE/RSJ Int. Conf.
on Intelligent Robots and Systems (IROS), August 2005,
-
P. Fong and F. Buron. Sensing Moving
and Deforming Objects with Commercial Off the Shelf Hardware, IEEE Int.
Workshop on Projector-Camera Systems (PROCAMS), June 2005,
Funding: NIH grant R33LM07295 and NSF grant
ACI-02-5671.
Any opinions, findings, and conclusions or recommendations expressed in the above material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation and the National Institute of Health.
Climbing robots
The goal of this research is to enable a multi-limbed robot to climb vertical rock using techniques similar to those developed by human climbers (Figure 1). The robot consists of a small number of articulated limbs. Only the limb end-points can make contact with the environment—a vertical surface with small, arbitrarily distributed features called holds (Figure 2). A path through this environment is a sequence of one-step climbing moves in which the robot brings a limb end-point to a new hold. The robot maintains balance during each move by pushing and/or pulling at other holds, exploiting contact and friction at these holds while adjusting internal degrees of freedom to avoid sliding. The fixed set of robot-hold contacts during a one-step move is called a stance. Our planner combines a multi-step and a one-step planner. The multi-step planner searches a graph representing the adjacency relation between stances to compute a sequence of steps from the initial to the goal stance. The one-step planner (a PRM planner) searches the robot’s configuration space at a given stance for a feasible path between the previous and the next stance in the sequence computed by the multi-step planner. The one-step planner makes use of an efficient test efficient of the quasi-static equilibrium of thee robot. The multi-step planner makes use of lazy search techniques to speed up the exploration of the stance graph. It also makes use of a trained classifier to quickly recognize infeasible transitions between stances. The planner was tested in simulation and on a real four-limbed robot—LEMUR IIB—created by NASA/JPL (Figure 2). A new climbing robot with an increased number of degrees of freedom is currently being developed (Figure 3). In another develop, we adapt and extend the planner to the ATHLETE robot, a six-legged vehicle designed by NASA/JPL to climb steep, irregular, and possibly non-rigid lunar terrain (Figure 4). In such terrain ATHLETE’s wheels are frozen and are used as “feet”. This project is a joint effort with the group of Prof. Steve Rock in the Stanford Aerospace Robotics Lab.
Figure 1
Figure 2
Figure 3
Figure 4
video clip (6.27MB)
ATHLETE video clip (6.85MB)
Slides (ppt)
Publications:
-
T. Bretl, S.M. Rock, and J.C. Latombe. Motion
Planning for a Three-Limbed Climbing Robot in Vertical Natural Terrain. IEEE
Int. Conf. on Robotics and Automation,
-
T. Bretl, T. Miller, S.M. Rock, and J.C.
Latombe. Climbing
Robots in Natural Terrain. 7th Int. Symp. on Artificial Intelligence,
Robotics and Automation in Space,
-
T. Bretl, J.C. Latombe, and S. Rock. Toward
Autonomous Free-Climbing Robots. 11th
Int. Symp. on Robotics Research,
-
T. Bretl, S.M. Rock, J.C. Latombe, B. Kennedy,
and H. Aghazarian. Free-Climbing
with a Multi-Use Robot. 9th
Int. Symp. on Experimental
-
T. Bretl, S. Lall, J.C. Latombe, S.M. Rock. Multi-Step
Motion Planning for Free-Climbing Robots. 6th International Workshop on the Algorithmic
Foundations of Robotics (WAFR’04), Utrecht/Zeist, The
-
K.
Hauser, T. Bretl, J.C. Latombe. Learning-Assisted
Multi-Step Planning. IEEE Int. Conf. on Robotics and Automation,
-
T. Bretl and S. Lall. A Fast and Adaptive Test
of Static Equilibrium for Legged Robots. To appear in Proc. IEEE Int. Conf.
on Robotics and Automation (ICRA),
- T. Bretl. Motion Planning of Multi-Limbed Robots Subject to Equilibrium Constraints: The Free-Climbing Robot Problem. Int. J. of Robotics Research, 25(4):317-342, Apr 2006.
- K. Hauser, T. Bretl, J.C. Latombe, and B. Wilcox. Motion Planning for a Six-Legged Lunar Robot. Workshop on Algorithmic Foundations of Robotics (WAFR), New-York, NY, July 2006.
Funding: NSF grant IIS-0412884, NASA.
Any opinions, findings, and conclusions or recommendations expressed in the above material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation and NASA.
