تخطيط الحركة

يصف التكوين وضعية الروبوت، ومساحة التكوين C هي مجموعة جميع التكوينات الممكنة. على سبيل المثال:

• إذا كان الروبوت عبارة عن نقطة واحدة (حجمها صفر) تنتقل في مستوى ثنائي الأبعاد (مساحة العمل)، فإن C عبارة عن مستوى، ويمكن تمثيل التكوين باستخدام معلمتين (x، y).
• إذا كان الروبوت شكلاً ثنائي الأبعاد يمكنه الانتقال والدوران، فإن مساحة العمل تظل ثنائية الأبعاد. ومع ذلك، فإن C هي المجموعة الإقليدية الخاصة ^SE ( 2) = R²${\displaystyle \times }$SO (2) (حيث SO (2) هي المجموعة المتعامدة الخاصة للدوران ثنائي الأبعاد)، ويمكن تمثيل التكوين باستخدام 3 معلمات (x، y، θ).
• إذا كان الروبوت شكلاً ثلاثي الأبعاد صلباً يمكنه الانتقال والدوران، فإن مساحة العمل تكون ثلاثية الأبعاد، لكن C هي المجموعة الإقليدية الخاصة SE(3) = R ³${\displaystyle \times }$SO (3)، ثم يتطلب التكوين 6 معلمات: (x، y، z) للانتقال، وزوايا أويلر (α، β، γ).
• إذا كان الروبوت عبارة عن مناول ذي قاعدة ثابتة مع N مفصل دوراني (وبدون حلقات مغلقة)، فإن C يكون ذا أبعاد N.
• إذا لم يكن قفل جيمبال مقبولاً (على سبيل المثال في R ^N حيث N ≥ 3 ) فقد يكون من الضروري استخدام الكواترنيونات أو حلول بديلة أخرى ، مما يزيد من أبعاد الدوران أو تعقيد الحل.

تُسمى مجموعة التكوينات التي تتجنب الاصطدام بالعوائق بالفضاء الحر C _{_free} . ويُسمى مكمل C _{_free في C_free بالعائق أو المنطقة المحظورة.}

غالباً ما يكون من الصعب للغاية حساب شكل الفضاء الخالي من _عوائق C بشكل صريح . مع ذلك، يُعدّ اختبار ما إذا كان تكوينٌ ما يقع ضمن هذا _الفضاء فعالاً. أولاً، تحدد الحركة الأمامية موضع هندسة الروبوت، ثم يختبر نظام كشف التصادم ما إذا كانت هندسة الروبوت تصطدم بهندسة البيئة المحيطة.

الفضاء المستهدف هو فضاء فرعي من الفضاء الحر، يُحدد المكان الذي نرغب في أن يتحرك إليه الروبوت. في تخطيط الحركة الشامل، يكون الفضاء المستهدف قابلاً للملاحظة بواسطة مستشعرات الروبوت. أما في تخطيط الحركة المحلي، فلا يستطيع الروبوت ملاحظة الفضاء المستهدف في بعض الحالات. ولحل هذه المشكلة، يمر الروبوت عبر عدة فضاءات مستهدفة افتراضية، يقع كل منها ضمن المنطقة القابلة للملاحظة (حول الروبوت). يُطلق على الفضاء المستهدف الافتراضي اسم "الهدف الفرعي".

مساحة العوائق هي مساحة لا يستطيع الروبوت الوصول إليها. مساحة العوائق ليست عكس المساحة الحرة.

تعتمد الأساليب القائمة على الشبكة على تطبيق شبكة على فضاء التكوين، وتفترض أن كل تكوين يُمثل بنقطة على الشبكة. عند كل نقطة، يُسمح للروبوت بالانتقال إلى النقاط المجاورة طالما أن الخط الواصل بينها يقع بالكامل ضمن فضاء C _الحر (يتم اختبار ذلك باستخدام خاصية كشف التصادم). يؤدي هذا إلى تقسيم مجموعة الإجراءات، وتُستخدم خوارزميات البحث (مثل A* ) لإيجاد مسار من نقطة البداية إلى نقطة النهاية.

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

تُنتج الأساليب التقليدية القائمة على الشبكة مساراتٍ تكون فيها تغييرات الاتجاه محدودة بمضاعفات زاوية أساسية معينة، مما يؤدي غالبًا إلى مسارات غير مثالية. أما أساليب تخطيط المسار بأي زاوية، فتجد مسارات أقصر من خلال نشر المعلومات على طول حواف الشبكة (للبحث السريع) دون تقييد مساراتها بحواف الشبكة (لإيجاد مسارات قصيرة).

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

تتشابه هذه الأساليب مع أساليب البحث القائمة على الشبكة، إلا أنها تُنشئ رصفًا يُغطي فضاء التكوين بالكامل بدلًا من شبكة. ^{[ 1 ]} يُقسّم الرصف إلى رصفين فرعيين X⁻ ^و X⁺ ^، _{مُكوّنين} من مربعات بحيث يكون X⁻ ^⊂ C⁺⁺ و C⁺⁺⁺ ^. يُعادل توصيف C⁺⁺⁺ _حلّ مسألة عكس المجموعة . وبالتالي، يُمكن استخدام تحليل الفترات عندما يتعذر وصف _{C⁺⁺⁺⁺} باستخدام المتباينات الخطية لضمان احتواء كامل.

وبالتالي، يُسمح للروبوت بالتحرك بحرية في X− ^، ولا يمكنه الخروج من X ⁺ . يتم إنشاء مخطط الجوار لكلتا المنطقتين الفرعيتين، ويمكن إيجاد المسارات باستخدام خوارزميات مثل ديكسترا أو A* . عندما يكون المسار ممكنًا في X− ^، يكون ممكنًا أيضًا في C _free . عندما لا يوجد مسار في X ⁺ من أي تكوين أولي إلى الهدف، نضمن عدم وجود مسار ممكن في C _free . أما بالنسبة للنهج القائم على الشبكة، فإن نهج الفترات غير مناسب للمسائل عالية الأبعاد، نظرًا لأن عدد المربعات المطلوب إنشاؤها ينمو أُسّيًا بالنسبة لبُعد فضاء التكوين.

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

أظهر نيكولاس ديلانو أن التفكيك باستخدام الرصفات الفرعية من خلال تحليل الفترات يسمح أيضًا بتوصيف طوبولوجيا C _الحرة ، مثل حساب عدد مكوناتها المتصلة. ^{[ 2 ]}

توجيه الروبوتات بين العوائق المضلعة

• رسم بياني للرؤية
• تحلل الخلايا
• مخطط فورونوي

نقل الأشياء بين العوائق

• مينكوفسكي سوم

إيجاد مخرج من مبنى

• أبعد مسار شعاعي

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

يتمثل أحد الأساليب في اعتبار وضعية الروبوت نقطةً في مجال جهد يجمع بين الانجذاب نحو الهدف والتنافر مع العوائق. ويُخرَج المسار الناتج كمسار. يتميز هذا الأسلوب بسهولة حساب المسار. مع ذلك، قد يقع الروبوت في الحد الأدنى المحلي لمجال الجهد، ما يؤدي إلى فشله في إيجاد مسار، أو قد يجد مسارًا غير مثالي. يمكن التعامل مع مجالات الجهد الاصطناعية كمعادلات متصلة مشابهة لمجالات الجهد الكهروستاتيكية (باعتبار الروبوت شحنة نقطية)، أو يمكن تقسيم الحركة عبر المجال باستخدام مجموعة من القواعد اللغوية. ^{[ 3 ]} تُعد دالة الملاحة ^{[ 4 ]} أو دالة الملاحة الاحتمالية ^{[ 5 ]} من أنواع دوال الجهد الاصطناعية التي لا تحتوي على نقاط دنيا باستثناء نقطة الهدف.

تمثل الخوارزميات القائمة على أخذ العينات فضاء التكوين باستخدام خريطة طريق للتكوينات المأخوذة عينات منها. تقوم خوارزمية أساسية بأخذ عينات من N تكوين في C، وتحتفظ بتلك الموجودة في C _الحرة لاستخدامها كمعالم . ثم تُنشأ خريطة طريق تربط بين معلمين P وQ إذا كان الخط PQ موجودًا بالكامل في C _الحرة . مرة أخرى، يُستخدم اكتشاف التصادم لاختبار الاحتواء في C _الحرة . لإيجاد مسار يربط بين S وG، تُضافان إلى خريطة الطريق. إذا كان هناك مسار في خريطة الطريق يربط بين S وG، ينجح المخطط، ويعيد ذلك المسار. إذا لم ينجح، فالسبب غير واضح: إما أنه لا يوجد مسار في C _الحرة ، أو أن المخطط لم يأخذ عينات كافية من المعالم.

تُعدّ هذه الخوارزميات فعّالة في فضاءات التكوين عالية الأبعاد، لأنّ وقت تشغيلها، على عكس الخوارزميات التوافقية، لا يعتمد (بشكل صريح) على بُعد فضاء التكوين. كما أنّها (عمومًا) أسهل بكثير في التنفيذ. وهي كاملة احتماليًا، أي أنّ احتمال إنتاجها حلًا يقترب من 1 مع زيادة الوقت المُستغرق. مع ذلك، لا يُمكنها تحديد ما إذا كان الحل غير موجود.

في ظل شروط الرؤية الأساسية على فضاء C _الحر ، ثبت أنه مع ازدياد عدد التكوينات N، يقترب احتمال إيجاد الخوارزمية المذكورة أعلاه حلاً من 1 بشكل أُسّي. ^{[ 6 ]} لا تعتمد الرؤية بشكل صريح على بُعد C؛ فمن الممكن وجود فضاء عالي الأبعاد برؤية "جيدة" أو فضاء منخفض الأبعاد برؤية "ضعيفة". ويشير النجاح التجريبي للطرق القائمة على العينات إلى أن معظم الفضاءات الشائعة تتمتع برؤية جيدة.

توجد العديد من الصيغ المختلفة لهذا المخطط الأساسي:

• عادة ما يكون اختبار الأجزاء الواقعة بين أزواج المعالم القريبة أسرع بكثير من اختبار جميع الأزواج.
• تحاول توزيعات العينات غير المنتظمة وضع المزيد من المعالم في المناطق التي تحسن ترابط خارطة الطريق.
• تنتج العينات شبه العشوائية عادةً تغطية أفضل لمساحة التكوين من العينات شبه العشوائية ، على الرغم من أن بعض الأعمال الحديثة تجادل بأن تأثير مصدر العشوائية ضئيل مقارنة بتأثير توزيع أخذ العينات.
• يستخدم أخذ العينات المحلية ^{[ 7 ]} من خلال تنفيذ سلسلة ماركوف الاتجاهية مونت كارلو المشي العشوائي مع بعض توزيع الاقتراح المحلي.
• من الممكن تقليل عدد المعالم اللازمة لحل مشكلة معينة بشكل كبير عن طريق السماح برؤية منحنية (على سبيل المثال عن طريق الزحف على العوائق التي تسد الطريق بين معلمين ^{[ 8 ]} ).
• إذا اقتصرت الحاجة على استعلام تخطيط واحد أو بضعة استعلامات، فليس من الضروري دائمًا إنشاء خريطة طريق للمساحة بأكملها. عادةً ما تكون طرق التخطيط القائمة على نمو الشجرة أسرع في هذه الحالة (تخطيط الاستعلام الواحد). مع ذلك، تظل خرائط الطريق مفيدة إذا كان سيتم إجراء العديد من الاستعلامات على نفس المساحة (تخطيط الاستعلامات المتعددة).

• أ*
• خوارزمية الأخطاء
• د*
• خوارزمية ديكسترا
• نهج النافذة الديناميكية
• خارطة طريق احتمالية
• شجرة عشوائية سريعة الاستكشاف
• ثيتا*
• مدرج تكراري لحقل متجهي

هولونوميك

• أذرع آلية (مع ديناميكيات)

غير هولونومي

• الطائرات بدون طيار
• سيارات
• الدراجات أحادية العجلة
• طائرات
• الأنظمة ذات التسارع المحدود
• العوائق المتحركة (لا يمكن للزمن أن يعود إلى الوراء)
• إبرة قابلة للتوجيه ذات طرف مشطوف
• روبوتات ذات محرك تفاضلي

الأنظمة الهجينة هي تلك التي تجمع بين السلوك المتقطع والمستمر. ومن أمثلة هذه الأنظمة:

• التلاعب الروبوتي
• التجميع الميكانيكي
• حركة الروبوتات ذات الأرجل
• الروبوتات القابلة لإعادة التشكيل

• عدم اليقين في الحركة
• المعلومات المفقودة
• الاستشعار النشط
• التخطيط بدون مستشعرات
• أنظمة التحكم الشبكية ^{[ 9 ]}

• خرائط الديناميكيات ^{[ 10 ]}