A multiresolution work space, multiresolution configuration space approach to solve the path planning problem

The algorithm SCOUT is proposed to solve the path-planning problem for robots moving between stationary obstacles. The configuration space of a robot is represented as a binary tree of blocks, each of which can be efficiently tested for collisions using a hierarchy of bubbles in work space. The configuration space is explored independently from start and goal until a contiguous path of free blocks connecting the two is found. The algorithm finds a first path quickly, then improves on the length of the path by testing more parts of the configuration space, and finally converges to the optimal path for any imposed metric. The tradeoff between the length of the path and time/memory usage is explicit and can be used to the advantage of integrated systems. The method is applicable to mobile robots as well as to manipulators. Results are shown for a 2 d.o.f. planar arm and a 5 d.o.f industrial manipulator