بعض من أهم التحديات التي تواجه الروبوتات ذاتية التحكم تكمن في مجال تخطيط الحركة التلقائي، وتتمثل المهمة النموذجية في العثور على مسار للروبوت، سواء كان ذراعًا آليًا أو روبوتًا متحركًا، من موضع لآخر مع تجنب العقبات. في هذا المقال سنتكلم عن خوارزمية الخنفساء وهي إحدى خوارزميات تخطيط المسار في البيئات الغير معروفة التي تحدد المسار للهدف باستخدام حساس المسافة 360 درجة.
ما نسعى له في هذه المقالة والمقالة القادمة هو شرح للخوارزمية تدعى خوارزمية الخنفساء Tangent Bug Algorithm وتطبيقها باستخدام محاكي في نظام تشغل الروبوت ROS كما هو موضح في الصورة لروبوت يتحرك من غرفة لأخرى تلقائياً.
صياغة المشكلة
ليكن لدينا البيئة الموضحة في الصورة التالية، حيث البيئة غير معروفة للروبوت والشيء الوحيد المعروف لدى الروبوت هو قيم الحساس وموقعه الحالي. المطلوب من الروبوت الذهاب للنقطة الحمراء من دون الاصطدام بأي عائق.
الخطوط السود المتقطعة هي البيئة المحيطة بالروبوت
النقطة الحمراء هي النقطة التي يريد الروبوت الذهاب إليها
تمهيد
قبل البدء بالتفاصيل العمليّة سنتعرف على بعض المفاهيم التي ستستخدم خلال المقال
- المسافة الإقليدية بين نقطتين q1=(x1, y1), q2=(x2, y2)
- الخوارزمية تفترض بأن باستطاعة الروبوت اكتشاف القيم المتقطعة كما هو موضح في الشكل التالي
الخطوط النحيفة هي قيم حساس المسافة، الخطوط السميكة تشير إلى التقطع في القيمة
ما هي خوارزمية الخنفساء؟
إن خوارزمية الخنفساء تستخدم سلوكين وهما:
- السير نحو الهدف
- السير بجهة الحدود
ما سيقوم الروبوت بفعله هو أن يستدعي أولا سلوك السير نحو الهدف والذي يتألف من قسمين:
1- الروبوت يسعى للسير في خط مستقيم باتجاه الهدف إلى أن يستشعر عقبة بمسافة R وتكون بشكل مباشر بينه وبين الهدف، والقصد بالشكل المباشر بأن الخط المستقيم الذي يصل الروبوت بالهدف يجب أن يقطع إحدى مجالات الاستمرارية
الآن، في اللحظة التي يستشعر الروبوت بوجود عقبة، ستشكل الدائرة التي نصف قطرها R مماساً للعقبة، وبعد ذلك النقطة المماسة ستنقسم لنقطتي نهاية وبينهما مجال استمرارية، إذا كانت العقبة أمام الروبوت فإن مجال الاستمرارية يتقاطع مع الخط الذي يصل الروبوت بالهدف.
2- لنأخذ بعين الاعتبار النقاط
|
أحد الأمثلة للدالة الإرشادية |
أمثلة:
النقطة O4 هي النقطة المصغرة(التي تعطي أصغر قيمة للدالة الإرشادية) للدالة الإرشادية | النقطة O2 هي النقطة المصغرة للدالة الإرشادية |
يتم تحديث المجموعة
عند الوقت t = 2الروبوت استشعر بوجود حاجز (موضح منحنى سميك)، الروبوت سوف يستمر بالسير نحو الهدف، ولكن إلى جانب الحاجز.
في كلا الوقتين t = 3 و t = 4 يستشعر الروبوت الحاجز أكثر وسيستمر بتقليل المسافة نحو الهدف بينما يسير بمحاذاة حدود الحاجز.
سيستمر الروبوت باستدعاء سلوك السير نحو الهدف إلى ألا يستطيع تقليل الدالة الإرشادية للهدف حينها سينتقل لسلوك السير بجهة الحدود.
النقطة Mهي النقطة ذات القيمة المحلية الأدنى للدالة الإرشادية، الخط المنقط يعبر عن مسار الروبوت في سلوك السير بجهة الحدود
عندما ينتقل الروبوت لسلوك السير بجهة الحدود، سيحدد نقطة على المنطقة المستشعرة حاليا من الحاجز التي لديها أقل مسافة للهدف، سنطلق على هذه النقطة “النقطة المتبعة”، وسنطلق على النقطة التي تسد الروبوت مباشرة عن الهدف بـ”نقطة الحجب”، في البداية تكون نقطة الحجب هي نفسها النقطة المتبعة.
النقطة 2 هي نقطة متبعة
الروبوت سيسير باستمرار باتجاه الحدود، بينما يسير الروبوت سيقوم بتحديث قيمتين
هي أقصر مسافة بين الهدف و أي نقطة في البيئة المستشعرة. هي أقصر مسافة لاحظها الروبوت أثناء السير بين الهدف و حدود العقبة المستشعرة.
طول الخط المستقيم رقم 2 هو latex d_{followed}$
عند عدم وجود حاجز يحجب الروبوت عن الهدف، وسنعرّف النقطة T لتكون نقطة تقاطع الدائرة ذات نصف القطر R و مركز x والخط الواصل بين x و
ماعدا ذلك تكون T غير معرفة وبالتالي
عندما تصبح
إذا دار الروبوت حول العائق بأكمله بدون تحقق الشرط
وفي المخطط الصندوقي التالي ملخصاً عن مراحل الخوارزمية
الجزء الثاني من المقال سيكون عن محاكاة الروبوت وكتابة اكواد باستخدام نظام الـ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/