Abstract
High-dimensional configuration space is usually searched using sampling-based motion planning methods. The well-known issue of sampling-based planners is the narrow passage problem caused by small regions of the configuration space that are difficult to cover by random samples. Practically, the presence of narrow passages decreases the probability of finding a solution, and to cope with it, the number of random samples has to be significantly increased, which also increases the planning time. By dilating the free space, e.g., by scaling-down or thinning the robot (or obstacles), narrow passages become wider, which allows us to compute an approximate solution. Then, the configuration space can be sampled densely around the approximate solution to find the solution of the original problem. However, this process may fail if the final solution is too far from the approximate one. In this paper, we propose a method to find multiple approximate solutions in the configuration space to increase the chance of finding the final solution. The approximate solutions are computed by repeated search of the configuration space while avoiding, if possible, the already discovered solutions. This enables us to search for distinct solutions leading through different parts of the configuration space. The number of approximate solutions is automatically determined based on their similarity. All approximate solutions are then used to guide the sampling of the configuration space. The performance of the proposed approach is verified in scenarios with multiple narrow passages and the benefits of the method are demonstrated by comparing the results with the state-of-the-art planners.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Al-Bluwi, I., Siméon, T., Cortés, J.: Motion planning algorithms for molecular simulations: a survey. Comput. Sci. Rev. 6(4), 125–143 (2012)
Amato, N.M., Dale, L.K., Bayazit, O.B., Jones, C.H., Vallejo, D. : OBPRM: an obstacle-based PRM for 3D workspaces. In: Workshop on the Algorithmic Foundations of Robotics (WAFR), pp 155–168. A. K. Peters, Ltd., Natick (1998)
Amato, N.M., Dill, K., Song, G.: Using motion planning to map protein folding landscapes and analyze folding kinetics of known native structures. J. Comput. Biol. 10(3-4), 239–255 (2003)
Bayazit, O.B., Xie, D., Amato, N.M.: Iterative relaxation of constraints: a framework for improving automated motion planning. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp 3433–3440 (2005)
Belter, D., Labecki, P., Skrzypczynski, P.: An exploration-based approach to terrain traversability assessment for a walking robot. In: IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR), pp 1–6 (2013)
Bhattacharya, S., Likhachev, M., Kumar, V.: Topological constraints in search-based robot path planning. Auton. Robot. 33(3), 273–290 (2012)
Brock, O., Kavraki, L.E.: Decomposition-based motion planning: a framework for real-time motion planning in high-dimensional configuration spaces. In: IEEE International Conference on Robotics and Automation (ICRA), vol. 2, pp 469–1474 (2001)
Demyen, D., Buro, M.: Efficient triangulation-based pathfinding. In: AAAI: Proceedings of the 21st National Conference on Artificial Intelligence (2006)
Denny, J., Sandström, R., Amato, N.M.: A general region-based framework for collaborative planning. In: Robotics Research, pp 563–579. Springer (2018)
Denny, J., Sandström, R., Bregger, A., Amato, N.M.: Dynamic region-biased rapidly-exploring random trees. In: Twelfth International Workshop on the Algorithmic Foundations of Robotics (WAFR) (2016)
Elbanhawi, M., Simic, M.: Sampling-based robot motion planning: a review. IEEE Access 2, 56–77 (2014)
Ghandi, S., Masehian, E.: Review and taxonomies of assembly and disassembly path planning problems and approaches. Comput. Aided Des. 67-68, 58–86 (2015)
Grigoriev, D., Slissenko, A.: Polytime algorithm for the shortest path in a homotopy class amidst semi-algebraic obstacles in the plane. In: ISSAC, vol. 98 (1998)
Hershberger, J., Snoeyink, J.: Computing minimum length paths of a given homotopy class. In: Workshop on Algorithms and Data Structures, pp 331–342. Springer (1991)
Hsu, D., Cheng, H., Latombe, J.-C.: Multi-level free-space dilation for sampling narrow passages in PRM planning. In: IEEE International Conference on Robotics and Automation (ICRA) (2006)
Hsu, D., Jiang, T., Reif, J., Sun, Z.: The bridge test for sampling narrow passages with probabilistic roadmap planners. In: IEEE International Conference on Robotics and Automation (ICRA), pp 4420–4426 (2003)
Hsu, D., Latombe, J.-C., Kurniawati, H.: On the probabilistic foundations of probabilistic roadmap planning. Int. J. Robot. Res. 25(7), 627–643 (2006)
Jaillet, L., Yershova, A., LaValle, S.M., Simeon, T.: Adaptive tuning of the sampling domain for dynamic-domain RRTs. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp 2851–2856 (2005)
Kavraki, L.E., Svestka, P., Latombe, J.-C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12, 566–580 (1996)
LaValle, S.M.: Rapidly-exploring random trees: a new tool for path planning. Technical report 98-11 (1998)
LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006)
Lindemann, S.R., LaValle, S.M.: Current issues in sampling-based motion planning. In: Robotics Research: The Eleventh International Symposium, pp 36–54 (2005)
Nguyen, M.K., Jaillet, L., Redon, S.: ART-RRT as-rigid-as-possible exploration of ligand unbinding pathways. Journal of Computational Chemistry 39(11), 665–678 (2018)
Overmars, M.H.: The gaussian sampling strategy for probabilistic roadmap planners. In: International Conference on Robotics and Automation (ICRA), pp 1018–1023 (1999)
Plaku, E., Kavraki, L.E., Vardi, M.Y.: Discrete search leading continuous exploration for kinodynamic motion planning. In: Robotics: Science and Systems, pp 326–333 (2007)
Rickert, M., Brock, O., Knoll, A.: Balancing exploration and exploitation in motion planning. In: IEEE International Conference on Robotics and Automation (ICRA), pp 2812–2817 (2008)
Schmitzberger, E., Bouchet, J.-L., Dufaut, M., Wolf, D., Husson, R.: Capture of homotopy classes with probabilistic road map. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (2002)
Szadeczky-Kardoss, E., Kiss, B.: Extension of the rapidly exploring random tree algorithm with key configurations for nonholonomic motion planning. In: IEEE International Conference on Mechatronics, pp 363–368 (2006)
Uwacu, D., Rex, R., Wang, B., Thomas, S.L., Amato, N.M.: Annotated-skeleton biased motion planning for faster relevant region discovery. arXiv:2003.02176 (2020)
Vonásek, V., Faigl, J., Krajník, T., Přeučil, L.: RRT-path — a guided rapidly exploring random tree. In: Robot Motion and Control (RoMoCo), pp 307–316. Springer (2009)
Vonásek, V., Pěnička, R.: Path planning of 3d solid objects using approximate solutions. In: 2019 24th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), pp 593–600 (2019)
Vonásek, V., Pěnička, R., Kozlíková, B.: Computing multiple guiding paths for sampling-based motion planning. In: 2019 19th International Conference on Advanced Robotics (ICAR), pp 374–381 (2019)
Wilmarth, S.A., Amato, N.M., P. F. Stiller: MAPRM: a probabilistic roadmap planner with sampling on the medial axis of the free space. In: IEEE International Conference on Robotics and Automation (ICRA), pp 1024–1031 (1999)
Yershova, A., Jaillet, L., Simeon, T., LaValle, S.M.: Dynamic-domain RRTs: efficient exploration by controlling the sampling domain. In: IEEE International Conference on Robotics and Automation (ICRA) (2005)
Zhang, L., Manocha, D.: An efficient retraction-based RRT planner. In: IEEE International Conference on Robotics and Automation (ICRA), pp 3743–3750 (2008)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The presented work has been supported by the Czech Science Foundation (GAČR) under research project No. 19-22555Y. Computational resources were supplied by the project “e-Infrastruktura CZ” (e-INFRA LM2018140) provided within the program Projects of Large Research, Development and Innovations Infrastructures.
Rights and permissions
About this article
Cite this article
Vonásek, V., Pěnička, R. & Kozlíková, B. Searching Multiple Approximate Solutions in Configuration Space to Guide Sampling-Based Motion Planning. J Intell Robot Syst 100, 1527–1543 (2020). https://doi.org/10.1007/s10846-020-01247-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-020-01247-4