روبوتمقالات

خوارزمية الخنفساء Tangent Bug Algorithm

أحد خوارزميات تخطيط حركة الروبوتات التلقائي

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

ما نسعى له في هذه المقالة والمقالة القادمة هو شرح للخوارزمية تدعى خوارزمية الخنفساء Tangent Bug Algorithm وتطبيقها باستخدام محاكي في نظام تشغل الروبوت ROS كما هو موضح في الصورة لروبوت يتحرك من غرفة لأخرى تلقائياً.

صياغة المشكلة

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

tangent-bug-map
الخط الأزرق الغير المنقطع هو ما يراه الروبوت
الخطوط السود المتقطعة هي البيئة المحيطة بالروبوت
النقطة الحمراء هي النقطة التي يريد الروبوت الذهاب إليها

تمهيد

قبل البدء بالتفاصيل العمليّة سنتعرف على بعض المفاهيم التي ستستخدم خلال المقال

  • المسافة الإقليدية بين نقطتين q1=(x1, y1), q2=(x2, y2)

$latex d(x, y) =\sqrt{(x2 – x1)^{2} + (y2 -y1)^{2}}$

  • الخوارزمية تفترض بأن باستطاعة الروبوت اكتشاف القيم المتقطعة كما هو موضح في الشكل التالي
tangent-bug-map-sensor
قيم الحساس بالنسبة لكل زاوية للحساس 3.14, -3.14 راديان
  •  
  • التقطع هو قفزة مفاجئة في قيم الحساس، في الحالة السابقة يوجد ثلاث قفزات سنطلق على نقاط التقطع بنقاط النهاية ونرمز لهم بـ $latex O_{i}$ . مجموعة النقاط بين نقاط النهاية هي مجال الاستمرارية.


  • الخطوط النحيفة هي قيم حساس المسافة، الخطوط السميكة تشير إلى التقطع في القيمة
  • النقاط O1, O2, O3, O4, O5, O6, O7, O8 هي أمثلة لنقط النهاية،مجموعة النقاط الغامقة ذات اللون الأسود بين O1 و O2، O3و O4،O5 و O6،O7و O8 هي أمثلة عن مجالات الاستمرارية
  • R هي القيمة العظمى التي يستطيع الحساس الاستشعار فيها.
  • ما هي خوارزمية الخنفساء؟

    إن خوارزمية الخنفساء تستخدم سلوكين وهما:

    1. السير نحو الهدف
    2. السير بجهة الحدود

    ما سيقوم الروبوت بفعله هو أن يستدعي أولا سلوك السير نحو الهدف والذي يتألف من قسمين:

    1- الروبوت يسعى للسير في خط مستقيم باتجاه الهدف إلى أن يستشعر عقبة بمسافة R وتكون بشكل مباشر بينه وبين الهدف، والقصد بالشكل المباشر  بأن الخط المستقيم الذي يصل الروبوت بالهدف يجب أن يقطع إحدى مجالات الاستمرارية

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

    2- لنأخذ بعين الاعتبار النقاط  $latex O_{i}$ بحيث تكون $latex d(Oi, q_{goal}) < d(x, q_{goal})$،فإن الروبوت سوف يسير نحو النقطة التي تعطينا أقل قيمة للدالة الإرشادية

    $latex d(x, O_{i}) + d(O_{i}, q_{goal})$

    أحد الأمثلة للدالة الإرشادية

    أمثلة:

    النقطة O4 هي النقطة المصغرة(التي تعطي أصغر قيمة
    للدالة الإرشادية) للدالة الإرشادية
    النقطة O2 هي النقطة المصغرة للدالة الإرشادية

    يتم تحديث المجموعة $latex O_{i}$ باستمرار بينما يتحرك الروبوت بإتجاه نقطة $latex O_{i}$ معينة

    عند الوقت t = 1 لم يستشعر الروبوت بوجود أي حاجز، لذلك الروبوت سوف يسير باتجاه الهدف.
    عند الوقت t = 2الروبوت استشعر بوجود حاجز (موضح منحنى سميك)، الروبوت سوف يستمر بالسير نحو الهدف، ولكن إلى جانب الحاجز.
    في كلا الوقتين t = 3 و t = 4 يستشعر الروبوت الحاجز أكثر وسيستمر بتقليل المسافة نحو الهدف بينما يسير بمحاذاة حدود الحاجز.

    سيستمر الروبوت باستدعاء سلوك السير نحو الهدف إلى ألا يستطيع تقليل الدالة الإرشادية للهدف حينها سينتقل لسلوك السير بجهة الحدود.


    النقطة Mهي النقطة ذات القيمة المحلية الأدنى للدالة الإرشادية، الخط المنقط يعبر عن مسار الروبوت في سلوك السير بجهة الحدود

    عندما ينتقل الروبوت لسلوك السير بجهة الحدود، سيحدد نقطة على المنطقة المستشعرة حاليا من الحاجز التي لديها أقل مسافة للهدف، سنطلق على هذه النقطة “النقطة المتبعة”، وسنطلق على النقطة التي تسد الروبوت مباشرة عن الهدف بـ”نقطة الحجب”، في البداية تكون نقطة الحجب هي نفسها النقطة المتبعة.

    النقطة 1 هي نقطة حجب
    النقطة 2 هي نقطة متبعة

    الروبوت سيسير باستمرار باتجاه الحدود، بينما يسير الروبوت سيقوم بتحديث قيمتين $latex d_{followed}$ و $latex d_{reach} $ حيث:

    • $latex d_{reach}$  هي أقصر مسافة بين الهدف و أي نقطة في البيئة المستشعرة.
    • $latex d_{followed}$ هي أقصر مسافة لاحظها الروبوت أثناء السير بين الهدف و حدود العقبة المستشعرة.
    طول الخط المستقيم رقم 1 هو $latex d_{reach} $
    طول الخط المستقيم رقم 2 هو latex d_{followed}$

    عند عدم وجود حاجز يحجب الروبوت عن الهدف، وسنعرّف النقطة T لتكون نقطة تقاطع الدائرة ذات نصف القطر R و مركز x والخط الواصل بين x و $latex q_{goal}$، لذلك عند عدم وجود حاجز:

    $latex dreach=d(T, q_{goal})$

    ماعدا ذلك تكون T غير معرفة وبالتالي $latex d_{reach}$ هي أقصر مسافة بين الهدف وأي نقطة على الحاجز المستشعر

    تعريف النقطة T

    عندما تصبح $latex d_{reach} < d_{followed}$ الروبوت سيتوقف عن سلوك السير بجهة الحدود، وينتقل الى سلوك السير نحو الهدف مجددا.

    إذا دار الروبوت حول العائق بأكمله بدون تحقق الشرط $latex d_{reach} < d_{followed}$ عندها يكون الهدف غير قابل للوصول.

    مثال توضيحي كامل عن الخوارزمية

    وفي المخطط الصندوقي التالي ملخصاً عن مراحل الخوارزمية

    ملخص الخوارزمية

    الجزء الثاني من المقال سيكون عن محاكاة الروبوت وكتابة اكواد باستخدام نظام الـROS لجعل الروبوت يصل للهدف باستخدام خوارزمية الخنفساء.

    لمزيد من المعلومات وللتعرّف على ROS يرجى الاطلاع على مجموعة الدورس المنشورة حولها

    قائمة المصطلحات

    قائمة المصطلحات *
    المسافة الإقليديةEuclidean distance
    القيم المتقطعةDiscontinuities
    مجال استمراريةInterval of continuity
    نقاط النهايةEndpoints
    الدالة الإرشاديةHeuristic function
    النقطة المتبعةFollowed obstacle
    نقطة الحجبFollowed obstacle
    *بعض المصطلحات لم تترجم حرفياً

    المراجع

    1. Principles of Robot Motion: Theory, Algorithms, and Implementation
    2. http://autorob.org/

    Jafar Abdi

    يدرس هندسة الميكاترونيكس ومهتم في علم الروبوتات وتحديداً نظام تشغيل الروبوت ROS ويطمح للمساعدة في إثراء المحتوى العربي.

    اترك تعليقاً

    لن يتم نشر عنوان بريدك الإلكتروني.

    هذا الموقع يستخدم Akismet للحدّ من التعليقات المزعجة والغير مرغوبة. تعرّف على كيفية معالجة بيانات تعليقك.

    زر الذهاب إلى الأعلى