DBSCAN-Based Minimum Enclosing Ellipse Using the Control Barrier Function for Safe Navigation of Mobile Robots

Ju-Feng Wu; Chia-Chun Huang; Ming-Yang Cheng

doi:10.46604/aiti.2025.14579

Authors

Ju-Feng Wu Department of Electrical Engineering, National Cheng Kung University, Tainan, Taiwan, ROC
Chia-Chun Huang Department of Electrical Engineering, National Cheng Kung University, Tainan, Taiwan, ROC
Ming-Yang Cheng Department of Electrical Engineering, National Cheng Kung University, Tainan, Taiwan, ROC

DOI:

https://doi.org/10.46604/aiti.2025.14579

Keywords:

collision avoidance, mobile robot navigation, Control Barrier Function, Control Lyapunov Function

Abstract

This paper aims to reduce the redundant unsafe area in quadratic program approaches based on the Control Barrier Function (CBF) and the Control Lyapunov Function (CLF) for collision avoidance, hereafter referred to as the CBF-CLF approach. Existing CBF-CLF quadratic program approaches typically construct CBF based on Euclidean distance; however, the redundant unsafe area due to obstacles is excessively large, which may prevent finding feasible solutions. To address this issue, this study employs density-based spatial clustering of applications with noise (DBSCAN) and the Minimum Enclosing Ellipse (MEE) to reduce the unsafe area. The proposed approach is referred to as the DBSCAN-MEE-CBF. The effectiveness of the proposed method is demonstrated through both computer simulations and real-world experiments. Specifically, the proposed method reduces the size of the redundant unsafe area by up to 26.52% while maintaining robust collision avoidance.

References

S. Sotnik and V. Lyashenko, “Modern Industrial Robotics Industry,” International Journal of Academic Engineering Research, vol. 6, no. 1, pp. 37-46, 2022.

Y. K. Hwang and N. Ahuja, “A Potential Field Approach to Path Planning,” IEEE Transactions on Robotics and Automation, vol. 8, no. 1, pp. 23-32, 1992.

C. Zong, Q. Du, J. Chen, Y. Shan, Y. Wu, and Zhida Sha, “A Design of Three-Dimensional Spatial Path Planning Algorithm Based on Vector Field Histogram*,” Sensors, vol. 24, no. 17, article no. 5647, 2024.

S. Koley, “Role of Fluid Dynamics in Infectious Disease Transmission: Insights from COVID-19 and Other Pathogens,” Trends in Sciences, vol. 21, no. 8, article no. 8287, 2024.

A. N. A. Rafai, N Adzhar, and N. I. Jaini, “A Review on Path Planning and Obstacle Avoidance Algorithms for Autonomous Mobile Robots,” Journal of Robotics, vol. 2022, no. 1, article no. 2538220, 2022.

H. I. Lin and M. F. Hsieh, “Robotic Arm Path Planning Based on Three-Dimensional Artificial Potential Field,” 18th International Conference on Control, Automation and Systems, pp. 740-745, 2018.

J. Chen, X. Zhang, X. Peng, D. Xu, and J. Peng, “Efficient Routing for Multi-AGV Based on Optimized Ant-Agent,” Computers & Industrial Engineering, vol. 167, article no. 108042, 2022.

C. Duan and S. Li, “Research on AGV Route Planning Based on Improved Artificial Potential Field Algorithm,” Proceedings of the 3rd Asia-Pacific Conference on Image Processing, Electronics and Computers, pp. 338-342, 2022.

R. Szczepanski, T. Tarczewski, and K. Erwinski, “Energy Efficient Local Path Planning Algorithm Based on Predictive Artificial Potential Field,” IEEE Access, vol. 10, pp. 39729-39742, 2022.

T. Xu, H. Zhou, S. Tan, Z. Li, X. Ju, and Y. Peng, “Mechanical Arm Obstacle Avoidance Path Planning Based on Improved Artificial Potential Field Method,” Industrial Robot, vol. 49, no. 2, pp. 271-279, 2022.

Z. Fang and X. Liang, “Intelligent Obstacle Avoidance Path Planning Method for Picking Manipulator Combined with Artificial Potential Field Method,” Industrial Robot, vol. 49, no. 5, pp. 835-850, 2022.

X. Xia, T. Li, S. Sang, Y. Cheng, H. Ma, Q. Zhang, et al., “Path Planning for Obstacle Avoidance of Robot Arm Based on Improved Potential Field Method,” Sensors, vol. 23, no. 7, article no. 3754, 2023.

J. Borenstein and Y. Koren, “The Vector Field Histogram-Fast Obstacle Avoidance for Mobile Robots,” IEEE Transactions on Robotics and Automation, vol. 7, no. 3, pp. 278-288, 1991.

I. Ulrich and J. Borenstein, “VFH/sup */: Local Obstacle Avoidance with Look-Ahead Verification,” Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), vol. 3, pp. 2505-2511, 2000.

T. Xu, “Recent Advances in Rapidly-Exploring Random Tree: A Review,” Heliyon, vol. 10, no. 11, article no. e32451, 2024.

A. D. Ames, X. Xu, J. W. Grizzle, and P. Tabuada, “Control Barrier Function Based Quadratic Programs for Safety Critical Systems,” IEEE Transactions on Automatic Control, vol. 62, no. 8, pp. 3861-3876, 2017.

E. A. Basso and K. Y. Pettersen, “Task-Priority Control of Redundant Robotic Systems Using Control Lyapunov and Control Barrier Function Based Quadratic Programs,” IFAC-PapersOnLine, vol. 53, no. 2, pp. 9037-9044, 2020.

E. Schubert, J. Sander, M. Ester, H. P. Kriegel, and X. Xu, “DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN,” ACM Transactions on Database Systems, vol. 42, no. 3, pp. 1-21, 2017.

I. Jang and H. J. Kim, “Safe Control for Navigation in Cluttered Space Using Multiple Lyapunov-Based Control Barrier Functions,” IEEE Robotics and Automation Letters, vol. 9, no. 3, pp. 2056-2063, 2024.

H. Dai, C. Jiang, H. Zhang, and A. Clark, “Verification and Synthesis of Compatible Control Lyapunov and Control Barrier Functions,” IEEE 63rd Conference on Decision and Control, pp. 8178-8185, 2024.