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

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

Jafar Uruç17th نوفمبر 2018

0 3 دقائق

بعض من أهم التحديات التي تواجه الروبوتات ذاتية التحكم تكمن في مجال تخطيط الحركة التلقائي، وتتمثل المهمة النموذجية في العثور على مسار للروبوت، سواء كان ذراعًا آليًا أو روبوتًا متحركًا، من موضع لآخر مع تجنب العقبات. في هذا المقال سنتكلم عن خوارزمية الخنفساء وهي إحدى خوارزميات تخطيط المسار في البيئات الغير معروفة التي تحدد المسار للهدف باستخدام حساس المسافة 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- الروبوت يسعى للسير في خط مستقيم باتجاه الهدف إلى أن يستشعر عقبة بمسافة R وتكون بشكل مباشر بينه وبين الهدف، والقصد بالشكل المباشر بأن الخط المستقيم الذي يصل الروبوت بالهدف يجب أن يقطع إحدى مجالات الاستمرارية

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

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

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

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

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

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

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

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

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

المراجع

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

Jafar Uruç17th نوفمبر 2018

0 3 دقائق

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

تمهيد

ما هي خوارزمية الخنفساء؟

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

المراجع

Jafar Uruç

كل ما يتعلق بـ ESP32 - الجزء الرابع 4

مقدمة عن واجهة rosserial_arduino

اترك تعليقاً إلغاء الرد