Finding Critical Changes in Dynamic Configuration Spaces
Yanyan Lu and Jyh-Ming Lien
Overview
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.
Publications
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
Paper(pdf) / Talk(ppt) / BibTeX
Benefits
- it reuses local roadmaps
- it avoids updating the global roadmap at unnecessary times
- it provides better completeness
- it can handle problems with high dimensional configuration space
A Simple Example
Details
- A Critical Time
 
|  
|   |
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 . In this case, free configuration space changes so the global roadmap has to be updated to inflect such topological changes. is not a critial time, therefore we do not need to update the global roadmap at .
- Time of Contact
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.
- Time Of Separation
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
- Computation Reuse
- Speedy Walking via Improved Feature Testing for Non-Convex Objects (SWIFT++)
- Dual-Space Expansion for Estimating Penetration Depth (DEEP)
- Interactive Continuous Collision Detection
List of MASC Research Pages