DOI: https://doi.org/10.19139/soic-2310-5070-3259
تاريخ النشر: 2026-01-04
المؤلف: Souhail Dhouib وآخرون
الموضوع الرئيسي: خوارزميات تخطيط المسار الروبوتي
نظرة عامة
تناقش هذه القسم أهمية تخطيط المسار في الروبوتات المتنقلة، مع التأكيد على هدف العثور على أقصر مسار ممكن من نقطة البداية إلى الهدف مع تجنب العقبات. تم استخدام طريقة تحسين سرب الجسيمات (PSO) بشكل شائع لهذا الغرض، لكنها تواجه تحديات مثل التعقيد الحسابي العالي، والحساسية لضبط المعلمات، والركود عند الأمثل المحلية. لمعالجة هذه القضايا، تم تقديم طريقة دهيب-ماتريكس-SPP (DM-SPP) الجديدة، التي تتميز بسرعة تنفيذها، وبساطتها، وغياب تعديلات المعلمات.
تظهر التجارب المحاكاة التي أجريت على دراسات حالة متنوعة (بيئات على شكل I، وU، وT، وأشكال عشوائية) أن DM-SPP تتفوق بشكل كبير على كل من تحسين سرب الجسيمات المرتب (rPSO) وتحسين سرب الجسيمات القائم على الحقل المحتمل الاصطناعي (apfrPSO) من حيث الكفاءة الحسابية، حيث كانت أسرع بـ 66 مرة من rPSO و31 مرة أسرع من apfrPSO. تشير النتائج إلى أن DM-SPP هي حل قوي وقابل للتوسع لتخطيط مسار الروبوتات المتنقلة، خاصة في البيئات الثابتة حيث تكون التقييمات السريعة للجدوى ضرورية. ومع ذلك، يشير المؤلفون إلى أنه في السيناريوهات الأكثر تعقيدًا أو الديناميكية، قد لا تزال طرق PSO التقليدية توفر مزايا، مما يشير إلى الحاجة إلى مزيد من البحث في تحسين الأهداف المتعددة، وتنعيم المسارات، ومجالات الحل ثلاثية الأبعاد.
مقدمة
تؤكد مقدمة هذه الورقة البحثية على الأهمية المتزايدة لتخطيط المسار في مجال الروبوتات المتنقلة المستقلة، التي تُستخدم بشكل متزايد في تطبيقات متنوعة مثل استكشاف الفضاء، والحقول الطبية، والعمليات الصناعية. يهدف تخطيط المسار إلى إنشاء طرق آمنة وخالية من التصادم من نقطة البداية إلى الوجهة في بيئات مليئة بالعقبات. تسلط الورقة الضوء على ضرورة عمل الروبوتات بشكل مستقل، والتكيف مع البيئات الديناميكية، واتخاذ قرارات سريعة دون تدخل بشري، مما يعزز السلامة والكفاءة في مختلف الصناعات.
يناقش المؤلفون تطور منهجيات تخطيط المسار، وخاصة ظهور الخوارزميات الاستدلالية بسبب قدرتها على إنتاج حلول قريبة من الأمثل بسرعة. تُلاحظ الأساليب التقليدية الميتاheuristic، بما في ذلك الخوارزميات الجينية (GA)، وتحسين سرب الجسيمات (PSO)، وتحسين مستعمرة النمل (ACO)، لمزاياها وقيودها المميزة. تقدم الورقة طريقة دهيب-ماتريكس-SPP (DM-SPP)، المصممة لحل مشكلة أقصر مسار في بيئات الشبكة بكفاءة، مع التركيز على سرعتها الحسابية وموثوقيتها. تظهر التجارب المقارنة فعالية DM-SPP مقابل طرق PSO، مع التركيز على جودة الحل وسرعة الدقة، مما يبرز إمكانية تطبيقها في السيناريوهات الواقعية. ستتناول الأقسام التالية من الورقة مبادئ PSO، وتفاصيل طريقة DM-SPP، وتقديم النتائج التجريبية والمناقشات.
النتائج
يقدم قسم النتائج تحليلًا مقارنًا لطريقة DM-SPP المقترحة مقابل اثنين من الميتاheuristics المستندة إلى تحسين سرب الجسيمات (PSO) الحديثة: تحسين سرب الجسيمات المرتب (rPSO) وتحسين سرب الجسيمات القائم على الحقل المحتمل الاصطناعي (apfrPSO). تم تنفيذ طريقة DM-SPP في بايثون واختبارها على جهاز كمبيوتر محمول من Dell مزود بمعالج Intel Core i7-1255U وذاكرة وصول عشوائي سعتها 16 جيجابايت. استخدمت التقييمات، التي تعتمد على الوقت الحسابي، وطول المسار، والجهد الخوارزمي (عدد التكرارات)، أربعة بيئات مرجعية – على شكل I، وU، وT، وأشكال عشوائية – تم اختيارها لتنوع تعقيدها الهيكلي وأهميتها في الدراسات السابقة.
تشير النتائج إلى أن DM-SPP تفوقت باستمرار على الطرق المنافسة عبر جميع السيناريوهات المرجعية، مما يبرز مزاياها الحتمية والخالية من المعلمات مقارنة بالأساليب التقليدية المستندة إلى السكان. تؤكد هذه الأداء على فعالية DM-SPP في حل مشاكل التحسين المعقدة، مما يشير إلى إمكانياتها لتطبيقات أوسع في هذا المجال.
المناقشة
تتناول قسم المناقشة في الورقة خوارزمية تحسين سرب الجسيمات (PSO)، التي تم تطويرها في الأصل بواسطة كينيدي وإيبرهارت في عام 1995، والتي تحاكي السلوكيات الاجتماعية في الطبيعة لتحسين الحلول. تعمل PSO مع مجموعة من الجسيمات التي تقوم بتحديث مواقعها وسرعاتها بناءً على أفضل الحلول الفردية والاجتماعية، مما يسمح لها باستكشاف مساحات البحث المعقدة بشكل فعال. على الرغم من مزاياها، تواجه PSO تحديات مثل الوقوع في الحد الأدنى المحلي والطلبات الحسابية العالية، مما دفع الباحثين إلى تطوير متغيرات هجينة وتكيفية لتعزيز أدائها في سيناريوهات التحسين المختلفة.
في المقابل، تم تقديم طريقة دهيب-ماتريكس لمشكلة أقصر مسار (DM-SPP) كخوارزمية جديدة خالية من المعلمات تحسب المسارات الأقصر بكفاءة مع تعقيد زمني قدره \(O(n + m)\). تتفوق DM-SPP بشكل كبير على المتغيرات المتقدمة من PSO، مثل PSO المرتب (rPSO) وPSO القائم على الحقل المحتمل الاصطناعي (apfrPSO)، من حيث السرعة الحسابية والموثوقية عبر بيئات اختبار متعددة (على شكل I، وU، وT، وأشكال عشوائية). تشير النتائج إلى أن DM-SPP يمكن أن تولد حلولًا أسرع حتى 83 مرة من rPSO و42 مرة أسرع من apfrPSO، مما يجعلها مناسبة بشكل خاص للتطبيقات في الوقت الحقيقي في الروبوتات المتنقلة حيث تكون اتخاذ القرارات السريعة أمرًا حاسمًا. ومع ذلك، فإن DM-SPP محدودة بالبيئات المنفصلة، مما يتطلب مزيدًا من البحث لتكييفها مع السيناريوهات المستمرة واستكشاف تحسين الأهداف المتعددة.
DOI: https://doi.org/10.19139/soic-2310-5070-3259
Publication Date: 2026-01-04
Author(s): Souhail Dhouib et al.
Primary Topic: Robotic Path Planning Algorithms
Overview
The section discusses the significance of path planning in mobile robotics, emphasizing the goal of finding the shortest feasible trajectory from a starting point to a target while avoiding obstacles. The Particle Swarm Optimization (PSO) method has been commonly used for this purpose, but it faces challenges such as high computational complexity, sensitivity to parameter tuning, and stagnation at local optima. To address these issues, the novel Dhouib-Matrix-SPP (DM-SPP) method is introduced, which is characterized by its rapid execution, simplicity, and lack of parameter adjustments.
Simulation experiments conducted on various case studies (I-shaped, U-shaped, T-shaped, and randomly shaped environments) demonstrate that DM-SPP significantly outperforms both the ranking Particle Swarm Optimization (rPSO) and the artificial potential field-based Particle Swarm Optimization (apfrPSO) in terms of computational efficiency, being 66 times faster than rPSO and 31 times faster than apfrPSO. The findings suggest that DM-SPP is a robust and scalable solution for mobile robot path planning, particularly in static environments where rapid feasibility assessments are crucial. However, the authors note that in more complex or dynamic scenarios, traditional PSO methods may still provide advantages, indicating a need for future research into multi-objective optimization, trajectory smoothing, and three-dimensional resolution domains.
Introduction
The introduction of this research paper emphasizes the growing significance of path planning in the realm of autonomous mobile robots, which are increasingly utilized across diverse applications such as space exploration, medical fields, and industrial operations. Path planning aims to establish safe, collision-free routes from a starting point to a destination in environments laden with obstacles. The paper highlights the necessity for robots to operate autonomously, adapt to dynamic environments, and make rapid decisions without human intervention, thereby enhancing safety and efficiency in various industries.
The authors discuss the evolution of path planning methodologies, particularly the rise of heuristic algorithms due to their ability to yield near-optimal solutions quickly. Traditional metaheuristic approaches, including Genetic Algorithms (GA), Particle Swarm Optimization (PSO), and Ant Colony Optimization (ACO), are noted for their distinct advantages and limitations. The paper introduces the Dhouib-Matrix-SPP (DM-SPP) method, which is designed to efficiently solve the shortest path problem in grid environments, emphasizing its computational speed and reliability. Comparative experiments demonstrate DM-SPP’s effectiveness against PSO methods, focusing on both solution quality and resolution speed, thereby underscoring its potential applicability in real-world scenarios. The subsequent sections of the paper will elaborate on the principles of PSO, detail the DM-SPP method, and present experimental results and discussions.
Results
The results section presents a comparative analysis of the proposed DM-SPP method against two recent Particle Swarm Optimization (PSO)-based metaheuristics: ranking Particle Swarm Optimization (rPSO) and artificial potential field-based Particle Swarm Optimization (apfrPSO). The DM-SPP method was implemented in Python and tested on a Dell laptop with an Intel Core i7-1255U processor and 16 GB RAM. The evaluation, based on computational time, path length, and algorithmic effort (iteration count), utilized four benchmark environments— I-shaped, U-shaped, T-shaped, and randomly shaped—chosen for their varying structural complexities and relevance in prior studies.
The findings indicate that DM-SPP consistently outperformed the competing methods across all benchmark scenarios, highlighting its deterministic and parameter-free advantages over traditional population-based metaheuristics. This performance underscores the effectiveness of DM-SPP in solving complex optimization problems, suggesting its potential for broader applications in the field.
Discussion
The discussion section of the paper elaborates on the Particle Swarm Optimization (PSO) metaheuristic, originally developed by Kennedy and Eberhart in 1995, which simulates social behaviors in nature to optimize solutions. PSO operates with a population of particles that update their positions and velocities based on individual and social bests, allowing it to explore complex search spaces effectively. Despite its advantages, PSO faces challenges such as local minima entrapment and high computational demands, prompting researchers to develop hybrid and adaptive variants to enhance its performance in various optimization scenarios.
In contrast, the Dhouib-Matrix Shortest Path Problem (DM-SPP) method is introduced as a novel, parameter-free algorithm that efficiently computes shortest paths with a time complexity of \(O(n + m)\). DM-SPP significantly outperforms advanced PSO variants, such as ranking PSO (rPSO) and artificial potential field-based PSO (apfrPSO), in terms of computational speed and reliability across multiple test environments (I-shaped, U-shaped, T-shaped, and randomly shaped). The results indicate that DM-SPP can generate solutions up to 83 times faster than rPSO and 42 times faster than apfrPSO, making it particularly suitable for real-time applications in mobile robotics where rapid decision-making is crucial. However, DM-SPP is limited to discrete environments, necessitating further research to adapt it for continuous scenarios and explore multi-objective optimization.