روبوتمقالات

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

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

 

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

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

 

 

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

 

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

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

 

تمهيد

 

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

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

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

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

    الخطوط النحيفة هي قيم حساس المسافة، الخطوط السميكة تشير إلى التقطع في القيمة

     

  • سنطلق على نقاط التقطع بنقاط النهاية ونرمز لهم بـ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- لنأخذ بعين الاعتبار النقاط  O_{i} بحيث تكون d(Oi, q_{goal}) < d(x, q_{goal})،فإن الروبوت سوف يسير نحو النقطة التي تعطينا أقل قيمة للدالة الإرشادية

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

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

أمثلة:

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

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

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

 

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

 


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

 

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

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

 

 

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

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

 

طول الخط المستقيم رقم 1 هو d_{reach}
طول الخط المستقيم رقم 2 هو latex d_{followed}$

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

dreach=d(T, q_{goal})

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

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

 

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

إذا دار الروبوت حول العائق بأكمله بدون تحقق الشرط 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 للحدّ من التعليقات المزعجة والغير مرغوبة. تعرّف على كيفية معالجة بيانات تعليقك.