Lydia Kavraki is the Noah Harding Professor of Computer Science at Rice University. She is also professor of Bioengineering, professor of Electrical and Computer Engineering, and professor of Mechanical Engineering at Rice. She is the current Director of the Ken Kennedy Institute at Rice.

Today we congratulate her on being elected to the American Academy of Arts and Sciences (AAAS).

Kavraki has multiple other affiliations listed on her home page, including her own laboratory on computational robotics and biomedicine. Now with AAAS, she acquires one more. It is enough to make us wonder whether her growth-of-affiliations function per year is additive or multiplicative.

If the latter, then it would call to mind the story of rice grains on a chessboard. The emperor thinks it would be trivial to grant a reward of one grain of rice on the first square, two on the second square, four on the third square, eight on the fourth, and so on. It does not take many doublings for the number of grains to grow far in excess of this picture:

Brief Roadmap to Her Work

Suppose a chess queen has outstretched arms that made it difficult to move her on a board without knocking over other pieces. We will require her to make a legal move in chess, but not necessarily take the direct route to her destination square. If a roundabout route through a less-crowded area of the board can get her safely to her goal, we will allow our player to move her that way. Naturally, the player could be a robot arm that can picture the whole board but may only slide the queen, not hoist her vertically to hop her to a square.

What’s the best way in practice to find a route, if one exists? We could try all possible paths, but here is where the grains-of-rice factor comes in. This is not because there are many squares, but because the queen’s arms may leave her little wiggle room on a square. She may have to shimmy to get by the nose of an enemy knight, but then find herself unable to twist around a chain of pawns. To avoid such backtracks, we’d need to make a roadmap of the entire board not in the space of squares, but in the possible configuration space of the queen, given the positioning of other pieces as obstacles. That space can be too large to map exhaustively.

In work with her PhD adviser Jean-Clause Latombe and others, Kavraki was the guiding force in discovering that random sampling of the configuration space almost always efficiently finds a route when one exists. The sampling grows progressively longer transitions between configurations that the queen is able to make, and proclaims success when the goal configuration is connected to the origin. Then a deterministic shortest-path algorithm can be run on the resulting graph—a manageable subset of the whole configuration space—to find an optimal route through that graph. By the nature of physical space, this is usually optimum overall.

Kavraki’s probabilistic roadmap paradigm extends to many other settings besides moving robots. In biomedicine it applies to how a drug molecule can be designed to maximize its expectation of finding configurations that will combat a pathogen. Her 2017 ACM Athena Lecturer Award citation notes how her work has found paths into “an impressively wide range of areas.”

Ken Kennedy’s Institute

Rice University is one of the top university especially when we look at its computer science program. This historically was thanks to Ken Kennedy who sadly died years ago on 2007 February 7th. Ken was one of the world’s foremost experts on high-performance computing. He attended Rice University, receiving a B.A. in mathematics (summa cum laude) in 1967. He pursued graduate studies at New York University, where he earned a M.S. in mathematics in 1969 and a Ph.D. in computer science in 1971. Then he returned to Rice.

Rice president David Leebron said:

“In Ken Kennedy, Rice has lost one of its great intellectual leaders and a great human being. [He] early on realized the power of computers to address real problems that confront people and the Earth. Ken leaves a great legacy for Rice and for mankind. He will be missed.”

Previous Leader

A previous leader of the Kennedy Institute is Moshe Vardi, an old friend whose work we first covered here and whom we’ve mentioned numerous times since, including about teaching during the pandemic.

He also has a bunch of titles, including Professor of Computer Science, University Professor, the Karen Ostrum George Professor in Computational Engineering, and Distinguished Service Professor—but more notable is that he has even more honorary doctorates than affiliations:

He holds honorary doctorates from the University of Saarland, Germany, the University of Orleans in France, UFRGS in Brazil, the University of Liege in Belgium, the Technical University of Vienna, Austria, the University of Edinburgh in Scotland, the University of Grenoble-Alpes, and Gothenburg University in Sweden.

David Oxtoby is the current President of the American Academy of Arts and Sciences. In his annoucement of the new class he says:

The very first class of members elected to the Academy in 1781 included Benjamin Franklin and George Washington, and today I’m pleased to announce the new members elected to the American Academy of Arts and Sciences this year.

The new computer science electees are listed here and include several others we know well and whose work we have covered. We list Kavraki again in case this list is taken as “the” list.

• Michael Franklin MF, University of Chicago
• Xuedong Huang XH, Microsoft Corporation
• Piotr Indyk PI, Massachusetts Institute of Technology
• Lydia Kavraki LK, Rice University
• Marta Kwiatkowska MK, University of Oxford (international honorary member)
• Maja Mataric MM, University of Southern California Viterbi School of Engineering
• Kathryn McKinley KM, Google LLC
• Gordon Plotkin (IHM) GP, University of Edinburgh
• Moti Yung MY, Google LLC

Open Problems

Our congratulations again to all those just elected.

[Words “for Information Technology” from previous name of the Ken Kennedy Institute deleted from intro]