ما هي أفضل طريقة للتنقل وتجنب العقبات أمام روبوت الخدمة؟
الروبوتات هي أنظمة ميكانيكية وبرامج تتفاعل مع العالم الحقيقي. بالنسبة إلى روبوت الخدمة ، من المهم للغاية فهم موقعك الحالي في الفضاء ، وموضع الهدف والقدرة على بناء طريق إلى الهدف مع تجنب العوائق المحتملة. نحن نعمل على تطوير
روبوت لجمع كرات الجولف في مجال القيادة . لقد أخذنا بعين الاعتبار خيارات مختلفة لبناء مسار للعثور على أفضل مسار لأنفسنا ، ربما تكون هذه المعلومات مثيرة للاهتمام بالنسبة لشخص ما.
أسهل طريقة لجعل الروبوت يوجه إلى هدفه النهائي في الفضاء ثنائي الأبعاد. المسبار نفسه هنا هو نقطة صغيرة أمامه لا توجد عقبات. لذلك ، يتحرك الروبوت في هذه الحالة في خط مستقيم ، وعندما يصل إلى الهدف يتوقف.
هذه الطريقة مناسبة إذا كان هناك روبوت فقط في العالم والهدف الذي يجب أن يحققه. سيسمح لك Direct بالوصول إلى التكوين النهائي في أسرع وقت ممكن.
لكن هذه الخوارزمية لا يمكن تطبيقها إذا ظهرت عقبة فجأة أمام الروبوت. تتحرك في خط مستقيم ، لن تتمكن المركبة من الالتفاف حولها أو المرور. في هذا الصدد ، يتوقف ببساطة أمام عقبة ولا يتحرك.
كيف تتجنب عقبة؟ أسهل طريقة لحل المشكلة هي خيار السلوك المسمى "تجنب العوائق". في الممارسة العملية ، يتم تمثيلها بواسطة خوارزميات مختلفة.
المشي إلى الخوارزمية
إذا لم يتحقق الهدف:
- تحرك نحو الهدف.
- خلاف ذلك: توقف.
هذه الطريقة مناسبة إذا كان هناك روبوت فقط في العالم والهدف الذي يجب أن يحققه. سيسمح لك Direct بالوصول إلى التكوين النهائي في أسرع وقت ممكن. ولكن ما هي الخوارزمية التي يجب تطبيقها إذا ظهرت عقبة أمام الهدف أمام الروبوت؟
لا تسمح العائق للروبوت بالوصول إلى وجهته في خط مستقيم ، حيث تتوقف المركبة المسبقة في هذه الحالة أمامها. في هذه الحالة ، يمكنك أيضًا استخدام خوارزمية "المشي إلى" ، ولكن يجب استكمالها.
خوارزمية الأخطاء
في الحياة العادية ، الشخص ، عندما ينتقل من نقطة إلى أخرى إلى الهدف ويواجه عقبة ، يتخطى ذلك ببساطة. يسمى هذا السلوك "تجنب العوائق". سوف يتم تطبيقه لتحقيق الهدف بواسطة الروبوت. أسهل طريقة لتطبيق خوارزمية الخنفساء.
يتم استدعاء خوارزمية الأخطاء من قبل الخبراء بهذه الطريقة نظرًا لحقيقة أن سلوك الخنفساء يؤخذ هنا كأساس - إذا رأيت عقبة ، فإنها تتجاوزها.
تسمى الخطوات التي يتخذها الروبوت أثناء تحركه نحو الهدف (بما في ذلك عند المشي حول عائق) مسار.
خدمت خوارزمية الأخطاء كأساس للمفاهيم المستخدمة في إنشاء طرق من نوع أكثر تعقيدًا. وتشمل هذه:
مفهوم المسار. هذه سلسلة بسيطة من حركات الروبوت ، والتي يؤديها من أجل تحقيق الهدف النهائي. خوارزمية الخنفساء هي أيضًا "مخطط مسار". بعد استلام إحداثيات النقاط التي يوجد فيها الروبوت والهدف منه ، تقوم الخوارزمية بتطوير مسار مناسب للحركة.
مفهوم السياسة . إذا تم استخدام خوارزمية خنفساء معينة ، يتم إرسال تعليمات معينة للحركة إلى الروبوت ، فإن هذه الطريقة في إنشاء الطريق تسمى "سياسة الإدارة".
مفهوم ارشادي. هذا هو اسم القاعدة المستخدمة لإبلاغ الروبوت عن المرحلة التالية من الخوارزمية. في هذه الحالة ، الإرشادي هو الخط الذي يتحرك فيه الجسم. عند إنشاء مسار ، تحتاج إلى تحديد مجريات الأمور بشكل صحيح. إذا تم ذلك بشكل غير صحيح ، فإن الطريق الذي تم بناؤه سيكون غير صالح للعمل.
ومع ذلك ، فإن مثل هذه الخوارزمية تحد من المطور ، لأنه بمساعدتها سيكون من الممكن بناء مسار محدود الحجم. عند استخدام مثل هذه الخوارزمية لبناء مسار ، من الضروري أن تأخذ جميع العقبات شكل مضلع محدب.
خوارزمية الأخطاء لها قيود أيضًا:
- يجب أن تكون العقبات على مسافة معينة من بعضها البعض ، فمن المستحيل أن يكون لديهم أرضية مشتركة ؛
- حدود العوائق هي منحنيات مغلقة ، في حين أنها يجب أن تكون بحيث يتقاطع الخط المستقيم الذي يتحرك الروبوت على طوله لكل منها لعدد محدود من المرات ؛
- الروبوت هو نقطة صغيرة بشكل غير متناسب ، لذا يمكنه التنقل بين العوائق بغض النظر عن المرور بينهما.
يمكن التغلب على بعض هذه القيود باستخدام خوارزمية DH-Bug المتقدمة. ميزتها هي أنه بمساعدتها سيكون الروبوت قادرًا على التعامل مع العقبات المتحركة. علاوة على ذلك ، تتكون هذه الخوارزمية من طبقتين. الأول استشاري. يسمح لك بإجراء تقييم مسبق للطريق دون استخدام معلومات إضافية. الطبقة الثانية قابلة للتكيف. بفضله ، يستجيب الروبوت في الوقت المناسب للعقبات التي لم يتم وضعها في البرنامج في البداية.
خوارزمية CBUG
خوارزمية CBUG هي نسخة من بناء المسار بطريقة تأخذ في الاعتبار جميع التفاصيل. أثناء تطويره ، أخذ المتخصصون في الاعتبار حجم الروبوت ، وحلوا أيضًا المشكلات المتعلقة بتحسين المسار الذي تم إنشاؤه. السمة المميزة لهذه الخوارزمية المحسنة هي أنه لإنشاء مسار ، من الضروري أن تظل نقطة البداية دائمًا في ذاكرة الكائن. دائمًا لخوارزمية CBUG ، فقط من أجل تطبيقها ، من الضروري أن يكون لديك مقدار ثابت من الذاكرة.
خوارزمية ديكسترا
تم إنشاء الخوارزمية المستخدمة في الرسوم البيانية بواسطة E. Dijkstroy في النصف الثاني من القرن الماضي. بمساعدتها ، سيكون من الممكن تحديد أقصر مسار من إحدى رؤوس الرسم البياني إلى الآخرين. تنتهي هذه الخوارزمية عندما يزور الروبوت جميع القمم. إذا كان أولئك الذين لم يزرهم بعد يركبون ، يتم تحديد ذروة بحد أدنى للعلامة.
تشمل مزايا خوارزمية Deister ما يلي:- الانتباه إلى طول المسار وتكلفته ؛
- يتم تحديث العقد إذا تم العثور على أكثر مثالية.
عيب هذه الطريقة في إنشاء مسار هو أنه مناسب فقط للرسومات البيانية حيث لا توجد حواف ذات وزن سالب. من غير المناسب أن يكون ضعيف التوجيه عند البحث في العرض.
خوارزمية بلمان-فورد
ولكن غالبًا ما تنشأ حالات يكون فيها من الضروري بناء طريق حيث توجد الأضلاع ذات الوزن السلبي. سوف تساعد خوارزمية Bellman-Ford على حل هذه المشكلة. ونتيجة لذلك ، إذا كان مجموع أوزان حواف المسار النهائي يأخذ قيمة سالبة ، فإنه يسمى دورة سالبة.
خوارزمية جونسون
تم تقديم هذه الخوارزمية بواسطة DB جونسون من أجل تحديد جميع أقصر الطرق من ذروة إلى أخرى. في هذه الحالة ، يمكن استخدام الطريقة للحواف ذات الأوزان الإيجابية والسلبية. العيب الوحيد للخوارزمية هو عدم وجود دورات سلبية.
خوارزمية أ *
للعثور على الطريقة المثلى باستخدام الرسوم البيانية ، تحتاج إلى تطبيق خوارزمية A *. يسمح لك بتحديد أفضل مسار من الروبوت إلى الهدف من خلال المطابقة الأولى على الرسم البياني. أساس هذه الخوارزمية هو الصيغة الإرشادية ، وهي كما يلي:
f(n)=g(n)+h(n).
f(n) - , n.
g(n) - n .
h(n) - .تتيح لك هذه الخوارزمية العثور على أقصر مسار للهدف حتى تأخذ h (n) القيمة القصوى المسموح بها. ميزة الخوارزمية A * هي مرونتها. في معظم الأحيان ، تكون الدولة هي الخلية أو موقع الروبوت. ولكن يمكن أن تكون السرعة أو التوجه.
في نفس الوقت ، تختلف الدول المجاورة اعتمادًا على الحالة المحددة.
تتجلى مرونة الخوارزمية أيضًا في حقيقة أن الهدف الذي يحتاج إليه الروبوت لتحقيقه يمكن أن يتكون من عدة مواقف في وقت واحد. في مثل هذه الحالة ، يجب أن يكون التقريب الإرشادي h (n) صالحًا على الفور لجميع الأغراض المتاحة.
يعتمد مدى نجاح الخوارزمية A * على الأس h (n). كلما كانت جودة التقريب التوجيهي أفضل ، زادت الكفاءة. أيضًا ، يؤثر مقدار الذاكرة الخالية ووقت المعالج على تشغيل الخوارزمية.
خوارزمية تتبع الموجة
أيضًا ، غالبًا ما تستخدم خوارزمية الموجة لرسم مسار على رسم بياني. عند إنشاء مسار بهذه الطريقة ، يتم استخدام طريقة البحث الأولى.
تتضمن الخوارزمية نفسها الخطوات التالية:- التهيئة
- بناء الموجة
- الانتعاش الطريق.
في المرحلة الأولية ، يتم إنشاء صورة العديد من الخلايا ، كل منها تصبح إما قابلة للتمرير أو سالبة للروبوت.
يحدد الروبوت ، الذي ينتقل من خلية إلى أخرى ، بالتتابع ما إذا كان من الممكن تمريره وما إذا كان لم يميزه من قبل.
بعد ذلك ، يتم إنشاء أقصر مسار من خلية البداية إلى الخلية الأخيرة بالقوة الغاشمة ، والتي يكون تحقيقها هو هدف المركبة.
تمييز خوارزمية الفضاء
- مساحة التكوين لها حجم ثابت في جميع الأبعاد.
- تمييز جميع القياسات بحيث يكون لها عدد ثابت من الخلايا.
- يجب تمييز جميع الخلايا الموجودة في مساحة التكوين داخل العائق بأنها غير سالكة.
- ونتيجة لذلك ، تحولت جميع الخلايا القابلة للتمرير إلى عُقد.
- تتصل كل عقدة بجميع الجيران في الرسم البياني.
العثور على مسار عشوائي
إن أكثر الجوانب صعوبة عند التخطيط لمسار ما هي حساب مساحة التكوين وتحديد المسار الأكثر ملاءمة عند المرور عبر هذه المساحة. بفضل خرائط الطريق ، سيكون من الممكن حل هذه المشاكل. جوهر الطريقة هو تقسيم المساحة إلى مربعات متطابقة ، وربط جميع القمم الأقرب. كرر على جميع المسارات. قم بفرز كافة المسارات للعثور على المسار بأقل قيمة.
خوارزمية خرائط الطريق الاحتمالية
- 1. إنشاء رسم بياني فارغ G.
- 2. أضف إلى الرسم البياني G عقدة الروبوت وهدفه النهائي.
- 3. بالنسبة للعدد التاسع من عمليات الدمج:
- ابحث عن عينة عشوائية موحدة لمساحة التكوين وأطلق عليها اسم R.
- إذا كان الروبوت في صراع مع تكوين R ، فيمكنك المتابعة.
- خلاف ذلك: أضف R إلى العمود G.
- 4. تحديد جميع العقد في الرسم البياني الموجودة ضمن النقطتين د و ر.
- 5. لجميع العقد N التي تناسب هذه المعلمة:
استكشاف خوارزمية الأشجار العشوائية بسرعة
تحتاج في بعض الأحيان إلى إنشاء مسار دون تطبيق استعلامات التخطيط السابقة. في مثل هذه الحالات ، يجب عليك استخدام الطريقة التالية:
- إنشاء شجرة T. فارغة
- إضافة إلى تكوين الروبوت الأولي T.
- حتى الوصول إلى الهدف:
- إحضار العقدة R.
- حدد في العقدة T الأقرب إلى R. أعطه الاسم K.
- انقل الروبوت من K إلى R حتى يتحقق الشرط التالي:
- في حالة حدوث تصادم ، انتقل إلى تعريف عينة عشوائية.
- خلاف ذلك: أضف عقدة جديدة إلى T في هذا التكوين.
- إذا تم الوصول إلى أقصى مسافة بين d و K ، فابدأ في العمل على أخذ عينات عشوائية مرة أخرى.
- يتم الحصول على الحل إذا كانت العقدة المتسلسلة تقع على مسافة d من أي عقدة T.
الخلاصة
بالنسبة لنا ، من الأفضل فصل قضية بناء الطريق إلى العالمية والمحلية. المسار العالمي عبارة عن قائمة بنقاط الهدف لتجاوز الحقل أو هدف العودة إلى القاعدة. يبدأ المسار المحلي عندما تكتشف مستشعرات الموجات فوق الصوتية أو المصد وجود عائق.
نظرًا لأن جميع العقبات في تفاصيلنا محدبة ، فإننا نستخدم أبسط خوارزمية BUG ، وحتى أبسط. طريقة ملاحية "صبيانية" معينة. عندما تكتشف الموجات فوق الصوتية وجود عائق ، تتحول العربة إلى اتجاه عقارب الساعة 90 درجة ، وتنتقل 1 متر ، وتدور 90 عكس اتجاه عقارب الساعة. إذا تم اكتشاف عائق من قبل المصد ، قبل إعادة الروبوت 0.5 متر للخلف.
الخطط
خلال بداية المشروع في صيف 2018. حدث عدد كبير من الأحداث. نحن نعد منشورًا عن تطوير مشروعنا. شكرا لكم على اهتمامكم!
المراجع