NURBs Based Multi-robots Path Planning with Obstacle Avoidance

Hadjira Belaidi; Fethi Demim

doi:10.62411/jcta.10387

NURBs Based Multi-robots Path Planning with Obstacle Avoidance

Hadjira Belaidi, Fethi Demim

Abstract

The primary problem for multi-robot displacement and motion phase solving requires that the robots prevent themselves from colliding with each other as well as stationary obstacles. In certain situations, robot conflict is unavoidable if one robot views its neighbors as immovable obstacles. Hence, this paper proposes a new NURBs (Non-Uniform Rational B-spline) based algorithm for multi-robot path planning in a crowded environment. First, the proposed technique finds each robot's free, smooth, optimal path while avoiding collision with the existing obstacles. Secondly, the prospect of possible collision between the preplanned trajectories will be computed to allow the robots to navigate in the same workspace and coordinate between them. Then, each robot's time to arrive at potential collision sites is computed based on its speed. As a result, the robots involved in the collision must choose whether to use the robot priority technique to prevent the collision. Simulation results under different scenarios and comparisons with previous works are provided to validate the work. The obtained results prove that the proposed approach is accurate (as the robot's instantaneous speed is taken into consideration), fast (as there is no need to broadcast the robots’ positions), the robots’ paths are optimal and smooth (to avoid jerk movements), and the approach ensures that the robots will not be trapped by local minima problem.

Keywords

Multi-robots; NURBs; Obstacle avoidance; Path planning; Robot velocity

Full Text:

PDF

References

H. Zheng, R. R. Negenborn, and G. Lodewijks, “Fast ADMM for Distributed Model Predictive Control of Cooperative Waterborne AGVs,” IEEE Trans. Control Syst. Technol., vol. 25, no. 4, pp. 1406–1413, Jul. 2017, doi: 10.1109/TCST.2016.2599485.

V. Digani, L. Sabattini, and C. Secchi, “A Probabilistic Eulerian Traffic Model for the Coordination of Multiple AGVs in Automatic Warehouses,” IEEE Robot. Autom. Lett., vol. 1, no. 1, pp. 26–32, Jan. 2016, doi: 10.1109/LRA.2015.2505646.

D. Jang, J. Yoo, C. Y. Son, D. Kim, and H. J. Kim, “Multi-Robot Active Sensing and Environmental Model Learning With Dis-tributed Gaussian Process,” IEEE Robot. Autom. Lett., vol. 5, no. 4, pp. 5905–5912, Oct. 2020, doi: 10.1109/LRA.2020.3010456.

Y. Yu, Z. Wu, Z. Cao, L. Pang, L. Ren, and C. Zhou, “A laser-based multi-robot collision avoidance approach in unknown envi-ronments,” Int. J. Adv. Robot. Syst., vol. 15, no. 1, p. 172988141875910, Jan. 2018, doi: 10.1177/1729881418759107.

P. Lijina and K. A. Nippun, “Bluetooth RSSI based collision avoidance in multirobot environment,” in 2016 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Sep. 2016, pp. 2168–2174. doi: 10.1109/ICACCI.2016.7732373.

S. E. García, E. Slawiñski, V. Mut, and F. Penizzotto, “Collision avoidance method for multi-operator multi-robot teleoperation system,” Robotica, vol. 36, no. 1, pp. 78–95, Jan. 2018, doi: 10.1017/S0263574717000169.

D. Claes and K. Tuyls, “Multi robot collision avoidance in a shared workspace,” Auton. Robots, vol. 42, no. 8, pp. 1749–1770, Dec. 2018, doi: 10.1007/s10514-018-9726-5.

O. Montiel, U. Orozco-Rosas, and R. Sepúlveda, “Path planning for mobile robots using Bacterial Potential Field for avoiding static and dynamic obstacles,” Expert Syst. Appl., vol. 42, no. 12, pp. 5177–5191, Jul. 2015, doi: 10.1016/j.eswa.2015.02.033.

A. M. Hassan, C. M. Elias, O. M. Shehata, and E. I. Morgan, “A global integrated artificial potential field/virtual obstacles path planning algorithm for multi-robot system applications,” Int. Res. J. Eng. Technol., vol. 4, no. 9, pp. 1198–1204, 2017.

F. Matoui, B. Boussaid, and M. N. Abdelkrim, “Distributed path planning of a multi-robot system based on the neighborhood artificial potential field approach,” Simulation, vol. 95, no. 7, pp. 637–657, Jul. 2019, doi: 10.1177/0037549718785440.

Z. Wu, W. Su, and J. Li, “Multi-robot path planning based on improved artificial potential field and B-spline curve optimization,” in 2019 Chinese Control Conference (CCC), Jul. 2019, pp. 4691–4696. doi: 10.23919/ChiCC.2019.8865232.

S. Moon, E. Oh, and D. H. Shim, “An Integral Framework of Task Assignment and Path Planning for Multiple Unmanned Aerial Vehicles in Dynamic Environments,” J. Intell. Robot. Syst., vol. 70, no. 1–4, pp. 303–313, Apr. 2013, doi: 10.1007/s10846-012-9740-3.

D. Liang, Z. Liu, and R. Bhamra, “Collaborative Multi-Robot Formation Control and Global Path Optimization,” Appl. Sci., vol. 12, no. 14, p. 7046, Jul. 2022, doi: 10.3390/app12147046.

F. Metoui, B. Boussaid, and M. N. Abdelkrim, “Path Planning for a Multi-robot System with Decentralized Control Architecture,” in Studies in Systems, Decision and Control, 2020, pp. 229–259. doi: 10.1007/978-981-15-1819-5_12.

S.-K. Huang, W.-J. Wang, and C.-H. Sun, “A Path Planning Strategy for Multi-Robot Moving with Path-Priority Order Based on a Generalized Voronoi Diagram,” Appl. Sci., vol. 11, no. 20, p. 9650, Oct. 2021, doi: 10.3390/app11209650.

H. Belaidi, H. Bentarzi, A. Belaidi, and A. Hentout, “Terrain Traversability and Optimal Path Planning in 3D Uneven Environment for an Autonomous Mobile Robot,” Arab. J. Sci. Eng., vol. 39, no. 11, pp. 8371–8381, Nov. 2014, doi: 10.1007/s13369-014-1352-8.

K. Mørken and M. Reimers, “An unconditionally convergent method for computing zeros of splines and polynomials,” Math. Comput., vol. 76, no. 258, pp. 845–865, Jan. 2007, doi: 10.1090/S0025-5718-07-01923-0.

F. Demim et al., “Smooth Sliding Mode Control Based Technique of an Autonomous Underwater Vehicle Based Localization Using Obstacle Avoidance Strategy,” in Proceedings of the 20th International Conference on Informatics in Control, Automation and Robotics, 2023, pp. 529–537. doi: 10.5220/0012118200003543.

R. Tallamraju, S. Rajappa, M. J. Black, K. Karlapalem, and A. Ahmad, “Decentralized MPC based Obstacle Avoidance for Mul-ti-Robot Target Tracking Scenarios,” in 2018 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR), Aug. 2018, pp. 1–8. doi: 10.1109/SSRR.2018.8468655.

F. Matoui, B. Boussaid, and M. N. Abdelkrim, “Local minimum solution for the potential field method in multiple robot motion planning task,” in 2015 16th International Conference on Sciences and Techniques of Automatic Control and Computer Engineering (STA), Dec. 2015, pp. 452–457. doi: 10.1109/STA.2015.7505223.

H. Belaidi, M. Abad, and A. E. Bouhamidi, “Hybrid Decentralized Multi-Robots Navigation Strategy,” J. Manuf. Technol. Res., vol. 13, no. 1/2, pp. 13–27, 2021.

J. Gregoire, M. ?áp, and E. Frazzoli, “Locally-optimal multi-robot navigation under delaying disturbances using homotopy con-straints,” Auton. Robots, vol. 42, no. 4, pp. 895–907, Apr. 2018, doi: 10.1007/s10514-017-9673-6.

J. Wang, R. Tai, and J. Xu, “A Bi-Level Probabilistic Path Planning Algorithm for Multiple Robots with Motion Uncertainty,” Complexity, vol. 2020, pp. 1–16, Jun. 2020, doi: 10.1155/2020/9207324.

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

K. Mørken, M. Reimers, and C. Schulz, “Computing intersections of planar spline curves using knot insertion,” Comput. Aided Geom. Des., vol. 26, no. 3, pp. 351–366, Mar. 2009, doi: 10.1016/j.cagd.2008.07.005.

B. Riviere, W. Honig, Y. Yue, and S.-J. Chung, “GLAS: Global-to-Local Safe Autonomy Synthesis for Multi-Robot Motion Planning With End-to-End Learning,” IEEE Robot. Autom. Lett., vol. 5, no. 3, pp. 4249–4256, Jul. 2020, doi: 10.1109/LRA.2020.2994035.

DOI: https://doi.org/10.62411/jcta.10387

Article Metrics

Abstract view : 0 times
PDF - 0 times

Refbacks

There are currently no refbacks.

Journal of Computing Theories and Applications published by Dian Nuswantoro University, Semarang, Indonesia collaborates with the Intelligent System (IntSys) Research and is supported by Future Techno Science Foundation, Indonesia.

Indexed by: