Search-based Planning for Higher-dimensional Robotic Systems
Prof. Maxim Likhachev
Robotics Institute, Carnegie Mellon University
April. 28, 2023 (Friday), 12:00 – 1:00 pm
In-person: Room 220, Building C
Abstract: Search-based Planning refers to planning by constructing a graph from systematic discretization of the state- and action-space of a robot and then employing a heuristic search to find an optimal path from the start to the goal vertex in this graph. This paradigm works well for low-dimensional robotic systems such as mobile robots and provides rigorous guarantees on solution quality. However, when it comes to planning for higher-dimensional robotic systems such as mobile manipulators, humanoids and ground and aerial vehicles navigating at high-speed, Search-based Planning has been typically thought of as infeasible. In this talk, I will describe some of the research that my group has done into changing this thinking. In particular, I will focus on two different principles. First, constructing multiple lower-dimensional abstractions of robotic systems, solutions to which can effectively guide the overall planning process using Multi-Heuristic A*. Second, using offline preprocessing to provide online planning algorithms that provably guarantee to return solutions within a (small) constant time for repetitive planning tasks. I will present algorithmic frameworks that utilize these principles, describe their theoretical properties, and demonstrate their applications to a wide range of physical high-dimensional robotic systems.
Bio: Maxim Likhachev is an Associate Professor at Carnegie Mellon University, directing Search-based Planning Laboratory (SBPL), and a Senior Staff Software Engineer at Waymo. His group at CMU researches heuristic search, decision-making and planning algorithms, all with applications to the control of robotic systems including unmanned ground and aerial vehicles, mobile manipulation platforms, humanoids, and multi-robot systems. Maxim obtained his Ph.D. in Computer Science from Carnegie Mellon University with a thesis called “Search-based Planning for Large Dynamic Environments.” He has over 150 publications in top journals and conferences on AI and Robotics and numerous paper awards. His work on Anytime D* algorithm, an anytime planning algorithm for dynamic environments, has been awarded the title of Influential 10-year Paper at International Conference on Automated Planning and Scheduling (ICAPS) 2017, the top venue for research on planning and scheduling. Other awards include selection for 2010 DARPA Computer Science Study Panel that recognizes promising faculty in Computer Science and being on a team that won 2007 DARPA Urban Challenge and on a team that won the Gold Edison award in 2013. Maxim founded RobotWits, a company devoted to developing advanced planning and decision-making technologies for self-driving vehicles and recently acquired by Waymo, and co-founded TravelWits, an online travel tech company that brings AI to make travel logistics easier. Finally, Maxim is an executive co-producer of regional Emmy-nominated The Robot Doctor TV series aimed at showing the use of mathematics in Robotics and inspiring high-school students to pursue careers in science and technology.