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
July 30th, 2019

New position at Harvard

I’m excited to announce that I’ll join Harvard University as Gordon McKay Professor of Computer Science on January 1, 2020. […]

July 25th, 2019

Social Choice and Welfare Prize

I was selected to receive the 2020 Social Choice and Welfare Prize, together with Pietro Ortoleva of Princeton University. The […]

May 24th, 2019

Alex Psomas to join Purdue University

Congratulations to Alex Psomas for accepting a faculty position at Purdue University! He will join the Department of Computer Science […]

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 […]