رویکرد احتمالی به مکان یابی خود تحت عدم قطعیت
فهرست:
- بومی سازی چیست و چرا یک ربات به آن نیاز دارد؟
- چرا از ابزارهای احتمالی برای محاسبه محلی سازی استفاده می کنیم؟
- یک مثال سرتاسر: چگونه از الگوریتم های بیزی برای تعیین موقعیت یک ربات در شرایط عدم قطعیت استفاده کنیم؟
چگونه خودروهای خودران با سرعت 60 مایل در ساعت می توانند در یک خط بمانند؟ چگونه یک ربات آی می تواند از سقوط از پله ها جلوگیری کند؟ رباتهای تحویلدهنده چگونه میتوانند بفهمند که به سمت مشتری گرسنه مناسبی میروند؟ اینها تنها تعدادی از سوالاتی است که خودروهای خودران بدون دخالت انسان باید به آنها پاسخ دهند.
1. بومی سازی چیست؟ و چرا به ربات نیاز دارد؟
همانطور که می توانید تصور کنید، مکان دقیق وسیله نقلیه برای اینکه آیا وسیله نقلیه خودران بتواند به طور موثر و ایمن وظایف خود را انجام دهد بسیار مهم است. فرآیند تعیین موقعیت خودرو از روی داده های حسگر را محلی سازی می گویند. دقت مکان یابی با حسگرهایی که اطلاعات را اضافه می کنند افزایش می یابد و با حرکت خودرو کاهش می یابد که نویز را اضافه می کند.
2. چرا از ابزارهای احتمالی برای محاسبه محلی سازی استفاده می شود؟
هنگامی که نه حسگرها و نه حرکت 100٪ دقیق نیستند، می توان از ابزارهای احتمالی برای بهبود دقت مکان استفاده کرد.
احتمال چیست؟
طبق تعریف فرهنگ لغت، احتمال “توضیح عددی از احتمال وقوع یک رویداد” (ویکی پدیا) است. با این حال، وقتی صحبت از معنای احتمال می شود، پاسخ به این سادگی نیست. تفاسیر رقابتی از احتمال از دو اردوگاه اصلی، مکرر گرایان و بیزی ها وجود دارد.
این زود زود رویکرد احتمال را به عنوان یک فرکانس نسبی در طول زمان تفسیر می کند. اگر یک آزمایش را چند بار تکرار کنم چند بار به نتیجه مطلوب می رسم؟
این رویکرد عینی است زیرا هرکسی که آزمایشها را انجام میدهد (مثلاً ورق زدن یک سکه) همان نتیجه را در دراز مدت خواهد گرفت.
این بیزی رویکرد احتمال را به عنوان درجه اطمینان از وقوع یک رویداد تفسیر می کند. چقدر مطمئن هستم که با توجه به تخصص و داده های موجود به نتیجه مطلوب خواهم رسید؟ این رویکرد ذهنی است زیرا وضعیت فعلی باور را با ترکیب دانش قبلی (ذهنی) و داده های تجربی شناخته شده تا به امروز نشان می دهد. این اجازه می دهد تا احتمال یک رویداد واحد را تخمین بزنیم که نمی توانیم چندین بار انجام دهیم، در جایی که معنای فرکانس اعمال نمی شود.
به عنوان مثال، اگر احتمال اینکه یک تاریخ بعد از اولین قرار برای شما پیام ارسال کند 0.8 باشد، ما 80% مطمئن هستیم که به شما خوش گذشته است و آن شخص به شما پیام خواهد داد. ما انجام ندهید به این معنی که اگر اولین قرار را بارها و بارها تکرار کنید، 80٪ مواقع پیامک ارسال می کنند.
مزایای احتمال بیزی چیست؟
احتمال بیزی به ما امکان می دهد درجه اعتقاد خود را کمیت کنیم و آن را در پرتو شواهد جدید به روز کنیم.
در زمینه ما، P(H) حدس اولیه ما از موقعیت ربات است، و P(H|E) حدس به روز شده ما پس از اندازه گیری شواهد حسگر E است.
توزیع احتمال فرضیه اطمینان ما را در موقعیت ربات کمیت می کند.
فرضیه ممکن است با توجه به شواهد تغییر کند
هر چه داده های حسگرها آموزنده تر و دقیق تر باشند، تأثیر بیشتری خواهد داشت. اگر سنسور کامل باشد، موقعیت ربات با خواندن سنسور هماهنگ می شود، در غیر این صورت، اگر داده های حسگر بسیار نویز یا بی اطلاع باشند، موقعیت ربات ثابت می ماند.
به روز رسانی ها می توانند چندین منبع شواهد را ترکیب کنند
ما می توانیم قانون بیز را برای ترکیب چندین منبع داده با استفاده از قانون زنجیره ای که به عنوان قانون کلی محصول نیز شناخته می شود، فرموله کنیم. این اجازه می دهد تا توزیع مشترک شواهد متعدد را به یک محصول احتمالات مشروط ساده کنید.
به عنوان مثال، ما اغلب از GPS برای پیمایش از مکان فعلی خود استفاده می کنیم، اما GPS در آسمان صاف بهترین عملکرد را دارد و دقت آن به چند متر محدود می شود. خودروهای خودران نمیتوانند برای ماندن در مسیری به عرض چندین متر و حرکت در تونلها یا پارکینگهای زیرزمینی تنها به GPS تکیه کنند. وسایل نقلیه خودران می توانند با افزودن منابع اطلاعاتی بیشتر مانند دوربین، کاستی های GPS را جبران کنند.
3. یک مثال سرتاسر: چگونه از الگوریتم های بیزی برای تعیین موقعیت ربات در شرایط عدم قطعیت استفاده کنیم؟
بیایید به یک فیلتر بیزی که به صورت بازگشتی تخمینهای احتمال محلیسازی را با استفاده از استنتاج بیزی بهبود میبخشد، نگاهی عمیق بیاندازیم. ماهیت بازگشتی به این معنی است که خروجی فیلتر در زمان t_0، P(H|E)، به عنوان ورودی به فرضیه برای مهر زمانی بعدی t_1، P(H) عمل می کند.
فرض کنید یک ربات تحویل دهنده یک مسیر دایره ای را در یک ایستگاه فضایی می چرخاند تا مواد را حمل کند. این ربات دارای نقشه ای است که طرح زمین و موقعیت سنسورها را با جزئیات نشان می دهد.
– تعریف مشکل:
ما مکان مورد انتظار ربات را به عنوان می نامیم فضای حالت ربات. به عنوان مثال، یک بردار دو بعدی (یعنی یک جفت اعداد مرتب شده) که موقعیت محور x و سرعت محور x را ردیابی می کند، می تواند مکان ربات و تغییر سرعت را در یک بعد ردیابی کند. امکان گسترش فضای حالت ربات به ابعاد اضافی برای ردیابی ابعاد چندگانه موقعیت (y، z)، جهت گیری و غیره وجود دارد.
برای سادگی، می توانیم فرض کنیم که ربات ما با سرعت ثابتی حرکت می کند. حرکت عدم قطعیت را به محاسبه اضافه می کند زیرا 100٪ قابل اعتماد نیست. ممکن است موتور با سرعت معینی کار نکند یا ربات با موانعی روبرو شود که باعث می شود ربات از حرکت مورد انتظارش تجاوز کند یا کمتر از آن عبور کند.
ربات ما مکان خود را با اندازه گیری حضور یک فانوس دریایی حس می کند. قرائت سنسور، همچنین نامیده می شود فضای اندازه گیری، 100% دقیق نیستند. سنسورها می توانند نویز را با سیگنال بیکن اشتباه بگیرند، که می تواند منجر به آلارم کاذب شود یا به هیچ وجه سیگنال را تشخیص ندهد.
– الگوریتم: فیلتر هیستوگرام
با این فیلتر بیزی، فضای حالت ربات توسط یک هیستوگرام از طریق تعداد محدودی از سطل ها یا مناطق نشان داده می شود. این یک فیلتر گسسته است، به این معنی که ربات فقط می تواند در یکی از این مناطق باشد و ما احتمال وجود ربات در هر یک را محاسبه می کنیم. همچنین در داخل هر ظرفی مانند مساحت 5 متر مربع، احتمال قرار گرفتن در هر نقطه خاص یکسان است. اگر بخواهیم دانه بندی را افزایش دهیم باید ظروف بیشتری اضافه کنیم.
این فیلتر ناپارامتریک است، به این معنی که هیچ فرضی قوی در مورد نمایش وضعیت ربات ندارد و به یک نوع توزیع، مانند گاوسی محدود نمی شود. این می تواند تخمین های مکان پیچیده را نشان دهد، مانند یک فرضیه چندوجهی که چندین بهترین حدس را پشتیبانی می کند، اما با هزینه محاسباتی – پیچیدگی نمایی همراه است. برای افزودن یک بعد اضافی، از 1-D به 2-D با حفظ جزئیات یکسان، به سطل های 10 × 10 نیاز داریم، برای رفتن به سطل های سه بعدی به سطل های 10x10x10 و غیره نیاز داریم. این یک محدودیت قابل توجه برای روبات هایی است که ابعاد چندگانه را ردیابی می کنند و از نظر حافظه و قدرت محاسباتی محدود هستند.
– محاسبه:
- حدس اولیه: ما از یک مکان ناشناخته، مجهز به نقشه شروع می کنیم. در ابتدا، هر منطقه به یک اندازه محتمل است، همانطور که با توزیع یکنواخت در همه سطل ها نشان داده می شود.
2. عملکرد حرکت: حرکت ربات را شبیه سازی می کند. حرکت ربات تصادفی است، به این معنی که تضمینی برای حرکت به سطل مورد نظر در هر مرحله زمانی وجود ندارد. برای به روز رسانی مکان ربات پس از هر حرکت، احتمال حضور ربات در هر منطقه را در مرحله بعدی محاسبه می کنیم. این محاسبه هم احتمال ماندن ربات در همان منطقه و هم احتمال حرکت آن به منطقه دیگر را در نظر می گیرد.
For each movement:
For each region:
Region probability at time t+1 =
Region probability at time t x stay probability +
Probability of robot coming from the neighboring region x move probability
همانطور که در معادله زیر نشان داده شده است، جابجایی ربات در یک پله به دلیل توزیع یکنواخت که در آن هر منطقه احتمال یکسانی برای ماندن و حرکت دارد، تخمین مکان را تغییر نخواهد داد.
حتی اگر در ابتدا از یک ظرف با اطمینان کامل (100٪) شروع کنیم، تصادفی بودن ذاتی حرکت به تدریج نویز را اضافه می کند که ما را به یک توزیع یکنواخت در طول زمان می برد. باید اطلاعات اضافه کنیم!
3. عملکرد حسی: شامل اندازه گیری هایی است که با استفاده از قضیه بیز اطلاعات را اضافه می کند.
After each movement:
For each region:
Region probability at time t+1 given measurement at time t+1 =
Likelihood of the measurement given the robot is in that region
x Region probability at time t+1 after movement
x normlization to ensure that all the probabilities sum to 1.
قابلیت اطمینان سنسورها با احتمالات نشان داده می شود، زیرا آنها 100٪ دقیق نیستند. معادلات زیر نشان می دهد که وقتی حسگر رنگ نارنجی را تشخیص می دهد، 90 درصد احتمال دارد که ربات در سطل نارنجی قرار داشته باشد و 10 درصد احتمال دارد که حسگر اشتباه کند و ربات در واقع در یک سطل آبی باشد.
محاسبات ارائه شده در زیر نشان می دهد که برخلاف حرکت، حسگرها اطلاعات را در اختیار ما قرار می دهند و درک ما را از مکان ربات بهبود می بخشند. به عنوان مثال، از آنجایی که ظرف 2 نارنجی نیست، احتمال اینکه ربات در آن باشد از 0.1 به 0.02 کاهش می یابد.
تصویر زیر فرضیه مکان به روز شده را پس از ترکیب داده های حرکت و حسگر به حدس اولیه ما نشان می دهد.
افکار نهایی
ربات کجاست؟ ما میتوانیم به طور مداوم پاسخ خود را به این سؤال با استفاده از فیلترهای بیزی بازگشتی اصلاح کنیم، از توزیع یکنواختی شروع میکنیم که همه حدسها را به یک اندازه محتمل نگه میدارد تا زمانی که به محتملترین آنها بپردازیم.
فیلترهای بیزی به ما کمک میکنند تا با بهروزرسانی این باور با یکپارچهسازی دادههای حسگر (نویزدار) با اطلاعات قبلی (موقعیت تقریبی ربات پس از حرکت)، اعتماد خود را نسبت به مکان ربات اندازهگیری کنیم.
منابع:
- اینها یادداشت های خلاصه من از اولین سخنرانی های دوره بسیار توصیه شده edX الگوریتم های بیزی برای وسایل نقلیه خودران توسط دکتر روی یوزوویچ است.
- GitBook Robotics Probabilistic Robotics: فیلتر ناپارامتری
- ویکی پدیا احتمال، نظریه احتمال و قضیه بیز
- وبلاگ شخصی Daniel Sabinasz در مورد فیلترهای هیستوگرام
- تبدیل آنلاین لاتکس به png.
- تصاویر: آواتار ربات ایجاد شده با Dall-E. تمام تصاویر دیگر استفاده شده در این مقاله توسط نویسنده ایجاد شده است.
چگونه خود را در دنیای دیجیتال پیدا کنیم؟ در ابتدا در Towards Data Science on Medium پست شد، جایی که مردم با برجسته کردن و پاسخ دادن به این داستان به گفتگو ادامه میدهند.