Velocity bounds for motion planning in the presence of moving planar obstacles

This paper is concerned with motion planning for a mobile robot operating in a planar environment with multiple arbitrarily moving obstacles. The robot and obstacles are rigid bodies of arbitrary shapes. All rigid motion-rotation and translation-is considered for the obstacles; the robot can move only by translation. The robot has no advance information about the obstacles´ shapes or motion, and obtains information about the surrounding environment from its sensors, in real time. Necessary and sufficient conditions are derived under which collision-free motion of the robot to its target position can be guaranteed. Namely, it is shown that if the maximum velocity of the robot is bounded below by a multiple of the maximum allowable velocity of the obstacles, then a provable motion planning algorithm can be devised. The constant multiple in this bound takes into account the nonconvexity of the obstacles and a bound on the (minimal) distance between any obstacle and the robot´s target position