Abstract
Current state-of-the-art motion planners rely on samplingbased planning to explore the problem space for a solution. However, sampling valid configurations in narrow or cluttered workspaces remains a challenge. If a valid path for the robot correlates to a path in the workspace, then the planning process can employ a representation of the workspace that captures its salient topological features. Prior approaches have investigated exploiting geometric decompositions of the workspace to bias sampling; while beneficial in some environments, complex narrow passages remain challenging to navigate.
In this work, we present Dynamic Region-biased RRT, a novel samplingbased planner that guides the exploration of a Rapidly-exploring Random Tree (RRT) by moving sampling regions along an embedded graph that captures the workspace topology. These sampling regions are dynamically created, manipulated, and destroyed to greedily bias sampling through unexplored passages that lead to the goal. We show that our approach reduces online planning time compared with related methods on a set of maze-like problems.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Amato, N.M., Bayazit, O.B., Dale, L.K., Jones, C., Vallejo, D.: OBPRM: an obstacle-based PRM for 3d workspaces. In: Proceedings of the thirdWorkshop on the Algorithmic Foundations of Robotics. pp. 155–168. A. K. Peters, Ltd., Natick, MA, USA (1998), (WAFR ‘98)
van den Berg, J.P., Overmars, M.H.: Using workspace information as a guide to non-uniform sampling in probabilistic roadmap planners. Int. J. Robot. Res. 24(12), 1055–1071 (2005)
Buss, A.A., Harshvardhan, Papadopoulos, I., Pearce, O., Smith, T.G., Tanase, G., Thomas, N., Xu, X., Bianco, M., Amato, N.M., Rauchwerger, L.: STAPL: standard template adaptive parallel library. In: Proceedings of of SYSTOR 2010: The 3rd Annual Haifa Experimental Systems Conference, Haifa, Israel, May 24-26, 2010. pp. 1–10. ACM, New York, NY, USA (2010), http://doi.acm.org/10.1145/1815695.1815713
Canutescu, A.A., Dunbrack, Jr., R.L.: Cyclic coordinate descent: A robotics algorithm for protein loop closure. Protein Sci. 12(5), 963–972 (2003)
Cheng, P., LaValle, S.: Reducing metric sensitivity in randomized trajectory design. In: Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS). vol. 1, pp. 43–48 vol.1 (2001)
Choset, H., Burdick, J.: Sensor-based exploration: The hierarchial generalized voronoi graph. Int. J. Robot. Res. 19(2), 96–125 (2000)
Denny, J., Sandstrom, R., Julian, N., Amato, N.M.: A region-based strategy for collaborative roadmap construction. In: Proc. Int. Workshop on Algorithmic Foundations of Robotics (WAFR). Istanbul, Turkey (August 2014)
Doraiswamy, H., Natarajan, V.: Efficient algorithms for computing reeb graphs. Comput. Geom. Theory Appl. 42(6-7), 606–616 (Aug 2009), http://dx.doi.org/0.1016/j.comgeo.2008.12.003
Foskey, M., Garber, M., Lin, M.C., Manocha, D.: A voronoi-based hybrid motion planner for rigid bodies. In: Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS). pp. 55–60 (2001)
Gayle, R., Sud, A., Lin, M.C., Manocha, D.: Reactive deformation roadmaps: Motion planning of multiple robots in dynamic environments. In: Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS) (2007)
Hatcher, A.: Algebraic Topology. Cambridge University Press (2001), http://www.math.cornell.edu/~hatcher/
Hilaga, M., Shinagawa, Y., Kohmura, T., Kunii, T.L.: Topology matching for fully automatic similarity estimation of 3d shapes. In: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. pp. 203–212. SIGGRAPH ’01, ACM, New York, NY, USA (2001), http://doi.acm.org/10.1145/383259.383282
Hsu, D., Latombe, J.C., Kurniawati, H.: On the probabilistic foundations of probabilistic roadmap planning. Int. J. Robot. Res. 25, 627–643 (July 2006)
Kalisiak, M., van de Panne, M.: Rrt-blossom: Rrt with a local flood-fill behavior. In: Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006. pp. 1237–1242 (May 2006)
Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. International Journal of Robotics Research (IJRR) 30, 846–894 (2011)
Kuffner, J.J., LaValle, S.M.: RRT-connect: An efficient approach to single-query path planning. In: Proc. IEEE Int. Conf. Robot. Autom. (ICRA). pp. 995–1001 (2000)
Kurniawati, H., Hsu, D.: Workspace importance sampling for probabilistic roadmap planning. In: Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS). vol. 2, pp. 1618–1623 (sept-2 oct 2004)
Kurniawati, H., Hsu, D.: Workspace-based connectivity oracle - an adaptive sampling strategy for prm planning. In: Algorithmic Foundation of Robotics VII, pp. 35–51. Springer, Berlin/Heidelberg (2008), book contains the proceedings of the International Workshop on the Algorithmic Foundations of Robotics (WAFR), New York City, 2006
LaValle, S.M., Kuffner, J.J.: Randomized kinodynamic planning. Int. J. Robot. Res. 20(5), 378–400 (May 2001)
Li, Y., Littlefield, Z., Bekris, K.E.: Sparse Methods for Efficient Asymptotically Optimal Kinodynamic Planning, pp. 263–282. Springer International Publishing, Cham (2015), http://dx.doi.org/10.1007/978-3-319-16595-0_16
Lien, J.M., Pratt, E.: Interactive planning for shepherd motion (March 2009), the AAAI Spring Symposium
Lozano-Pérez, T., Wesley, M.A.: An algorithm for planning collision-free paths among polyhedral obstacles. Communications of the ACM 22(10), 560–570 (October 1979)
McMahon, T., Thomas, S.L., Amato, N.M.: Reachable volume RRT. In: Proc. IEEE Int. Conf. Robot. Autom. (ICRA). pp. 2977–2984. Seattle, Wa. (May 2015)
Morales, M., Tapia, L., Pearce, R., Rodriguez, S., Amato, N.M.: A machine learning approach for feature-sensitive motion planning. In: Algorithmic Foundations of Robotics VI, pp. 361–376. Springer Tracts in Advanced Robotics, Springer, Berlin/Heidelberg (2005), (WAFR ‘04)
Pascucci, V., Scorzelli, G., Bremer, P.T., Mascarenhas, A.: Robust on-line computation of reeb graphs: Simplicity and speed. ACM Trans. Graph. 26(3) (Jul 2007), http://doi.acm.org/10.1145/1276377.1276449
Plaku, E., Kavraki, L., Vardi, M.: Motion planning with dynamics by a synergistic combination of layers of planning 26(3), 469–482 (June 2010)
Reeb, G.: Sur les points singuliers d’une forme de pfaff complement integrable ou d’une fonction numerique. Comptes Rendus Acad. Sciences Paris 222, 847–849 (1946)
Reif, J.H.: Complexity of the mover’s problem and generalizations. In: Proc. IEEE Symp. Foundations of Computer Science (FOCS). pp. 421–427. San Juan, Puerto Rico (October 1979)
Rodriguez, S., Tang, X., Lien, J.M., Amato, N.M.: An obstacle-based rapidlyexploring random tree. In: Proc. IEEE Int. Conf. Robot. Autom. (ICRA) (2006)
Si, H.: Tetgen, a delaunay-based quality tetrahedral mesh generator. ACM Trans. Math. Softw. 41(2), 11:1–11:36 (Feb 2015), http://doi.acm.org/10.1145/2629697
Suh, C., Kim, B., Park, F.C.: The tangent bundle RRT algorithms for constrained motion planning. In: 13th World Congress in Mechanism and Machine Science (2011)
Wood, Z., Hoppe, H., Desbrun, M., Schröder, P.: Removing excess topology from isosurfaces. ACM Trans. Graph. 23(2), 190–208 (Apr 2004), http://doi.acm.org/10.1145/990002.990007
Wood, Z.J., Schröder, P., Breen, D., Desbrun, M.: Semi-regular mesh extraction from volumes. In: Proceedings of the Conference on Visualization ’00. pp. 275–282. VIS ’00, IEEE Computer Society Press, Los Alamitos, CA, USA (2000), http://dl.acm.org/citation.cfm?id=375213.375254
Yan, Y., Poirson, E., Bennis, F.: Integrating user to minimize assembly path planning time in PLM. In: Product Lifecycle Management for Society, IFIP Advances in Information and Communication Technology, vol. 409, pp. 471–480. Springer Berlin Heidelberg (2013)
Yershova, A., Jaillet, L., Simeon, T., Lavalle, S.M.: Dynamic-domain RRTs: Efficient exploration by controlling the sampling domain. In: Proc. IEEE Int. Conf. Robot. Autom. (ICRA). pp. 3856–3861 (April 2005)
Zhang, L., Manocha, D.: An efficient retraction-based RRT planner. In: Proc. IEEE Int. Conf. Robot. Autom. (ICRA) (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Denny, J., Sandström, R., Bregger, A., Amato, N.M. (2020). Dynamic Region-biased Rapidly-exploring Random Trees. In: Goldberg, K., Abbeel, P., Bekris, K., Miller, L. (eds) Algorithmic Foundations of Robotics XII. Springer Proceedings in Advanced Robotics, vol 13. Springer, Cham. https://doi.org/10.1007/978-3-030-43089-4_41
Download citation
DOI: https://doi.org/10.1007/978-3-030-43089-4_41
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-43088-7
Online ISBN: 978-3-030-43089-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)