Avoidance of Obstacles With Unknown Trajectories: Locally Optimal Paths and Periodic Sensor Readings

We consider the problem of moving a mobile robot through a two-dimensional workspace containing obstacles moving on unknown trajectories. The workspace and obstacles are convex polygons, and the robot is a point. We propose to use sensor information to predict the trajectories of the obstacles and in terleave path planning and execution. Sensors are read only at equally spaced intervals of time. We discuss how small this in terval must be to guarantee that the robot will be able to avoid collisions. We also define a locally minimum velocity path as an optimal robot trajectory, given only local information about obstacle trajectories. We prove that our algorithm can ap proximate the locally minimum velocity path to any required accuracy.