Finding critical changes in dynamic configuration spaces

Given a motion planning problem in a dynamic but fully known environment, we propose the first roadmap-based method, called critical roadmap, that has the ability to identify and exploit the critical topological changes of the free configuration space. Comparing to the existing methods that either ignore temporal coherence or only repair their roadmaps at fixed times, our method provides not only a more complete representation of the free (configuration-time) space but also provides significant efficiency improvement. Our experimental results show that the critical roadmap method has a higher chance of finding solutions, and it is at least one order of magnitude faster than some well-known planners.