Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-24T20:53:06.210Z Has data issue: false hasContentIssue false
  • English
  • Français

Dynamic path planning over CG-Space of 10DOF Rover with static and randomly moving obstacles using RRT* rewiring

Published online by Cambridge University Press:  07 January 2022

Shubhi Katiyar Open the ORCID record for Shubhi Katiyar [Opens in a new window]  and
Ashish Dutta Open the ORCID record for Ashish Dutta [Opens in a new window]
Shubhi Katiyar*
Affiliation:
Department of Mechanical Engineering, Indian Institute of Technology, Kanpur, Uttar Pradesh 208016, India
Ashish Dutta
Affiliation:
Department of Mechanical Engineering, Indian Institute of Technology, Kanpur, Uttar Pradesh 208016, India
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Dynamic path planning is a core research content for intelligent robots. This paper presents a CG-Space-based dynamic path planning and obstacle avoidance algorithm for 10 DOF wheeled mobile robot (Rover) traversing over 3D uneven terrains. CG-Space is the locus of the center of gravity location of Rover while moving on a 3D terrain. A CG-Space-based modified RRT* samples a random space tree structure. Dynamic rewiring this tree can handle the randomly moving obstacles and target in real time. Simulations demonstrate that the Rover can obtain the target location in 3D uneven dynamic environments with fixed and randomly moving obstacles.

Keywords

dynamic path planningRRT* algorithmCG-SpaceRover
Type
Research Article
Information
Robotica , Volume 40 , Issue 8 , August 2022 , pp. 2610 - 2629
Copyright
© The Author(s), 2022. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Latombe, J.-C., Robot Motion Planning (Kluwer Academic Publisher, Boston, MA, 1991) 651 p.CrossRefGoogle Scholar
Canny, J., The Complexity of Robot Motion Planning (MIT Press, Cambridge, MA, 1988).Google Scholar
Lozano-Pérez, T., Spatial Planning: A Configuration Space Approach (Springer, New York, NY, 1990). Available from: https://doi.org/10.1007/978-1-4613-8997-2_20 Google Scholar
Fiorini, P., Robot Motion Planning Among Moving Obstacles Ph.D. Thesis (University of California, Los Angeles, 1995).Google Scholar
LaValle, S. M., Planning Algorithms (Cambridge University Press, New York, 2006).CrossRefGoogle Scholar
Inoue, A., Inoue, K. and Okawa, Y., “On-line motion planning of an autonomous mobile robot to avoid multiple moving obstacles based on the prediction of their future trajectories,” J. Rob. Soc. Jpn. 15(2), 249–60 (1997).CrossRefGoogle Scholar
Fox, D., Burgard, W. and Thrun, S., “The dynamic window approach to collision avoidance,” IEEE Rob. Autom. Mag. 4(1), 23–33 (1997;).CrossRefGoogle Scholar
Fraichard, T. and Asama, H., “Inevitable collision states-a step towards safer robots?,” Adv. Rob. 18(10), 1001–1024 (2004).Google Scholar
Petti, S. and Fraichard, T., “Safe Motion Planning in Dynamic Environments,” 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems (2005) pp. 2210–2215.Google Scholar
Shiller, Z., Large, F. and Sekhavat, S., “Motion Planning in Dynamic Environments: Obstacles Moving Along Arbitrary Trajectories,” Proceedings 2001 ICRA IEEE International Conference on Robotics and Automation (Cat No01CH37164), vol. 4 (2001) pp. 3716–37121.Google Scholar
van den Berg, J. P., Path Planning in Dynamic Environments Dissertation (Utrecht University, 2007). Available from: http://localhost/handle/1874/20873 Google Scholar
Kai-bo, X. U., Hai-yan, L. U., Yang, H. and Shi-juan, H. U., “Robot path planning based on double-layer ant colony optimization algorithm and dynamic environment,” Acta Electonica Sinica 47(10), 2166 (2019).Google Scholar
Nasrollahy, A. Z. and Javadi, H. H. S., “Using Particle Swarm Optimization for Robot Path Planning in Dynamic Environments with Moving Obstacles and Target,” 2009 Third UKSim European Symposium on Computer Modeling and Simulation (2009) pp. 60–65.Google Scholar
Hwu, T., Wang, A. Y., Oros, N. and Krichmar, J. L., “Adaptive robot path planning using a spiking neuron algorithm with axonal delays,” IEEE Trans. Cognit. Develop. Syst. 10(2), 126–137 (2018).Google Scholar
Zhang, X., Zhao, Y., Deng, N. and Guo, K., “Dynamic path planning algorithm for a mobile robot based on visible space and an improved genetic algorithm,” Int. J. Adv. Rob. Syst. 13(3), 91 (2016).CrossRefGoogle Scholar
Koenig, S., Likhachev, M. and Furcy, D., “D*-Lite,” 18th National Conference on Artificial Intelligence, Edmonton, Canada, 28 July–1 August (AAAI Press, Palo Alto, 2002) pp. 476–483.Google Scholar
Koenig, S., Likhachev, M. and Furcy, D., “Lifelong planning A∗,” Artif. Intell. 155(1), 93–146 (2004).CrossRefGoogle Scholar
Likhachev, M. and Ferguson, D., “Planning long dynamically feasible maneuvers for autonomous vehicles,” Int. J. Rob. Res. 28(8), 933–945 (2009).CrossRefGoogle Scholar
Karaman, S. and Frazzoli, E., “Sampling-based algorithms for optimal motion planning,” Int. J. Rob. Res. 30(7), 846–894 (2011).CrossRefGoogle Scholar
LaValle, S. M. and Kuffner, J. J., “Randomized kinodynamic planning,” Int. J. Rob. Res. 20(5), 378–400 (2001).CrossRefGoogle Scholar
Bruce, J. and Veloso, M. M., “Real-Time Randomized Path Planning for Robot Navigation,” In: RoboCup 2002: Robot Soccer World Cup VI (Kaminka, G. A., Lima, P. U. and Rojas, R., eds.), Lecture Notes in Computer Science (Springer, Berlin, Heidelberg, 2003) pp. 288–295.Google Scholar
Qureshi, A. H., Iqbal, K. F., Qamar, S. M., Islam, F., Ayaz, Y. and Muhammad, N., “Potential Guided Directional-RRT* for Accelerated Motion Planning in Cluttered Environments,” 2013 IEEE International Conference on Mechatronics and Automation (2013) pp. 519–524.Google Scholar
Zucker, M., Kuffner, J. and Branicky, M., “Multipartite RRTs for Rapid Replanning in Dynamic Environments,” Proceedings 2007 IEEE International Conference on Robotics and Automation (2007) pp. 1603–1609.Google Scholar
Adiyatov, O. and Varol, H. A., “A Novel RRT*-based Algorithm for Motion Planning in Dynamic Environments,” 2017 IEEE International Conference on Mechatronics and Automation (ICMA) (2017) pp. 1416–1421.Google Scholar
Gayle, R., Klingler, K. R. and Xavier, P. G., “Lazy Reconfiguration Forest (LRF) - An Approach for Motion Planning with Multiple Tasks in Dynamic Environments,” Proceedings 2007 IEEE International Conference on Robotics and Automation (2007) pp. 1316–1323.Google Scholar
Martin, S. R., Wright, S. E. and Sheppard, J. W., “Offline and Online Evolutionary Bi-Directional RRT Algorithms for Efficient Re-Planning in Dynamic Environments,” 2007 IEEE International Conference on Automation Science and Engineering (2007) pp. 1131–1136.Google Scholar
Otte, M., Any-Com Multi-Robot Path Planning Ph.D. Thesis (University of Colorado at Boulder, USA, 2011).Google Scholar
Arslan, O. and Tsiotras, P., “Use of Relaxation Methods in Sampling-Based Algorithms for Optimal Motion Planning,” 2013 IEEE International Conference on Robotics and Automation (2013) pp. 2421–2428.Google Scholar
Salzman, O., Shaharabani, D., Agarwal, P. K. and Halperin, D., “Sparsification of motion-planning roadmaps by edge contraction,” Int. J. Rob. Res. 33(14), 1711–1725 (2014).CrossRefGoogle Scholar
Otte, M. and Frazzoli, E., “RRTX: Asymptotically optimal single-query sampling-based motion planning with quick replanning,” Int. J. Rob. Res. 35(7), 797–822 (2016).CrossRefGoogle Scholar
Masehian, E. and Katebi, Y., “Sensor-based motion planning of wheeled mobile robots in unknown dynamic environments,” J. Intell. Robot. Syst. 74(3), 893–914 (2014).CrossRefGoogle Scholar
Yoshida, E., Esteves, C., Belousov, I., Laumond, J.-P., Sakaguchi, T. and Yokoi, K., “Planning 3-D collision-free dynamic robotic motion through iterative reshaping,” IEEE Trans. Rob. 24(5), 1186–11898 (2008).Google Scholar
Zhang, B. and Duan, H., “Three-dimensional path planning for uninhabited combat aerial vehicle based on predator-prey pigeon-inspired optimization in dynamic environment,” IEEE/ACM Trans. Comput. Biol. Bioinf. 14(1), 97–107 (2017).CrossRefGoogle Scholar
Thomas, G. and Vantsevich, V. V., “Wheel-terrain-obstacle interaction in vehicle mobility analysis,” Veh. Syst. Dyn. 48(sup1), 139–156 (2010).CrossRefGoogle Scholar
Raja, R., Dutta, A. and Venkatesh, K. S., “New potential field method for rough terrain path planning using genetic algorithm for a 6-wheel rover,” Rob. Auton. Syst. 72, 295–306 (2015).CrossRefGoogle Scholar
Katiyar, S. and Dutta, A., “Path Planning and Obstacle Avoidance in CG Space of a 10 DOF Rover using RRT*,” Proceedings of the Advances in Robotics 2019. Chennai, India (2019) pp. 1–6.Google Scholar
LaValle, S. M., Rapidly-exploring random trees: A new tool for path planning. Computer Science Department, Iowa State University; 1998. Report No.: TR 98-11.Google Scholar
Karaman, S. and Frazzoli, E., “Optimal Kinodynamic Motion Planning Using Incremental Sampling-Based Methods,” 49th IEEE Conference on Decision and Control (CDC) (2010) pp. 7681–7687.Google Scholar
Connell, D. and La, H. M., “Dynamic Path Planning and Replanning for Mobile Robots Using RRT,” 2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC) (2017) pp. 1429–1434.Google Scholar
Katiyar, S. and Dutta, A., “PSO Based Path Planning and Dynamic Obstacle Avoidance in CG Space of a 10 DOF Rover,” Proceedings of the Advances in Robotics 2021. Kanpur, India (2021) pp. 1–6.Google Scholar