Bezier Curve Collision-Free Route Planning Using Meta-Heuristic Optimization

  • Faculty of Advance Technology and Multidiscipline, Universitas Airlangga
  • Fakulti Teknologi Kejuruteraan Mekanikal dan Pembuatan, Universiti Teknikal Malaysia Melaka
Abstract views: 215 , PDF downloads: 144
Keywords: Bezier Curve, Collision Avoidance, GA, GWO


A collision-free route is very important for achieving sustainability in a manufacturing process and vehicle robot trajectories that commonly operate in a hazardous environment surrounded by obstacles. This paper presents a collision avoidance algorithm using a Bezier curve as a route path. The route planning is modeled as an optimization problem with the objective optimization is to minimize the route length considering an avoiding collision constraint. The collision-avoidance algorithm based on curve point analysis is developed incorporating metaheuristic optimizations, namely a Genetic Algorithm (GA) and a Grey Wolf Optimizer (GWO). In the collision avoidance algorithm, checking of curve point's position is important to evaluate the individual fitness value. The curve points are analyzed in such a way so that only the paths which are outside the obstacle area are selected. In this case, besides the minimum length as a fitness function, the constraint is the position of curve points from an obstacle. With the help of meta-heuristic optimization, the developed collision avoidance algorithm has been applied successfully to different types of obstacle geometries. The optimization problem is converted to the maximization problem so that the highest fitness value is used to measure the performance of the GA and GWO. In general, results show that the GWO outperforms the GA, where it exhibits the highest fitness value. However, the GA has shown better performance for the narrow passage problem than that of the GWO. Thus, for future research, implementing the hybrid technique combining the GA and the GWO to solve the advanced path planning is essential.


Download data is not yet available.


J. Jiang, Y. Ma Y, “Path planning strategies to optimize accuracy, quality, build time and material use in additive manufacturing: a review,” Micromachines, vol. 11, no. 7, pp. 633, 2020

H. Giberti, L. Sbaglia, M. Urgo, “A path planning algorithm for industrial processes under velocity constraints with an application to additive manufacturing,” J. Manuf. Syst., vol. 43, pp. 160–167, April 2017

L. Wang, “Collaborative robot monitoring and control for enhanced sustainability,” Int. J. Adv. Manuf. Technol., vol. 81, no. 9, pp.1433–1445, Dec. 2015

M. Zhang, A. Filippone, N. Bojdo, “Multi-objective optimisation of aircraft departure trajectories,” Aerosp. Sci. Technol., vol. 79, pp. 37–47, Aug. 2018

M. Gil, J. Montewka, P. Krata, T. Hinz, S. Hirdaris, “Determination of the dynamic critical maneuvering area in an encounter between two vessels: Operation with negligible environmental disruption,” Ocean Eng., vol. 213, Oct. 2020

M. Garetti, M. Taisch M, (2012) “Sustainable manufacturing: trends and research challenges,” Prod. Plan Control, vol. 23, no, (2-3), 2019, pp. 83–104

R. A. Saeed, D. R. Recupero, P. Remagnino, (2020) “A boundary node method for path planning of mobile robots,” Robot. Auton. Syst., vol. 123, pp. 03320, Jan. 2020

R. Kala, A. Shukla, R. Tiwari, “Robotic path planning in static environment using hierarchical multi-neuron heuristic search and probability based fitness,” Neurocomputing, vol. no. 74 (14–15), pp. 2314-2335, July 2011

Y. Linquan, L. Zhongwen, T. Zhonghua, Lv Weixian, “Path planning Algorithm for Mobile Robot Obstacle Avoidance Adopting Bezier Curve Based on GA,” in Proc. 2008 Chinese Control and Decision Conference (CCDC 2008), pp. 3286-3289, doi: 10.1109/CCDC.2008.4597937

J. Choi, G. H. Elkaim, “Smoth Path Generation Based on Bezier Curves for Autonomous Vehicle,” in Proc. World Congress on Engineering and Computer Science (WCECS), 2009, ISBN: 978-988-98671-0-2.

Z. Lil, D.S. Meek, D.J. Walton, “A smooth, obstacle-avoiding curve”, Comput. Graph., Vol. 30, pp. 581–587, Aug. 2006

S.N. Sivanandam, S.N. Deepa, Introduction to Genetic Algorithm, Spinger-Verlag, 2008

S. Mirjalili, S. M. Mirjalili, A. Lewis, “Grey wolf optimizer,” Adv. Eng. Softw., vol. 69, pp. 46–61, March. 2014

J. M. Lien, J. Keyser, N. M. Amato NM, (2006) “Simultaneous shape decomposition and skeletonization,” in ACM symposium on solid and physical modeling, 2006, pp 219–228

V. Vonásek, R. Pěnička, B. Kozlíková, “Searching Multiple Approximate Solutions in Configuration Space to Guide Sampling-Based Motion Planning,” J Intell Robot Syst, vol. 100, pp. 1527–1543, Aug. 2020

A. Varava, J. F. Carvalho, F. T. Pokorny, D. Kragic, “Free space of rigid objects: Caging, path non-existence, and narrow passage detection. In Workshop on algorithmic foundations of robotics, 2018, pp. 19-35

E. J. Griffith, C. Mishra, J. F. Ralph and S. Maskell, "A system for the generation of synthetic Wide Area Aerial surveillance imagery", Simulation Modelling Practice and Theory, vol. 84, pp. 286-308, 2018.

C. Yuan, H. Cai, “Spatial reasoning mechanism to enable automated adaptive trajectory planning in ground penetrating radar survey,” Autom. Constr., vol. 114, pp. 103157, 2020

A.L. Alfeo, M.G. Cimino, G. Vaglini, “Enhancing biologically inspired swarm behavior: Metaheuristics to foster the optimization of UAVS coordination in target search,” Computers & Operations Research, vol. 110, pp. 34-47, 2019

Zimmermann M., Frejinger E., “A tutorial on recursive models for analyzing and predicting path choice behavior,” EURO Journal on Transportation and Logistics, vol. 9, pp. 100004, 2020

B. I. Kazem, A. I. Mahdi, A. T. Oudah, "Motion Planning for a Robot Arm by Using Genetic Algorithm", Jordan Journal of Mechanical and Industrial Engineering, vol. 2, no. 3, pp. 131-136, 2008.

P. Corke, Robotics, Vision and Control: Fundamental Algorithms In MATLAB, Berlin: Springer, 2017

M. Shanmugavel, A. Tsourdos, B. A. White, R. Zbikowski, “Differential Geometric Path Planning of Multiple UAVs,” ASME Journal, Vol. 129, No. 11, pp. 620-632, 2007.

M. Shanmugavel, A. Tsourdos, B. A. White, R. Zbikowski, “Co-operative Path Planning of Multiple UAVs using Dubins Paths with Clothoid arcs” Control Engineering Practice, Vol. 18, pp. 1084-1092, 2010.

How to Cite
, & . (2021). Bezier Curve Collision-Free Route Planning Using Meta-Heuristic Optimization. International Journal of Artificial Intelligence & Robotics (IJAIR), 3(1), 1-14.