DOI: https://doi.org/10.1109/jiot.2026.3663569
تاريخ النشر: 2026-02-11
المؤلف: Junkai Jiang وآخرون
الموضوع الرئيسي: خوارزميات تخطيط المسار الروبوتي
نظرة عامة
تقدم هذه الورقة مشكلة جديدة في البحث عن المسارات متعددة الوكلاء (MAPF) تُعرف بتسلسل المهام التعاونية – البحث عن المسارات متعددة الوكلاء (CTS-MAPF)، حيث يجب على الوكلاء التنقل في مسارات خالية من التصادم أثناء زيارة مواقع المهام المحددة بترتيب معين قبل الوصول إلى وجهاتهم النهائية. لمواجهة هذا التحدي، يقترح المؤلفون خوارزمية تسلسل المهام التعاونية – البحث القائم على الصراع (CTS-CBS)، التي تستخدم استراتيجية بحث من مستويين. يولد البحث على المستوى العالي غابة من الأشجار تمثل تسلسلات المهام المشتركة بناءً على حل مشكلة البائع المتجول العامة (jTSP)، بينما يركز البحث على المستوى المنخفض على تخطيط المسار لوكيل واحد مقيد لضمان الالتزام بالقيود على المستوى العالي. يقدم المؤلفون ضمانات نظرية بشأن اكتمال الخوارزمية وفعاليتها، أو عدم الكفاءة المحدودة مع معلمة مقيدة.
تظهر التجارب الواسعة التي أجريت على مجموعتين من البيانات، CTS-MAPF وMG-MAPF، أن CTS-CBS تتفوق بشكل كبير على الخوارزميات الأساسية، حيث تحقق معدلات نجاح تصل إلى 20 مرة أعلى وتحسينات في وقت التشغيل تصل إلى 100 مرة، مع تضحيات طفيفة تقل عن 10% في جودة الحل. يتم تسليط الضوء على مرونة الخوارزمية من خلال قدرتها على ضبط حد عدم الكفاءة $\omega$، مما يسمح للمستخدمين بالتوازن بين جودة الحل والكفاءة. تؤكد اختبارات الروبوت العملية أيضًا على قابلية تطبيق الخوارزمية في السيناريوهات الواقعية، مما يجعلها أداة قيمة للممارسين في الروبوتات المستقلة وأتمتة المستودعات. تشمل اتجاهات البحث المستقبلية تعزيز كفاءة CTS-CBS، ودمج القيود الحركية، وتوسيع تطبيقها إلى السيناريوهات الديناميكية وطويلة الأمد.
النتائج
في هذا القسم، يتم تقييم أداء التعديلات المختلفة لخوارزمية CTS-CBS على مجموعة بيانات MG-MAPF، مع تسليط الضوء على قدرتها على معالجة كل من مشكلات CTS-MAPF وMG-MAPF. تم اقتراح ثلاث تعديلات: CTS-CBS-A، التي تزيل القيود النهائية للسماح بإكمال المهام بشكل مرن؛ CTS-CBS-B، التي تبسط مشكلة MG-MAPF من خلال تحويلها إلى متغير CTS-MAPF؛ وCTS-CBS-C، التي تجمع بين النهجين الأولين. تشمل مقاييس الأداء المستخدمة للمقارنة معدل النجاح، ووقت التشغيل، وجودة الحل، حيث يتم تقييم الأخيرة باستخدام نسبة جودة الحل (SQR).
تشير النتائج إلى أن CTS-CBS-A تحقق حلولًا قريبة من المثالية مع معدل نجاح ووقت تشغيل يتحسن بشكل كبير مع زيادة صعوبة الخريطة. بينما تضحي CTS-CBS-B ببعض المثالية، فإنها تظهر زيادة ملحوظة في الكفاءة، حيث تحقق معدلات نجاح أعلى وأوقات تشغيل أقل مقارنة بالخوارزميات الأساسية. تظهر CTS-CBS-C، كنهج هجين، خصائص أداء تختلف مع تعقيد المشكلة، حيث تنتقل من نقاط قوة CTS-CBS-A في السيناريوهات الأبسط إلى نقاط قوة CTS-CBS-B في السيناريوهات الأكثر تحديًا. بشكل عام، تتفوق تعديلات CTS-CBS بشكل ملحوظ على الخوارزميات الأساسية، حيث تحقق معدلات نجاح تصل إلى 20 مرة أعلى وأوقات تشغيل أسرع تصل إلى 100 مرة، مع تضحيات طفيفة في جودة الحل.
المناقشة
تناقش هذه القسم خوارزمية تسلسل المهام التعاونية – البحث القائم على الصراع (CTS-CBS)، التي تعالج مشكلة تسلسل المهام المتكاملة متعددة الوكلاء وتخطيط المسارات (MA-ITSPP)، وخاصة مشكلة تسلسل المهام التعاونية – البحث عن المسارات متعددة الوكلاء (CTS-MAPF). تعتمد الطرق الحالية بشكل أساسي على توسيع مشكلة البحث عن المسارات متعددة الوكلاء (MAPF) وغالبًا ما تعتمد على تقنيات البحث القائم على الصراع (CBS). ومع ذلك، لا توازن هذه الأساليب بشكل كافٍ بين جودة الحل وكفاءة الحساب لمشكلة CTS-MAPF. تدمج خوارزمية CTS-CBS خوارزميات مشكلة البائع المتجول (TSP) وMAPF لتوفير حلول مثالية أو حلول غير مثالية محدودة من خلال هيكل بحث من مستويين. يولد البحث على المستوى العالي غابة بحث من أشجار القيود التي تتوافق مع تسلسلات المهام المشتركة، بينما يستخدم البحث على المستوى المنخفض تخطيط المسار لوكيل واحد مقيد.
تشمل المساهمات الرئيسية للورقة تقديم CTS-CBS، التي تضمن الاكتمال والفعالية (أو عدم الكفاءة المحدودة)، وطريقة جديدة لحساب أفضل K حلول لمشكلة TSP المشتركة (jTSP)، وتعديلات على CTS-CBS لمشكلات MAPF متعددة الأهداف التي تتفوق على الخوارزميات الحالية. يتم تعزيز كفاءة الخوارزمية من خلال التحقق من الضرورة للعقد الجذرية الجديدة واستخدام معلمة حدودية لتحقيق التوازن بين المثالية والعبء الحسابي. تتضمن الورقة أيضًا اختبارات عملية للروبوتات للتحقق من قابلية تطبيق الخوارزمية في السيناريوهات الواقعية، مما يشير إلى إمكانياتها في تسلسل المهام الفعال وتخطيط المسارات في أنظمة متعددة الوكلاء.
DOI: https://doi.org/10.1109/jiot.2026.3663569
Publication Date: 2026-02-11
Author(s): Junkai Jiang et al.
Primary Topic: Robotic Path Planning Algorithms
Overview
This paper introduces a novel problem in Multi-Agent Pathfinding (MAPF) known as Collaborative Task Sequencing – Multi-Agent Pathfinding (CTS-MAPF), where agents must navigate collision-free paths while visiting designated task locations in a specified order before reaching their final destinations. To tackle this challenge, the authors propose the Collaborative Task Sequencing – Conflict-Based Search (CTS-CBS) algorithm, which employs a two-level search strategy. The high-level search generates a forest of trees representing joint task sequences based on the generalized Traveling Salesman Problem (jTSP) solution, while the low-level search focuses on constrained single-agent path planning to ensure adherence to high-level constraints. The authors provide theoretical guarantees regarding the algorithm’s completeness and optimality, or sub-optimality with a bounded parameter.
Extensive experiments conducted on two datasets, CTS-MAPF and MG-MAPF, reveal that CTS-CBS significantly outperforms baseline algorithms, achieving success rates up to 20 times higher and runtime improvements of up to 100 times, with only a minor sacrifice of less than 10% in solution quality. The algorithm’s flexibility is highlighted by its ability to adjust the sub-optimality bound $\omega$, allowing users to balance solution quality and efficiency. Practical robot tests further validate the algorithm’s applicability in real-world scenarios, making it a valuable tool for practitioners in autonomous robotics and warehouse automation. Future research directions include enhancing CTS-CBS’s efficiency, incorporating kinematic constraints, and extending its application to dynamic and lifelong scenarios.
Results
In this section, the performance of various adaptations of the CTS-CBS algorithm is evaluated on the MG-MAPF dataset, highlighting its capability to address both the CTS-MAPF and MG-MAPF problems. Three adaptations are proposed: CTS-CBS-A, which removes terminal constraints to allow flexible task completion; CTS-CBS-B, which simplifies the MG-MAPF problem by transforming it into a CTS-MAPF variant; and CTS-CBS-C, which combines the first two approaches. The performance metrics used for comparison include success rate, runtime, and solution quality, with the latter assessed using the Solution Quality Ratio (SQR).
The results indicate that CTS-CBS-A achieves near-optimal solutions with a success rate and runtime that improve significantly as the map difficulty increases. CTS-CBS-B, while sacrificing some optimality, demonstrates a marked increase in efficiency, achieving higher success rates and reduced runtimes compared to baselines. CTS-CBS-C, as a hybrid approach, shows performance characteristics that vary with problem complexity, transitioning from the strengths of CTS-CBS-A in simpler scenarios to those of CTS-CBS-B in more challenging ones. Overall, the adaptations of CTS-CBS markedly outperform baseline algorithms, achieving up to 20 times higher success rates and up to 100 times faster runtimes, with only a minor compromise in solution quality.
Discussion
The section discusses the Collaborative Task Sequencing – Conflict-Based Search (CTS-CBS) algorithm, which addresses the multi-agent integrated task sequencing and path planning (MA-ITSPP) problem, particularly the Collaborative Task Sequencing – Multi-Agent Path Finding (CTS-MAPF) problem. Existing methods primarily extend the Multi-Agent Path Finding (MAPF) problem and often rely on Conflict-Based Search (CBS) techniques. However, these approaches do not adequately balance solution quality and computational efficiency for CTS-MAPF. The CTS-CBS algorithm integrates Traveling Salesman Problem (TSP) and MAPF algorithms to provide optimal or bounded suboptimal solutions through a two-level search structure. The high-level search generates a search forest of constraint trees corresponding to joint task sequences, while the low-level search employs constrained single-agent path planning.
Key contributions of the paper include the introduction of CTS-CBS, which guarantees completeness and optimality (or bounded suboptimality), a novel method for computing K-best solutions for the joint TSP (jTSP), and adaptations of CTS-CBS for multi-goal MAPF problems that outperform existing algorithms. The algorithm’s efficiency is enhanced through necessity checking for new root nodes and the use of a boundary parameter to balance optimality and computational load. The paper also includes practical robot tests to validate the algorithm’s applicability in real-world scenarios, indicating its potential for effective task sequencing and path planning in multi-agent systems.