DOI: https://doi.org/10.1109/tro.2026.3661719
تاريخ النشر: 2026-01-01
المؤلف: Zongyuan Shen وآخرون
الموضوع الرئيسي: خوارزميات تخطيط المسار الروبوتي
نظرة عامة
تقدم الورقة خوارزمية جديدة تعتمد على العينات، تُعرف باسم C*، مصممة للتخطيط لمسار التغطية في الوقت الحقيقي (CPP) في بيئات غير معروفة. تستخدم C* رسم بياني للتغطية السريعة (RCG)، الذي يتم بناؤه تدريجياً أثناء تنقل الروبوت من خلال أخذ عينات متقدمة من مساحة البحث. يعمل هذا RCG كرسم بياني كافٍ أدنى، حيث تمثل عقده نقاط الطريق المحتملة وتمثل حوافه أجزاء من مسار التغطية. تتعقب الخوارزمية تقدم التغطية بفعالية، وتولد مسار التغطية، وتساعد الروبوت في التنقل في حالات الطرق المسدودة.
تهدف C* إلى تقليل وقت التغطية من خلال إنتاج نمط تغطية ذهاباً وإياباً مع تحسين تغطية المناطق المعزولة المحلية، التي تُعرف بثقوب التغطية، والتي تحيط بها العقبات والمناطق المغطاة بالفعل. توضح الورقة تحليلياً أن C* تحقق تغطية كاملة للبيئات غير المعروفة. تجعل بساطتها وتعقيدها الحسابي المنخفض مناسبة للتطبيقات في الوقت الحقيقي. يتم التحقق من أداء C* من خلال محاكاة واسعة النطاق وتجارب مختبرية مع روبوت مستقل، تظهر مسارات قريبة من المثالية. تكشف تحليل مقارن مع سبع طرق CPP موجودة عن تحسينات كبيرة في وقت التغطية، وعدد المنعطفات، وطول المسار، ونسبة التداخل، مع منع فعال لثقوب التغطية. بالإضافة إلى ذلك، يتم تقييم C* في سيناريوهين مختلفين من CPP تشمل الروبوتات المقيدة بالطاقة وفرق الروبوتات المتعددة.
مقدمة
تسلط مقدمة هذه الورقة البحثية الضوء على الأهمية المتزايدة للروبوتات الخدمية المستقلة في تعزيز جودة حياة الإنسان من خلال مهام متنوعة، خاصة في سياق مشكلة تخطيط مسار التغطية (CPP). يعد CPP حاسماً للتطبيقات عبر مجالات متنوعة مثل الاستكشاف، والصناعة، والزراعة، والمهام المنزلية، وإزالة المخاطر، والدفاع. نظراً لأن هذه العمليات تحدث غالباً في بيئات غير معروفة، فإن تطوير طرق CPP المعتمدة على المستشعرات التي يمكن أن تعيد تخطيط مسارات التغطية بشكل تكيفي في الوقت الحقيقي أمر ضروري. تؤكد الورقة على الحاجة إلى خوارزميات CPP لضمان تغطية كاملة دون إنشاء ثقوب تغطية وسيطة، وتقليل وقت التغطية، وأن تكون فعالة حسابياً للتنفيذ في الوقت الحقيقي على منصات الروبوتات.
لمعالجة هذه التحديات، يقدم المؤلفون خوارزمية جديدة تُسمى C*، التي تستخدم نهجاً يعتمد على العينات استناداً إلى الرسوم البيانية العشوائية للتغطية (RCGs). تعمل RCGs كتمثيل رسومي أدنى للمساحة الخالية من العقبات، يتم بناؤه تدريجياً أثناء التنقل. تضمن C* تغطية كاملة مع استخدام نمط ذهاب وإياب وتتكيف لمنع ثقوب التغطية من خلال الاستفادة من الحلول من مشكلة بائع المتجول (TSP). يتم التحقق من فعالية الخوارزمية من خلال محاكاة عالية الدقة وتجارب في العالم الحقيقي، مما يظهر تحسينات كبيرة مقارنة بطرق CPP الموجودة من حيث وقت التغطية، وطول المسار، وعدد المنعطفات، ونسبة التداخل، مع الحفاظ على بساطتها وكفاءتها الحسابية للتطبيقات في الوقت الحقيقي.
طرق
تستعرض هذه القسم منهجيات مختلفة لتخطيط مسار التغطية (CPP)، مصنفة إلى عدة أنواع متميزة بناءً على خصائصها وتطبيقاتها. تُصنف طرق CPP بشكل أساسي على أنها عشوائية أو منهجية، حيث تضمن الطرق المنهجية تغطية كاملة في وقت محدود من خلال أنماط محددة، بينما قد تؤدي الطرق العشوائية إلى مسارات متداخلة. بالإضافة إلى ذلك، يتم تمييز طرق CPP حسب الأبعاد، حيث تكون الطرق ثنائية الأبعاد مناسبة للأسطح مثل الأرضيات والطرق ثلاثية الأبعاد مناسبة لبيئات مثل التضاريس تحت الماء أو الخرائط الجوية.
تُقسم الطرق أيضاً إلى فئات غير متصلة بالإنترنت ومتصلة بالإنترنت. تعتمد الطرق غير المتصلة على بيانات بيئية موجودة مسبقاً، مما قد يؤدي إلى مشاكل في الأداء إذا كانت المعلومات غير دقيقة. في المقابل، تتكيف الطرق المتصلة بالإنترنت في الوقت الحقيقي باستخدام بيانات من المستشعرات الموجودة على متن الطائرة. يناقش القسم أيضاً خوارزميات محددة تم تطويرها لكل من البيئات المعروفة وغير المعروفة، مع تسليط الضوء على استراتيجيات متنوعة مثل الطرق المعتمدة على الشبكات، والنهج القائمة على الشبكات العصبية، والخوارزميات المقيدة بالطاقة. تشمل التطورات الأخيرة أنظمة الروبوتات المتعددة وطرق تأخذ في الاعتبار قيود الطاقة، مما يضمن تغطية فعالة مع إدارة القيود التشغيلية لمنصات الروبوتات.
نتائج
تستند نتائج هذه الدراسة إلى ثلاث منهجيات رئيسية: محاكاة عالية الدقة، وتجارب في العالم الحقيقي أجريت مع روبوتات مستقلة في بيئة مختبرية محكومة، وتطبيقات عملية تعالج مشكلتين متميزتين في تخطيط المسار التعاوني (CPP). تركز المشكلة الأولى على الروبوتات المقيدة بالطاقة، بينما تفحص الثانية السيناريوهات التي تشمل فرق الروبوتات المتعددة.
تتحقق هذه الأساليب مجتمعة من فعالية الطريقة المقترحة، المعروفة باسم C*، مما يظهر قابليتها للتطبيق ومرونتها في سياقات تشغيلية متنوعة. تشير النتائج إلى أن C* تعالج بنجاح التحديات التي تطرحها كل من قيود الطاقة وتعقيدات تنسيق الروبوتات المتعددة، مما يبرز إمكانياتها للنشر في العالم الحقيقي في الأنظمة المستقلة.
مناقشة
يقدم قسم المناقشة في الورقة نظرة شاملة على خوارزمية C*، وهي طريقة جديدة تعتمد على العينات لتخطيط مسار التغطية (CPP) مصممة للتغطية التكيفية في الوقت الحقيقي للبيئات غير المعروفة. تميز خوارزمية C* نفسها عن الطرق التقليدية المعتمدة على الشبكات من خلال استخدام RCG يتم بناؤه بسرعة (رسم بياني للتغطية السريعة)، الذي يتم بناؤه تدريجياً من خلال أخذ عينات متقدمة من البيئة. يسمح هذا النهج بتوليد نقاط طريق فعالة والتنقل، مما يمكّن الروبوت من تغطية المناطق بشكل تكيفي مع تقليل التداخلات وأطوال المسارات. تشمل الميزات الرئيسية لـ C* قدرتها على الهروب من الطرق المسدودة باستخدام استراتيجية هروب من الطرق المسدودة التي تحدد العقد القريبة للعودة واستراتيجية استباقية لمنع ثقوب التغطية التي تكشف وتعالج المناطق المعزولة غير المغطاة في الموقع باستخدام مسارات قائمة على TSP.
تقارن الورقة أيضاً C* مع عدة خوارزميات أساسية، مبرزة مزاياها من حيث الكفاءة الحسابية، واختيار نقاط الطريق غير القريبة، ومنع ثقوب التغطية. على عكس الطرق الأساسية، التي غالباً ما تولد نقاط طريق قريبة وقد تؤدي إلى ثقوب تغطية تتطلب مسارات عودة إضافية، تكتشف C* بنشاط وتغطي هذه الثقوب أثناء تنقلها، مما يعزز الأداء العام للتغطية ويقلل من الوقت. يتم التأكيد على مساهمات خوارزمية C* من خلال محاكاة واسعة النطاق وتجارب في العالم الحقيقي تظهر أدائها المتفوق مقارنة بالطرق الموجودة، مما يجعلها حلاً واعداً لمجموعة متنوعة من التطبيقات في مهام تغطية الروبوتات.
DOI: https://doi.org/10.1109/tro.2026.3661719
Publication Date: 2026-01-01
Author(s): Zongyuan Shen et al.
Primary Topic: Robotic Path Planning Algorithms
Overview
The paper introduces a novel sample-based algorithm, denoted as C*, designed for real-time coverage path planning (CPP) in unknown environments. C* utilizes a Rapidly Covering Graph (RCG), which is incrementally built during robot navigation through progressive sampling of the search space. This RCG serves as a minimum-sufficient graph, where its nodes represent potential waypoints and edges represent segments of the coverage trajectory. The algorithm effectively tracks coverage progress, generates the coverage trajectory, and aids the robot in navigating dead-end situations.
C* aims to minimize coverage time by producing a back-and-forth coverage pattern while optimizing the coverage of local isolated regions, termed coverage holes, which are encircled by obstacles and already covered areas. The paper analytically demonstrates that C* achieves complete coverage of unknown environments. Its simplicity and low computational complexity make it suitable for real-time applications. The performance of C* is validated through extensive simulations and laboratory experiments with an autonomous robot, showing near-optimal trajectories. A comparative analysis with seven existing CPP methods reveals significant enhancements in coverage time, number of turns, trajectory length, and overlap ratio, while effectively preventing coverage holes. Additionally, C* is evaluated in two distinct CPP scenarios involving energy-constrained robots and multi-robot teams.
Introduction
The introduction of this research paper highlights the growing importance of autonomous service robots in enhancing human quality of life through various tasks, particularly in the context of the Coverage Path Planning (CPP) problem. CPP is crucial for applications across diverse fields such as exploration, industry, agriculture, household tasks, hazard removal, and defense. Given that these operations often occur in unknown environments, the development of sensor-based CPP methods that can adaptively replan coverage trajectories in real-time is essential. The paper emphasizes the need for CPP algorithms to ensure complete coverage without creating intermediate coverage holes, minimize coverage time, and be computationally efficient for real-time implementation on robotic platforms.
To address these challenges, the authors introduce a novel algorithm named C*, which utilizes a sample-based approach based on Randomized Coverage Graphs (RCGs). RCGs serve as a minimal graphical representation of the obstacle-free space, constructed incrementally during navigation. C* guarantees complete coverage while employing a back-and-forth pattern and adapts to prevent coverage holes by leveraging solutions from the Traveling Salesman Problem (TSP). The algorithm’s effectiveness is validated through high-fidelity simulations and real-world experiments, demonstrating significant improvements over existing CPP methods in terms of coverage time, trajectory length, number of turns, and overlap ratio, while remaining simple and computationally efficient for real-time applications.
Methods
The section outlines various methodologies for Coverage Path Planning (CPP), categorizing them into several distinct types based on their characteristics and applications. CPP methods are primarily classified as random or systematic, with systematic methods ensuring complete coverage in finite time through defined patterns, while random methods may lead to overlapping trajectories. Additionally, CPP methods are differentiated by dimensionality, with 2D methods applicable to surfaces like floors and 3D methods suited for environments such as underwater terrains or aerial mapping.
The methods are further divided into offline and online categories. Offline methods rely on pre-existing environmental data, which can lead to performance issues if the information is inaccurate. In contrast, online methods adapt in real-time using data from onboard sensors. The section also discusses specific algorithms developed for both known and unknown environments, highlighting various strategies such as grid-based methods, neural network approaches, and energy-constrained algorithms. Recent advancements include multi-robot systems and methods that consider energy limitations, ensuring efficient coverage while managing the operational constraints of robotic platforms.
Results
The results of this study are derived from three primary methodologies: high-fidelity simulations, real-world experiments conducted with autonomous robots in a controlled laboratory environment, and practical applications addressing two distinct Cooperative Path Planning (CPP) problems. The first problem focuses on energy-constrained robots, while the second examines scenarios involving multi-robot teams.
These approaches collectively validate the effectiveness of the proposed method, denoted as C*, demonstrating its applicability and robustness in various operational contexts. The findings indicate that C* successfully addresses the challenges posed by both energy limitations and the complexities of coordinating multiple robots, highlighting its potential for real-world deployment in autonomous systems.
Discussion
The discussion section of the paper presents a comprehensive overview of the C* algorithm, a novel sample-based coverage path planning (CPP) method designed for real-time adaptive coverage of unknown environments. The C* algorithm distinguishes itself from traditional grid-based CPP methods by utilizing a rapidly constructed RCG (Rapidly-exploring Coverage Graph), which is incrementally built through progressive sampling of the environment. This approach allows for efficient waypoint generation and navigation, enabling the robot to adaptively cover areas while minimizing overlaps and trajectory lengths. Key features of C* include its ability to escape dead-ends using a dead-end escape strategy that identifies nearby retreat nodes and a proactive coverage hole prevention strategy that detects and addresses isolated uncovered regions in situ using TSP-based trajectories.
The paper also compares C* with several baseline algorithms, highlighting its advantages in terms of computational efficiency, non-myopic waypoint selection, and the prevention of coverage holes. Unlike the baseline methods, which often generate myopic waypoints and may result in coverage holes that require additional return trajectories, C* actively detects and covers these holes during its navigation, thus enhancing overall coverage performance and reducing time. The contributions of the C* algorithm are underscored by extensive simulations and real-world experiments demonstrating its superior performance over existing methods, making it a promising solution for various applications in robotic coverage tasks.