هزینه محاسباتی در برابر دقت: مقایسه راه‌حل‌های فیلتر کالمن توسعه‌یافته و فیلتر ذره‌ای برای SLAM

در کنفرانس ملی هوش مصنوعی AAAI در سال ۲۰۰۲ در ادمونتون کانادا، محققانی چون مایکل مونتمرلو، سباستین ترون، دافنه کولر و بن وگ‌بریت راه‌حلی برای یک گلوگاه ریاضی ارائه کردند که رباتیک خودران را فلج کرده بود. الگوریتم آن‌ها با موفقیت ۵۰ هزار نشانگر متمایز را در یک محیط نقشه‌برداری کرد، که دستاوردی حیرت‌انگیز برای آن دوران محسوب می‌شد. پیش از این نمایش، الگوریتم‌های استاندارد صنعتی به سختی می‌توانستند چند صد ویژگی محیطی را مدیریت کنند قبل از آنکه پردازنده‌های آن زمان را تحت فشار قرار دهند. این ارائه یک تغییر اساسی در نحوه درک ربات‌ها از محیط اطرافشان ایجاد کرد و صنعت را از ماتریس‌های صلب به سمت حدس‌های احتمالی سوق داد.[2]

چالشی که آن‌ها حل می‌کردند، به عنوان مکان‌یابی و نقشه‌برداری همزمان (SLAM) شناخته می‌شود. وقتی یک ربات در یک محیط ناشناخته شروع به کار می‌کند، با یک تناقض عمیق روبرو است: برای اینکه بداند کجاست، به یک نقشه دقیق نیاز دارد، اما برای ساختن یک نقشه قابل اعتماد، باید دقیقاً بداند کجاست. هر بار که حسگرهای ربات یک دیوار، گوشه یا درخت – که به عنوان یک نشانگر (Landmark) شناخته می‌شود – را تشخیص می‌دهند، باید هم موقعیت آن نشانگر و هم موقعیت خود را نسبت به آن محاسبه کند. این کار باید با در نظر گرفتن دائمی نویز ذاتی، لغزش و انحراف در مسافت‌سنجی چرخ‌های آن انجام شود.

در طول دهه ۱۹۹۰، رویکرد ریاضی غالب برای حل این تناقض، فیلتر کالمن توسعه‌یافته (EKF) بود. EKF SLAM بر یک بردار وضعیت واحد و عظیم تکیه دارد که وضعیت (Pose) ربات را در کنار مختصات مطلق هر نشانگر شناخته شده ردیابی می‌کند. برای مدیریت عدم قطعیت این اندازه‌گیری‌ها، یک ماتریس کوواریانس عظیم را حفظ می‌کند که به طور مداوم به‌روزرسانی می‌شود. همانطور که مایکل کالوندر در یک تحلیل مقایسه‌ای برای مؤسسه فناوری فدرال سوئیس (EPFL) اشاره کرد: «اساساً، EKF SLAM و فست‌اِس‌لَم همان مسئله را حل می‌کنند، در حالی که از مدل‌های حرکتی و اندازه‌گیری احتمالی یکسانی استفاده می‌کنند.»[1]

نقص مهلک EKF SLAM در معماری همان ماتریس کوواریانس نهفته است. از آنجایی که این فیلتر همبستگی بین وضعیت ربات و تک‌تک نشانگرها را ردیابی می‌کند، ماتریس با مقیاس درجه دوم نسبت به محیط رشد می‌کند. همانطور که مونتمرلو و تیمش در مقاله بنیادی سال ۲۰۰۲ خود نوشتند: «الگوریتم‌های مبتنی بر فیلتر کالمن، برای مثال، برای گنجاندن هر مشاهده حسگر، به زمانی نیاز دارند که درجه دوم تعداد نشانگرها باشد.» از نظر الگوریتمی، این یک پیچیدگی زمانی O(K²) است، که در آن K تعداد نشانگرها است. یک اتاق با ۱۰۰ نشانگر به ۱۰٬۰۰۰ محاسبه در هر مرحله نیاز دارد؛ یک ساختمان با ۱٬۰۰۰ نشانگر به یک میلیون محاسبه نیاز دارد که به سرعت سیستم را از کار می‌اندازد.[2]

مقاله AAAI سال ۲۰۰۲، فست‌اِس‌لَم را معرفی کرد که با استفاده از یک فیلتر ذره‌ای رائو-بلک‌ولایز شده، این دیوار درجه دوم را دور زد. فست‌اِس‌لَم به جای حفظ یک ماتریس غول‌پیکر از قطعیت مطلق، صدها یا هزاران «ذره» مجازی تولید می‌کند. هر ذره یک مسیر خاص و حدسی را نشان می‌دهد که ربات ممکن است در اتاق طی کرده باشد. از آنجایی که مسیر در واقعیت مجزای هر ذره، شناخته شده فرض می‌شود، مکان‌های نشانگرها به طور مشروط از یکدیگر مستقل می‌شوند و پیوندهای ریاضی را که باعث باد کردن ماتریس EKF می‌شدند، قطع می‌کنند.[2]

این تجزیه (فاکتورگیری) اساساً ریاضیات ناوبری خودران را تغییر داد. فست‌اِس‌لَم به جای ماتریس O(K²)، به پیچیدگی O(M log K) دست یافت، که در آن M تعداد ذرات است. در داخل هر ذره، الگوریتم فقط باید ماتریس‌های کوواریانس کوچک ۲×۲ را برای نشانگرها ذخیره کند. هزینه محاسباتی به جای مقیاس درجه دوم، به صورت لگاریتمی با اندازه نقشه مقیاس می‌شود. این کارایی الگوریتمی دقیقاً همان چیزی است که تیم استنفورد توانستند با آن ۵۰ هزار نشانگر را بدون از کار انداختن سخت‌افزار خود پردازش کنند و دریچه‌ای به سوی نقشه‌برداری در مقیاس بزرگ در فضای باز گشودند.[1][2]

با این حال، فست‌اِس‌لَم حالت شکست منحصر به فرد خود را معرفی کرد: تخلیه ذرات. اگر رباتی در یک محیط بسیار مبهم حرکت کند – مانند یک راهروی طولانی و بدون ویژگی با درهای یکسان – الگوریتم برای حذف مسیرهای نادرست، به نمونه‌برداری مجدد آماری متکی است. با گذشت زمان، این نمونه‌برداری مجدد تهاجمی می‌تواند به طور تصادفی مسیر واقعی را کنار بگذارد و ربات را کاملاً گم کند، بدون هیچ راهی برای بازیابی. در حالی که EKF SLAM به طور قابل پیش‌بینی به دلیل فرسودگی پردازنده شکست می‌خورد، فست‌اِس‌لَم زمانی شکست می‌خورد که حدس‌های آماری آن تحت عدم قطعیت پایدار فرو می‌ریزند و آن را در محیط‌های کم‌تراکم شکننده می‌سازد.[1][6]

در طول دهه گذشته، صنعت رباتیک تا حد زیادی از هر دو روش EKF خالص و فیلتر ذره‌ای خالص برای نقشه‌برداری سه‌بعدی در مقیاس بزرگ عبور کرده است. در سال ۲۰۱۸، محققانی چون یان‌هاو ژانگ، تنگ ژانگ و شودونگ هوانگ در دانشگاه فناوری سیدنی (UTS) یک مقایسه جامع منتشر کردند که نشان می‌داد SLAM مبتنی بر بهینه‌سازی – به ویژه بهینه‌سازی کمترین مربعات غیرخطی – در اکثر سناریوهای عملی، دقت EKF ناوردا را برابر یا از آن فراتر می‌رود. این تحقیق آنچه را که متخصصان در این حوزه مشاهده می‌کردند، تأیید کرد: فیلترینگ در حال واگذاری میدان به بهینه‌سازی بود.[3]

این تغییر اکنون به اجماع صنعت تبدیل شده است. همانطور که یک تحلیل فنی با امتیاز بالا در سال ۲۰۲۲ در Robotics Stack Exchange توضیح داد، سیستم‌های سه‌بعدی مدرن تقریباً به طور انحصاری بر بهینه‌سازی گراف وضعیت (Pose-Graph Optimization) تکیه دارند که اغلب به عنوان گراف‌های فاکتور (Factor Graphs) شناخته می‌شوند. ریاضیات زیربنایی ارتباط نزدیکی دارند، اما نحوه اجرا متفاوت است. یک مهندس خاطرنشان کرد: «گراف‌های فاکتور و فیلترهای کالمن توسعه‌یافته در واقع مسئله را دقیقاً به یک شکل حل می‌کنند»، و اشاره کرد که گراف‌های فاکتور صرفاً تکراری هستند و قالب‌بندی متفاوتی دارند، که به آن‌ها اجازه می‌دهد هنگام رسیدن داده‌های جدید، خطاهای گذشته را مجدداً ارزیابی کنند.[5]

گذار از EKF به فست‌اِس‌لَم و سپس به بهینه‌سازی گراف، مسیر دقیق سخت‌افزار محاسباتی خودران را ترسیم می‌کند. سیستم‌های اولیه برای بقا بر روی پردازنده‌های مرکزی محدود، به ترفندهای ریاضی ظریف و فیلترینگ سخت‌گیرانه نیاز داشتند، در حالی که سیستم‌های مدرن از حافظه فراوان و پردازش موازی برای بهینه‌سازی کل مسیرها به طور همزمان بهره می‌برند. دستاورد ۵۰ هزار نشانگری سال ۲۰۰۲ ثابت کرد که نقشه‌برداری در مقیاس بزرگ امکان‌پذیر است؛ گراف‌های فاکتور امروزی صرفاً آن را به اندازه کافی قابل اعتماد می‌سازند تا بتوان به وسایل نقلیه مسافربری در بزرگراه‌های عمومی اعتماد کرد. با ادامه تکامل الگوریتم‌ها، تنش اساسی بین هزینه محاسباتی و دقت مکان‌یابی همچنان چالش اصلی مهندسی این حوزه باقی مانده است.[2][3][7]