Smoothing the Curvature of Trajectory of Ground Robot in 3D Space

Purpose or research. Development of an algorithm for smoothing the trajectory of a ground robot over rough terrain, represented as a graph in three-dimensional space.
Methods. This article presents the CSA (Curve Smoothing and Averaging) algorithm for smoothing local curves in the Oxy plane that make up a global curve, represented as a path on a connected graph in 3D space. The presented algorithm is based on the previously developed LRLHD-A * approach, which uses information about the vertices of the graph, their neighbors and the edges connecting them to select the area through which the smoothed curve will run. In order to avoid a broken curve at the output of the algorithm, a curve averaging method was developed, the idea of which is to shift the midpoints of local curves along the edges on which they are located.
Results. An experimental comparison was made of the curvature of the trajectories obtained using the curve smoothing algorithm with curve averaging (CSA) and without it (CS). The method was carried out on a threedimensional map of the area, presented in the form of a graph with 100082 vertices. For the experiments, a sample of 10 pairs of random vertices was used, between which a path was built using the LRLHD-A * algorithm. The results of the experiments have shown that averaging the curve after smoothing reduces its curvature from 24 to 42%.
Conclusion. Trajectories smoothed using the developed CSA algorithm have smoother curve bends at turns, compared to the algorithm taken as a basis. This allows the robots to move more smoothly and, as a consequence, reduce the consumption of the robot's battery.

1. Dubins L.E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. American Journal of mathematics, 1957, no. 79(3), pp. 497-516. https://doi.org/10.2307/2372560

2. Pérez J., Godoy J., Villagrá J., Onieva E. Trajectory generator for autonomous vehicles in urban environments. 2013 IEEE International Conference on Robotics and Automation, IEEE. 2013, pp. 409-414. https://doi.org/10.1109/ICRA.2013.6630608

3. Gerlach A.R., Kingston D., Walker B.K. UAV navigation using predictive vector field control. 2014 American Control Conference, IEEE. 2014, pp. 4907-4912. https://doi.org/10.1109/ACC.2014.6859082

4. Lin Y., Saripalli S. Path planning using 3D dubins curve for unmanned aerial vehicles. 2014 international conference on unmanned aircraft systems (ICUAS). IEEE, 2014, pp. 296-304. https://doi.org/10.1109/ICUAS.2014.6842268

5. Choi J., Curry R., Elkaim G. Path planning based on bézier curve for autonomous ground vehicles. Advances in Electrical and Electronics Engineering-IAENG Special Edition of the World Congress on Engineering and Computer Science 2008. IEEE, 2008, pp. 158- 166. https://doi.org/10.1109/WCECS.2008.27

6. Rastelli J.P., Lattarulo R., Nashashibi F. Dynamic trajectory generation using continuous-curvature algorithms for door to door assistance vehicles. 2014 IEEE Intelligent Vehicles Symposium Proceedings. IEEE, 2014, pp. 510-515. https://doi.org/10.1109/ IVS.2014.6856526

7. Walton D.J., Meek D.S., Ali J.M. Planar G2 transition curves composed of cubic Bé- zier spiral segments. Journal of Computational and Applied Mathematics, 2003, no. 157(2), pp. 453-476. https://doi.org/10.1016/S0377-0427(03)00435-7

8. Montes N., Mora M.C., Tornero J. Trajectory generation based on rational bezier curves as clothoids. 2007 IEEE Intelligent Vehicles Symposium. IEEE, 2007, pp. 505-510. https://doi.org/10.1109/IVS.2007.4290165

9. Montés N., Herraez A., Armesto L., Tornero J. Real-time clothoid approximation by Rational Bezier curves. 2008 IEEE International Conference on Robotics and Automation. IEEE, 2008, pp. 2246-2251. https://doi.org/10.1109/ROBOT.2008.4543548

10. Han L., Yashiro H., Nejad, H.T.N., Do Q.H., Mita S. Bezier curve based path planning for autonomous vehicle in urban environment. 2010 IEEE Intelligent Vehicles Symposium. IEEE, 2010, pp. 1036-1042. https://doi.org/10.1109/IVS.2010.5548085

11. González D., Perez J., Lattarulo R., Milanés V., Nashashibi F. Continuous curvature planning with obstacle avoidance capabilities in urban scenarios. 17th International IEEE Conference on Intelligent Transportation Systems (ITSC). IEEE, 2014, pp. 1430-1435. https://doi.org/10.1109/ITSC.2014.6957887

12. Elbanhawi M., Simic M., Jazar R.N. Continuous path smoothing for car-like robots using B-spline curves. Journal of Intelligent & Robotic Systems, 2015, no. 80(1), pp. 23-56. https://doi.org/10.1007/s10846-014-0172-0

13. Elbanhawi M., Simic M., Jazar R. Randomized bidirectional B-Spline parameterization motion planning. IEEE Transactions on intelligent transportation systems, 2015, no. 17(2), pp. 406-419. https://doi.org/10.1109/TITS.2015.2477355

14. Komoriya K., Tanie K. Trajectory design and control of a wheel-type mobile robot using B-spline curve. Proceedings. IEEE/RSJ International Workshop on Intelligent Robots and Systems'. (IROS'89)'The Autonomous Mobile Robots and Its Applications IEEE, 1989, pp. 398-405. https://doi.org/10.1109/IROS.1989.637937

15. Berglund T., Brodnik A., Jonsson H., Staffanson M., Soderkvist I. Planning smooth and obstacle-avoiding B-spline paths for autonomous mining vehicles. IEEE Transactions on Automation Science and Engineering, 2009, no. 7(1), pp. 167-172. https://doi.org/10.1109/TASE.2009.2015886

16. Yang K., Sukkarieh S. An analytical continuous-curvature path-smoothing algorithm. IEEE Transactions on Robotics, 2010, no. 26(3), pp. 561-568. https://doi.org/10.1109/TRO.2010.2042990

17. Herrmann P., Gerngroß M., Endisch C. NURBS based trajectory generation for an industrial five axis needle winding robot. 2018 4th International Conference on Control, Automation and Robotics (ICCAR). IEEE, 2018, pp. 31-36. https://doi.org/10.1109/ICCAR.2018.8384640

18. Ravari A.N., Taghirad H.D. NURBS-based representation of urban environments for mobile robots. 2016 4th International Conference on Robotics and Mechatronics (ICROM). IEEE, 2016, pp. 20-25. https://doi.org/10.1109/ICRoM.2016.7886782

19. Shi X., Fang H., Guo L. Multi-objective optimal trajectory planning of manipulators based on quintic NURBS. 2016 IEEE International Conference on Mechatronics and Automation. IEEE, 2016, pp. 759-765. https://doi.org/10.1109/ICMA.2016.7558658

20. Belaidi H., Hentout A., Bouzouia B., Bentarzi H., Belaidi A. NURBs trajectory generation and following by an autonomous mobile robot navigating in 3D environment. The 4th Annual IEEE International Conference on Cyber Technology in Automation, Control and Intelligent. IEEE, 2014, pp. 168-173. https://doi.org/10.1109/CYBER.2014.6917455

21. Guo H., Meng Y., Jin Y. Swarm robot pattern formation using a morphogenetic multi-cellular based self-organizing algorithm. 2011 IEEE International Conference on Robotics and Automation. IEEE, 2011, pp. 3205-3210. https://doi.org/10.1109/ICRA.2011.5979821

22. Huh U.Y., Chang S.R. AG 2 continuous path-smoothing algorithm using modified quadratic polynomial interpolation. International Journal of Advanced Robotic Systems, 2014, no. 11(2), 25 p. https://doi.org/10.5772/57340

23. Chang S.R., Huh U.Y. A collision-free G 2 continuous path-smoothing algorithm using quadratic polynomial interpolation. International Journal of Advanced Robotic Systems, 2014, no. 11(12), 194 p. https://doi.org/10.5772/59463

24. Lawonn K., Gasteiger R., Rössl C., Preim B. Adaptive and robust curve smoothing on surface meshes. Computers & graphics, 2014, no. 40(22-35). https://doi.org/10.1016/j.cag.2014.01.004

25. Zhang H., Yang S. Smooth path and velocity planning under 3D path constraints for car-like vehicles. Robotics and Autonomous Systems, 2018, no. 107, pp. 87-99. https://doi.org/10.1016/j.robot.2018.05.013

26. Hameiri E., Shimshoni I. Estimating the principal curvatures and the Darboux frame from real 3-D range data. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2003, no.33(4), pp. 626-637. https://doi.org/10.1109/TSMCB.2003.814304

27. Zakharov K., Saveliev A., Sivchenko O. Energy-Efficient Path Planning Algorithm on Three-Dimensional Large-Scale Terrain Maps for Mobile Robots. International Conference on Interactive Collaborative Robotics. Springer, Cham, 2020, pp. 319-330. https://doi.org/10.1007/978-3-030-60337-3_31

28. Аksamentov E., Astapova M., Usina E. Approach to Obstacle Localization for Robot Navigation in Agricultural Territories. International Conference on Interactive Collaborative Robotics. Springer, Cham, 2020, pp. 13-20. https://doi.org/10.1007/978-3-030-60337-3_2

29. Dudarenko D., Kovalev A., Tolstoy I., Vatamaniuk I. Robot Navigation System in Stochastic Environment Based on Reinforcement Learning on Lidar Data. Proceedings of 14th International Conference on Electromechanics and Robotics “Zavalishin's Readings”. Springer, Singapore, 2020, pp. 537-547. https://doi.org/10.1007/978-981-13-9267-2_

30. Denisov A.V. Algoritmy organizatsii besprovodnogo informatsionnogo vzaimodeistviya sensornykh sistem i robotizirovannykh ustroistv [Development of a recommender system for parameter calculation in wireless network of sensor devices]. Izvestiya Volgogradskogo gosudarstvennogo tekhnicheskogo universiteta = Bulletin of the Volgograd State Technical University, 2019, no. 7(4), pp. 30-34 (In Russ.). https://doi.org/10.26102/2310-6018/2019.27.4.025

31. Ronzhin A.L., Ngo K.T., Nguyen V.V. Zadachi upravleniya obmenom fizicheskikh resursov mezhdu sel'skokhozyaistvennoi tekhnikoi raznoi stepeni robotizatsii [Tasks of controlling the exchange of physical resources between agricultural means with varying degrees of robotization]. Izvestiya YuFU. Tekhnicheskie nauki = Izvestiya SFedU. Engineering Sciences, 2020, no. 1, pp. 40-51 (In Russ.). https://doi.org/10.18522/2311-3103-2020-1-39-51

32. Kovalev A.D. Podkhod k rekonfiguratsii modul'noi robototekhnicheskoi siste-my s ispol'zovaniem polinomial'nogo algoritma suboptimal'nogo poiska [Approach to reconfiguration of a modular robot system with a suboptimal search polynomial algorithm]. Izvestiya Volgogradskogo gosudarstvennogo tekhnicheskogo universiteta = Bulletin of the Volgograd State Technical University. 2020, no. 9(244), pp. 48-51 (In Russ.). https://doi.org/10.35211/1990-5297-2020-9-244-48-51

33. Pavliuk N., Saveliev A., Cherskikh E., Pykhov D. Formation of Modular Structures with Mobile Autonomous Reconfigurable System. Proceedings of 14th International Conference on Electromechanics and Robotics “Zavalishin's Readings”. Springer, Singapore. 2019, pp. 383-395. https://doi.org/10.1007/978-981-13-9267-2_31