DOI: https://doi.org/10.1038/s41598-025-92675-5
PMID: https://pubmed.ncbi.nlm.nih.gov/40246857
تاريخ النشر: 2025-04-17
المؤلف: Zhenyun Du وآخرون
الموضوع الرئيسي: خوارزميات تخطيط المسار الروبوتي
نظرة عامة
تقدم ورقة البحث خوارزمية دمج استراتيجيات متعددة RRT (MSF-RRT)، المصممة لمعالجة قيود أشجار البحث العشوائي التقليدية (RRT) في تخطيط المسار، بما في ذلك مشكلات العمى في البحث، والعشوائية العالية، وبطء التقارب، والمسارات غير السلسة. تتضمن خوارزمية MSF-RRT عدة استراتيجيات: استراتيجية انحياز الهدف التي تزيد من احتمال أخذ عينات النقاط في منطقة الهدف، واستراتيجية توسيع الانحياز لتوسيع النقاط بشكل منظم نحو النقاط المستهدفة، واستراتيجية حجم الخطوة التكيفية التي تعدل خطوة التوسع بناءً على تعقيد الخريطة. بالإضافة إلى ذلك، تستخدم الخوارزمية عملية تقليم ومنحنيات B-spline مكعبة لتحسين المسار.
تظهر نتائج المحاكاة أن خوارزمية MSF-RRT تتفوق بشكل كبير على خوارزميات RRT التقليدية وRRT-Star وRRT-Connect، محققة تخفيضات متوسطة في وقت البحث (90.53%)، وطول المسار (16.84%)، وعدد العقد (88.43%) مقارنة بـ RRT، بالإضافة إلى تحسينات كبيرة على الخوارزميات الأخرى. تشير النتائج إلى أن خوارزمية MSF-RRT لا تعزز فقط الكفاءة والأداء في تخطيط المسار ولكنها تتماشى أيضًا بشكل أفضل مع الخصائص الحركية للمهمة. ومع ذلك، يشير المؤلفون إلى أن ظاهرة “رانج” قد تحدث في بعض البيئات المعقدة، مما يشير إلى الحاجة إلى مزيد من التحقيق في طرق تركيب المنحنيات البديلة لتعزيز الدقة والاستقرار في تخطيط المسار.
النتائج
تظهر نتائج تجارب المحاكاة الأداء المتفوق لخوارزمية MSF-RRT المقترحة مقارنة بخوارزميات تخطيط المسار التقليدية، بما في ذلك RRT وRRT-Star وRRT-Connect. تقلل خوارزمية MSF-RRT بشكل كبير من وقت البحث عن المسار بنسبة 91.04% إلى 88.85% مقارنة بـ RRT التقليدية، و76.31% إلى 79.86% مقارنة بـ RRT-Star، و50.44% إلى 42.30% مقارنة بـ RRT-Connect عبر بيئات مختلفة. بالإضافة إلى ذلك، فإن أطوال المسارات التي تنتجها خوارزمية MSF-RRT أقصر، مع تخفيضات تتراوح بين 20.24% إلى 14.96% مقارنة بـ RRT، و14.96% إلى 11.90% مقارنة بـ RRT-Star، و18.94% إلى 15.42% مقارنة بـ RRT-Connect. كما أن عدد عقد المسار أقل بكثير، مع تخفيضات تتراوح بين 88.15% إلى 86.63% مقارنة بـ RRT، و75.78% إلى 77.18% مقارنة بـ RRT-Star، و67.06% إلى 64.29% مقارنة بـ RRT-Connect.
تشير النتائج إلى أن خوارزمية MSF-RRT تقلل بشكل فعال من العشوائية في عمليات البحث عن المسار مع الحفاظ على الكفاءة والاستقرار عبر مستويات تعقيد مختلفة. تقترح الورقة تطبيقات هندسية عملية حيث يمكن للمستخدمين ضبط معلمات الخوارزمية ديناميكيًا بناءً على تعقيد البيئة لتحسين الأداء. تشمل التوصيات زيادة أخذ عينات انحياز الهدف في البيئات المعقدة واستخدام تقنيات الحوسبة المتوازية لتعزيز سرعة التنفيذ. يتم التأكيد على موثوقية الخوارزمية، داعيًا إلى تقييمات متكررة لضمان الدقة والقابلية للتنبؤ في التطبيقات الواقعية. بشكل عام، بينما تظهر خوارزمية MSF-RRT قدرات قوية، فإن التقييم الدقيق والتحسين ضروريان لتلبية الاحتياجات الهندسية المتنوعة.
المناقشة
تتناول قسم المناقشة في ورقة البحث التحسينات التي تم إدخالها على خوارزمية شجرة البحث العشوائي التقليدية (RRT) لتخطيط المسار. تقوم خوارزمية RRT التقليدية بأخذ عينات تدريجية للنقاط في مساحة البحث، موسعة شجرة من نقطة البداية إلى نقطة الهدف. ومع ذلك، تعاني من عدم الكفاءة بسبب نهج أخذ العينات العشوائي العالمي، مما قد يؤدي إلى عمليات بحث عمياء. لمعالجة ذلك، تقدم الورقة استراتيجية انحياز الهدف، التي تتضمن آلية احتمالية لتفضيل أخذ العينات بالقرب من نقطة الهدف، مما يقلل من العمى في البحث ويحسن الكفاءة. يتم تحقيق ذلك من خلال دالة تسمى GBRandomFree، التي تعدل طريقة أخذ العينات بناءً على معدل أخذ عينات مستهدف محدد مسبقًا.
تتم تحسينات إضافية من خلال استراتيجية توسيع الانحياز، التي توجه نمو الشجرة نحو كل من العقدة الجديدة ونقطة الهدف، مما يوضح اتجاه التوسع ويقلل من العشوائية. تعزز إدخال استراتيجية حجم الخطوة التكيفية من قدرة الخوارزمية على التكيف مع تعقيدات الخرائط المتغيرة، مما يسمح بتعديلات ديناميكية لحجم الخطوة بناءً على كثافة العقبات والمسافة إلى الهدف. لا تعزز هذه المرونة من تسريع التقارب فحسب، بل تقلل أيضًا من خطر الاصطدامات. أخيرًا، تناقش الورقة تقنيات تحسين المسار، بما في ذلك تقليم المسار وتنعيمه، التي تبسط المسارات الناتجة من خلال إزالة العقد غير الضرورية وتقليل الشوائب، مما يعزز في النهاية الكفاءة الحسابية وجودة المسار. تساهم هذه الاستراتيجيات مجتمعة في خوارزمية تخطيط مسار أكثر فعالية وقوة.
DOI: https://doi.org/10.1038/s41598-025-92675-5
PMID: https://pubmed.ncbi.nlm.nih.gov/40246857
Publication Date: 2025-04-17
Author(s): Zhenyun Du et al.
Primary Topic: Robotic Path Planning Algorithms
Overview
The research paper introduces the Multi-Strategy Fusion RRT (MSF-RRT) algorithm, designed to address the limitations of traditional Rapidly-exploring Random Trees (RRT) in path planning, including issues of search blindness, high randomness, slow convergence, and non-smooth paths. The MSF-RRT algorithm incorporates several strategies: a target bias strategy that increases the likelihood of sampling points in the target region, a bias expansion strategy for orderly point expansion towards target points, and an adaptive step size strategy that adjusts the expansion step based on map complexity. Additionally, the algorithm employs a pruning process and cubic B-spline curves for path optimization.
Simulation results demonstrate that the MSF-RRT algorithm significantly outperforms traditional RRT, RRT-Star, and RRT-Connect algorithms, achieving average reductions in search time (90.53%), path length (16.84%), and number of nodes (88.43%) compared to RRT, as well as substantial improvements over the other two algorithms. The findings indicate that the MSF-RRT algorithm not only enhances efficiency and performance in path planning but also aligns better with the kinematic properties of the task. However, the authors note that the phenomenon of “Runge” may still occur in certain complex environments, suggesting a need for further investigation into alternative curve fitting methods to enhance accuracy and stability in path planning.
Results
The results of the simulation experiments demonstrate the superior performance of the proposed MSF-RRT algorithm compared to traditional path-planning algorithms, including RRT, RRT-Star, and RRT-Connect. The MSF-RRT algorithm significantly reduces path search time by 91.04% to 88.85% against the traditional RRT, 76.31% to 79.86% against RRT-Star, and 50.44% to 42.30% against RRT-Connect across various environments. Additionally, the path lengths generated by the MSF-RRT algorithm are shorter, with reductions of 20.24% to 14.96% compared to RRT, 14.96% to 11.90% against RRT-Star, and 18.94% to 15.42% against RRT-Connect. The number of path nodes is also significantly lower, with reductions of 88.15% to 86.63% compared to RRT, 75.78% to 77.18% against RRT-Star, and 67.06% to 64.29% against RRT-Connect.
The findings indicate that the MSF-RRT algorithm effectively minimizes randomness in path searches while maintaining efficiency and stability across different complexity levels. The paper suggests practical engineering applications where users can dynamically adjust algorithm parameters based on environmental complexity to optimize performance. Recommendations include increasing target bias sampling in complex environments and employing parallel computing techniques to enhance execution speed. The reliability of the algorithm is emphasized, advocating for repeated assessments to ensure accuracy and predictability in real-world applications. Overall, while the MSF-RRT algorithm shows strong capabilities, careful evaluation and optimization are necessary for diverse engineering needs.
Discussion
The discussion section of the research paper elaborates on the enhancements made to the traditional Rapidly-exploring Random Tree (RRT) algorithm for path planning. The traditional RRT algorithm incrementally samples points in a search space, expanding a tree from a starting point to a goal point. However, it suffers from inefficiencies due to its global random sampling approach, which can lead to blind searches. To address this, the paper introduces a Target Bias strategy, which incorporates a probabilistic mechanism to favor sampling near the target point, thereby reducing search blindness and improving efficiency. This is achieved through a function called GBRandomFree, which adjusts the sampling method based on a predefined target sampling rate.
Further improvements are made through the Bias Expansion strategy, which directs the growth of the tree towards both the new node and the target point, effectively clarifying the expansion direction and minimizing randomness. The introduction of an adaptive step size strategy enhances the algorithm’s adaptability to varying map complexities, allowing for dynamic adjustments of the step size based on obstacle density and the distance to the target. This flexibility not only accelerates convergence but also mitigates the risk of collisions. Lastly, the paper discusses path optimization techniques, including path pruning and smoothing, which streamline the generated paths by removing unnecessary nodes and reducing irregularities, ultimately enhancing computational efficiency and path quality. These strategies collectively contribute to a more effective and robust path planning algorithm.