Dynamic RRT* Algorithm for Probabilistic Path Prediction in Dynamic Environment

Authors

  • Samir N. Ajani St. Vincent Pallotti College of Engineering and Technology, Nagpur, Maharashtra, India
  • Pooja V. Potnurwar Shri Ramdeobaba College of Engineering and Management, Nagpur, Maharashtra, India
  • Vrushali K. Bongirwar Shri Ramdeobaba College of Engineering and Management, Nagpur, Maharashtra, India
  • Archana. V. Potnurwar Priyadarshini College of Engineering, Nagpur, Maharashtra, India
  • Anuradha Joshi G. H. Raisoni College of Engineering, Nagpur, Maharashtra, India
  • Namita Parati Maturi Venkata Subba Rao (MVSR) Engineering College, Hyderabad, Telangana State, India

Keywords:

Dynamic, Path Planning, RRT*, Environment, algorithm

Abstract

In the recent years, the probabilistic path planning is an emerging area in the field of navigation. The navigation applications increases day by day which helps the society to solve the real world problems. The major challenge in this path planning is to deal with the dynamics in the environment. The dynamicity refers with the ability of an obstacle to move around the working environment and able to change their possessions frequently. There are many solutions were available to deal with the challenges in the dynamic environment and support the robot to navigate over the environment to move from source to a destination. Sampling based algorithms are the one which are most suitable for the path planning where the dynamic obstacles are present in the working environment. Rapidly Exploring Random Tree (RRT) and their variants like RRT*, F-RRT*, PQ-RRT*, etc. are the algorithms, have been shown significant improvement over predicted path and the time to navigate over predicted path. These variants of RRT* algorithms are analyzing over the asymptotic behaviour and the cost of the generated path is also analyzed. In this work we have proposed a dynamic RRT* algorithm which is critically analyzed in terms of optimality and the asymptotic behaviour is cortically analyzed to present a dynamic RRT* planner, which can be effectively used for the path planning over dynamic environment. However these algorithms were not analyzed in terms of dynamicity of the environment and make the approach dynamic which can adapt the environment features to be work dynamically to generate a path. The presented simulation results shows that the presented dynamic RRT* algorithm work significantly better in terms of path length and the navigation time during the actual run from source to a destination. The study of path planners developed over the years by the research community has been discussed and presented here in this work. Moreover the proposed dynamic RRT* approach shows that the computational cost of the algorithm makes it to a probabilistically complete solution to work with the dynamic environment.

Downloads

Download data is not yet available.

References

E. Rimon and D. E. Koditschek, "Exact robot navigation using artificial potential functions," in IEEE Transactions on Robotics and Automation, vol. 8, no. 5, pp. 501-518, Oct. 1992, doi: 10.1109/70.163777.

D. A. Panagiotopoulos, R. W. Newcomb and S. K. Singh, "Planning with a functional neural network architecture," in IEEE Transactions on Neural Networks, vol. 10, no. 1, pp. 115-127, Jan. 1999, doi: 10.1109/72.737498.

S. S. Ge and Y. J. Cui, "New potential functions for mobile robot path planning," in IEEE Transactions on Robotics and Automation, vol. 16, no. 5, pp. 615-620, Oct. 2000, doi: 10.1109/70.880813.

E. Plaku, K. E. Bekris, B. Y. Chen, A. M. Ladd and L. E. Kavraki, "Sampling-based roadmap of trees for parallel motion planning," in IEEE Transactions on Robotics, vol. 21, no. 4, pp. 597-608, Aug. 2005, doi: 10.1109/TRO.2005.847599.

R. Al-Hmouz, T. Gulrez and A. Al-Jumaily, "Probabilistic road maps with obstacle avoidance in cluttered dynamic environment," Proceedings of the 2004 Intelligent Sensors, Sensor Networks and Information Processing Conference, 2004., 2004, pp. 241-245, doi: 10.1109/ISSNIP.2004.1417469.

M. Baumann, S. Léonard, E. A. Croft and J. J. Little, "Path Planning for Improved Visibility Using a Probabilistic Road Map," in IEEE Transactions on Robotics, vol. 26, no. 1, pp. 195-200, Feb. 2010, doi: 10.1109/TRO.2009.2035745.

P. Cheng, E. Frazzoli and S. LaValle, "Improving the Performance of Sampling-Based Motion Planning With Symmetry-Based Gap Reduction," in IEEE Transactions on Robotics, vol. 24, no. 2, pp. 488-494, April 2008, doi: 10.1109/TRO.2007.913993.

M. Rickert, A. Sieverling and O. Brock, "Balancing Exploration and Exploitation in Sampling-Based Motion Planning," in IEEE Transactions on Robotics, vol. 30, no. 6, pp. 1305-1317, Dec. 2014, doi: 10.1109/TRO.2014.2340191.

L. Ma, J. Xue, K. Kawabata, J. Zhu, C. Ma and N. Zheng, "Efficient Sampling-Based Motion Planning for On-Road Autonomous Driving," in IEEE Transactions on Intelligent Transportation Systems, vol. 16, no. 4, pp. 1961-1976, Aug. 2015, doi: 10.1109/TITS.2015.2389215.

B. Zhao, R. Skjetne, M. Blanke and F. Dukan, "Particle Filter for Fault Diagnosis and Robust Navigation of Underwater Robot," in IEEE Transactions on Control Systems Technology, vol. 22, no. 6, pp. 2399-2407, Nov. 2014, doi: 10.1109/TCST.2014.2300815.

B. Wang, L. Yu, Z. Deng and M. Fu, "A Particle Filter-Based Matching Algorithm With Gravity Sample Vector for Underwater Gravity Aided Navigation," in IEEE/ASME Transactions on Mechatronics, vol. 21, no. 3, pp. 1399-1408, June 2016, doi: 10.1109/TMECH.2016.2519925.

T. Ju, S. Liu, J. Yang and D. Sun, "Rapidly Exploring Random Tree Algorithm-Based Path Planning for Robot-Aided Optical Manipulation of Biological Cells," in IEEE Transactions on Automation Science and Engineering, vol. 11, no. 3, pp. 649-657, July 2014, doi: 10.1109/TASE.2013.2289311.

L. G. D. O. Véras, F. L. L. Medeiros and L. N. F. Guimaráes, "Systematic Literature Review of Sampling Process in Rapidly-Exploring Random Trees," in IEEE Access, vol. 7, pp. 50933-50953, 2019, doi: 10.1109/ACCESS.2019.2908100.

Vinston Raja, R., Ashok Kumar, K. ., & Gokula Krishnan, V. . (2023). Condition based Ensemble Deep Learning and Machine Learning Classification Technique for Integrated Potential Fishing Zone Future Forecasting. International Journal on Recent and Innovation Trends in Computing and Communication, 11(2), 75–85. https://doi.org/10.17762/ijritcc.v11i2.6131

M. Kleinbort, K. Solovey, Z. Littlefield, K. E. Bekris and D. Halperin, "Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning With Forward Propagation," in IEEE Robotics and Automation Letters, vol. 4, no. 2, pp. x-xvi, April 2019, doi: 10.1109/LRA.2018.2888947.

C. Yuan, W. Zhang, G. Liu, X. Pan and X. Liu, "A Heuristic Rapidly-Exploring Random Trees Method for Manipulator Motion Planning," in IEEE Access, vol. 8, pp. 900-910, 2020, doi: 10.1109/ACCESS.2019.2958876.

P. Pharpatara, B. Hérissé and Y. Bestaoui, "3-D Trajectory Planning of Aerial Vehicles Using RRT*," in IEEE Transactions on Control Systems Technology, vol. 25, no. 3, pp. 1116-1123, May 2017, doi: 10.1109/TCST.2016.2582144.

Li Yuncheng and Shao Jie, "A revised Gaussian distribution sampling scheme based on RRT* algorithms in robot motion planning," 2017 3rd International Conference on Control, Automation and Robotics (ICCAR), 2017, pp. 22-26, doi: 10.1109/ICCAR.2017.7942654.

Anandpwar, W. ., S. . Barhate, S. . Limkar, M. . Vyawahare, S. N. . Ajani, and P. . Borkar. “Significance of Artificial Intelligence in the Production of Effective Output in Power Electronics”. International Journal on Recent and Innovation Trends in Computing and Communication, vol. 11, no. 3s, Mar. 2023, pp. 30-36, doi:10.17762/ijritcc.v11i3s.6152.

J. Ichnowski and R. Alterovitz, "Scalable Multicore Motion Planning Using Lock-Free Concurrency," in IEEE Transactions on Robotics, vol. 30, no. 5, pp. 1123-1136, Oct. 2014, doi: 10.1109/TRO.2014.2331091.

R. Cui, Y. Li and W. Yan, "Mutual Information-Based Multi-AUV Path Planning for Scalar Field Sampling Using Multidimensional RRT*," in IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 46, no. 7, pp. 993-1004, July 2016, doi: 10.1109/TSMC.2015.2500027.

M. Guo and M. M. Zavlanos, "Probabilistic Motion Planning Under Temporal Tasks and Soft Constraints," in IEEE Transactions on Automatic Control, vol. 63, no. 12, pp. 4051-4066, Dec. 2018, doi: 10.1109/TAC.2018.2799561.

H. -T. L. Chiang, J. Hsu, M. Fiser, L. Tapia and A. Faust, "RL-RRT: Kinodynamic Motion Planning via Learning Reachability Estimators From RL Policies," in IEEE Robotics and Automation Letters, vol. 4, no. 4, pp. 4298-4305, Oct. 2019, doi: 10.1109/LRA.2019.2931199.

M. Luo, X. Hou and S. X. Yang, "A Multi-Scale Map Method Based on Bioinspired Neural Network Algorithm for Robot Path Planning," in IEEE Access, vol. 7, pp. 142682-142691, 2019, doi: 10.1109/ACCESS.2019.2943009.

Allauddin Mulla, R. ., M. . Eknath Pawar, S. . S. Banait, S. . N. Ajani, M. . Pravin Borawake, and S. . Hundekari. “Design and Implementation of Deep Learning Method for Disease Identification in Plant Leaf”. International Journal on Recent and Innovation Trends in Computing and Communication, vol. 11, no. 2s, Mar. 2023, pp. 278-85, doi:10.17762/ijritcc.v11i2s.6147.

Abdul Rahman, Artificial Intelligence in Drug Discovery and Personalized Medicine , Machine Learning Applications Conference Proceedings, Vol 1 2021.

J. Yuan, H. Wang, C. Lin, D. Liu and D. Yu, "A Novel GRU-RNN Network Model for Dynamic Path Planning of Mobile Robot," in IEEE Access, vol. 7, pp. 15140-15151, 2019, doi: 10.1109/ACCESS.2019.2894626.

J. Liang, Z. Xu, X. Zhou, S. Li and G. Ye, "Recurrent Neural Networks-Based Collision-Free Motion Planning for Dual Manipulators Under Multiple Constraints," in IEEE Access, vol. 8, pp. 54225-54236, 2020, doi: 10.1109/ACCESS.2020.2981688.

Borkar, P., Wankhede, V.A., Mane, D.T. et al. Deep learning and image processing-based early detection of Alzheimer disease in cognitively normal individuals. Soft Comput (2023). https://doi.org/10.1007/s00500-023-08615-w

P. Ladosz, H. Oh, G. Zheng and W. Chen, "Gaussian Process Based Channel Prediction for Communication-Relay UAV in Urban Environments," in IEEE Transactions on Aerospace and Electronic Systems, vol. 56, no. 1, pp. 313-325, Feb. 2020, doi: 10.1109/TAES.2019.2917989.

Ajani, S.N., Mulla, R.A., Limkar, S. et al. DLMBHCO: design of an augmented bioinspired deep learning-based multidomain body parameter analysis via heterogeneous correlative body organ analysis. Soft Comput (2023). https://doi.org/10.1007/s00500-023-08613-y

Y. Jeong, S. Kim and K. Yi, "Surround Vehicle Motion Prediction Using LSTM-RNN for Motion Planning of Autonomous Vehicles at Multi-Lane Turn Intersections," in IEEE Open Journal of Intelligent Transportation Systems, vol. 1, pp. 2-14, 2020, doi: 10.1109/OJITS.2020.2965969.

Y. Jeong and K. Yi, "Bidirectional Long Shot-Term Memory-Based Interactive Motion Prediction of Cut-In Vehicles in Urban Environments," in IEEE Access, vol. 8, pp. 106183-106197, 2020, doi: 10.1109/ACCESS.2020.2994929.

The length of the path without a collision as determined by simulation

Downloads

Published

01.07.2023

How to Cite

Ajani, S. N. ., Potnurwar, P. V. ., Bongirwar, V. K. ., Potnurwar, A. V. ., Joshi, A. ., & Parati, N. . (2023). Dynamic RRT* Algorithm for Probabilistic Path Prediction in Dynamic Environment. International Journal of Intelligent Systems and Applications in Engineering, 11(7s), 263–271. Retrieved from https://ijisae.org/index.php/IJISAE/article/view/2952

Issue

Vol. 11 No. 7s (2023): Advancements in Machine Learning for Computer Science and Decision Support Systems

Section

Research Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.

IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.

Most read articles by the same author(s)