A study of the obstacle avoidance problem based on the deformation retract technique

A point automaton operating in three-dimensional (3D) Cartesian space R³ has an infinite number of possible directions to pass around a 3D body. By making use of the natural constraints imposed by the manipulator arm kinematics, it is show that a two-dimensional (2D) approach can be applied, with proper modifications, to a three-link 3D arm manipulator with sliding joints (a Cartesian arm) operating among unknown obstacles of arbitrary shape. The configuration space (C-space) of the arm manipulator exhibits a certain monotonicity property, which makes the free C-space consist of a finite number of components, each homeomorphic to a cube with a finite number of vertical cylindrical holes removed. It is shown that if there exists a path in the free C-space, then there must be a path in the 2D surface that presents C-space deformation retract containing the start and target positions. The existence of a path between the given start and target positions can be determined via online exploration of the underlying connectivity graph. Also, a motion planning algorithm is outlined in terms of searching the same graph