مسیریابی برخط ربات خودمختار در محیط با موانع محدب مبتنی بر هندسه مماسی

معدی, سیدحسام الدین; مظفری, مهدی; منافی, ابوالفضل; مهدوی گلمیشه, فاطمه; شمقدری, سعید

doi:10.47176/MAJ.2025.1520

مسیریابی برخط ربات خودمختار در محیط با موانع محدب مبتنی بر هندسه مماسی

نوع مقاله : گرایش دینامیک، ارتعاشات و کنترل

نویسندگان

سیدحسام الدین معدی ¹

مهدی مظفری ¹

ابوالفضل منافی ²

فاطمه مهدوی گلمیشه ³

سعید شمقدری ⁴

¹ دانشجوی کارشناسی ارشد، دانشگاه علم و صنعت ایران ، تهران، ایران

² کارشناسی ارشد، دانشگاه علم و صنعت ایران ، تهران، ایران

³ دکتری، دانشگاه علم و صنعت ایران ، تهران، ایران

⁴ دانشیار، دانشگاه علم و صنعت ایران ، تهران، ایران

10.47176/MAJ.2025.1520

چکیده

در این پژوهش یک الگوریتم هندسی نوآورانه برای مسیریابی برخط ربات‌های خودمختار در محیط‌های دوبعدی با موانع محدب ارائه می‌شود. ایده اصلی روش پیشنهادی استفاده از بیضی‌های محاطی بهینه برای مدل‌سازی موانع و به‌کارگیری خطوط مماسی به عنوان مسیرهای کاندید است. بدین ترتیب، مسئله مسیریابی در هر گام به یک حوزه‌ی محدب کاهش یافته و انتخاب مسیر نهایی از طریق کمینه‌سازی یک تابع هزینه‌ی سه‌جزئی (طول مسیر، میزان انحراف زاویه‌ای و فاصله از موانع) صورت می‌گیرد. این رویکرد نه تنها سادگی محاسبات را تضمین می‌کند؛ بلکه امکان به‌روزرسانی سریع و برخط مسیر در محیط‌های پویا را فراهم می‌سازد. یافته‌های شبیه‌سازی نشان می‌دهد که الگوریتم پیشنهادی به طور چشمگیری بر روش‌های مرسوم A*،RRT* و ACO برتری دارد. در محیط نخست، زمان اجرا، تنها 032/0 ثانیه (در برابر 981/3 و 1/4ثانیه)، طول مسیر 9/1896 کوتاه‌تر از RRT* با 2/1952 متر و نرمی مسیر 225/0(در برابر 6/696 و 147/5) ثبت شد. در محیط دوم نیز زمان محاسباتی 124/0 ثانیه و نرمی مسیر 4/0 گزارش گردید که حداقل 60٪ سریع‌تر از A* و حدود 20٪ سریع‌تر از RRT* است. علاوه بر این، مصرف انرژی در مسیرهای الگوریتم به طور متوسط بین 5 تا 10 درصد کمتر از سایر مسیرها بود. نتایج نشان می‌دهد با ترکیب هندسه مماسی و مدل‌سازی بیضوی موانع، قادر است مسیرهایی کوتاه‌تر، نرم‌تر و بهینه‌تر ایجاد کرده و در عین حال زمان پردازش را به طور معناداری کاهش دهد. بدین ترتیب، گزینه‌ای کارآمد برای کاربردهای مقیاس بالا و برخط محسوب شده، در ضمن قابلیت توسعه به محیط‌های سه‌بعدی را نیز داراست.

چکیده تصویری

کلیدواژه‌ها

مسیریابی برخط

هندسه کاربردی

ربات خودمختار

بهینه‌سازی

موضوعات

دینامیک ارتعاشات و کنترل

عنوان مقاله English

Real-Time Tangent Based Path Planning for Autonomous Robots in Convex Obstacle Environments

نویسندگان English

Hesamedin Moedi ¹

Mahdi Mozaffari ¹

Abolfazl Manafi ²

Fatemeh Mahdavi G. ³

Saeed Shamaghdari ⁴

¹ Master's student, Iran University of Science and Technology, Tehran, Iran

² Master's degree, Iran University of Science and Technology, Tehran, Iran

³ PhD, Iran University of Science and Technology, Tehran, Iran

⁴ Associate Professor, Iran University of Science and Technology, Tehran, Iran

چکیده English

This study introduces a novel geometric algorithm for online path planning of autonomous robots in two-dimensional environments with convex obstacles. The proposed method models obstacles using optimized inscribed ellipses and generates candidate trajectories through tangent lines. By doing so, the planning problem at each step is confined to a convex region, and the optimal path is determined by minimizing a three-term cost function that incorporates path length, angular deviation, and obstacle clearance. This formulation not only simplifies the computational process but also supports rapid, real-time path updates in dynamic environments.

Extensive simulations confirm that the algorithm considerably outperforms well-established approaches such as A*, RRT*, and ACO. In the first test environment, it achieved an execution time of only 0.032 s (versus 3.981 s for A* and 4.1 s for RRT*), a path length of 1896.9 m (shorter than 1952.2 m for RRT*), and a smoothness value of 0.225 (compared with 696.6 for A* and 5.147 for RRT*). In the second environment, the computation time was 0.124 s and the smoothness 0.40, representing at least a 60% improvement over A* and a 20% improvement over RRT*. Furthermore, the method reduced the average energy consumption by 5–10% compared with competing algorithms.

Overall, the findings demonstrate that the proposed algorithm produces shorter, smoother, and more energy-efficient paths while significantly reducing computational cost. These advantages make it a promising candidate for large-scale, real-time robotic applications, with potential for further extension to three-dimensional environments.

کلیدواژه‌ها English

Real-Time Path Planning

Applied Geometry

Autonomous Robot

Optimization

[1] Madridano Á، Al-Kaff A، Martín D، de la Escalera A. Trajectory planning for multi-robot systems: Methods and applications. Expert Systems with Applications. 2021;173:114660.

[2] Aggarwal S، Kumar N. Path planning techniques for unmanned aerial vehicles: A review، solutions، and challenges. Computer Communications. 2020;149:270–99.

[3] Liu L، Wang X، Yang X، Liu H، Li J، Wang P. Path planning techniques for mobile robots: Review and prospect. Expert Systems with Applications. 2023;227:120254.

[4] Lei Z، Wang W، Zhu Z، Ma J، Ge SS. Safe Motion Planning for Multi-Vehicle Autonomous Driving in Uncertain Environment. IEEE Robotics and Automation Letters. 2025;10(3):2199–206.

[5] Hewawasam HS، Ibrahim MY، Appuhamillage GK. Past، Present and Future of Path-Planning Algorithms for Mobile Robot Navigation in Dynamic Environments. IEEE Open Journal of the Industrial Electronics Society. 2022;3:353–65.

[6] Amores D، Tanin E، Vasardani M. Flexible Paths: A Path Planning Approach to Dynamic Navigation. IEEE Transactions on Intelligent Transportation Systems. 2024;25(6):4795–808.

[7] Alarabi S، Santora M، editors. Review:Path Planning Techniques for Automated Guided Vehicles (AGVs). 2024 9th Asia-Pacific Conference on Intelligent Robot Systems (ACIRS); 2024 18–20 July 2024.

[8] Lin Z، Wu K، Shen R، Yu X، Huang S. An Efficient and Accurate A-Star Algorithm for Autonomous Vehicle Path Planning. IEEE Transactions on Vehicular Technology. 2024;73(6):9003–8.

[9] Yang C، Lin Z. Dictionary-Labeled A*: Optimal Path-and-Posture Planning for Mobile Robots With Turning Radius Constraints. IEEE Robotics and Automation Letters. 2024;9(12):10740–7.

[10] Vagale A، Bye RT، Oucheikh R، Osen OL، Fossen TI. Path planning and collision avoidance for autonomous surface vehicles II: a comparative study of algorithms. Journal of Marine Science and Technology. 2021;26(4):1307–23.

[11] Karur K، Sharma N، Dharmatti C، Siegel JE. A Survey of Path Planning Algorithms for Mobile Robots. Vehicles. 2021;3(3):448–68.

[12] Liu H، Wu G، Zhou L، Pedrycz W، Suganthan PN. Tangent-Based Path Planning for UAV in a 3-D Low Altitude Urban Environment. IEEE Transactions on Intelligent Transportation Systems. 2023;24(11):12062–77.

[13] Zafar MM، Anjum ML، Hussain W. LTA*: Local tangent based A* for optimal path planning. Autonomous Robots. 2021;45(2):209–27.

[14] Rashid A، Marhoon A، Yahia Z. An algorithm for Path planning with polygon obstacles avoidance based on the virtual circle tangents. Iraq Journal Electrical and Electronic Engineering. 2016;12:221.

[15] Zhang H، Xie X، Wei M، Wang X، Song D، Luo J، editors. An Improved Goal-bias RRT algorithm for Unmanned Aerial Vehicle Path Planning. 2024 IEEE International Conference on Mechatronics and Automation (ICMA); 2024 4–7 Aug. 2024.

[16] Kim M، Ahn J، Park J. TargetTree-RRT*: Continuous-Curvature Path Planning Algorithm for Autonomous Parking in Complex Environments. IEEE Transactions on Automation Science and Engineering. 2024;21(1):606–17.

[17] Tan CS، Mohd-Mokhtar R، Arshad MR. A Comprehensive Review of Coverage Path Planning in Robotics Using Classical and Heuristic Algorithms. IEEE Access. 2021;9:119310–42.

[18] Mahdavi F، Shamaghdari S. Optimal Formation Control for Unmanned Aerial Vehicle Teams with Collision Avoidance Constraint and Unknown Dynamics. Journal of Aerospace Mechanics. 2023;19(1):61–79. (In Persian)

[19] Rahman MA، Azad MAK. To Escape Local Minimum Problem for Multi-Agent Path Planning using Improved Artificial Potential Field-Based Regression Search Method. Proceedings of the 2017 International Conference on Information Technology; Singapore، Singapore: Association for Computing Machinery; 2017. p. 371–6.

[20] Vasudevan A، Kumar A، Theetharapan N، Bhuvaneswari NS، editors. Robot Operating System Based Path Planning. Intelligent Data Communication Technologies and Internet of Things; 2020 2020//; Cham: Springer International Publishing.

[21] Yue Y، Zhang D، Niu L، Zuo X. OPTIMAL PATH PLANNING METHOD FOR UAV BASED ON THE TANGENT POINT ALGORITHM IN URBAN ENVIRONMENT. International Journal of Innovative Computing، Information and Control.19:32.

[22] Zardashti R، Nikkhah AA، Yazdanpanah MJ. Considering Terrain Contour MatchingSystem Requirements in the TF/TA Based Constraint Optimal Trajectory Design for UAVs. Aerospace Mechanics Journal. 2017;12(4):25. (]n Persian)

[23] Radmanesh A، Radmanesh H، qorbani m، Mohamadhossein H. Six Degree of Freedom Simulation and Hybrid Guidance of Parafoil-Payload Systems Considering Wind and Terrain Constraints. Aerospace Mechanics. 2021;17(1):21–36. (]n Persian)

[24] Boyd S، Vandenberghe L. Convex Optimization. Cambridge: Cambridge University Press; 2004.