💻 computer science

Distributed Lloyd-Based algorithm for uncertainty-aware multi-robot under-canopy flocking

تقدم هذه الورقة خوارزمية موزعة ومدركة لعدم اليقين تتيح التوافق الجماعي لعدة روبوتات عند ارتفاع ثابت في بيئات معقدة تحت مظلة الأشجار باستخدام الاستشعار على متن الروبوت فقط، مع ضمان تجنب الاصطدام والحفاظ على التقارب دون معرفة مسبقة بالبيئة أو اتصالات صريحة.

المؤلفون الأصليون: Manuel Boldrer, Vit Kratky, Viktor Walter, Martin Saska

نُشر 2026-03-02

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Manuel Boldrer, Vit Kratky, Viktor Walter, Martin Saska

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل سرباً من الطيور يحلق عبر غابة كثيفة يملؤها الضباب. إنهم لا يستخدمون أجهزة اللاسلكي للتحدث مع بعضهم البعض، ولا يملكون خريطة GPS للأشجار، ولا يمكنهم رؤية الغابة بأكملها في وقت واحد. ومع ذلك، فإنهم ينجحون في الطيران معاً كمجموعة، ويتجنبون الاصطدام بالأغصان، ولا يفقدون أبداً رؤية أصدقائهم.

تصف هذه الورقة برنامجاً حاسوبياً (خوارزمية) يعلّم الروبوتات القيام بذلك تماماً. إليك تفصيل كيفية عمله، باستخدام تشبيهات بسيطة.

المشكلة الكبرى: الطيران في عماء وسط الزحام

عادةً، عندما يكون لديك مجموعة من الطائرات بدون طيار (الروبوتات)، فأنت بحاجة لأن تتواصل مع بعضها البعض لتبقى آمنة. "أنا أتحرك يساراً!" "حسناً، سأتحرك يميناً!". لكن في غابة كثيفة، يمكن للأشجار والأوراق أن تحجب إشارات الراديو. كما أن الروبوتات قد لا تملك خريطة مثالية لمواقع الأشجار.

أراد المؤلفون إنشاء نظام حيث:

لا يوجد حديث: الروبوتات لا تتبادل الرسائل.
لا توجد خرائط: لا يعرفون تخطيط الغابة مسبقاً.
لا توجد أخطاء: يتعاملون مع الحالات التي تكون فيها مستشعراتهم غير دقيقة أو إذا انحرفوا عن مسارهم.
البقاء معاً: يجب عليهم الحفاظ على مسافة محددة من "أصدقائهم" (التشكيل الجماعي) دون الاصطدام.

الحل: استراتيجية "الفقاعة الشخصية"

الفكرة الجوهرية تعتمد على ما يسمى بـ خوارزمية لويد (Lloyd Algorithm). فكر في هذا الأمر كأنه لعبة "الكرة الساخنة" التي تُلعَب بفقاعات غير مرئية.

1. الفقاعات غير المرئية (خلايا فورونوي - Voronoi Cells)
تخيل أن كل روبوت يرسم فقاعة غير مرئية حول نفسه. تمثل هذه الفقاعة "مساحته الشخصية".

إذا اقتربت شجرة، تتقلص الفقاعة من ذلك الجانب لتجنب الشجرة.
إذا اقترب صديق، تتقلص الفقاعة لتجنبه.
هدف الروبوت هو التحرك إلى المركز الدقيق (المركز الهندسي أو "centroid") لفقاعته الخاصة.

2. قاعدة "التشكيل الجماعي" (Flocking Rule)
عادةً، إذا طارد الروبوت مجرد مركز فقاعته، فقد يبتعد عن المجموعة ويتركها. ولحل هذه المشكلة، أضاف المؤلفون قاعدة: "لا يمكن لفقاعتك أن تبتعد كثيراً عن فقاعات أصدقائك."
الأمر يشبه مجموعة من الأصدقاء يسيرون في سوق مزدحم وهم يمسكون بأيدي بعضهم عبر حبال مطاطية غير مرئية. إذا ابتعدت، ستسحبك الحبال للخلف، لكنك لا تزال قادراً على اختيار مسارك الخاص.

3. "هامش الأمان" (التعامل مع الأخطاء)
هذا هو الجزء الأكثر ذكاءً. الروبوتات ليست مثالية؛ فقد تخبر مستشعراتها أن الشجرة تبعد 5 أمتار، بينما هي في الواقع تبعد 4.8 متر. أو قد يظن الروبوت أنه يتحرك في خط مستقيم، لكن الرياح تدفعه جانباً.

الطريقة القديمة: إذا خططت مسارك بدقة عند حافة الأمان، فإن خطأً صغيراً واحداً سيؤدي إلى اصطدام.
طريقة هذه الورقة: يقوم الروبوت عمداً بجعل "فقاعته الشخصية" أصغر والبقاء بعيداً عن الحواف. الأمر يشبه القيادة مع هامش أمان كبير. إذا ظن الروبوت أن الشجرة تبعد 5 أمتار، فإنه يتصرف كما لو كانت الشجرة تبعد 6 أمتار. هذا "الهامش الأماني" يضمن أنه حتى لو أخطأ الروبوت في تقدير مكان الأشياء، فإنه لن يصطدم بها.

كيف اختبروا ذلك؟

لم يكتف الفريق بتشغيل هذا النظام على جهاز كمبيوتر فحسب، بل قاموا فعلياً بتحليق أربع طائرات بدون طيار حقيقية في غابة كثيفة في جمهورية التشيك.

الإعداد: لم تكن هناك إشارة GPS في الغابة. كان على الطائرات الاعتماد على الكاميرات والليزر لرؤية الأشجار والطائرات الأخرى.
النتيجة: حلقت الطائرات عبر الأشجار، وتجنبت الأغصان، وبقيت قريبة من بعضها البعض (مثل سرب الطيور)، ووصلت إلى وجهتها دون تصادم أو تواصل فيما بينها.

لماذا هذا مهم؟

فكر في هذا كتعليم سرب من النحل كيفية التنقل وسط عاصفة دون وجود ملكة تقودهم.

القابلية للتوسع: يمكنك إضافة 10 طائرات أو 100 طائرة، وسوف يجد الجميع طريقهم بأنفسهم.
المتانة: إذا تعطل مستشعر إحدى الطائرات، فلن تصطدم بها الطائرات الأخرى لأن الجميع يحافظ على "منطقة أمان" فاصلة.
الاستخدام في العالم الحقيقي: هذا مثالي لمهام البحث والإنقاذ في مناطق الكوارث (حيث تنقطع الاتصالات) أو لمراقبة الغابات والمحاصيل حيث لا تريد الاعتماد على بنية تحتية مكلفة.

باختصار: لقد توصل المؤلفون إلى كيفية جعل مجموعة من الروبوتات تتصرف مثل سرب طيور ذكي ومتماسك، حتى عندما يكونون "عميان"، أو يعانون من ضجيج في البيانات، أو محاطين بالعقبات، وذلك من خلال منح كل روبوت "مساحة شخصية آمنة" تتعدل تلقائياً للحفاظ على تماسك الجميع وسلامتهم.

إليك ملخص تقني مفصل للورقة البحثية بعنوان: "خوارزمية لويد الموزعة للتحليق الجماعي متعدد الروبوتات الواعي بالشك (Uncertainty-aware) تحت غطاء الأشجار."

1. بيان المشكلة

تتناول الورقة البحثية تحدي تنسيق سرب من الطائرات بدون طيار (UAVs) في بيئات كثيفة، غير منظمة، ومزدحمة (تحديداً الغابات) تحت قيود صارمة:

لا يوجد اتصال صريح: لا يمكن للروبوتات تبادل البيانات (المواقع، السرعات، المسارات) مع بعضها البعض.
لا يوجد تحديد موقع عالمي: يعمل النظام بدون نظام تحديد المواقع العالمي (GNSS) أو إطار مرجعي مشترك؛ حيث تعتمد الروبوتات فقط على المستشعرات الموجودة على متنها.
قيود التحليق الجماعي (Flocking): يجب على الروبوتات الحفاظ على القرب من جيران محددين (الحفاظ على التقارب) أثناء الانتقال إلى منطقة الهدف.
التعامل مع الشك (Uncertainty): يجب أن يتعامل النظام مع أخطاء التتبع المحدودة (بسبب الديناميكيات) وعدم اليقين في القياس (بسبب ضجيج المستشعرات).
السلامة: يجب ضمان تجنب الاصطدام بكل من العوائق الثابتة والروبوتات الديناميكية الأخرى في جميع الأوقات.

تتمثل المشكلة الجوهرية في ابتكار قانون تحكم موزع يضمن وصول السرب إلى هدف ما، ويحافظ على تماسك التحليق الجماعي، ويضمن السلامة رغم هذه القيود والشكوك.

2. المنهجية

الحل المقترح هو خوارزمية لويد موزعة (Distributed Lloyd-based algorithm) معززة باستراتيجيات تكيفية للتعامل مع حالات الشك.

أ. الإطار الأساسي: مخططات فورونوي الموزونة المحدبة (CWVD)

تستند الخوارية إلى خوارزمية لويد، التي تقلل دالة تكلفة التغطية. يستخدم المؤلفون مخططات فورونوي الموزونة المحدبة (CWVD) لتقسيم مساحة المهمة لكل روبوت بناءً على:

جيران الروبوت ( $V^p_i$ ): يتم تحديدهم عبر المواقع النسبية للروبوتات القريبة.
العوائق ( $V^o_i$ ): يتم تحديدهم عبر القرب من العوائق.
معلمات الوزن ( $\epsilon_p, \epsilon_o$ ): تنظم هذه المعلمات درجة "الحذر". حيث تعني $\epsilon=1$ سلوكاً هجومياً، بينما تعني $\epsilon=2$ (فورونوي الكلاسيكي) سلوكاً متحفظاً.

ب. إعادة تشكيل هندسة الخلية من أجل السلامة والتحليق الجماعي

لضمان السلامة والتحليق الجماعي، يتم إعادة تشكيل خلية فورونوي القياسية $V_i$ إلى خلية نهائية $F_i$ من خلال التقاطع:

إعادة تشكيل السلامة ( $A_i$ ): يتم تعديل الخلية لضمان أن المسار المستقيم من موقع الروبوت الحالي إلى مركز الخلية خالٍ من الاصطدام. يتضمن ذلك توسيع النصف قطر الفعال للروبوتات والعوائق بأبعادها الفيزيائية ( $\delta$ ).
إعادة تشكيل التحليق الجماعي ( $M_i$ ): يتم تقييد الخلية بشكل أكبر بواسطة مجموعة تقارب $M_i$ ، مما يضمن بقاء الروبوت ضمن مسافة قصوى $\Gamma_{ij}$ من جيرانه المحددين.
الخلية النهائية ( $F_i = \tilde{V}^p_i \cap \tilde{V}^o_i \cap S_i \cap M_i$ ): يتحرك الروبوت نحو مركز هذه المجموعة المحدبة النهائية.

ج. دالة الوزن التكيفية ( $\phi_i(q)$ )

للتعامل مع أخطاء التتبع وعدم اليقين في القياس، قدم المؤلفون دالة وزن تكيفية $\phi_i(q)$ ممركزة عند هدف افتراضي $\bar{p}_i$ .

الآلية: يتم التحكم في "انتشار" دالة الوزن بواسطة المعلمة $\beta_i$ .
قاعدة التكيف: يتم ضبط $\beta_i$ عبر الإنترنت (online). تجعل $\beta_i$ الأصغر الروبوت أكثر هجومية (المركز أقرب إلى حدود الخلية)، بينما تجعل $\beta_i$ الأكبر الروبوت أكثر تحفظاً (المركز أبعد عن الحدود).
التعويض عن الشك: تحسب الخوارزمية مسافة أمان دنيا $d_u$ (مجموع خطأ التتبع $d^t_u$ وعدم اليقين في القياس $d^m_u$ ). وهي تفرض حداً أدنى لـ $\beta_i$ ( $\beta_{min}$ ) لضمان بقاء المركز $c_{F_i}$ على مسافة لا تقل عن $d_u$ من حدود الخلية $\partial F_i$ . هذا يخلق "هامش سلامة" يستوعب الأخطاء المحتملة دون انتهاك قيود الاصطدام أو التحليق الجماعي.

د. تنفيذ التحكم

الديناميكيات: يتم تنفيذ قانون التحكم عبر التحكم التنبئي بالنماذج (MPC) للتعامل مع الديناميكيات غير الهولونومية للطائرات بدون طيار.
المستشعرات: يعتمد النظام على IMU، وليدر (Lidar) ثنائي الأبعاد، مستشعرات الارتفاع، وتقنية UVDAR (تحديد الاتجاه والمدى بالأشعة فوق البفولتية) لتحديد الموقع النسبي للجيران.

3. المساهمات الرئيسية

خوارزمية موزعة مبتكرة: متحكم قائم على لويد يعمل بدون اتصال صريح أو تحديد موقع عالمي، وهو مناسب لبيئات الغابات الكثيفة.
ضمانات نظرية: توفر الورقة شروطاً كافية (النظرية 1 و2) لضمان:
- تجنب الاصطدام بالعوائق والروبوتات الأخرى رياضياً.
- الحفاظ على قيود التحليق الجماعي (التقارب).
- المتانة تجاه أخطاء التتبع المحدودة وعدم اليقين في القياس.
التعامل التكيفي مع الشك: استراتيجية فريدة تستخدم المعلمة التكيفية $\beta_i$ لتعديل "عدوانية" الروبوت ديناميكياً بناءً على تقديرات الخطأ في الوقت الفعلي، مما يضمن السلامة دون الحاجة إلى إعادة تشكيل هندسة الخلية ديناميكياً (والذي قد يؤدي إلى حالات غير معرفة).
التحقق الشامل: تم التحقق من النهج من خلال محاكاة مكثفة وتجارب واقعية في غابة كثيفة باستخدام ما يصل إلى 4 طائرات بدون طيار، مما أظهر العمل بدون GNSS أو التقاط حركة خارجي.

4. النتائج

نتائج المحاكاة

القابلية للتوسع: تم الاختبار مع 9 و16 روبوتاً في بيئات مزدحمة.
المتانة: عندما تم ضبط هامش الشك ( $d_u$ ) عند 0، كان النظام أسرع ولكنه عانى من اصطدامات. وعندما تم ضبط $d_u$ وفقاً للحدود النظرية (1.0 متر)، حقق النظام نسبة نجاح 100% في تجنب الاصطدام والحفاظ على التحليق الجماعي.
المقارنة: بالمقارنة مع PACNav (وهي خوارزمية متطورة لا تعتمد على الاتصال)، تفوقت الطريقة المقترحة بشكل كبير على PACNav في السيناريوهات المعقدة (مثل 9 روبوتات)، حيث فشلت PACNav في التقارب أو الحفاظ على السلامة (نسبة نجاح 0% في بعض السيناريوهات الكثيفة)، بينما حافظت الطريقة المقترحة على نسبة نجاح 100%.

النتائج التجريبية (الغابة الواقعية)

الإعداد: 4 طائرات بدون طيار تتنقل لمسافة 40 متراً عبر غابة كثيفة بدون GNSS.
الأداء: وصلت جميع الطائرات الأربع بنجاح إلى منطقة الهدف.
المقاييس:
- تراوحت متوسط السرعات بين 0.33 إلى 0.37 م/ث.
- إجمالي وقت المهمة: حوالي 150-175 ثانية.
- السلامة والتحليق الجماعي: ظلت المسافة بين الروبوتات ضمن قيود السلامة والتحليق الجماعي المحددة طوال المهمة، رغم وجود ضجيج عالٍ في القياس وحالات حجب من الأشجار.
- التعامل مع الأخطاء: تم استخدام استراتيجيات عملية (استبعاد القياسات ذات الشك العالي وإعادة إسقاط المواقع) بنجاح للتعامل مع حالات فشل المستشعرات المؤقتة الناتجة عن حجب الأشجار.

5. الأهمية

يمثل هذا العمل خطوة كبيرة للأمام في الأنظمة متعددة الروبوتات ذاتية القيادة للتطبيقات الواقعية:

الاستقلالية التشغيلية: يثبت أنه يمكن تحقيق سلوكيات تحليق جماعي معقدة دون الاعتماد على شبكات اتصال هشة أو بنية تحتية خارجية (مثل التقاط الحركة أو GNSS)، وهو أمر بالغ الأهمية للاستجابة للكوارث، والبحث والإنقاذ، والمراقبة الزراعية في المناطق النائية.
التصميم المرتكز على السلامة: على عكس العديد من النهج التجريبية، يوفر هذا الأسلوب ضمانات رياضية صارمة للسلامة والتقارب، مما يجعله مناسباً للنشر في البيئات المأهولة بالسكان أو شديدة الازدحام.
الوعي بالشك: إن التكامل الصريح لأخطاء التتبع والقياس في معلمات التحكم ( $\beta$ ) يقدم إطاراً قوياً للعمل مع مستشعرات غير مثالية، وهو واقع شائع في الروبوتات الميدانية.
المصدر المفتوح: يوفر المؤلفون كوداً مفتوح المصدر وعروض فيديو، مما يسهل إعادة الإنتاج ومزيد من الأبحاث في مجال الروبوتات الموزعة.

القيود: يقتصر التنفيذ الحالي على الحركة المستوية ثنائية الأبعاد (ارتفاع ثابت). ويهدف العمل المستقبلي إلى توسيع الخوارزمية لتشمل الحركة ثلاثية الأبعاد وتحسين الرشاقة.