محلی‌سازی و نقشه‌برداری همزمان

نقشه‌برداری و ناوبری رباتیک، مکانیابی و نقشه‌برداری همزمان (به انگلیسی: simultaneous localization and mapping (SLAM))مساله ی محاسباتی برای به‌روزرسانی نقشه یک محیط ناشناخته است در حالی که ربات به‌ طور همزمان مکان خود را در طی مسیر در نقشه حدس میزند. در ابتدای امر به یاد ضرب‌المثل معروف مرغ یا تخم مرغ می‌افتیم اما در واقع الگوریتم‌های زیادی هستند که برای حل مسئله در زمان قابل قبول، شناخته شده‌اند. روش‌های تقریبی بسیاری مانند فیلتر ذرات، کالمن فیلتر توسعه‌یافته و گراف اسلم (انگلیسی: GraphSLAM) معرفی شده‌اند. الگوریتم‌های SLAM با منابع موجود متناسب هستند از این رو به دنبال مدل ایدئال نیستند، بلکه به دنبال انطباق عملیاتی هستند. این موارد در خودروی خودران، پهپاد، وسایل نقلیه خودکار زیر آب، سطح‌نورد، ربات‌های جدید داخلی و حتی درون بدن انسان نیز استفاده می‌شوند.

تعریف مسئله

با توجه به مجموعه‌ای از مشاهدات سنسور$o_{t}$ در طول مراحل زمانی گسسته $t$ مسئله SLAM محاسبه یک تخمین از مکان‌یاب $x_{t}$و نقشه محیط$m_{t}$است. همه مقادیر معمولاً احتمالاتی هستند، بنابراین داریم:

$P(m_{t},x_{t}|o_{1:t})$

استفاده از قضیه بیز، چارچوبی برای به‌روزرسانی مداوم موقعیت جغرافیایی ارائه می‌دهد، البته با توجه به یک نگاشت و یک تابع انتقال:$P(x_{t}|x_{t-1})$

$P(x_{t}|o_{1:t},m_{t})=\sum _{m_{t-1}}P(o_{t}|x_{t},m_{t})\sum _{x_{t-1}}P(x_{t}|x_{t-1})P(x_{t-1}|m_{t},o_{1:t-1})/Z$

به همین ترتیب نگاشت می‌تواند به صورت پی‌درپی به‌روز شود.

$P(m_{t}|x_{t},o_{1:t})=\sum _{x_{t}}\sum _{m_{t}}P(m_{t}|x_{t},m_{t-1},o_{t})P(m_{t-1},x_{t}|o_{1:t-1},m_{t-1})$

مانند بسیاری از مسائل استنتاج، راه‌حل‌هایی برای استنتاج این دو متغیر را می‌توان به یک راه‌حل بهینه با به‌روزرسانی متناوب به شکل الگوریتم امید ریاضی–بیشینه کردن یافت.

الگوریتم‌ها

تکنیک‌های آماری که برای تخمین معادلات بالا استفاده می‌شوند عبارتند از فیلتر کالمان و فیلترهای ذرات (معروف به روش‌های مونت‌کارلو). آن‌ها تخمینی از تابع احتمال پوستریوری را برای حالت ربات و پارامترهای نقشه ارائه می‌کنند. روش‌های تنظیم برآورد معمولاً بر اساس انتشار اینتروال هستند. آن‌ها مجموعه‌ای را فراهم می‌کنند که حالت ربات و تخمین مجموعه‌ای از نقشه را دربرگرفته‌است. یکی دیگر از تکنیک‌های محبوب SLAM با استفاده از داده‌های تصویری، تنظیم بسته نرم‌افزاری و به‌طور عمومی‌تر برآوردگر بیشینه‌گر احتمال پسین (انگلیسی: Maximum a posteriori estimation) است که به‌طور مشترک حالت و موقعیت نقطه عطف، افزایش انطباق به نقشه را تخمین می‌زند و در سیستم‌های SLAM تجاری مانند Google's ARCore مورد استفاده قرار می‌گیرد. برآوردگرهای MAP، محتمل‌ترین توضیحات برای ربات را محاسبه می‌کنند. الگوریتم‌های SLAM جدید یک حوزه پژوهش خاص هستند، و اغلب با فرضیات متفاوت در مورد انواع نقشه‌ها، حسگرها و مدل‌ها هدایت می‌شوند. بسیاری از سیستم‌های SLAM را می‌توان ترکیبی از انتخاب هر کدام از موارد دید.

مپ کردن

نقشه‌های توپولوژیکی یک روش بازنمایی محیطی است که اتصال (یعنی توپولوژی) محیط را جذب می‌کند تا نقشهٔ هندسی دقیق را ایجاد کند. روش‌های توپولوژیکال برای اعمال ثبات جهانی در الگوریتم‌های SLAM متریک استفاده شده‌اند. در مقابل، نقشه‌های شبکه از آرایه‌های (معمولاً مربع یا شش‌ضلعی) سلول‌های گسسته برای نشان دادن یک جهان توپولوژیکی استفاده می‌کنند، و نتیجه می‌گیرند که کدام سلول‌ها اشغال شده‌اند. به‌طور معمول، برای ساده‌سازی محاسبات، سلول‌ها به صورت آماری مستقل فرض می‌شوند. با توجه به چنین فرضی، $P(m_{t}|x_{t},m_{t-1},o_{t})$اگر سلول‌های نقشه جدید با مشاهدات $o_{t}$در مکان $x_{t}$سازگار باشند، برای مقدار ۱ تنظیم می‌شوند (مقدار ۱ را می‌گیرند) و در غیر این صورت مقدار ۰ را می‌گیرند. اغلب خودروهای خودگردان با استفاده از اطلاعات نقشه ای که از پیش ثبت کرده‌اند، مشکل نقشه‌برداری را ساده‌تر می‌کنند. داده‌های بصری برچسب گذاری شده از مکان مانند گوگل استریت ویو نیز ممکن است به عنوان بخشی از نقشه‌ها استفاده شود. اساساً این سیستم‌ها مشکل SLAM را بهبود می‌بخشند تا کار ساده‌تری برای محلی سازی انجام شود.

حسگر

SLAM همواره از انواع مختلفی از حسگرها استفاده می‌کند، و قدرت و محدودیت‌های انواع مختلف حسگر، یکی از محرک‌های اصلی الگوریتم‌های جدید بوده‌است. انواع مختلفی از سنسور باعث ایجاد الگوریتم‌های مختلفی می‌شوند که فرضیات آن‌ها برای حسگرها بسیار مناسب هستند. در یک سطح خاص، اسکن لیزری یا ویژگی‌های بصری جزئیات بسیاری از نقاط را در یک ناحیه فراهم می‌کند و گاهی چنین نتیجه ای برای SLAM را غیر ضروری می‌سازد. در نقطه مقابل، سنسورهای تاکتیل به شدت پراکنده هستند چون تنها حاوی اطلاعات مربوط به نقاط بسیار نزدیک به عامل هستند، بنابراین آن‌ها به مدل‌های قبلی قوی نیاز دارند تا مشکل را جبران کنند.

مدل‌های سنسور به رویکردهای مبتنی بر نقطه پایه و داده‌های خام تقسیم می‌شوند.

سنسورهای نوری ممکن است یک بعدی (پرتوی منفرد) یا دو بعدی - (مسافت‌یاب لیزری)، سه بعدی با تعریف بالا، سه بعدی فلش ریدر، سنسور سونار دو یا سه بعدی و دوربین عکاسی یک یا دو بعدی باشند. از سال ۲۰۰۵، تحقیقات بسیاری در VSLAM با استفاده از سنسورهای دوربین (دوربین)، به دلیل افزایش حضور دوربین‌ها مثل دستگاه‌های تلفن همراه، انجام شده‌است. سنسورهای Visual و LIDAR به اندازه کافی آموزنده هستند که در بسیاری از موارد امکان استخراج نقاط برجسته را فراهم می‌کنند. مدل‌های دیگر Slam، لمسی، رادار و وایفای هستند. اخیراً، مخابرات بی‌سیم شبه نوری را به عنوان تابعی از معیارهای بی‌سیم نامنظم استفاده می‌کنند. یک نوع SLAM برای عابران پیاده از یک واحد اندازه‌گیری درونی مجهز در کفش به عنوان حسگر اصلی استفاده می‌کند و می‌توانند نقشهٔ ساختمان‌ها را به صورت خودکار ایجاد کنند. برای برخی از کاربردهای خارج از فضای باز، نیاز به SLAM به دلیل حسگرهای تفاضلی دقیق GPS به‌طور کامل حذف شده‌است. از دیدگاه SLAM، این‌ها ممکن است به عنوان سنسورهای مکان‌یاب در نظر گرفته شوند که به‌طور کامل بر این مسئله تسلط دارند.

مدل‌سازی کینماتیک

$P(x_{t}|x_{t-1})$بیانگر سینماتیک این مدل است که شامل اطلاعات مربوط به دستورهای داده شده به یک ربات می‌باشد. به عنوان بخشی از مدل، که به سینماتیک ربات مربوط می‌شود، برای بهبود تخمین‌های حساسیت در شرایط نویز ذاتی و محیط می‌باشد. مدل دینامیک، به کمک سنسورهای مختلف، مدل‌های خطای جزئی مختلف را متعادل می‌کند و در نهایت در یک نمایش مجازی به عنوان نقشه با موقعیت و سمت ربات به عنوان ابری از احتمال استفاده می‌کند. نگاشت، آخرین تصویر از چنین مدلی است، نقشه یا نمایش یا عبارت انتزاعی برای مدل است. برای ربات‌های دو بعدی سینماتیک معمولاً با ترکیبی از چرخش و فرمان «حرکت به جلو» ارائه می‌شود که با نویز موتور اضافی اجرا می‌شوند. توزیع ناشی از نویز مستقل در جهت زاویه ای و خطی گاوسی نیستند، اما اغلب توسط یک عبارت گاوسی تقریب زده می‌شود.

اشیاء چندگانه

مسائل مربوط به ارتباط داده‌ها و پیچیدگی محاسباتی هنوز به‌طور کامل حل نشده‌است، به عنوان مثال شناسایی نشانه‌های چندگانه. یک پیشرفت قابل‌توجه در تاریخچه SLAM مبتنی بر ویژگی شامل بررسی مجدد اساس احتمالاتی برای مکانیزیسیون و نقشه‌برداری همزمان (SLAM) است.

اشیا متحرک

محیط‌های غیر ایستا، مانند آن‌هایی که حاوی وسایل نقلیه و عابران پیاده هستند، به چالش‌های تحقیقاتی حاضر ادامه می‌دهند.SLAM با DATMO مدلی است که اشیا در حال حرکت را به روشی مشابه به خود نماینده ردیابی می‌کند.

بسته شدن حلقه

بسته بودن حلقه، مسئله تشخیص مکان بازدید شده قبلی و به روز رسانی براساس آن است البته می‌تواند یک مشکل باشد زیرا خطاهای مدل یا الگوریتم می‌توانند موقعیت‌های کمتری را تعیین کنند. در این روش، الگوریتم دوم را برای محاسبه برخی از انواع اندازه‌گیری حسگر اعمال می‌کنند، و زمانی که تطابقی تشخیص داده می‌شود، موقعیت را تعیین می‌کند. به عنوان مثال، این کار را می‌توان با ذخیره‌سازی و مقایسه مجموعه‌ای از بردارهای ویژه مشخصه‌های تبدیل ویژگی مقیاس‌نابسته ازهر مکان مورد بازدید قبلی انجام داد.

شناسایی

" SLAM فعال " مسئله ترکیبی SLAM را با تصمیم‌گیری در مورد محل حرکت بعدی به منظور ساخت نقشه به مؤثرترین شکل ممکن مورد مطالعه قرار می‌دهد.SLAM فعال معمولاً با تقریب آنتروپی نقشه تحت اقدامات فرضی انجام می‌شود." SLAM چندعامله این مسئله را در مورد چندین روبات گسترش می‌دهد که خودشان را برای کاوش بهینه هماهنگ می‌کنند.

الهامات زیستی

در علم اعصاب، هیپوکامپ، در محاسبات SLAM مانند سلول‌های میانی دخیل است و اساس نظام‌های زیستی الهام‌گرفته شده از زیستی مانند RatSLAM را تشکیل داده‌است.

پیچیدگی

محققان و متخصصان هوش مصنوعی برای حل مشکل SLAM در محیط‌های عملی تلاش کرده‌اند:یعنی، به مقدار زیادی توان محاسباتی نیاز داشت تا یک منطقه بزرگ را حس کرده و داده‌های حاصل را برای هر دو نقشه و محلی سازی پردازش نماید. در بررسی‌های سال ۲۰۰۸ این موضوع به‌طور خلاصه بیان شده‌است :SLAM یکی از چالش‌های بنیادی رباتیک است.[اما] به نظر می‌رسد که تقریباً تمام رویکردهای فعلی نمی‌توانند نقشه‌های ثابت را برای مناطق بزرگ انجام دهند، زیرا در زمانی که سناریو بزرگ‌تر است افزایش هزینه محاسباتی و عدم قطعیت ایجاد می‌شود. به‌طور کلی، راه‌حل‌های SLAM سه بعدی از نظر محاسباتی بسیار پیچیده هستند.

ربات‌هایی که از سیستم‌های تعبیه‌شده‌استفاده می‌کنند نمی‌توانند به‌طور کامل به دلیل محدودیت‌های خود در قدرت محاسبه، به‌طور کامل پیاده‌سازی شوند. نگویین، هراتی و سیگ وارت در سال ۲۰۰۷ یک راه‌حل سریع و سبک‌وزن به نام OrthoSLAM ارائه دادند که پیچیدگی محیط را به صفحات متعامد تجزیه می‌کند.

پیاده‌سازی

الگوریتم‌های مختلف SLAM در سیستم عامل روبات (ROS) منبع باز استفاده می‌شود که اغلب با استفاده از کتابخانه ابر نقطه برای نقشه‌های سه‌بعدی یا ویژگی‌های بصری مورد استفاده قرار می‌گیرد.

تاریخچه

کار اصلی برای SLAM توسط اسمیت و چسمن در سال ۱۹۸۶ انجام شد. کارهای پیشگام دیگری در این زمینه توسط گروه تحقیقاتی هیو اف در دهه ۱۹۹۰ انجام شد. این یافته، انگیزهٔ جستجوی الگوریتم‌هایی شد که محاسباتی قابل ردیابی و تقریبی برای راه حل، ارائه می‌دهند. امروزه از الگوریتم‌های SLAM در تولید ربات‌های جاروبرقی به صورت انبوه استفاده شده‌است.

جستارهای وابسته

• فهرست روش‌های SLAM
• عکاسی محاسباتی
• فیلتر کالمان
• جعبه ابزار برنامه‌ریزی موبایل
• مکان‌یابی مو نت کارلو
• چالش بین‌المللی روباتیک چندمنظوره
• رباتیک Neato
• فیلتر ذرات
• تانگو (پلتفرم)
• ثبت تصویر
• نگاشت روباتیک
• تصویرسنجی
• ساختار از حرکت

منابع

https://en.wikipedia.org/wiki/Simultaneous_localization_and_mapping