Planning collision-free paths for kinematically redundant robots by selectively mapping configuration space

摘要

Two path planning algorithms have been developed for kinematically redundant robots which are also applicable to nonredundant robots. They are the first configuration space algorithms which allow full use of the redundant joints along the entire path. A novel approach of selectively mapping configuration space is used instead of the typical approach of completely mapping a reduced dimension subset of configuration space. The algorithms search for good, but not necessarily optimal, collision-free paths while attempting to map a minimal amount of the space. Example paths for seven degree of freedom robots with three sizeable moving links and revolute joints are included for both algorithms. The first algorithm operates using only local world information to build a partial configuration space map leading from the starting configuration to a goal configuration. This partial map gives the planner a memory of safe and unsafe robot configurations. The algorithm was found to be inadequate in environments of moderate complexity due to the local conflict between moving towards the goal and avoiding obstacles. The second algorithm avoids this conflict by using a new technique to separate planning into two phases. The first phase forms a path connecting the starting configuration with a goal. The second phase modifies this path in a systematic fashion until it is collision-free or it is determined that no solution exists. This phase incorporates the new concept of using global information from the world model to develop collision avoidance strategies for each obstacle encountered in configuration space. Since the strategies are selected using global information, the located path belongs to a class of efficient paths. The optimal path within this class can be found. In the worst case, the algorithm maps in configuration space a straight line path from the start to the goal and the surfaces of the interfering obstacles. The included examples show that it can locate efficient paths while mapping a small amount of configuration space. The drawbacks of local methods are also avoided.