Constraint-aware Path Planning from Natural Language Instructions Using Large Language Models
تقترح هذه الورقة إطار عمل مرن يسخر النماذج اللغوية الكبيرة لحل مشكلات تخطيط المسارات المقيدة المتنوعة مباشرة من التعليمات باللغة الطبيعية عبر مطابقة المدخلات مع صيغ معروفة أو استنتاج صيغ جديدة ذاتياً، يتبع ذلك عملية تصحيح ذاتي تكرارية لتوليد حلول قابلة للتنفيذ ومثالية.
تخيل أنك تخطط لرحلة على الطريق. في الماضي، إذا أردت من الكمبيوتر أن يساعدك في إيجاد أفضل مسار، كان عليك التحدث بلغته. لم يكن بإمكانك ببساطة أن تقول: "أريد زيارة خمس أماكن رائعة، لكن ليس لدي سوى 100 ميل من الوقود وأحتاج للتوقف عند محطة وقود كل 30 ميلاً". كان عليك ترجمة ذلك إلى معادلات رياضية معقدة وقواعد صارمة يمكن لبرنامج كمبيوتر متخصص فهمها. وإذا تضمنت رحلتك قاعدة غريبة وجديدة (مثل "يجب أن أزور مخبزاً قبل الظهر")، فغالباً ما كان عليك استئجار عالم رياضيات لإعادة كتابة البرنامج بالكامل.
تقدم هذه الورقة طريقة جديدة للقيام بذلك باستخدام "المتحدثين الأذكياء" (النماذج اللغوية الكبيرة أو LLMs).
فكر في النموذج اللغوي الكبير ليس كآلة حاسبة، بل كـ وكيل سفر فائق الذكاء قد قرأ كل كتب السفر، والخرائط، وكتيبات اللوجستيات في العالم. إليك كيف يعمل نظامهم الجديد، مقسماً بتبسيط عبر التشبيهات:
1. نظام "المسارين"
بنى الباحثون نظاماً يعمل مثل مكتبة ذكية لها طريقتان مختلفتان للعثور على كتاب:
المسار (أ): "خزانة الملفات" (للطلبات الشائعة) إذا طلبت شيئاً شائعاً، مثل "جد أقصر مسار لزيارة 10 مدن"، فإن النظام يتحقق من مكتبة جاهزة من خطط السفر القياسية. يجد "النموذج" الدقيق لرحلة تضم 10 مدن، ويملأه بأسماء مدنك المحددة، ثم يسلمه للذكاء الاصطنا artificial. الأمر يشبه سحب مسودة رحلة مطبوعة مسبقاً من الرف وكتابة أسماء مدنك فيها فقط.
المسار (ب): "المهندس المعماري المبدع" (للطلبات الغريبة) إذا طلبت شيئاً لم يره النظام من قبل (على سبيل المثال: "أريد زيارة 3 مدن، ولكن يجب أن أبدأ من حديقة معينة، وأنتهي عند الشاطئ، وأتجنب الطرق السريعة")، فلا يوجد نموذج جاهز. لذا، يتصرف الذكاء الاصطناعي كمهندس معماري مبدع. يقرأ وصفك العفوي غير المنظم، ويفهم القواعد من تلقاء نفسه، ثم يبني خطة جديدة من الصفر.
2. حلقة "التصحيح الذاتي" (الخوارزمية الجينية)
هذا هو الجزء الأكثر ذكاءً. في الماضي، إذا طلبت من الكمبيوتر مساراً، فإنه يعطيك إجابة واحدة، وإذا كانت خاطئة، فستظل عالقاً.
في هذا النظام الجديد، يعمل الذكاء الاصطناعي مثل التطور الجيني للأفكار:
المسودة: يقوم الذكاء الاصطناعي بإنشاء مسار.
المفتش: يلعب الذكاء الاصطناعي فوراً دور المفتش الصارم. يتحقق من المسار مقابل قواعدك: "هل زرت كل المدن؟ هل نفد منك الوقود؟ هل بدأت من المكان الصحيح؟"
الإصلاح: إذا وجد الذكاء الاصطناعي خطأً، فهو لا يكتفي بقول "خطأ". بل يقول: "عذراً، لقد فاتني المخبز. دعني أحاول مرة أخرى".
التطور: يفعل ذلك مراراً وتكراراً، حيث ينتج نسخاً أفضل قليلاً من المسار في كل مرة، ويقارن بينها مثل مدرب يختار أفضل لاعب من بين فريق. يحتفظ بالنسخة الأفضل ويتخلص من السيئة حتى يجد المسار المثالي.
3. لماذا يعد هذا أمراً هاماً؟
لا مزيد من "لغة الرياضيات": يمكنك التحدث إلى النظام كما تتحدث إلى صديق بشري. "أريد الذهاب إلى حديقة الحيوان، ثم المتحف، لكني سأشعر بالتعب بعد ساعتين". يفهم النظام كلمة "تعب" كقيد زمني.
المرونة: إذا ابتكرت نوعاً جديداً من الرحلات غداً، فلن يحتاج النظام إلى تحديث برمجيات. سيستخدم فقط وضع "المهندس المعماري المبدع" لفهم الأمر. فتحت لـ التدقيق الذاتي: النظام صارم. لن يعطيك مساراً يكسر قواعدك، حتى لو اضطر للمحاولة 10 مرات ليصل إلى النتيجة الصحيحة.
العقبة (القيود)
تعترف الورقة بأن النظام ليس مثالياً بعد.
حد "ضبابية الدماغ": إذا طلبت من الذكاء الاصطناعي التخطيط لرحلة تضم 50 مدينة دفعة واحدة، سيبدأ في الارتباك. قد ينسى مدينة أو يزور نفس المدينة مرتين. الأمر يشبه إنساناً يحاول حفظ رقم هاتف مكون من 50 رقماً؛ قد يسقط منه رقم ما.
لا "ضمان رياضي": نظرًا لأن الذكاء الاصطناعي يقوم بالتخمين والتحسين بدلاً من استخدام معادلة رياضية صارمة، فإنه لا يستطيع أن يضمن بنسبة 100% أن المسار هو الأفضل رياضياً على الإطلاق. هو فقط يضمن أنه مسار جيد جداً يتبع قواعدك.
الخلاصة
هذا البحث يشبه منح روبوت عقلاً لغوياً طبيعياً للوجستيات. بدلاً من إجبار البشر على تعلم لغة البرمجة المعقدة للروبوت، يمكننا أخيراً ببساطة إخبار الروبوت بما نريد بلغة بسيطة، وسيتولى هو القيام بالرياضيات، والتحقق من عمله، وإعطائنا خطة رائعة. إنها خطوة عملاقة نحو جعل أدوات التخطيط الذكية متاحة للجميع، وليس فقط لعلماء الرياضيات.
إليك ملخص تقني مفصل لورقة البحث بعنوان "تخطيط المسارات المدرك للقيود باستخدام التعليمات باللغة الطبيعية عبر النماذج اللغوية الكبيرة" من إعداد ديلان شيما ومينغهان وي.
1. بيان المشكلة
غالبًا ما تتضمن مهام تخطيط المسارات في العالم الحقيقي (مثل اللوجستيات، التوصيل، السفر) قيودًا معقدة يحددها المستخدم وتتجاوز مجرد تحسين المسار البسيط. وتشمل هذه القيود:
القيود المتغيرة: عدد المسارات، الحد الأقصى لطول المسار، مواقع مستودعات محددة، النوافذ الزمنية، ومتطلبات الجدولة.
مشكلات القابلية للتوسع: تعتمد النهج التقليدية على صياغات رياضية مخصصة وخوارزميات متخصصة (مثل TSP، وVRP، وCapacitated VRP) لكل نوع محدد من المشكلات. يتطلب هذا معرفة خبيرة وضبطًا مكثفًا، مما يجعل من الصعب التوسع لتغطية سيناريوهات متنوعة أو جديدة.
الفجوة: هناك حاجة لنظام يمكنه استقبال تعليمات بـ اللغة الطبيعية (NL)، وتفسير القيود المعقدة دون الحاجة لصياغة يدوية، وتوليد مسارات قابلة للتنفيذ ومحسنة دون مطالبة المستخدم بتعريف نموذج رياضي مهيكل.
2. المنهجية
يقترح المؤلفون إطار عمل مرن يستفيد من النماذج اللغوية الكبيرة (LLMs) لحل مشكلات تخطيط المسارات المقيدة مباشرة من مدخلات اللغة الطبيعية. يعمل النظام عبر بنية ذات مسارين مقترنة بـ حلقة تحقق وتحسين تكرارية.
أ. نظام المسارين
يحدد النظام كيفية معالجة المدخلات بناءً على ما إذا كانت المشكلة تطابق أنماطًا معروفة:
المسار الأول: مطابقة المشكلة (الأنواع المعروفة)
يقوم النموذج اللغوي الكبير بتحليل مدخلات اللغة الطبيعية والبحث في مكتبة حالات (Case Library) لـ صياغات المشكلات المهيكلة (SPFs).
إذا تم العثور على تطابق (مثل مسألة البائع المتجول القياسية TSP أو نوع معين من مسائل توجيه المركبات VRP)، يسترجع النموذج اللغوي الكبير الصياغة المقابلة.
تتضمن الصياغة (SPF) الهدف، والقيود (المعبر عنها كمتراجحات رياضية)، ومتطلبات صارمة لتنسيق المخرجات.
المسار الثاني: التعلم في السياق (الأنواع الجديدة)
إذا وصف المدخل نوعًا جديدًا أو غير مرئي من المشكلات، فلا يمكن للنموذج اللغوي الكبير العثور على تطابق. // باستخدام التلقين بنموذج واحد (single-shot prompting) (تقديم مثال واحد لتحويل اللغة الطبيعية إلى صياغة SPF)، يستنتج النموذج اللغوي هيكل المشكلة بشكل مستقل.
يقوم بتوليد صياغة (SPF) مخصصة وحل أولي دون الاعتماد على قوالب موجودة مسبقًا.
ب. توليد الحل والتحقق التكراري
بمجرد توليد الحل (عبر أي من المسارين)، يستخدم النظام عملية تحسين مستوحاة من الخوارزميات الجينية:
التحقق من القيود: يتحقق النظام مما إذا كان الحل المرشح يستوفي جميع القيود (مثل زيارة جميع المدن مرة واحدة بالضبط، والبدء/الانتهاء عند المستودع الصحيح).
مع وجود SPF: يستخدم النظام متراجحات رياضية صريحة للتحقق من الجدوى.
بدون وجود SPF: يقوم النموذج اللغوي الكبير بـ التحقق الذاتي من خلال فحص مخرجاته مقابل القيود التي ولدها بنفسه.
التصحيح الذاتي: إذا تم اكتشاف انتهاكات، يتم توجيه النموذج اللغوي الكبير لمراجعة الحل، مع معالجة القيود التي فشلت صراحةً.
التحسين التكراري: يولد النموذج اللغوي الكبير عدة حلول مرشحة، ويقارن بينها بناءً على تكلفة السفر (دالة الهدف)، ويختار الأفضل. تتكرر هذه الدورة حتى يتم العثور على حل قابل للتنفيذ أو الوصول إلى الحد الأقصى لعدد التكرارات.
3. المساهمات الرئيسية
واجهة لغة طبيعية للتوجيه: تطوير خط معالجة يسمح للمستخدمين بتحديد مهام التوجيه المعقدة عبر المحادثة، مما يلغي الحاجة إلى صياغة رياضية رسمية للمشكلة.
حل هجين للمشكلات: تصميم نظام ثنائي المسار يتعامل مع كل من أنواع المشكلات المدروسة مسبقًا (عبر مطابقة المكتبة) والمواصفات الجديدة (عبر التعلم في السياق)، مما يضمن القدرة على التعميم.
إطار التحقق التكراري: دمج حلقة تصحيح ذاتي تضمن أن الحلول قابلة للتنفيذ (متوافقة مع القيود) وتعمل على تحسين جودة الحل تدريجيًا (تقليل التكلفة).
مخرجات لغة طبيعية مباشرة: على عكس الأعمال السابقة التي تطلبت من النماذج اللغوية الكبيرة توليد أكواد برمجية قابلة للتنفيذ (Python/C++) لحل مشكلات التحسين، يتيح هذا الإطار للنموذج اللغوي الكبير إخراج حلول لغة طبيعية مهيكلة مباشرة.
4. النتائج التجريبية
تم تقييم إطار العمل باستخدام نماذج لغوية كبيرة متطورة (GPT-4-Turbo, Llama3.3 70b) عبر أربعة أنواع من المشكلات:
مسألة البائع المتجول الأساسية (TSP) (مستودع واحد، مسار واحد).
مسألة البائع المتجول متعددة الأيام (مستودع واحد، مسارات متعددة).
مسألة البائع المتجول متعددة الأيام مع تغيير المستودعات (مستودع مختلف لكل يوم).
قيود مختلطة/جديدة (صياغة SPF مولدة ذاتيًا).
النتائج الرئيسية:
الجدوى: مع وحدة التحقق الذاتي، كانت 95.38% من الحلول المولدة صالحة. بدون التحقق، انخفضت الصلاحية إلى 85.63%.
الأمثلية: قلل التحسين التكراري إجمالي تكاليف السفر في 64% من الحالات.
مثال: بالنسبة لنوع المشكلة 2، انخفض متوسط التكلفة من 589.45 (بدون تكرار) إلى 537.52 (مع التكرار)، وهو انخفاض بنسبة 8.81%.
اتساق التنسيق: كانت المطالبات المهيكلة (SPF) حاسمة. بدونها، واجهت النماذج اللغوية الكبيرة صعوبة في إنتاج مخرجات قابلة للتحليل، وغالبًا ما انتهكت القيود أو فشلت في اتباع التنسيق.
حد القابلية للتوسع: عمل النظام بشكل جيد في المشكلات التي تضم ما يصل إلى 10-15 مدينة. تدهور الأداء بشكل كبير مع أكثر من 15-20 مدينة، مما أدى إلى حدوث هلوسة (فقدان مدن، زيارات مكررة) وأخطاء في التنسيق.
5. الأهمية والقيود
الأهمية:
دمقرطة التحسين: جعل تحسين المسارات المعقدة متاحًا لغير الخبراء الذين يمكنهم وصف المشكلات بلغة بسيطة.
المرونة: القدرة على التكيف مع تركيبات قيود جديدة دون إعادة هندسة الخوارزميات.
إطار عمل قابل للتوسع: يوفر نهجًا قابلًا للتعميم لمهام التوجيه في العالم الحقيقي حيث تتغير المتطلبات ديناميكيًا.
القيود:
لا توجد ضمانات نظرية: نظرًا لأن المشكلات الأساسية هي من نوع NP-hard، لا يمكن للنموذج اللغوي الكبير تقديم براهين رياضية للأمثلية أو حدود التقريب (على عكس خوارزميات التقريب التقليدية).
القابلية للتوسع: تواجه النماذج اللغوية الكبيرة الحالية صعوبة في التعامل مع الحالات واسعة النطاق (>20 عقدة)، حيث تنتج غالبًا مخرجات غير صالحة يمكن لوحدة التحقق اكتشافها ولكن لا يمكن للنموذج اللغوي الكبير تصحيحها ذاتيًا بشكل موثوق.
العمل المستقبلي: يقترح المؤلفون نهجًا هجينًا حيث يقوم النموذج اللغوي الكبير بتحويل قيود اللغة الطبيعية إلى صياغة البرمجة الخطية الصحيحة (ILP)، وتفويض خطوة التحسين النهائية إلى برنامج ILP تقليدي للتغلب على مشكلات القابلية للتوسع وضمانات الأمثلية.