Lydia Kavraki

Digital Library

ACM AAAI Allen Newell Award

USA - 2019


For pioneering contributions to robotic motion planning and their applications in bioinformatics and biomedicine, including the invention of randomized motion planning algorithms and probabilistic roadmaps.

Lydia E. Kavraki is recognized for her foundational work on physical algorithms and their applications in robotics (motion planning, hybrid systems, formal methods in robotics, assembly planning, and micro- and flexible manipulation), as well as in computational structural biology, translational bioinformatics, and biomedical informatics. Kavraki has authored more than 240 peer-reviewed publications and is a co-author of the widely used robotics textbook Principles of Robot Motion. Her seminal paper "Probabilistic Roadmaps for Path Planning in High Dimensional Configuration Spaces" (with Svestka, Latombe, and Overmars), was the first to establish a probabilistic approach to developing roadmaps for high-dimensional spaces, which has become one of the key techniques for motion planning for complex physical systems. Kavraki's contributions go beyond robotics to problems underlying the functional annotation of proteins, the understanding of metabolic networks, and the investigation of molecular conformations and protein flexibility. She has contributed to problems that involve reasoning about the three-dimensional structure of biomolecules, their flexibility, and their ability to interact with other biomolecules primarily for drug design.

Press Release

ACM Athena Lecturer Award

USA - 2017


For the invention of randomized motion planning algorithms in robotics and the development of robotics-inspired methods for bioinformatics and biomedicine.

Press Release

ACM Fellows

Greece - 2010


For contributions to robotic motion planning and its application to computational biology.

ACM Grace Murray Hopper Award

Greece - 2000


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.