Subir Ghosh (TIFR Mumbai)

In this lecture we first discuss how to reduce the problems of robot motion planning to the problems of computing paths inside polygons with or without holes. Then we discuss how to compute the geometric shortest path and the minimum link path inside a polygon using visibility structure of the polygon. In this context, we also discuss curvature-constrained shortest path problem. Finally, we discuss the problems of exploring an unknown polygon using both continous and discreet visibility, and present a few approximation on line algorithms. We summarize the discussion by suggesting a few open problems.