🤖 machine learning

Test-Time Graph Search for Goal-Conditioned Reinforcement Learning

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

المؤلفون الأصليون: Evgenii Opryshko, Junwei Quan, Claas Voelcker, Yilun Du, Igor Gilitschenski

نُشر 2026-05-26✓ Author reviewed ⓘ

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Evgenii Opryshko, Junwei Quan, Claas Voelcker, Yilun Du, Igor Gilitschenski

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

تقدم هذه الورقة حلاً ذكياً بنظام "التوصيل والتشغيل" (plug-and-play) يسمى البحث في الرسم البياني في وقت الاختبار (Test-Time Graph Search - TTGS). هذا الحل لا يتطلب إعادة تدريب الروبوت أو تعليمه مهارات جديدة، بل يمنح الروبوت "خريطة" و"دليلاً" مباشرة قبل أن يبدأ في الحركة.

إليك كيف يعمل، باستخدام تشبيهات بسيطة:

1. المشكلة: فخ "القفزة العملاقة"

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

2. الحل: استراتيجية "سباق التتابع"

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

الخريطة (الرسم البياني - The Graph): ينظر النظام إلى المكتبة الضخمة من جولات التدريب السابقة (مجموعة البيانات غير المتصلة بالإنترنت/offline dataset) التي قام بها الروبوت بالفعل. ويستخرج منها "نقاط علام" (waypoints) رئيسية ويربطها ببعضها مثل النقاط على الخريطة.
الدليل (المسار الأقصر): عندما تعطيه هدفاً جديداً، يستخدم النظام خوارزمية رياضية كلاسيكية (خوارزمية ديكسترا - Dijkstra's algorithm) لإيجاد أقصر وأسلم مسار بين البداية والنهاية باستخدام النقاط المستخرجة من جولات التدريب القديمة فقط.
عمليات التسليم (الأهداف الفرعية): لا ينظر الروبوت إلى الوجهة النهائية بعد؛ بل ينظر فقط إلى "نقطة العلام" التالية على الخريطة. وبمجرد وصوله إليها، يتلقى تعليمات جديدة للذهاب إلى نقطة العلام التالية. ويستمر في فعل ذلك حتى يصل إلى الهدف.

3. السر الخفي: "العقوبة الناعمة"

هناك عقبة: أحياناً قد تقترح "الخريطة" طريقاً مختصراً يبدو قصيراً ولكنه في الواقع خطير (مثل جسر يبدو صلباً ولكنه محطم في الواقع). لاحظ مؤلفو الورقة أن "تخمين" الروبوت الداخلي للمسافة يمكن أن يكون خاطئاً.

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

4. لماذا هو مميز؟

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

النتائج

اختبر الباحثون هذا النظام على معيار تقييم يسمى OGBench، والذي يتضمن متاهات معقدة لروبوتات مثل النمل والروبوتات البشرية (humanoids).

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

الملخص

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

ملخص تقني: البحث في الرسوم البيانية وقت الاختبار لتعلم التعزيز المشروط بالهدف

بيان المشكلة

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

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

المنهجية: البحث في الرسوم البيانية وقت الاختبار (TTGS)

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

المكونات الأساسية

بناء الرسم البياني (Graph Construction):
- يتم أخذ عينة من الحالات من مجموعة البيانات غير المتصلة لتكون بمثابة رؤوس (vertices) للرسم البياني.
- تُستخدم إشارة مسافة لتعيين أوزان الحواف (edges) بين هذه الرؤوس. يمكن اشتقاق هذه الإشارة من:
  - المسافات المستمدة من القيمة: ربط دالة القيمة المشروطة بالهدف $V(s, g)$ بعدد الخطوات المقدر $\hat{d}(s, g)$ . توفر الورقة خرائط مغلقة الصيغة لاتفاقيات المكافأة الشائعة (مثل المكافآت النهائية المتفرقة أو عقوبات الخطوة الواحدة).
  - المسافات الخاصة بالمجال: استخدام المقاييس الهندسية مثل المسافة الإقليدية بين مواضع الجسم عند توفرها.
- آلية العقوبة الناعمة (Soft Penalty Mechanism): لمعالجة مشكلة المبالغة في تقدير الدوال في القيم للاتصال (مما يخلق "ثقوباً دودية" عبر الفجوات)، يستخدم TTGS دالة عقوبة فوق خطية $p(\cdot)$ للتحولات التي تتجاوز عتبة منطقة الثقة $\tau$ . الحواف التي تبلغ مسافتها $D_{ij} < \tau$ تحتفظ بمسافتها الأصلية، بينما الحواف التي تبلغ $D_{ij} \ge \tau$ يتم تعيين وزن لها $p(D_{ij})$ (على سبيل المثال، $x \cdot 1000^{x/\tau}$ ). هذا يحافظ على البنية المترية المحلية مع توجيه المخطط نحو سلاسل من القفزات القصيرة والموثوقة، مما يمنع الرسم البياني من التجزؤ (كما يفعل العتبة الصارمة) أو السماح بقفزات طويلة غير ممكنة.
التخطيط وقت الاختبار (Test-Time Planning):
- البحث عن أقصر مسار: بالنظر إلى حالة البداية $s_0$ والهدف $g$ ، تقوم الخوارزمية بتحديد أقرب الرؤوس في الرسم البياني وتحسب أقصر مسار باستخدام خوار𝓰يتم Dijkstra. يتم حساب هذا المسار الموجه مرة واحدة لكل حلقة (episode).
- الاختيار التكيفي للأهداف الفرعية: أثناء التنفيذ، لا يتبع الوكيل المسار بشكل أعمى. بدلاً من ذلك، يختار هدفاً فرعياً من المسار المحسوب مسبقاً بناءً على ميزانية الخطوات $T$ . يحدد الوكيل أبعد نقطة طريق (waypoint) على المسار تقع ضمن الميزانية $T$ من الحالة الحالية. إذا لم توجد مثل هذه النقطة، فإنه يختار نقطة الطريق التالية مباشرة لضمان التقدم للأمام.
- تنفيذ السياسة: يتم استدعاء السياسة الأساسية المجمدة $\pi(a | s, \tilde{g})$ مع الحالة الحالية والهدف الفرعي المختار $\tilde{g}$ .

الأداة التشخيصية

تقدم الورقة نسبة أكبر قفزة ( $\rho$ ) كأداة تشخيصية خالية من عمليات التشغيل (rollout-free) للتنبؤ بما إذا كان TTGS سيكون مفيداً لمهمة جديدة. $\rho$ هي نسبة أقصى تكلفة حافة على طول المسار المخطط له إلى إجمالي المسافة المقدرة. تشير $\rho$ المنخفضة إلى وجود تغطية كافية للحالات الوسيطة (وهو أمر مفيد لـ TTGS)، بينما تشير $\rho$ العالية إلى أن مجموعة البيانات تفتقر إلى الحالات الجسرية، وفي هذه الحالة يعود TTGS إلى سلوك السياسة الأساسية.

المساهمات الرئيسية

إعادة تقييم دوال القيمة: يوضح المؤلفون أن دوال القيمة القياسية في GCRL غير المتصل، والتي كانت تعتبر سابقاً غير موثوقة جداً للبحث، تحتوي على بنية هندسية محلية كافية لدعم التخطيط طويل الأمد القوي عند معالجتها بآلية عقوبة ناعمة مبتكرة.
إطار عمل خالٍ من التدريب: يوفر TTGS طريقة لتحسين أداء الأفق الطويل من خلال إعادة استخدام السياسات ودوال القيمة الموجودة دون تعديل مسار التدريب، ودون الحاجة إلى إشراف إضافي أو تفاعل عبر الإنترنت.
الأداء بأقل قدر من التكاليف: تظهر النتائج التجريبية أن TTGS يعزز معدلات النجاح بشكل كبير لوكلاء GCRL غير المتصل الأحدث (HIQL, QRL, GCIQL, SAW, OTA) مع تكاليف حوسبة ضئيلة (وقت التخطيط < ثانية واحدة لكل حلقة).

النتائج التجريبية

تم تقييم الطريقة على معيار OGBench، الذي يغطي مهام الحركة (pointmaze, antmaze, humanoidmaze) ومهام التلاعب.

مهام الحركة (Locomotion Tasks): حقق TTGS مكاسب كبيرة في مهام "الحياكة" (stitch) طويلة الأمد حيث تفشل السياسات الأساسية عادةً.
- في pointmaze-giant-stitch-v0، تحسنت معدلات النجاح لـ HIQL من 0.0% إلى 80.9%، ولـ GCIQL من 0.0% إلى 98.0%.
- في humanoidmaze-giant-stitch-v0، تحسن HIQL من 4.4% إلى 78.1%.
- غالباً ما تضاهي هذه التحسينات أو تتفوق على الطرق المعقدة التي تتطلب تدريباً إضافياً أو نماذج توليدية.
مهام التلاعب (Manipulation Tasks): في المهام التي تقع فيها أهداف التقييم خارج نطاق البيانات (مثل scene-play-v0)، قدم TTGS مكاسب ضئيلة (0-2 نقطة مئوية) ولكنه لم يؤدِ إلى تدهور الأداء، حيث عاد بشكل صحيح إلى سلوك السياسة الأساسية عندما كانت الحالات الوسيطة مفقودة.
الدراسات الاستقصائية (Ablations):
- العقوبات الناعمة مقابل الصارمة: إزالة العقوبة الناعمة (استخدام المسافات الخام) أو استخدام عتبة صارمة (إزالة الحواف الطويلة) أدى إلى تدهور الأداء بشكل كبير في مهام الحياكة بسبب انقطاع الرسم البياني أو المسارات غير الممكنة.
- اختيار الهدف الفرعي: تفوقت الاستراتيجية التكيفية لاختيار أبعد نقطة طريق يمكن الوصول إليها على استراتيجية أبسط تعتمد دائماً على اختيار نقطة الطريق التالية مباشرة.
- مصادر المسافة: عمل TTGS بفعالية مع كل من المسافات المستمدة من القيمة والمسافات الإقليدية البسيطة لمواضع الجسم، مما أظهر مرونة عالية.

الأهمية والادعاءات

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

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