Finding Critical Changes in Dynamic Configuration Spaces

Yanyan Lu and Jyh-Ming Lien


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.

Finding Critical Changes in Dynamic Configuration Spaces, Yanyan Lu and Jyh-Ming Lien, Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), September 2011
Paper(pdf) / Talk(ppt) / BibTeX


A Simple Example

$t_2$ is a critical time because A's local roadmap becomes collision with B's local roadmap. Little c from A's local roadmap and B are penetrating at $t_2$. In this case, free configuration space changes so the global roadmap has to be updated to inflect such topological changes. $t_1$ is not a critial time, therefore we do not need to update the global roadmap at $t_1$.

We estimate the time of contact for any two objects by generalizing the idea of conservative advancement. In each iteration, we estimate the advancing time during which A can be safely moved toward B without causing any collision. The estimated advancing time is calculated based on a tight lower bound of the closest distance between A and B and an upper bound of the motions of A and B. The process repeats until the distance between A and B is under some user-defined threshold.

When two objects are intersecting, we apply the similar idea to estimate their time of separation. The difference is that instead of finding a tigher lower bound of the closest distance in each iteration, penetration depth is computed. The process continues until penetration depth is under some predefined threshold.

Related Work

List of MASC Research Pages
Computer Science @ George Mason University