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*, an algorithm recently developed by my group. Second, using offline pre-processing to provide a *provably* constant-time online planning 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.
Biography: Maxim Likhachev is an Associate Professor at Carnegie Mellon University, directing Search-based Planning Laboratory (SBPL). His group 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 120 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. Finally, Maxim founded RobotWits, a company that develops advanced planning and decision-making technologies for self-driving vehicles, and co-founded TravelWits, an online travel startup that brings AI to make travel logistics easier.