Citation
For her seminal work on the probabilistic roadmap approach which has caused a paradigm shift in the area of path planning, and has many applications in robotics, manufacturing, nanotechnology and computational biology.

In her doctoral dissertation, Lydia Kavraki developed randomized path-planning algorithms for robots with many degrees of freedom. Traditional algorithms for such problems usually depend exponentially on the dimensionality of the problem and are thus impractical for problems with more than five degrees of freedom. Dr. Kavraki established the effectiveness of methods that combine randomization with local, problem-specific techniques for problems that simply could not be handled any other way. Establishing the effectiveness of the approach required both sophisticated and novel mathematical techniques as well as cutting-edge experimental work. This approach, now considered the method of choice and called the probabilistic roadmap approach, has since generated tremendous interest in many research centers around the world, and Dr. Kavraki's experimental results have been replicated by many other researchers.

Recently, Dr. Kavraki has extended her work in several directions. The first extension is the application of randomized path planning to model molecular docking in rational drug design. There are nice parallels between path planning in robotics and in drug design, but there are also significant differences. Her second extension is the treatment of flexible objects. Although this problem has been recognized for over a decade, Dr. Kavraki was the first to develop a rigorous planning model for flexible objects.

Dr. Kavraki's contributions have had a profound influence on the development of path planning techniques and are recognized for both their depth and breadth. Her work reflects a level of originality, rigor, and elegance that stands out in the research community.