Reproduce “ST-RRT*: Asymptotically-Optimal Bidirectional Motion Planning through Space-Time” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Francesco Grothe, Valentin N. Hartmann, Andreas Orthey, Marc Toussaint
ST-RRT* (Space-Time Rapidly-exploring Random Tree Star) plans robot motions in dynamic environments with moving obstacles and time-dependent goals without requiring prior knowledge of arrival time. The algorithm achieves probabilistic completeness and asymptotic optimality, demonstrating superior performance in solution time, success rate, and solution quality compared to baseline methods in various high-dimensional scenarios.
Key insights
- Progressive Goal Region Expansion: The algorithm gradually increases the sampled time range with a weighted sampling strategy, allowing efficient exploration of the unbounded time dimension while maintaining a uniform distribution.
- Conditional Sampling: Search is focused on reachable regions by sampling only within the intersection of start and goal velocity cones, which significantly improves sampling efficiency by avoiding unreachable states.
- Simplified Rewiring: Asymptotic optimality is achieved by only rewiring the goal trees, which reduces computational overhead compared to standard RRT* while still optimizing the arrival time.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.