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

مقاله 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]