Development of a configuration space motion planner for robot in dynamic environment

In this paper, the on-line motion planning of articulated robots in dynamic environment is investigated. We propose a practical on-line robot motion planning approach that is based upon pre-computing the global configuration space (C-space) connectivity with respect to all possible obstacle positions. The proposed motion planner consists of an off-line stage and an on-line stage. In the off-line stage, the obstacles in the C-space (C-obstacle) with respect to the obstacle positions in the workspace are computed, which are then stored using a hierarchical data structure with non-uniform 2^m trees. In the on-line stage, the real obstacle cells in the workspace are identified and the corresponding 2^m trees from the pre-computed database are superposed to construct the real-time C-space. The collision-free path is then searched in this C-space by using the A* algorithm under a multi-resolution strategy which has excellent computational efficiency. In this approach, the most time-consuming operation is performed in the off-line stage, while the on-line computing only need to deal with the real-time obstacles occurring in the dynamic environment. The minimized on-line computational cost makes it feasible for real-time on-line motion planning. The validity and efficiency of this approach is demonstrated using manipulator prototypes with 5 and 7 degree-of-freedom.