DOI: https://doi.org/10.1038/s41598-026-36066-4
PMID: https://pubmed.ncbi.nlm.nih.gov/41580457
تاريخ النشر: 2026-01-24
المؤلف: Xinshi Zhang وآخرون
الموضوع الرئيسي: خوارزميات تخطيط المسار الروبوتي
نظرة عامة
تقدم البحث DASA*، وهو تحسين واعٍ بالاتجاه وقابل للتكيف للغرض التقليدي A*، يهدف إلى معالجة قيوده في البيئات ثلاثية الأبعاد المعقدة. يقدم الإطار المقترح آلية اختيار حيّ واعٍ بالاتجاه هرمية قابلة للتكيف، تستخدم كاشف ركود خفيف الوزن لتسهيل التبديل التلقائي بين زوايا مخروطية ضيقة وتغطية كاملة لـ 26 حيّ. تحل هذه الابتكار مشكلة عدم اكتمال البحث في خوارزميات A* الاتجاهية ذات الزاوية الثابتة، مما يحسن كفاءة التخطيط ومعدلات النجاح.
بالإضافة إلى ذلك، يتضمن DASA* استراتيجية بحث قابلة للتكيف مع الدقة التي تعدل ديناميكيًا دقة التخطيط بناءً على كثافة العقبات المحلية، مما يحسن كلاً من الكفاءة والسلامة في البيئات غير المتجانسة. يتميز الإطار أيضًا بواجهة مكونة هيكليًا قابلة للتعلم لدمج نماذج تحسين السياسة القريبة (PPO)، مما يعزز التوجيه الهيكلي لتحقيق بحث أكثر فعالية. تبسط استراتيجية تعديل المسار المتأخرة المسارات من خلال إزالة نقاط الطريق الزائدة وتطبيق تداخل B-spline مكعب للحصول على مسارات أكثر سلاسة. تظهر النتائج التجريبية أن DASA* يتفوق على A* التقليدي وخوارزميات أخرى رائجة عبر مقاييس متعددة، بما في ذلك وقت التخطيط، طول المسار، ومعدل النجاح، مما يثبت عمليته للتطبيقات الواقعية مثل تنقل الطائرات بدون طيار والروبوتات المتنقلة. ستركز الأعمال المستقبلية على تحسين كفاءة ودقة الخوارزمية في البيئات الديناميكية.
مقدمة
في المقدمة، يبرز البحث القيمة الكبيرة للطائرات بدون طيار (UAVs) في تطبيقات متنوعة، بما في ذلك مراقبة البيئة، الاستجابة للكوارث، اللوجستيات الحضرية، والاستطلاع العسكري. تعتمد فعالية عمليات الطائرات بدون طيار بشكل كبير على تقنية تخطيط المسار، والتي تُؤطر كمشكلة تحسين متعددة الأهداف. يتضمن ذلك تحقيق التوازن بين عوامل متعددة مثل السلامة، التوقيت، تجنب العقبات، استهلاك الطاقة، ومسافة الطيران، خاصة في سياق المدن الذكية حيث يكون تدفق المرور الفعال والنقل أمرًا حاسمًا.
يقوم المؤلفون بتصنيف طرق تخطيط المسار الحالية إلى أربع مجموعات رئيسية: الخوارزميات التقليدية (مثل خوارزمية ديكسترا، A*، الحقل المحتمل الاصطناعي، وشجرة الاستكشاف العشوائية السريعة)، خوارزميات تحسين ذكاء السكان (مثل تحسين مستعمرة النمل، تحسين سرب الجسيمات، وبحث الدُعاء)، الخوارزميات التطورية (مثل الخوارزمية الجينية والتطور التفاضلي)، وخوارزميات التعلم التعزيزي. لكل فئة نقاط قوتها وقيودها، خاصة في البيئات المعقدة. على سبيل المثال، بينما تكون الخوارزميات التقليدية قوية نظريًا، إلا أنها تواجه صعوبات في الفضاءات عالية الأبعاد. على العكس، أظهرت الأساليب الهجينة، مثل تلك التي تجمع بين الخوارزميات الجينية مع تحسين مستعمرة النمل، وعدًا في معالجة تحديات تخطيط المسار التعاوني. تمهد المقدمة الطريق لاستكشاف خوارزميات متقدمة يمكن أن تعزز كفاءة وسلامة تخطيط مسار الطائرات بدون طيار في البيئات الحضرية الديناميكية.
نقاش
في هذا القسم، يناقش المؤلفون التقدم في خوارزميات تخطيط المسار، مع التركيز بشكل خاص على قيود الطرق التقليدية مثل A* وتقديم خوارزمية DASA* المقترحة. يبرزون مجموعة متنوعة من الأساليب الحالية، مثل خوارزمية التعلم Q لأساطيل الطائرات بدون طيار والتحسينات على A* من خلال الهيكليات الديناميكية، لكنهم يلاحظون التحديات الشائعة مثل الحمل الحسابي وعدم الكفاءة في البيئات المعقدة. تعالج خوارزمية DASA* هذه القضايا من خلال تنفيذ آلية اختيار حيّ واعٍ بالاتجاه هرمية قابلة للتكيف، والتي تحسن عملية البحث من خلال تقليل الاستكشافات غير الضرورية وتعزيز الكفاءة الحسابية.
تتضمن خوارزمية DASA* واجهة هيكلية قابلة للتعلم تعتمد على تحسين السياسة القريبة (PPO)، مما يسمح بسلوك بحث ذكي يتكيف مع ميزات البيئة. بالإضافة إلى ذلك، يتم استخدام استراتيجية تعديل المسار لتبسيط المسارات وتعزيز السلاسة من خلال كشف التصادم وطرق التداخل. تظهر النتائج التجريبية أن DASA* يتفوق بشكل كبير على A* التقليدي وخوارزميات أخرى من حيث طول المسار، وقت التخطيط، وعدد العقد الموسعة، محققًا توازنًا بين الكفاءة والامتياز. بشكل عام، تؤكد النتائج على قوة الخوارزمية وقدرتها على التكيف في البيئات المعقدة، مما يمثل تحسينًا كبيرًا في منهجيات تخطيط المسار.
DOI: https://doi.org/10.1038/s41598-026-36066-4
PMID: https://pubmed.ncbi.nlm.nih.gov/41580457
Publication Date: 2026-01-24
Author(s): Xinshi Zhang et al.
Primary Topic: Robotic Path Planning Algorithms
Overview
The research presents DASA*, a direction-aware and self-adaptive enhancement of the traditional A* algorithm, aimed at addressing its limitations in complex 3D environments. The proposed framework introduces an adaptive hierarchical direction-aware neighborhood selection mechanism, which utilizes a lightweight stagnation detector to facilitate automatic switching between narrow conical angles and full 26-neighborhood coverage. This innovation resolves the search incompleteness of conventional fixed-cone-angle directional A* algorithms, thereby improving planning efficiency and success rates.
Additionally, DASA* incorporates a resolution-adaptive search strategy that dynamically adjusts planning granularity based on local obstacle density, optimizing both efficiency and safety in heterogeneous environments. The framework also features a learnable heuristic plugin interface for integrating Proximal Policy Optimization (PPO) models, enhancing heuristic guidance for more effective pathfinding. A delayed path adjustment strategy simplifies trajectories by removing redundant waypoints and applying cubic B-spline interpolation for smoother paths. Experimental results demonstrate that DASA* outperforms traditional A* and other mainstream algorithms across multiple metrics, including planning time, path length, and success rate, establishing its practicality for real-world applications such as UAV navigation and mobile robotics. Future work will focus on improving the algorithm’s efficiency and accuracy in dynamic environments.
Introduction
In the introduction, the paper highlights the significant value of Unmanned Aerial Vehicles (UAVs) in various applications, including environmental monitoring, disaster response, urban logistics, and military reconnaissance. The effectiveness of UAV operations heavily relies on path planning technology, which is framed as a multi-objective optimization problem. This involves balancing multiple factors such as safety, timeliness, obstacle avoidance, energy consumption, and flight distance, particularly in the context of smart cities where efficient traffic flow and transportation are critical.
The authors categorize existing path planning methods into four main groups: traditional algorithms (e.g., Dijkstra’s, A*, Artificial Potential Field, and Rapidly-exploring Random Tree), population intelligence optimization algorithms (e.g., Ant Colony Optimization, Particle Swarm Optimization, and Cuckoo Search), evolutionary algorithms (e.g., Genetic Algorithm and Differential Evolution), and reinforcement learning algorithms. Each category has its strengths and limitations, particularly in complex environments. For instance, while traditional algorithms are theoretically robust, they struggle in high-dimensional spaces. Conversely, hybrid approaches, such as those combining genetic algorithms with ant colony optimization, have shown promise in addressing cooperative path planning challenges. The introduction sets the stage for exploring advanced algorithms that can enhance UAV path planning efficiency and safety in dynamic urban settings.
Discussion
In this section, the authors discuss advancements in path planning algorithms, particularly focusing on the limitations of traditional methods like A* and the introduction of their proposed Direction-Aware and Self-Adaptive A* (DASA*) algorithm. They highlight various existing approaches, such as the Q-Learning algorithm for UAV swarms and improvements to A* through dynamic heuristics, but note common challenges like computational overhead and inefficiencies in complex environments. The DASA* algorithm addresses these issues by implementing an adaptive hierarchical direction-aware neighborhood selection mechanism, which optimizes the search process by reducing unnecessary explorations and enhancing computational efficiency.
The DASA* algorithm incorporates a learning heuristic interface based on Proximal Policy Optimization (PPO), allowing for intelligent search behavior that adapts to environmental features. Additionally, a path adjustment strategy is employed to simplify paths and enhance smoothness through collision detection and interpolation methods. Experimental results demonstrate that DASA* significantly outperforms traditional A* and other algorithms in terms of path length, planning time, and the number of expanded nodes, achieving a balance between efficiency and optimality. Overall, the findings underscore the algorithm’s robustness and adaptability in complex environments, marking a substantial improvement in path planning methodologies.