A Scalable Direction-Guided Any-Angle A* Algorithm for Efficient Warehouse AGV Path Planning

في قلب الخدمات اللوجستية الحديثة الصاخب، من مراكز تنفيذ الطلبات الضخمة لعمالقة التجارة الإلكترونية إلى الأرضيات المؤتمتة للمصانع الذكية، تتحرك قوة عاملة صامتة من الروبوتات بدقة لا تلين. هذه الآلات، المعروفة باسم المركبات الموجهة آلياً (AGVs)، هي العضلات الكامنة وراء الكواليس، حيث تنقل الطرود والمواد عبر المستودعات المترامية الأطراف. ومع ذلك، فإن كفاءتها تعتمد كلياً على صانع قرار واحد غير مرئي: خوارزمية تخطيط المسار. يجب على هذا العقل الرقمي أن يحسب باستمرار أفضل مسار من النقطة (أ) إلى النقطة (ب)، متجنباً العقبات مثل الرفوف والروبوتات الأخرى، مع تقليل الوقت والطاقة المستهلكة في الرحلة. لعقود من الزمن، كانت الأداة القياسية لهذه المهمة هي طريقة رياضية تسمى (A*)، والتي تعمل مثل مستكشف دقيق، يفحص كل خطوة ممكنة لضمان العثور على أقصر مسار. ومع ذلك، مع ازدياد حجم المستودعات وعدد الروبوتات، يصبح هذا المستكشف التقليدي مثقلاً بالأعباء؛ فهو يفحص الكثير من الطرق المسدودة، مما يبطئ النظام بأكمله، ويجبر الروبوتات غالباً على اتخاذ مسارات متعرجة وغير متناسقة، وهي غير فعالة للآلات المصممة للتحرك في خطوط مستقيمة.

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

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

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

اختبر الباحثون هذه الطريقة الجديدة مقابل خمس خوارزميات تخطيط شائعة أخرى باستخدام بيئات محاكاة متنوعة. فقد أنشأوا ثلاثين خريطة مختلفة للإعدادات العامة وثلاثين أخرى تحاكي التخطيط المحدد للمستودع، بما في ذلك صفوف الرفوف والمناطق المخصصة ذات الحركة المرورية العالية حيث تزدحم الروبوتات غالباً. وفي هذه الاختبارات، أثبتت الخوارزمية الجديدة كفاءة ملحوظة. ففي البيئات العامة، قللت عدد "العقد" - أو النقاط التي يتعين على الكمبيوتر فحصها - بنسبة تقرب من 80 بالمائة مقارنة بالطريقة التقليدية. وفي محاكاة المستودعات الأكثر تعقيداً، تمكنت من تقليل جهد البحث بأكثر من 74 بالمائة. والأهم من ذلك، أن هذا المكسب الهائل في السرعة لم يأتِ على حساب طول الرحلة؛ فقد كانت المسارات التي تولدها الطريقة الجديدة أطول بنسبة 0.3 بالمائ المائة فقط من أقصر مسار ممكن، وهو فرق ضئيل جداً لدرجة أنه غير مرئي عملياً.

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

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

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

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

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