DIMACS Theoretical Computer Science Seminar

Title: Algorithmic Challenges in Robot Motion Planning

Speaker: Kostas Bekris, Rutgers University

Date: Wednesday, December 4, 2014 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


Motion planning is a prototypical computationally hard problem, which requires the computation of collision-free, feasible paths for moving bodies in continuous spaces. Due to its importance in many applications, such as robotics and computer simulations, a variety of practical approaches have been developed for solving effectively many planning instances. A popular methodology samples valid configurations of a moving body to incrementally construct and connect the nodes of a graph on which path planning problems are then solved. These methods provide probabilistic instead of deterministic completeness. A recent development has been the identification of the conditions under which these methods also converge asymptotically to optimal paths in continuous configuration spaces.

This talk will review the state-of-the-art in algorithmic motion planning and recent contributions of our research group in balancing performance guarantees, such as completeness and path quality, and computational requirements, such as time and memory requirements. Furthermore, open problems will be identified that motivate further research in this area.

See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F13/