Optimistic Motion Planning Using Recursive Sub- Sampling: A New Approach to Sampling-Based Motion Planning.

Lhilo Kenye; Rahul Kala

doi:10.9781/ijimai.2022.04.001

Authors

Lhilo Kenye Indian Institute of Information Technology Allahabad
Rahul Kala Indian Institute of Information Technology Allahabad

DOI:

https://doi.org/10.9781/ijimai.2022.04.001

Keywords:

Probabilistic Roadmap, Sampling, Planning, Robotics

Supporting Agencies

This work is funded by the Indian Institute of Information Technology, Allahabad.

Abstract

Sampling-based motion planning in the field of robot motion planning has provided an effective approach to finding path for even high dimensional configuration space and with the motivation from the concepts of sampling based-motion planners, this paper presents a new sampling-based planning strategy called Optimistic Motion Planning using Recursive Sub-Sampling (OMPRSS), for finding a path from a source to a destination sanguinely without having to construct a roadmap or a tree. The random sample points are generated recursively and connected by straight lines. Generating sample points is limited to a range and edge connectivity is prioritized based on their distances from the line connecting through the parent samples with the intention to shorten the path. The planner is analysed and compared with some sampling strategies of probabilistic roadmap method (PRM) and the experimental results show agile planning with early convergence.

Downloads

Download data is not yet available.

References

Latombe, J.-C., “Motion Planning: A Journey of Robots, Molecules, Digital Actors, and Other Artifacts,” The International Journal of Robotics Research, 1999, 18, (11), pp. 1119-1128. doi: 10.1177/02783649922067753.

Kavraki, L. and Latombe, J., “Randomized Preprocessing of Configuration for Fast Path Planning,” in, Proceedings of the 1994 IEEE International Conference on Robotics and Automation, (1994)), pp. 2138-2145 vol. 2133. doi: 10.1109/ROBOT.1994.350966.

Elbanhawi, M. and Simic, M., “Sampling-Based Robot Motion Planning: A Review,” IEEE Access, 2014, 2, pp. 56-77. doi:10.1109/ACCESS.2014.2302442.

Lavalle, S.M., “Rapidly-Exploring Random Trees: A New Tool for Path Planning,” October 1998, Technical Report, Computer Science Dept., I.S.U. (TR 98–11). doi: 10.1.1.35.1853.

Tsianos, K.I., Sucan, I.A., and Kavraki, L.E., “Sampling-Based Robot Motion Planning: Towards Realistic Applications,” Computer Science Review, 2007, 1, (1), pp. 2-11. doi: 10.1016/j.cosrev.2007.08.002.

Kumar, A. and Kala, R., “Linear Temporal Logic-Based Mission Planning,” International Journal of Interactive Multimedia and Artificial Intelligence, 2016, 3. doi: 10.9781/ijimai.2016.375.

Montana, F.J., Liu, J., and Dodd, T.J., “Sampling-Based Reactive Motion Planning with Temporal Logic Constraints and Imperfect State Information,” in Petrucci, L., Seceleanu, C., and Cavalcanti, A. (eds.), Critical Systems: Formal Methods and Automated Verification, (Springer International Publishing, 2017)), pp. 134-149. doi: 10.1007/978-3-319-67113-0_9.

Kavraki, L.E., Svestka, P., Latombe, J., and Overmars, M.H., “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces,” IEEE Transactions on Robotics and Automation, 1996, 12, (4), pp. 566-580. doi: 10.1109/70.508439.

Amato, N.M. and Wu, Y., “A Randomized Roadmap Method for Path and Manipulation Planning,” in, Proceedings of IEEE International Conference on Robotics and Automation, (1996)), 1, pp. 113-120, vol. 111. doi: 10.1109/ROBOT.1996.503582.

Persson, S.M. and Sharf, I., “Sampling-Based a* Algorithm for Robot Path-Planning,” The International Journal of Robotics Research, 2014, 33, (13), pp. 1683-1708. doi: 10.1177/0278364914547786.

Sucan, I.A., Moll, M., and Kavraki, L.E., “The Open Motion Planning Library,” IEEE Robotics & Automation Magazine, 2012, 19, (4), pp. 72-82. doi: 10.1109/MRA.2012.2205651.

Bohlin, R. and Kavraki, L.E., “Path Planning Using Lazy Prm,” in, Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), (2000)), 1, pp. 521-528, vol. 521. doi: 10.1109/ROBOT.2000.844107.

Karaman, S. and Frazzoli, E., “Sampling-Based Algorithms for Optimal Motion Planning,” The International Journal of Robotics Research, 2011, 30, (7), pp. 846-894. doi: 10.1177/0278364911406761.

Dobson, A. and Bekris, K.E., “Sparse Roadmap Spanners for Asymptotically near-Optimal Motion Planning,” The International Journal of Robotics Research, 2014, 33, (1), pp. 18-47. doi: 10.1177/0278364913498292.

Hsu, D., Tingting, J., Reif, J., and Zheng, S., “The Bridge Test for Sampling Narrow Passages with Probabilistic Roadmap Planners,” in, 2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422), (2003)), 3, pp. 4420-4426, vol. 4423. doi: 10.1109/ROBOT.2003.1242285.

Boor, V., Overmars, M.H., and Stappen, A.F.v.d., “The Gaussian Sampling Strategy for Probabilistic Roadmap Planners,” in, Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C), (1999)), 2, pp. 1018-1023, vol. 1012. doi: 10.1109/ROBOT.1999.772447.

Amato, N.M., Bayazit, O.B., Dale, L.K., Jones, C., and Vallejo, D., “Obprm: An Obstacle-Based Prm for 3d Workspaces,” in, Proceedings of the third workshop on the algorithmic foundations of robotics on Robotics: the algorithmic perspective: the algorithmic perspective, (A. K. Peters, Ltd., 1998 of Conference, Edition edn.), pp. 155–168. doi: 10.1201/9781439863886-19.

Geraerts, R. and Overmars, M.H., “Reachability-Based Analysis for Probabilistic Roadmap Planners,” Robotics and Autonomous Systems, 2007, 55, (11), pp. 824-836. doi: 10.1016/j.robot.2007.06.002.

Geraerts, R. and Overmars, M.H., “Sampling and Node Adding in Probabilistic Roadmap Planners,” Robotics and Autonomous Systems, 2006, 54, (2), pp. 165-173. doi: 10.1016/j.robot.2005.09.026.

Kuffner, J.J. and LaValle, S.M., “Rrt-Connect: An Efficient Approach to Single-Query Path Planning,” in, Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), (2000)), 2, pp. 995-1001, vol. 1002. doi: 10.1109/ROBOT.2000.844730.

Kala, R., “Rapidly Exploring Random Graphs: Motion Planning of Multiple Mobile Robots,” Advanced Robotics, 2013, 27, (14), pp. 1113-1122. doi: 10.1080/01691864.2013.805472.

Janson, L., Ichter, B., and Pavone, M., “Deterministic Sampling-Based Motion Planning: Optimality, Complexity, and Performance,” The International Journal of Robotics Research, 2017, 37, (1), pp. 46-61. doi: 10.1177/0278364917714338.

Solovey, K. and Kleinbort, M., “The Critical Radius in Sampling-Based Motion Planning,” The International Journal of Robotics Research, 2019, 39, (2-3), pp. 266-285. doi: 10.1177/0278364919859627.

Ichter, B., Schmerling, E., Lee, T.W.E., and Faust, A., “Learned Critical Probabilistic Roadmaps for Robotic Motion Planning,” in, 2020 IEEE International Conference on Robotics and Automation (ICRA), (2020)), pp. 9535-9541. doi: 10.1109/ICRA40945.2020.9197106.

Vonásek, V., Pěnička, R., and Kozlíková, B., “Computing Multiple Guiding Paths for Sampling-Based Motion Planning,” in, 2019 19th International Conference on Advanced Robotics (ICAR), (2019)), pp. 374-381. doi: 10.1109/ICAR46387.2019.8981589.

Kim, D., Kwon, Y., and Yoon, S., “Adaptive Lazy Collision Checking for Optimal Sampling-Based Motion Planning,” in, 2018 15th International Conference on Ubiquitous Robots (UR), (2018)), pp. 320-327. doi: 10.1109/URAI.2018.8442203.

Švestka, P. and Overmars, M.H., “Coordinated Path Planning for Multiple Robots,” Robotics and Autonomous Systems, 1998, 23, (3), pp. 125-152. doi: 10.1016/S0921-8890(97)00033-X.

Clark, C.M., “Probabilistic Road Map Sampling Strategies for Multi-Robot Motion Planning,” Robotics and Autonomous Systems, 2005, 53, (3), pp. 244-264. doi: 10.1016/j.robot.2005.09.002.

Yao, Z. and Gupta, K., “Path Planning with General End-Effector Constraints,” Robotics and Autonomous Systems, 2007, 55, (4), pp. 316-327. doi: 10.1016/j.robot.2006.11.004.

Kala, R., “Sampling Based Mission Planning for Multiple Robots,” in, IEEE Congress on Evolutionary Computation (CEC), (2016)), pp. 662-669. doi:10.1109/CEC.2016.7743856.