Robomobiles بدون سائق توصيل البيتزا. سيارات الأجرة بدون سائق تحمل الناس. الشاحنات بدون سائق تحمل حمولات متعددة الأطنان. إذا قمنا بتحليل كل هذه المشاريع الرائعة ، فسوف نصل إلى مهام نموذجية مختلفة ، وأهمها البحث عن الطرق وتحسينها. يتم حل هذه المشاكل باستخدام
نظرية الرسم البياني . هذا الموضوع ليس بسيطًا ، حيث يتم دراسته بشكل رئيسي في الجامعة أو على الأقل في الفصول المتخصصة العليا. ولكن في هذا المنشور ، سأوضح كيفية استخدام LEGO EV3 لتعلم نظرية الرسم البياني بالفعل في المدرسة الثانوية. وبدون حشر ، ولكن على مستوى تطبيق رائع.
داني LAB EV3 ناقل السيارات يجمع حقا سيارات LEGO. لكن الأمر لا يتعلق به قليلاً.لكي يصل النقل بدون طيار إلى حيث هو مطلوب ، يجب أن يكون قادرًا على بناء طريق بين النقاط المحددة. أقصر ومتسق مع قواعد المرور أمر مرغوب فيه. لمحاكاة هذه المشكلة وحلها ، نحتاج إلى منصة LEGO EV3 المحمولة ، وفي الواقع ، الخريطة التي ستنتقل إليها هذه المنصة.
LEGO EV3 منصة متنقلة
يجب أن تكون منصة الهاتف المحمول لدينا مجهزة بأجهزة استشعار وأجهزة. يمكن العثور على كل ما تحتاجه في المجموعة التعليمية الأساسية من LEGO Mindstorms EV3 45544. إليك ما تبدو عليه المنصة:
لا يتطلب التجميع معرفة بالالكترونيات ولا يستغرق أكثر من نصف ساعة. تحتوي المنصة على كل ما تحتاجه للارتقاء إلى مستوى عالٍ من التجريد في حل مشكلة.
خارطة الطريق
لنرسم خريطة طريق على شكل شبكة. الخطوط هي الطرق ونقاط التقاطع هي تقاطعات الطرق:
جميع أجزاء الطريق بين التقاطعات متساوية الطول ، وحركة المرور عليها ذات اتجاهين. يتم حظر بعض الطرق - ويتم تمييزها بـ "لبنة". بالإضافة إلى ذلك ، فإن جميع المنعطفات على خريطتنا مضاعفات 90 درجة. لن يؤثر تعقيد شبكة الطرق على مبدأ حل المشكلة ، وللوضوح ، سنفعل بخيار بسيط إلى حد ما. مهمتنا هي القيادة من النقطة A إلى النقطة B حول أقصر مسار.
العد
لكل تقاطع إحداثياته الخاصة - أرقام الخطوط الأفقية والرأسية. في نظرية الرسم البياني ، تسمى هذه التقاطعات
القمم . يشار إلى الطرق بين التقاطعات بالسهام. في نظرية الرسم البياني ، هذه
حواف . جميع الطرق ذات اتجاهين (الأسهم في كلا الاتجاهين) تعني أن الرسم البياني
غير موجه . التكلفة (وقت السفر) هي نفسها لجميع أقسام الطريق ، مما يعني أن الرسم البياني غير
مرجح .
مصفوفة المجاورة
يوضح الرسم البياني الذي تمثله الصورة بوضوح الخريطة والروابط الموجودة بداخلها. ولكن على الكمبيوتر - بما في ذلك EV3 - من الصعب معالجة المعلومات الرسومية. من الأفضل ترميز رسم بياني بمصفوفة ، مصفوفة مجاورة.
إذا لم يكن هناك اتصال مباشر بين التقاطعات ، نضع 0. إذا كان هناك - 1. إذا كان هناك - 1. اتفقنا على أن جميع المسافات بين التقاطعات المتجاورة تساوي 1. إذا كان الرسم البياني مرجحًا ، فبدلاً من الوحدة عند كل تقاطع سنضع " وزن "المؤامرة. وإذا تم أخذ اتجاه الحركة في الاعتبار ، فإن المصفوفة أعلاه ستكون غير متماثلة - في اتجاه واحد يمكن أن يكون 1 ، وفي الآخر 0.
باستخدام مصفوفة مجاورة ، يمكن للروبوت لدينا بالفعل حل المشكلة - ابحث عن أقصر مسار من أ إلى ب. ولكن لدينا مصفوفة ثنائية الأبعاد ، وفي EV3 فقط يمكن تخزين صفائف أحادية البعد. يمكننا بسهولة الانتقال إلى صفيف أحادي البعد من خلال التحول n * Y + X ، حيث n هو حجم المصفوفة.
خوارزمية ديكسترا
سيتم استخدام خوارزمية Dijkstra ، وهي خوارزمية العثور على أقصر مسار بين قمة واحدة للرسم البياني وجميع الآخرين ، لحلها. تم اختراع الخوارزمية في عام 1956 من قبل العالم الهولندي Edsger Dijkstroy. إذا كان التفسير بسيطًا قدر الإمكان ، فإن الخوارزمية تعتمد على التقدم المتسلسل للقمم المجاورة للرسم البياني مع تقييم مستمر للمسافة المقطوعة. يمكن العثور على مثال توضيحي جيد ومخطط انسيابي أساسي للخوارزمية في مقالة ويكيبيديا.
في حالتنا ، سيبدو مخطط تدفق خوارزمية Dijkstra ("Dijkstra" الخاص بنا) كما يلي:
وفقًا للخوارزمية ، وأفضل وفقًا لنموذجها الرياضي ، يمكننا بالفعل إنشاء برنامج للروبوت. المدخلات ستكون مصفوفة المجاورة ونقاط البداية والنهاية. بعد كل الإجراءات الموصوفة ، يمكن العثور على البحث عن أقصر مسار بين أي نقاط على نفس الخريطة بسرعة.
بالطبع ، بالإضافة إلى خوارزمية Dijkstra ، سيحتاج الروبوت المستندة إلى LEGO EV3 إلى عدد من وحدات البرنامج الأبسط (البرامج الفرعية): الانتقال على طول الخط إلى التقاطع ، وحساب التقاطعات ، وتحويل كلا الاتجاهين ، وتحديد موقعك بالنسبة لنظام الإحداثيات المطلق X ، Y ، Θ ، حيث X ، Y - ينسق على الشبكة ، Θ - الاتجاه الحالي للروبوت (يتم التعبير عنه من خلال الرمز ، على سبيل المثال 1 - لأعلى ، 2 - إلى اليمين ، 3 - لأسفل ، 4 - إلى اليسار).
وها هو عرض حي لحل المشكلة. تختلف بيانات الإدخال قليلاً ، ولكن هذا لا يغير الجوهر.موضوع المكافأة: قياس المسافات
يمكن دمج إمكانيات قياس المسافات في المهام للتحرك على الأرض - على سبيل المثال ، بحيث يفهم الروبوت في المتاهة مكانه وأين يتحرك. باستخدام قياس المسافات ، يتم تقدير حركة الروبوت استنادًا إلى البيانات المتعلقة بحركة محركات الأقراص (دوران المحركات). بمعرفة قطر العجلات ، يمكننا حساب المسافة التي قطعها الروبوت في وقت معين. بمعرفة السرعة الزاوية للعجلات ، يمكننا تحديد الزاوية التي تحول بها الروبوت بالنسبة إلى الأصل. ومن خلال تعيين سرعات زاوية مختلفة ، يمكننا ضبط حركة الروبوت على طول القوس وفي نفس الوقت تحديد "الحلقات" عند تحريك الروبوت ، كما في الفيديو أدناه:
في المدارس ، يتم إيلاء الكثير من الاهتمام لعلم المثلثات ، ولكن تطبيقه العملي لا يتم تغطيته بأي شكل من الأشكال. تُظهر مشكلات قياس المسافات التي تم حلها باستخدام LEGO EV3 سبب الحاجة إلى حساب المثلثات على الإطلاق. من الناحية العملية ، لا يتم استخدام قياس المسافات في النقل فحسب ، بل أيضًا ، على سبيل المثال ، لتتبع موضع الأداة في آلات CNC (التحكم العددي).
أين يمكنني تعلم كل هذا؟
أسمح لنفسي ببعض الإعلانات. المهمة الموصوفة أعلاه ، والمهام الأكثر تعقيدًا يمكن حلها جيدًا من قبل أطفال الصفوف 7-9 الذين تم تدريبهم في نوادي الروبوتات. أنا أدير أحد هذه الأندية ، روبيت ، في يكاترينبورغ - هذا هو برنامجنا
التدريبي . صورنا الفيديو من العرض التوضيحي للمهمة أعلاه في أحد الفصول. ثم درس طالب الصف الثامن من نادينا في 6 ساعات أساسيات نظرية الرسم البياني وحل مشكلة مماثلة.
كيفية اختيار بيئة برمجة LEGO EV3
لا يمكن حل المشكلات بدون اختيار بيئة البرمجة المناسبة لـ LEGO EV3. هناك
مواد منفصلة عن آخرها في هذا المجال. أحاول تعليم الأطفال اختيار لغة برمجة للمهمة ، وليس مهمة لغة البرمجة تلك ، التي تعلموا عنها. ولكن في الدرجات الدنيا ، من الصعب العمل على الفور في لغة برمجة نصية ، لذلك نبدأ في دراسة الخوارزميات باللغات الرسومية ، حيث يكون حد الإدخال أقل. من 10 سنوات ، يتعلم الطلاب البيئة الرسومية لـ EV3 Mindstorms. تقيد بعض مسابقات الروبوتات مجموعات الأدوات بهذه البيئة فقط.
من سن 12 ، يبدأ الرجال في إتقان بيئة EV3 الأساسية. البيئة سهلة التعلم نسبيًا ، وتوفر Basic وظائف قوية لمنصة LEGO EV3. بالإضافة إلى ذلك ، نحن نبرمج في بيئة EV3Dev ، حيث يمكنك تثبيت العديد من اللغات المختلفة - Python ، Java ، C. باستخدام EV3Dev ، يحصل الرجال على تجربتهم الأولى في اللغات الشائعة الشائعة. ناقص EV3Dev الوحيد هو معدل اقتراع مستشعر أقل نسبيًا مقارنة بالبيئات الأخرى. باتباع النهج الصحيح ، تصبح LEGO EV3 أداة رائعة للتعرف على البرمجة. عندما يرى الطلاب كودهم يتنفس الحياة في مُنشئ ، فهذا دافع ممتاز.
ما هي الخطوة التالية؟
بعد دراسة هذه الخوارزميات في المدرسة الثانوية ، سيتمكن الأطفال من تعزيز معرفتهم بشكل أكبر ، على سبيل المثال ، المشاركة في التصميم والأولمبياد الخاضعة للمكافآت الحقيقية - على سبيل المثال ، 100 نقطة تلقائيًا في الامتحان في القبول في الجامعات.