Algorithm for planning energy-efficient local trajectories of ground-based robotics, considering the global route

Algorithm for planning energy-efficient local trajectories of ground-based robotics, considering the global route

Anton I. Saveliev
PhD in Technical Sciences, Saint Petersburg Federal Research Center of the Russian Academy of Sciences (SPC RAS), Laboratory of Autonomous Robotic Systems, Senior Research Scientist, 39, 14 line V.O., Saint Petersburg, 199178, Russia, This email address is being protected from spambots. You need JavaScript enabled to view it., ORCID: 0000-0003-1851-2699

Konstantin V. Kamynin
SPC RAS, Laboratory of Autonomous Robotic Systems, Software Engineer, 39, 14 line V.O., Saint Petersburg, 199178, Russia, This email address is being protected from spambots. You need JavaScript enabled to view it.

Aleksei A. Erashov
SPC RAS, Laboratory of Autonomous Robotic Systems, Junior Research Scientist, 39, 14 line V.O., Saint Petersburg, 199178, Russia, This email address is being protected from spambots. You need JavaScript enabled to view it., ORCID: 0000-0001-8003-3643

Ekaterina O. Cherskikh
SPC RAS, Laboratory of Autonomous Robotic Systems, Junior Research Scientist, 39, 14 line V.O., Saint Petersburg, 199178, Russia, This email address is being protected from spambots. You need JavaScript enabled to view it., ORCID: 0000-0002-4443-2281

Received May 30, 2023

Abstract
In this paper, an algorithm is presented that provides dynamic planning of a local trajectory of movement based on the data from the 3D lidar, considering a predetermined global route on rough terrain. The proposed local planning algorithm considers the features of the LRLHD-A* global energy-efficient trajectory planning algorithm previously developed by the authors. The novelty of the proposed solution lies in the algorithm for generating a graph of the surrounding space from the data obtained from a three-dimensional lidar installed on a mobile robot with O(nlogn) complexity, which reduces the time to build a local trajectory. The developed solution makes it possible to combine the processes of constructing a local and global trajectory of movement by using the energy-efficient algorithm for constructing trajectories LRLHD-A* as the basis. During the experiments, it was revealed that when choosing a step of 0.5 m for a local grid of 10 × 10 m in size, the time for constructing the grid and the trajectory does not exceed 0.1 s. The developed algorithm can be used as a local scheduler in close to real time mode, providing prompt response to various obstacles on the global trajectory of the robot, considering the features of the terrain and the current global trajectory.

Key words
Trajectory planning, local trajectory, local navigation, dynamic obstacles, overcoming obstacles, energy efficient movement.

Acknowledgements
This work is supported by the RFBR Project No. 20-79-10325.

DOI
10.31776/RTCJ.11304

Bibliographic description
Saveliev, A.I., Kamynin, K.V., Erashov, A.A. and Cherskikh, E.O. (2023). "Algorithm for planning energy-efficient local trajectories of ground-based robotics, considering the global route". Robotics and Technical Cybernetics, vol. 11, no. 3, pp. 188-196, DOI: 10.31776/RTCJ.11304. (in Russian).

UDC identifier:
004.021

References

  1. Ravankar, A.A., Ravankar, A., Emaru, T. and Kobayashi, Y. (2020), HPPRM: hybrid potential based probabilistic roadmap algorithm for improved dynamic path planning of mobile robots, IEEE Access, 8, pp. 221743-221766, DOI: 10.1109/ACCESS.2020.3043333.
  2. Kavraki, L.E., Svestka, P., Latombe, J.C. and Overmars, M.H. (1996), Probabilistic roadmaps for path planning in high-dimensional configuration spaces. Transactions on Robotics and Automation, 12(4), pp. 566-580, DOI: 10.1109/70.508439.
  3. Khatib, O. (1986), Real-time obstacle avoidance for manipulators and mobile robots, The international journal of robotics research, 5(1), pp. 90-98.
  4. Barraquand, J., Langlois, B. and Latombe, J.C. (1992), Numerical potential field techniques for robot path planning, Transactions on systems, man, and cybernetics, 22(2), pp. 224-241.
  5. Le Gouguec, A., Kemeny, A., Berthoz, A. and Merienne, F. (2017), Artificial Potential Field Simulation Framework for Semi-Autonomous Car Conception, In: Driving Simulation Conference.
  6. Rösmann, C., Hoffmann, F. and Bertram, T. (2017), Kinodynamic trajectory optimization and control for car-like robots. In: International Conference on Intelligent Robots and Systems (IROS), 5681-5686.
  7. Kroumov, V., Yu, J. and Shibayama, K. (2010), 3D path planning for mobile robots using simulated annealing neural network, International Journal of Innovative Computing, Information and Control, 6(7), pp. 2885-2899.
  8. Visca, M., Powell, R., Gao, Y. and Fallah, S. (2022), Meta-Conv1D energy-aware path planner for mobile robots in unstructured terrains, TechRxiv, Preprint, 14(8).
  9. Josef, S. and Degani, A. (2020), Deep reinforcement learning for safe local planning of a ground vehicle in unknown rough terrain, In: Robotics and Automation Letters, 5(4), pp. 6748-6755.
  10. Harik, E.H.C. and Korsaeth, A. (2019), The heading weight function: A novel LiDAR-based local planner for nonholonomic mobile robots, Sensors, 19(16), p. 3606, DOI: 10.3390/s19163606.
  11. Chilian, A. and Hirschmüller, H. (2009), October. Stereo camera based navigation of mobile robots on rough terrain, In: International Conference on Intelligent Robots and Systems,IEEE, pp. 4571-4576.
  12. Zhang, X., Wang, J., Fang, Y. and Yuan, J. (2018), Multilevel humanlike motion planning for mobile robots in complex indoor environments, Transactions on Automation Science and Engineering, 16(3), pp.1 244-1258.
  13. Likhachev, M. et al. (2008), Anytime search in dynamic graphs, Artificial Intelligence, 172(14), pp. 1613-1643.
  14. Likhachev, M., Gordon, G.J. and Thrun, S. (2003), ARA*: Anytime A* with provable bounds on sub-optimality, Advances in neural information processing systems, 16.
  15. Mohammadpour, M. et al. (2021), An investigation into the energy-efficient motion of autonomous wheeled mobile robots, Energies, 14(12), p. 3517.
  16. Yahja, A., Singh, S. and Stentz, A. (2000), An efficient on-line path planner for outdoor mobile robots, Robotics and Autonomous systems, 32(2-3), pp. 129-143.
  17. Santos, A.S., Azpúrua, H.I.P., Pessin, G. and Freitas, G.M. (2018), Path planning for mobile robots on rough terrain, In 2018 Latin American Robotic Symposium, 2018 Brazilian Symposium on Robotics (SBR) and 2018 Workshop on Robotics in Education (WRE), 265-270.
  18. Suo, C. et al. (2019), Real time obstacle avoidance and navigation with mobile robot via local elevation information, In: International Conference on Robotics and Biomimetics (ROBIO), 2896-2901.
  19. Pütz, S., Wiemann, T., Piening, M.K. and Hertzberg, J. (2021), Continuous Multilayer and Multilevel Shortest Path Vector Field Navigation on 3D Triangular Meshes for Mobile Robots, IEEE International Conference on Robotics and Automation (ICRA), DOI: 10.1109/ICRA48506.2021.9560981.
  20. Sethian, J.A. (1996), A fast marching level set method for monotonically advancing fronts, Proceedings of the National Academy of Sciences, 93(4), pp. 1591-1595.
  21. Zakharov, K., Saveliev, A. and Sivchenko, O. (2020), Energy-efficient path planning algorithm on three-dimensional large-scale terrain maps for mobile robots, In: Interactive Collaborative Robotics: 5th International Conference, ICR 2020, 319-330.
  22. Ram, P. and Sinha, K. (2019), Revisiting kd-tree for nearest neighbor search, In: Proceedings of the 25th acm sigkdd international conference on knowledge discovery & data mining, pp. 1378-1388.