چگونه یک ربات می تواند مکان یابی، نقشه برداری و حرکت در یک محیط ناشناخته را پیدا کند؟

1. پیشگفتار با توسعه سریع فناوری رایانه، با تعمیق تحقیقات ربات‌ها و افزایش تقاضای مردم برای روبات‌ها، ربات‌هایی که می‌توانند هوشمندانه حرکت کنند و به صورت مستقل حرکت کنند، در کانون تحقیقات قرار گرفته‌اند. راه‌حل‌های عملی برای محلی‌سازی مستقل ربات در محیط شناخته شده و ایجاد نقشه موقعیت ربات شناخته شده وجود دارد. با این حال، در بسیاری از محیط ها، ربات نمی تواند از سیستم موقعیت یابی جهانی برای موقعیت یابی استفاده کند و به سختی می توان نقشه محیط کار ربات را از قبل به دست آورد. در این زمان، ربات باید یک نقشه در یک محیط کاملاً ناشناخته در شرایط نامشخص ایجاد کند و از نقشه برای موقعیت یابی و ناوبری مستقل استفاده کند. فناوری Slam (موقعیت یابی همزمان و ساخت نقشه) به عنوان فناوری اصلی و کلیدی برای تحقق ربات متحرک واقعا مستقل در نظر گرفته می شود. ربات از یک موقعیت نامعلوم در یک محیط ناشناخته شروع به حرکت می کند. در فرآیند جابجایی با توجه به تخمین موقعیت و داده های سنسور مکان یابی می شود و به تدریج بهبود می یابد و نقشه کاملی می سازد. این یک فرآیند اسلم است. در اسلم، ربات از حسگر خود برای شناسایی علامت مشخصه در محیط ناشناخته استفاده می کند و سپس مختصات جهانی ربات و علامت ویژگی را با توجه به موقعیت نسبی بین ربات و علامت مشخصه و قرائت کیلومتر شمار تخمین می زند. این موقعیت‌یابی آنلاین و ایجاد نقشه نیاز به حفظ اطلاعات دقیق بین ربات و علامت ویژگی دارد. در سال های اخیر تحقیقات اسلم پیشرفت زیادی داشته و در محیط های مختلفی مانند ربات، AR، VR، پهپاد، خلبان خودکار و غیره کاربرد داشته است.2. مسائل کلیدی اسلم 2.1 نمایش نقشه در حال حاضر، روش های رایج نمایش نقشه را می توان تقریباً به سه دسته تقسیم کرد: نمایش شبکه ای، نمایش اطلاعات هندسی و نمایش توپولوژی. هر روشی مزایا و معایب خاص خود را دارد. (1) نقشه اطلاعات هندسی نمایش نقشه اطلاعات هندسی به این معنی است که ربات اطلاعات ادراک محیط را جمع آوری می کند، ویژگی های هندسی انتزاعی بیشتری را استخراج می کند، مانند قطعات خط یا منحنی ها، و از این اطلاعات هندسی برای توصیف محیط استفاده می کند. مزیت: برای تخمین موقعیت و تشخیص هدف فشرده تر و راحت تر است. روش هندسی از فیلتر کالمن برای به دست آوردن دقت بالا و مقدار کمی از محاسبه در ناحیه محلی استفاده می کند. معایب: استخراج اطلاعات هندسی مستلزم پردازش اضافی اطلاعات ادراکی است و برای به دست آوردن نتایج به مقدار معینی داده ادراکی نیاز است. حفظ اطلاعات مختصات دقیق در محیط وسیع دشوار است. (2) نقشه شبکه نقشه شبکه برای تقسیم کل محیط به چندین شبکه با اندازه یکسان، و اشاره به وجود موانع برای هر شبکه است. مزیت: ایجاد و نگهداری آسان و سعی در حفظ انواع اطلاعات از کل محیط. با کمک نقشه، موقعیت یابی خود و برنامه ریزی مسیر را می توان به راحتی انجام داد. معایب: هنگامی که تعداد شبکه ها افزایش می یابد (در محیط های بزرگ یا زمانی که محیط با جزئیات تقسیم می شود)، حفظ نقشه دشوار می شود. در عین حال، فضای جستجوی زیادی در فرآیند موقعیت یابی وجود دارد. اگر الگوریتم ساده شده خوبی وجود نداشته باشد، تحقق کاربرد بلادرنگ دشوار است. (3) نقشه توپولوژیکی نقشه های توپولوژیکی بسیار انتزاعی هستند، به خصوص زمانی که محیط بزرگ و ساده باشد. در این روش محیط به صورت یک گراف به معنای توپولوژی نمایش داده می شود و گره های موجود در گراف با حالت و موقعیت مشخصی در محیط مطابقت دارند. اگر یک مسیر ارتباط مستقیم بین گره ها وجود داشته باشد، معادل گره های اتصال قوس در شکل است. مزیت: مساعد برای برنامه ریزی مسیر و کار بیشتر. فضای ذخیره سازی و جستجو نسبتاً کوچک است و راندمان محاسباتی بالا است. بسیاری از الگوریتم های جستجو و استدلال بالغ و کارآمد را می توان استفاده کرد. معایب: هنگام استفاده باید بر اساس شناسایی و تطبیق گره های توپولوژی باشد. به عنوان مثال، هنگامی که دو مکان بسیار مشابه در محیط وجود دارد، برای روش نقشه توپولوژی تعیین اینکه آیا آنها یک نقطه هستند یا خیر دشوار خواهد بود.2.2 شرح اطلاعات نامشخص زمانی که محیط کاملا ناشناخته است، اگر ربات بخواهد نقشه بسازد و راه برود، باید با کمک سنسورهای دیگر مانند کیلومترشمار، سونار، فاصله یاب لیزری، بینایی و ... اطلاعاتی را به دست آورد. با توجه به محدودیت های خود سنسور، درجات مختلفی از عدم قطعیت در اطلاعات سنجش وجود دارد. به عنوان مثال، عدم قطعیت فاصله یاب لیزری عمدتاً از خطای اندازه گیری فاصله و خطای زاویه اندازه گیری ناشی از چرخش بازتابنده و پراکندگی لیزر ناشی می شود. همانطور که در شکل بالا نشان داده شده است، عدم قطعیت اطلاعات درک شده به ناچار منجر به عدم امکان دقیق بودن مدل محیط ساخته شده می شود. به همین ترتیب، هنگام تصمیم گیری بر اساس مدل و ادراک، عدم قطعیت وجود دارد، یعنی عدم اطمینان متعدی است. روش‌های اندازه‌گیری عدم قطعیت عمدتاً شامل اندازه‌گیری احتمال، اندازه‌گیری اعتماد، اندازه‌گیری امکان، اندازه‌گیری فازی و نظریه شواهد است. در حال حاضر، اندازه گیری احتمال و اندازه گیری فازی به طور گسترده در ساخت نقشه AMR استفاده می شود. دو شکل اصلی اندازه‌گیری احتمال وجود دارد: (1) اطلاعات نامشخص با ویژگی‌های احتمال مانند میانگین، واریانس و کوواریانس توصیف می‌شوند. مزیت این روش اندازه گیری این است که مشخصه های احتمال مانند میانگین اهمیت هندسی واضحی دارند، اما عیب آن این است که فرمول محاسبه گسسته مشخصه های احتمال مشخص نشده است. (2) مدل احتمال برای توصیف اطلاعات نامطمئن، عمدتاً با استفاده از قانون بیز و فرضیه مارکوف استفاده می شود. مزیت این روش اندازه گیری این است که موقعیت، نگرش و اطلاعات محیطی ربات توسط مدل احتمال تصادفی توصیف می شود و استحکام بسیار خوبی دارد. عیب آن این است که مقدار محاسبه مدل احتمال بسیار زیاد است و احتمال قبلی مدل باید از قبل شناخته شده باشد که کاربرد عملی را دشوار می کند.2.3 استخراج ویژگی های مکان و محیطی خود محلی سازی ربات متحرک ارتباط نزدیکی با مدل سازی محیطی دارد. دقت مدل محیطی به دقت موقعیت یابی بستگی دارد و اجرای موقعیت یابی از مدل محیطی جدایی ناپذیر است. در محیط ناشناخته، ربات هیچ مرجعی ندارد و فقط می تواند به حسگرهای نادرست خود برای به دست آوردن اطلاعات خارجی تکیه کند، درست مانند یک مرد نابینا که در یک محیط ناآشنا دست و پا می زند. در این مورد، موقعیت یابی دشوار است. هم تعیین موقعیت نقشه و هم ایجاد نقشه با موقعیت یابی آسان است، اما موقعیت یابی بدون نقشه و ایجاد نقشه بدون موقعیت مانند مشکل "تخم مرغ" است. در تحقیقات موجود، راه‌حل‌های چنین مشکلاتی را می‌توان به دو دسته تقسیم کرد: (1) ضمن تکیه بر حسگرهای داخلی برای تخمین حرکت خود، از حسگرهای خارجی (مانند فاصله‌یاب لیزری، بینایی و غیره) برای درک محیط استفاده می‌شود. ، اطلاعات به دست آمده را تجزیه و تحلیل کنید، ویژگی های محیطی را استخراج و ذخیره کنید. در مرحله بعد، موقعیت خود آنها با مقایسه ویژگی های محیطی اصلاح می شود. اما این روش به توانایی به دست آوردن ویژگی های محیطی بستگی دارد. (2) با استفاده از انواع حسگرهای داخلی (از جمله کیلومترشمار، قطب نما، شتاب سنج، و غیره) که توسط خود حمل می شوند، خطای موقعیت یابی از طریق ترکیب انواع اطلاعات حسگر کاهش می یابد. اکثر الگوریتم های فیوژن مورد استفاده بر اساس فیلتر کالمن هستند. از آنجایی که این روش ها به اطلاعات خارجی اشاره نمی کنند، پس از رومینگ طولانی مدت، انباشت خطا زیاد خواهد بود. روش های استخراج ویژگی های محیطی عبارتند از: 1) . تبدیل Hough نوعی روش برای تشخیص خطوط و سایر منحنی ها بر اساس تصویر خاکستری است. این روش به خوشه ای از منحنی های خاص از پیش آماده شده نیاز دارد که بتوان آنها را جستجو کرد و پارامترهای منحنی را مطابق خوشه ای از منحنی ها در تصویر خاکستری نمایش داده شده تولید می کند. 2) . تجزیه و تحلیل خوشه بندی یک ابزار تشخیص داده است که برای نمونه های طبقه بندی نشده موثر است. در عین حال، هدف آن تقسیم اشیاء هدف به دسته های طبیعی یا کلاس های خوشه ای بر اساس شباهت یا فاصله است. هنگامی که دسته بندی شی استخراج شده ناشناخته است، فناوری خوشه بندی در مقایسه با Houghtransform فناوری موثرتری است. کلاس‌های خوشه‌ای باید بر روی «انسجام» متمرکز شوند، نه اینکه پراکنده و از هم گسسته باشند. برخی اوقات استخراج ویژگی های محیطی دشوار است. به عنوان مثال، زمانی که ویژگی های محیطی به اندازه کافی واضح نیستند یا اطلاعات حسگر کمی وجود دارد، به دست آوردن ویژگی های محیطی از اطلاعات یک بار مصرف دشوار است.2.4 انجمن داده ارتباط داده عبارت است از تطبیق دو علامت ویژگی برای تعیین اینکه آیا آنها با یک شی در محیط مطابقت دارند یا خیر. ارتباط داده ها در اسلم عمدتاً به انجام سه کار نیاز دارد: (1) تطبیق بین نقشه ها. (2) تطبیق علائم ویژگی. (3) تشخیص علائم ویژگی جدید. اگرچه ارتباط داده‌ها در زمینه‌های ردیابی هدف و همجوشی حسگر به خوبی حل شده است، این روش‌ها مقدار زیادی محاسبات دارند و نمی‌توانند نیازهای بلادرنگ اسلم را برآورده کنند. پیچیدگی ارتباط داده‌ها بین نشانه‌های M و نقشه‌ها با علامت n نمایی است با M. با فرض اینکه هر علامت مشاهده‌شده I یک تطابق احتمالی دارد، برای نشانه‌های M، لازم است مطابقت صحیح را در فضای نمایی = جستجو کنید. فضای جستجوی ارتباط داده ها با پیچیدگی محیط و خطای موقعیت یابی ربات مرتبط است. افزایش پیچیدگی محیط باعث افزایش m و افزایش خطا باعث افزایش Ni می شود.2.5 خطای تجمعی خطاها در اسلم عمدتاً از سه جنبه ناشی می شوند: (1) خطای مشاهده. (2) خطای کیلومتر شمار. (3) خطاهای ناشی از ارتباط داده های نادرست. هنگامی که ربات در محیط نقشه شناخته شده قرار می گیرد، ربات می تواند خطای کیلومترشمار را با مشاهده علامت مشخصه با موقعیت مشخص جبران کند. هر مشاهده باعث می شود که خطای موقعیت ربات به مجموع خطای مشاهده و خطای موقعیت علامت مشخصه گرایش پیدا کند. با این حال، در اسلم، چون موقعیت ربات و موقعیت علامت مشخصه در محیط ناشناخته است، اطلاعات مشاهده نمی تواند به طور موثر خطای کیلومتر شمار را تصحیح کند و خطای موقعیت ربات با فاصله حرکتی افزایش می یابد. روبات. افزایش خطای موقعیت ربات منجر به ارتباط اشتباه داده ها می شود که باعث افزایش خطای موقعیت علامت ویژگی می شود. به نوبه خود، خطای علامت ویژگی باعث افزایش خطای موقعیت ربات می شود. بنابراین، خطای موقعیت ربات ارتباط نزدیکی با خطای موقعیت علامت ویژگی دارد. تعامل بین آنها باعث می شود که تخمین موقعیت ربات و علامت مشخصه خطای تجمعی ایجاد کند که اطمینان از سازگاری نقشه دشوار است. 3. روش اجرای slam در حال حاضر، روش های slam را می توان به طور تقریبی به دو دسته تقسیم کرد: (1) روش های مبتنی بر مدل احتمال: slam کامل بر اساس فیلتر کالمن، فیلتر فشرده سازی، FastSLAM و غیره (2) روش های مدل غیر احتمالی: sm - اسلم، تطبیق اسکن، ارتباط داده ها، بر اساس منطق فازی و غیره.روش پیاده سازی 3.1 بر اساس فیلتر کالمن از نظر آماری، اسلم یک مشکل فیلترینگ است، یعنی تخمین وضعیت فعلی سیستم با توجه به وضعیت اولیه سیستم و اطلاعات مشاهده و اطلاعات کنترلی (خوانش کیلومتر شمار) از 0 تا t. در اسلم، وضعیت سیستم از وضعیت ربات R و اطلاعات نقشه m (شامل اطلاعات موقعیت هر علامت مشخصه) تشکیل شده است. با فرض اینکه مدل حرکت و مدل مشاهده سیستم، مدل‌های خطی با نویز گاوسی هستند و وضعیت سیستم تابع توزیع گاوسی است، با فیلتر کالمن می‌توان به اسلم پی برد. SLAM بر اساس فیلتر Kalman شامل دو مرحله است: پیش بینی وضعیت سیستم و به روز رسانی. در عین حال، نیاز به مدیریت اطلاعات نقشه مانند افزودن علائم ویژگی جدید و حذف علائم ویژگی دارد. فیلتر کالمن فرض می کند که سیستم یک سیستم خطی است، اما در عمل، مدل حرکت و مدل مشاهده ربات غیرخطی هستند. بنابراین معمولاً از فیلتر کالمن توسعه یافته استفاده می شود. فیلتر کالمن توسعه یافته تقریباً مدل غیرخطی را از طریق بسط تیلور مرتبه اول نشان می دهد. یکی دیگر از فیلترهای کالمن مناسب برای مدل های غیر خطی UKF (فیلتر کالمن بدون عطر) است. UKF از توزیع گاوسی شرطی برای تقریب یک توزیع احتمال پسینی استفاده می کند. در مقایسه با EKF، UKF دقت خطی سازی بالاتری دارد و نیازی به محاسبه ماتریس ژاکوبین ندارد. فیلتر کالمن به روش اساسی برای تحقق اسلم تبدیل شده است. ماتریس کوواریانس آن حاوی اطلاعات نامشخص موقعیت و نقشه ربات است. هنگامی که ربات به طور مداوم علائم مشخصه را در محیط مشاهده می کند، تعیین کننده هر زیر ماتریس ماتریس کوواریانس به طور یکنواخت کاهش می یابد. از نظر تئوری، وقتی تعداد مشاهدات به بی نهایت میل می کند، کوواریانس هر علامت مشخصه فقط به کوواریانس موقعیت شروع ربات مربوط می شود. پیچیدگی زمانی فیلتر کالمن O () است. از آنجایی که ربات فقط می تواند در هر بار چند علامت مشخصه را مشاهده کند، پیچیدگی زمانی SLAM بر اساس فیلتر کالمن را می توان به صورت O () بهینه کرد، و N نشان دهنده تعداد علائم ویژگی در نقشه است.3.2 روش نقشه فرعی محلی روش نقشه فرعی محلی، slam را از منظر فضا به برخی مسائل فرعی کوچکتر تجزیه می کند. مشکلات زیر باید در روش نقشه فرعی در نظر گرفته شود: (1) نحوه تقسیم نقشه های فرعی. (2) نحوه نمایش رابطه بین نقشه های فرعی. (3) نحوه انتقال اطلاعات نقشه فرعی به نقشه جهانی و اینکه آیا می توان سازگاری نقشه جهانی را تضمین کرد. ساده ترین روش نقشه فرعی محلی، تقسیم نقشه جهانی به نقشه های فرعی مستقل شامل تعداد ثابتی از نشانگرهای مشخصه بدون در نظر گرفتن رابطه بین نقشه های فرعی، و پیاده سازی slam به ترتیب در هر نقشه فرعی است. پیچیدگی زمانی این روش O (1) است. با این حال، به دلیل از دست دادن اطلاعات مفید که نشان دهنده همبستگی بین نقشه های فرعی مختلف است، این روش نمی تواند سازگاری جهانی نقشه را تضمین کند. در این رابطه لئونارد و همکاران. روش پیشنهادی DSM (نقشه برداری تصادفی جداشده). هر نقشه فرعی در DSM تخمین موقعیت ربات خود را ذخیره می کند. هنگامی که ربات از یک نقشه فرعی a وارد نقشه فرعی B دیگری می شود، روش مبتنی بر EKF برای انتقال اطلاعات در نقشه فرعی a به نقشه فرعی B استفاده می شود. بی ویلیامز و همکاران. یک روش slam بر اساس CLSF (فیلتر زیر نقشه محلی محدود) پیشنهاد کرد. CLSF یک نقشه فرعی با مختصات جهانی شناخته شده در نقشه ایجاد می کند. در طول پیشرفت ربات، فقط از اطلاعات مشاهده برای به روز رسانی موقعیت علائم ویژگی در ربات و نقشه فرعی محلی استفاده می شود و اطلاعات نقشه فرعی محلی در یک بازه زمانی مشخص به نقشه جهانی منتقل می شود. اگرچه آزمایش‌ها نشان می‌دهند که این دو الگوریتم عملکرد خوبی دارند، اما از نظر تئوری ثابت نشده است که بتوانند سازگاری نقشه‌ها را حفظ کنند. جی. گویوانت و همکاران. یک الگوریتم بهینه سازی slam cekf (فیلتر کالمن توسعه یافته فشرده) بدون از دست دادن اطلاعات پیشنهاد شده است. Cekf علائم مشخصه مشاهده شده را به قسمت های A و B تقسیم می کند. A نشان دهنده ناحیه مجاور موقعیت فعلی ربات است که به آن نقشه فرعی فعال می گویند. هنگامی که ربات در زیر نقشه فعال a حرکت می کند، موقعیت ربات و نقشه فرعی a در زمان واقعی با استفاده از اطلاعات مشاهده به روز می شوند و تاثیر اطلاعات مشاهده بر روی نقشه فرعی B با روش بازگشتی ثبت می شود. هنگامی که ربات از زیر نقشه فعال a خارج می شود، اطلاعات مشاهده بدون از دست دادن به زیر نقشه B منتقل می شود، به طوری که نقشه فرعی B در یک زمان به روز می شود و همزمان یک نقشه فرعی فعال جدید ایجاد می شود. زمان محاسبه این روش از دو بخش تشکیل شده است: نقشه فرعی slam در فعالیت که پیچیدگی زمانی آن O () است که تعداد علائم ویژگی در نقشه فرعی فعالیت a است. پیچیدگی زمانی به‌روزرسانی نقشه فرعی B O () است، که تعداد نشانه‌های ویژگی در نقشه B است. وقتی فاصله زمانی ادغام نقشه‌های فرعی زیاد باشد، cekf می‌تواند به طور موثر میزان محاسبه slam را کاهش دهد.3.3 روش همبستگی راه دیگر برای کاهش پیچیدگی slam نادیده گرفتن برخی از عناصر با مقادیر کوچکتر در ماتریس کوواریانس که نشان دهنده رابطه همبستگی است و تبدیل آن به یک ماتریس پراکنده است. با این حال، به دلیل از بین رفتن اطلاعات، ثبات نقشه را نیز از دست خواهد داد. با این حال، اگر بتوان نمایش ماتریس کوواریانس را طوری تغییر داد که بسیاری از عناصر آن نزدیک یا برابر با صفر باشند، می توان با خیال راحت از آن چشم پوشی کرد. SLAM بر اساس فیلتر اطلاعات گسترده (EIF) بر اساس این ایده است. EIF بیان مبتنی بر اطلاعات EKF است. تفاوت آنها در این است که اطلاعات را به اشکال مختلف نشان می دهند. EIF از ماتریس معکوس ماتریس کوواریانس برای نشان دادن اطلاعات نامشخص در اسلم استفاده می کند که به آن ماتریس اطلاعات می گویند. ادغام دو ماتریس اطلاعاتی نامرتبط را می توان به سادگی به صورت جمع دو ماتریس بیان کرد. هر عنصر غیر مورب در ماتریس اطلاعات نشان دهنده یک رابطه محدودیت بین ربات و علامت ویژگی یا بین علامت ویژگی و علامت ویژگی است. این روابط محدودیت را می توان به صورت محلی از طریق رابطه سیگنال وضعیت سیستم به روز کرد. این آپدیت محلی ماتریس اطلاعات را به ماتریس پراکنده تقریبی می کند و خطای نازک شدن آن بسیار کم است. بر این اساس S. Thrun و همکاران. یک روش slam مبتنی بر فیلتر اطلاعات پراکنده seif (فیلتر اطلاعات گسترده پراکنده) پیشنهاد کرد و ثابت کرد که پیچیدگی زمانی slam با استفاده از ماتریس اطلاعات پراکنده O (1) است. اگرچه EIF می تواند به طور موثر پیچیدگی زمانی اسلم را کاهش دهد، اما هنوز مشکلاتی در نمایش و مدیریت اطلاعات نقشه وجود دارد. اولاً، مقدار میانگین حالت سیستم را فقط می توان تقریباً در زمان ثابت محاسبه کرد. ثانیاً، در روش اسلم مبتنی بر EIF، افزودن و حذف علائم ویژگی ناخوشایند است.