Our paper “The Provable Virtue of Laziness in Motion Planning” has been selected to receive the best paper award at the 28th International Conference on Automated Planning and Scheduling, out of 209 submissions. The paper is joint work with Nika Haghtalab (CMU), Simon Mackenzie (CMU), Oren Salzman (CMU), and Sidd Srinivasa (UW).

Abstract: The Lazy Shortest Path (LazySP) class consists of motion-planning algorithms that only evaluate edges along shortest paths between the source and target. These algorithms were designed to minimize the number of edge evaluations in settings where edge evaluation dominates the running time of the algorithm; but how close to optimal are LazySP algorithms in terms of this objective? Our main result is an analytical upper bound, in a probabilistic model, on the number of edge evaluations required by LazySP algorithms; a matching lower bound shows that these algorithms are asymptotically optimal in the worst case.


1 2 3 4
April 9th, 2019

Tom Yan wins an NSF Fellowship

Congratulations to Tom Yan for winning a 2019-2022 National Science Foundation Graduate Research Fellowship.

March 31st, 2019

EC-20 PC co-chair

Together with Michael Ostrovsky, I’m serving as co-chair of the program committee of the 21st ACM Conference on Economics and Computation […]

March 7th, 2019

Gerdus Benade to join Boston University

Congratulations to Gerdus Benade for accepting a faculty position at Boston University! He will join the Questrom School of Business at […]

January 7th, 2019

Bloomberg Opinion

My piece about the “tragedy of the commons” playing out in AI research appeared today in Bloomberg Opinion. The plan […]

October 31st, 2018

Nika Haghtalab wins the SCS Distinguished Dissertation Award

My former PhD student Nika Haghtalab (co-advised with Avrim Blum) won the SCS Distinguished Dissertation Award, given annually for the […]

August 27th, 2018

AAAI Council

I was elected to a 3-year term on the Executive Council of the Association for the Advancement of Artificial Intelligence […]

June 14th, 2018

Nika Haghtalab to join Cornell University

Congratulations to Nika Haghtalab for accepting a faculty position at Cornell University! She will join Cornell as Assistant Professor of […]

June 13th, 2018

ICAPS-18 best paper

Our paper “The Provable Virtue of Laziness in Motion Planning” has been selected to receive the best paper award at […]

April 5th, 2018

Guggenheim Fellowship

I am honored to have been named a Guggenheim fellow, together with 172 other scholars, artists, and scientists.

February 16th, 2018

Op-ed in the Washington Post

An op-ed that I wrote with Wes Pegden was published by the Washington Post. We discuss our cake-cutting-inspired redistricting protocol, […]