Motion planning in a dynamic domain

Abstract

Motion planning is studied in a time-varying environment. Each obstacle is a convex polygon that moves in a fixed direction at a constant speed. The robot is a convex polygon that is subject to a speed bound. A method of determining whether or not there is a translational collision-free motion for a polygonal robot from an initial position to a final position and of planning such a motion, if it exists, is presented. The method makes use of the concept of configuration spaces and accessibility. An algorithm is given for motion planning in such an environment, and its time complexity is analyzed.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>