DOI: https://doi.org/10.1007/s00521-024-10945-1
تاريخ النشر: 2025-01-02
المؤلف: Thi Thuy Ngan Duong وآخرون
الموضوع الرئيسي: خوارزميات تخطيط المسار الروبوتي
نظرة عامة
تقدم البحث خوارزمية جديدة لتخطيط المسار في الطائرات بدون طيار (UAVs) تُسمى تحسين سرب الجسيمات متعدد الأهداف القائم على المتغيرات الملاحية (NMOPSO). تصوغ هذه الخوارزمية تخطيط المسار كمشكلة تحسين، مع تحديد مجموعة من الدوال الهدف التي تشمل كل من متطلبات الأمثلية والسلامة لعمليات الطائرات بدون طيار. تستخدم NMOPSO تمثيلًا فريدًا للمسار يستفيد من المتغيرات الملاحية لدمج القيود الحركية واستغلال قدرة المناورة للطائرة بدون طيار. بالإضافة إلى ذلك، تتميز بآلية طفرات تكيفية لتعزيز تنوع السرب، مما يؤدي إلى تحسين جودة الحلول.
تظهر التحليلات المقارنة أن NMOPSO تتفوق على مجموعة متنوعة من متغيرات تحسين سرب الجسيمات (PSO) وغيرها من خوارزميات تحسين متعددة الأهداف والمتاهيرستيك المتطورة عبر معايير متعددة، بما في ذلك طول المسار، والسلامة، والنعومة. علاوة على ذلك، تؤكد التجارب العملية التي أجريت مع طائرات بدون طيار حقيقية فعالية الخوارزمية، كما يتضح من التوافق بين المسارات المخطط لها والمسارات الفعلية. الشيفرة المصدرية لـ NMOPSO متاحة للجمهور، مما يسهل المزيد من البحث والتطبيق في تخطيط مسار الطائرات بدون طيار.
مقدمة
تتناول مقدمة هذه الورقة البحثية القضية الحرجة لتخطيط المسار للطائرات بدون طيار (UAVs)، مع التأكيد على الحاجة إلى مسارات طيران مثالية تقلل من معايير مثل المسافة واستهلاك الطاقة مع الالتزام بالقيود الحركية ومتطلبات السلامة. تستعرض هذه الفقرة تقنيات تخطيط المسار المختلفة، بما في ذلك A*، والحقول المحتملة الاصطناعية (APF)، والأساليب المعتمدة على العينة مثل الأشجار العشوائية المستكشفة بسرعة (RRT)، مع تسليط الضوء على نقاط قوتها وقيودها. من الجدير بالذكر أنه بينما يعد A* فعالًا في العثور على أقصر مسار، فإنه يواجه صعوبة في التوسع بسبب التقطيع، وRRT، على الرغم من قدرته على العثور على المسارات، لا يقوم بتحسين طول المسار بشكل جوهري.
تستكشف الورقة أيضًا تقنيات تحسين مستوحاة من الطبيعة، مثل تحسين سرب الجسيمات (PSO) والخوارزميات الجينية، التي اكتسبت زخمًا لقدرتها على تقديم حلول مثالية. ومع ذلك، تركز معظم الخوارزميات الحالية على تحسين هدف واحد، مما قد يؤدي إلى حلول دون المستوى الأمثل عندما تكون الأهداف متعددة. لمعالجة ذلك، يقترح المؤلفون خوارزمية جديدة تُسمى تحسين سرب الجسيمات متعدد الأهداف القائم على المتغيرات الملاحية (NMOPSO)، والتي تدمج قيود الحركة للطائرات بدون طيار وأهداف متعددة لتوليد مسارات Pareto-optimal. توضح المقدمة مساهمات الدراسة، بما في ذلك تطوير NMOPSO، وموصل طفرات تكيفي لتعزيز الأداء، وتطبيق خرائط نموذج الارتفاع الرقمي (DEM) الحقيقية للتقييم، مما يمهد الطريق للأقسام التالية من الورقة.
طرق
في هذا القسم، يوضح المؤلفون التحقق التجريبي من خوارزمية NMOPSO المقترحة لتوليد مسارات الطيران لطائرة بدون طيار، تحديدًا 3DR Solo. أُجريت التجارب في منطقة مسيطر عليها بمساحة 100 × 100 م²، تقع عند الإحداثيات (-33.876399، 151.192293)، والتي تضمنت أربعة عوائق. تم إدخال مواقع البداية والهدف للطائرة بدون طيار في خوارزمية NMOPSO المنفذة في MATLAB، مما أسفر عن مسار مخطط تم تمثيله بسلسلة من نقاط الطريق.
تم تحويل هذه النقاط لاحقًا إلى إحداثيات جغرافية وتحميلها إلى الطائرة بدون طيار عبر برنامج Mission Planner. أظهرت نتائج الطيران أن المسار المخطط (الموضح بخط أصفر) يتطابق بشكل وثيق مع المسار الفعلي للطيران (الموضح كخط بنفسجي)، مما يدل على جدوى المسار الذي تم إنشاؤه بواسطة NMOPSO. من المهم أن المسار لم يتقاطع مع دوائر التهديد المحددة، مما يؤكد سلامته لعمليات الطائرات بدون طيار. بشكل عام، تؤكد النتائج فعالية خوارزمية NMOPSO للتطبيقات العملية للطيران.
نتائج
تظهر نتائج الدراسة فعالية الخوارزمية المقترحة من خلال مقارنات وتجارب متنوعة. على وجه التحديد، تكشف نتائج تخطيط المسار للسيناريوهات 1 و4، الموضحة في الأشكال 5 و6، أن جميع المسارات المولدة خالية من التصادم وتصل بنجاح إلى مواقع الهدف المحددة. تظهر المسارات قابلية التكيف مع هيكل التضاريس؛ ومع ذلك، يتم تقليل التغيرات الحادة في الارتفاع بسبب القيود الحركية والنعومة المفروضة، مما يضمن أن المسارات قابلة للتنفيذ للطائرات بدون طيار (UAVs) لتتبعها.
بالإضافة إلى ذلك، من المهم ملاحظة أن المسارات المقدمة في الأشكال 5 و6 تمثل فقط مجموعة فرعية من الحلول غير المهيمنة العديدة التي حددتها الخوارزمية على جبهة Pareto. كل حل يتفوق في أهداف معينة، مما يشير إلى أن التفضيل لبعض الحلول غير المهيمنة قد يختلف بناءً على سياق التطبيق المحدد.
مناقشة
ت outlines قسم المناقشة في الورقة البحثية النموذج الحركي ودوال الهدف لتخطيط مسار الطائرات بدون طيار، مع التأكيد على دمج القيود الفيزيائية في عملية التحسين. يتم نمذجة الطائرة بدون طيار كنقطة في الفضاء، حيث تحكم حركتها المعادلات الحركية التي تأخذ في الاعتبار السرعة والزوايا، مع الالتزام بالحدود المحددة. يقترح المؤلفون أربع دوال هدف: تقليل طول المسار، وضمان تجنب التصادم، والحفاظ على ارتفاع طيران مستقر، وتحقيق النعومة في الطيران. تم صياغة كل دالة بعناية لتعكس متطلبات تشغيل الطائرة بدون طيار، مع تخصيص تكاليف محددة لمقاطع المسار بناءً على قربها من العوائق والانحرافات عن الارتفاع الأمثل.
لمعالجة التبادلات الكامنة بين هذه الأهداف، يستخدم المؤلفون نهج تحسين متعدد الأهداف، وتحديدًا خوارزمية تحسين سرب الجسيمات متعددة الأهداف الجديدة (NMOPSO). تسعى هذه الطريقة إلى تحديد الحلول المثلى Pareto، حيث لا يمكن تحسين هدف واحد دون المساس بآخر. تتضمن NMOPSO تحسينات مثل المتغيرات الملاحية وآلية الطفرات التكيفية لاستكشاف فضاء الحلول بفعالية وتجنب الحلول المحلية المثلى. تظهر النتائج أن NMOPSO تتفوق على متغيرات PSO التقليدية وغيرها من الخوارزميات المتاهيرستيك في توليد مسارات طائرات بدون طيار قابلة للتنفيذ وفعالة وآمنة، مما يبرز إمكانياتها للتطبيقات العملية في البيئات المعقدة.
DOI: https://doi.org/10.1007/s00521-024-10945-1
Publication Date: 2025-01-02
Author(s): Thi Thuy Ngan Duong et al.
Primary Topic: Robotic Path Planning Algorithms
Overview
The research introduces a novel algorithm for path planning in unmanned aerial vehicles (UAVs) called navigation variable-based multi-objective particle swarm optimization (NMOPSO). This algorithm formulates path planning as an optimization problem, defining a set of objective functions that encompass both optimality and safety requirements for UAV operations. NMOPSO employs a unique path representation utilizing navigation variables to incorporate kinematic constraints and leverage the UAV’s maneuverability. Additionally, it features an adaptive mutation mechanism to enhance swarm diversity, leading to improved solution quality.
Comparative analyses demonstrate that NMOPSO outperforms various particle swarm optimization (PSO) variants and other state-of-the-art multi-objective and metaheuristic optimization algorithms across multiple criteria, including path length, safety, and smoothness. Furthermore, practical experiments conducted with real UAVs validate the algorithm’s effectiveness, as evidenced by the alignment between planned and actual flight paths. The source code for NMOPSO is publicly available, facilitating further research and application in UAV path planning.
Introduction
The introduction of this research paper addresses the critical issue of path planning for unmanned aerial vehicles (UAVs), emphasizing the need for optimal flight paths that minimize criteria such as distance and energy consumption while adhering to kinematic constraints and safety requirements. The section reviews various path planning techniques, including A*, artificial potential fields (APF), and sampling-based methods like rapidly-exploring random trees (RRT), highlighting their strengths and limitations. Notably, while A* is effective for finding the shortest path, it struggles with scalability due to discretization, and RRT, although capable of finding paths, does not inherently optimize path length.
The paper further explores nature-inspired optimization techniques, such as particle swarm optimization (PSO) and genetic algorithms, which have gained traction for their ability to yield optimal solutions. However, most existing algorithms focus on single-objective optimization, which can lead to suboptimal solutions when multiple objectives are present. To address this, the authors propose a novel algorithm named navigation variable-based multi-objective PSO (NMOPSO), which incorporates UAV kinematic constraints and multiple objectives to generate Pareto-optimal paths. The introduction outlines the contributions of the study, including the development of NMOPSO, an adaptive mutation operator to enhance performance, and the application of real digital elevation model (DEM) maps for evaluation, setting the stage for the subsequent sections of the paper.
Methods
In this section, the authors detail the experimental validation of their proposed NMOPSO algorithm for generating flight paths for a UAV, specifically the 3DR Solo. The experiments were conducted in a controlled area measuring 100 × 100 m², located at coordinates (-33.876399, 151.192293), which included four obstacles. The UAV’s starting and goal locations were input into the NMOPSO algorithm implemented in MATLAB, resulting in a planned path represented by a series of waypoints.
These waypoints were subsequently converted to geographic coordinates and uploaded to the UAV via the Mission Planner software. The flight results illustrated that the planned path (depicted by a yellow line) closely matched the actual flight path (shown as a purple line), indicating the feasibility of the NMOPSO-generated path. Importantly, the flight path did not intersect with designated threat circles, confirming its safety for UAV operations. Overall, the findings validate the effectiveness of the NMOPSO algorithm for practical flight applications.
Results
The results of the study demonstrate the effectiveness of the proposed algorithm through various comparisons and experiments. Specifically, the path planning outcomes for scenarios 1 and 4, illustrated in Figures 5 and 6, reveal that all generated paths are collision-free and successfully reach their designated goal positions. The paths exhibit adaptability to the terrain structure; however, sharp altitude changes are minimized due to imposed kinematic and smoothness constraints, ensuring that the paths are feasible for unmanned aerial vehicles (UAVs) to follow.
Additionally, it is important to note that the paths presented in Figures 5 and 6 represent only a subset of the numerous non-dominated solutions identified on the Pareto Front by the algorithm. Each solution excels in specific objectives, indicating that the preference for certain non-dominated solutions may vary based on the particular application context.
Discussion
The discussion section of the research paper outlines the kinematic model and objective functions for UAV path planning, emphasizing the integration of physical constraints into the optimization process. The UAV is modeled as a point in space, with its motion governed by kinematic equations that account for velocity and angles, subject to defined limits. The authors propose four objective functions: minimizing path length, ensuring collision avoidance, maintaining stable flight altitude, and achieving smoothness in flight. Each function is carefully formulated to reflect the UAV’s operational requirements, with specific costs assigned to path segments based on their proximity to obstacles and deviations from optimal altitude.
To address the inherent trade-offs among these objectives, the authors employ a multi-objective optimization approach, specifically a novel multi-objective particle swarm optimization (NMOPSO) algorithm. This method seeks to identify Pareto-optimal solutions, where no single objective can be improved without compromising another. The NMOPSO incorporates enhancements such as navigation variables and an adaptive mutation mechanism to effectively explore the solution space and avoid local optima. The results demonstrate that NMOPSO outperforms traditional PSO variants and other metaheuristic algorithms in generating feasible, efficient, and safe UAV paths, showcasing its potential for practical applications in complex environments.