Generalized Lazy Search for Efficient Robot Motion Planning

Aditya Mandalika, University of Washington


Location: Zoom

Time: 2:40p.m.

Abstract: Robotics has become a part of the solution in various applications today: autonomous vehicles navigating busy streets, articulated robots tirelessly sorting packages in warehouses, feeding people in care homes and mobile robots assisting in rescue operations. Central to any robot that needs to navigate its environment for its application, is Motion Planning: the task of computing a collision-free motion for a (robotic) system between given start and goal states in an environment cluttered with obstacles. As tasks become more complex, there is a need to develop more sophisticated motion planning algorithms that can compute high quality solutions for the robot quickly.

In this talk, we will specifically investigate the computational bottlenecks in search for the shortest path on a graph: search effort and collision evaluations. Lazy search algorithms can efficiently solve shortest path problems where evaluating edges for collision is expensive, as is the case in robotics. We show that the existing algorithms can provably minimize the number of collision evaluations, but at the cost of increased graph operations. This can be prohibitively expensive in cluttered environments that necessitate large graphs. In this talk, we discuss a framework of lazy search algorithms that seamlessly interleave lazy search with edge evaluations to prevent wasted computational effort and to minimize the total planning time. I will close the talk with a brief discussion on the efficacy of the framework, the potential extensions and (exciting) future work.