پاورپوینت کامل برنامه ریزی و جهت یابی (Planning and Navigation) 117 اسلاید در PowerPoint

توجه : این فایل به صورت فایل power point (پاور پوینت) ارائه میگردد

 پاورپوینت کامل برنامه ریزی و جهت یابی (Planning and Navigation) 117 اسلاید در PowerPoint دارای ۱۱۷ اسلاید می باشد و دارای تنظیمات کامل در PowerPoint می باشد و آماده ارائه یا چاپ است

شما با استفاده ازاین پاورپوینت میتوانید یک ارائه بسیارعالی و با شکوهی داشته باشید و همه حاضرین با اشتیاق به مطالب شما گوش خواهند داد.

لطفا نگران مطالب داخل پاورپوینت نباشید، مطالب داخل اسلاید ها بسیار ساده و قابل درک برای شما می باشد، ما عالی بودن این فایل رو تضمین می کنیم.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل می باشد و در فایل اصلی پاورپوینت کامل برنامه ریزی و جهت یابی (Planning and Navigation) 117 اسلاید در PowerPoint،به هیچ وجه بهم ریختگی وجود ندارد

بخشی از مطالب داخلی اسلاید ها

پاورپوینت کامل برنامه ریزی و جهت یابی (Planning and Navigation) 117 اسلاید در PowerPoint

اسلاید ۴: Configuration Spaceمسئله مسیریابی برای روباتهای صنعتی و متحرک در فضائی با نام configuration space انجام میشود.برای روباتی با k درجه آزادی هر ترکیب موقعیت آن را میتوان با k مقدار حقیقی q1,…,q k نشان داد. که این مقادیر نقطه ای مثل p را در فضای kبعدی نشان میدهند. این فضا configuration space نامیده میشود.

اسلاید ۵: Free Spaceاگر فضای حقیقی (work space ) دارای مانع باشد، عمل مسیریابی باید مسیری از نقطه اولیه به هدف پیدا نماید که بدون مانع باشد.این مسیر فضای آزاد نامیده میشود:F=C-O فضای ازادفضای موقعیتفضای مانع

اسلاید ۶: Configuration Spaceیک روبات با دو درجه آزادی در فضای حقیقیفضای موقعیت و فضای آزاد و مسیری که به هدف منجر میشود

اسلاید ۷: configuration space of a mobile robotبرای یک روبات متحرک رسم بر این است که آنرا بصورت holomonic فرض کنیم. در اینصورت روبات را میتوان بصورت یک نقطه در نظر گرفت .در نتیجه فضای موقعیت را میتوان بصورت دو بعدی با محورهای x, y نشان داد.در این حالت اشیا موجود در محیط باندازه شعاع روبات بزرگ میشوند تا فرض نقطه ای بودن روبات درست باشد.

اسلاید ۸: Example of a World (and Robot)ObstaclesFree SpaceRobotx,y

اسلاید ۹: Configuration Space: Accommodate Robot SizeObstaclesFree SpaceRobot(treat as point object)x,y

اسلاید ۱۰: Path Planingفرض میشود که یک نقشه مناسب از محیط وجود داشته باشد:توپولوژیکمتریک یا ترکیبی از این دواولین مرحله از مسیریابی تبدیل نقشه به یک نقشه گسسته است. اینکار به چند طریق ممکن است انجام شود:Visibility GraphVoronoi DiagramCell Decomposition Connectivity GraphPotential Field

اسلاید ۱۱: Road-Map Path Planning:در این روش فضای آزاد بصورت شبکه ای از منحنی ها و یا خطوط که نقشه راه نامیده میشود نشان داده میشود.مسیریابی در این حالت عبارت است از اتصال مبدا و مقصد روبات به نقشه راه و بدنبال آن جستجوی راه هائی که ایندو را به هم متصل میکنند.در این روش فضای حالت روبات با استفاده از هندسه موانع تجزیه میشود.دو روش مختلف برای اینکار: Visibility GraphVoronoi Diagram

اسلاید ۱۲: Visibility GraphVisibility Graph (گراف پدیداری)برای یک فضای موقعیت مرکب از چند ضلعی ها از لبه هائی تشکیل میشود که رئوس چند ضلعیها را دو بدو به هم متصل میکنند.وظیفه مسیریاب پیدا کردن کوتاهترین مسیر از مبدا به مقصد است.پیاده سازی این روش ساده بوده و مسیر پیدا شده توسط آن بهینه است.اگر تعداد اشیا محیط زیاد شود تعداد لبه ها و گره ها زیاد شده و سرعت الگوریتم کاهش می یابد. مشکل جدی این روش این است که مسیر پیدا شده توسط آن روبات را تا حد ممکن به اشیا نزدیک میکند.

اسلاید ۱۳: Visibility GraphG: non-directed graph گره ها عبارتند از نقطه شروع و هدف و رئوس چند ضلعی هایال ها عبارتند از خطوط مستقیمی که از اتصال دو نقطه بدست می آیند و هیچ مانعی را قطع نمیکنند.qinitqGoal

اسلاید ۱۴: الگوریتمConstruct a visibility graph G Search G for a path from qinit to qgoalIf a path is found, return it; otherwise, indicate failureConstruction most expensive: – naively O(n3)- sweep-line algorithm renders it O(n2 log n)- O(n2) proposed.

اسلاید ۱۵: میتوان با کاهش تعداد یالها مرتبه اجرای الگوریتم را کاهش داد.از G رئوس مقعر و یالهای non-tangentحذف میشوند. یال tangent یالی است که از هر دو گره برموانع مماس باشد.Reduced Visibility GraphsqinitqgoalqinitQgoal Algorithm: O(… + n log n) possible.

اسلاید ۱۶: Voronoi Diagramبرخلاف روش visibility graph این روش سعی دارد تا فاصله روبات تا اشیا را حداکثر نماید.برای ساختن Veronoi graphنقاطی از صفحه که فاصله شان ازدو و یا چند شیئ یکسان است پیدا شده و به هم متصل میشوند. این نموداز شامل خطوط صاف و منحنی خواهد بود.مسیر یافته شده توسط این روش با مسیر بهینه فاصله دارد.اجرای این الگوریتم بر روی روبات ساده است: روبات با استفاده از سنسور های فاصله سعی درحداکثر کردن فاصله اش از اشیا اطراف خواهد نمود تا همیشه در مسیر این نمودار قراربگیرد.این خطر وجود دارد که روبات بعلت محدودیت سنسورهایش قادر به اندازه گیری فاصله تا اشیا دور نباشد.

اسلاید ۱۷: Voronoi Diagram

اسلاید ۱۸: Voronoi diagramVoronoi diagram of floor map

اسلاید ۱۹: نمودار ورونوی برای مجموعه ای از نقاط

اسلاید ۲۰: Generalized Voronoi Diagrams

اسلاید ۲۱: Naive Method of Constructing Voronoi Diagramscompute all arcs (for each vertex-vertex, edge-edge, and vertex-edge pair)compute all intersection points (dividing arcs into segments)keep segments which are closest only to the vertices/edges that defined them

اسلاید ۲۲: Cell Decompositionدر این روش محل های مربوط به فضای آزاد و اشیاء از هم جدا میشوند. برای اینکار:فضا را به نواحی ساده و به هم متصلی به نام سلول تقسیم کنید.سلولهای آزادی که مجاورهم هستند را مشخص نموده ویک گراف اتصال تشکیل دهید.سلولهائی که حاوی نقطه مبدا و مقصدهستند را پیدا کنید.مسیری در گراف اتصال پیدا کنید که این سلولها رابه هم وصل کند.در این سلولها مسیری را پیدا کنید که از آن سلول عبور کند. مثلا مسیری که نقطه وسط سلول را به مرزهایش وصل نماید.

اسلاید ۲۳: Exact Cell Decomposition

اسلاید ۲۴: Cell Decomposition Trapezoidal Decomposition

اسلاید ۲۵: Cell Decomposition Trapezoidal Decompositionبازای هر یک از رئوس موانع خط عمودی در فضای آزاد رسم میشود که یا به مانع دیگری برسد و یا به مرز برخورد کند

اسلاید ۲۶: Cell Decomposition Trapezoidal Decompositionبا تقلیل محیط به سلولها میتوان گراف متناظری را ساختstartgoal

اسلاید ۲۷: Cell Decomposition Trapezoidal Decompositionبا استفاده از یک گراف مجاورت میتوان مسیری را از مبدا به مقصد بدست اورد.startgoal

اسلاید ۲۸: Approximate Cell Decompositionیکی از روشهای متداول در مسیریابی روباتهای متحرک است که بخصوص برای مواردی که محیط بصورت grid based استفاده میشود.فضا به سلولهائی با اندازه ثابت( یا متغیر) تقسیم بندی میشود.در حالت استفاده از سلول با اندازه ثابت ممکن است برخی مسیرها از دست بروند.

اسلاید ۲۹: Approximate Cell Decomposition

اسلاید ۳۰: Adaptive Cell Decomposition

اسلاید ۳۱: Adaptive Cell DecompositionQuadtreeUniform

اسلاید ۳۲: مسائلپیوستگی مسیر تابعی از رزولوشن انتخاب شده است.با افزایش رزلوشن پیچیدگی محاسباتی افزایش می یابد.مواردی وجود دارند که دقت از بین میرود. برای مثال در شکل زیر تشخیص مانع از فضای آزاد مشکل خواهد بود

اسلاید ۳۳: برای جستجو از تکنیک NF1 و یا grassfire استفاده میشود که در آن به هر سلول فاصله آن تا نقطه هدف نسبت داده میشود.سایرروشها:Breadth-First SearchDepth-First SearchGreedy search and A *Path / Graph Search Strategies

اسلاید ۳۴: The Wavefront plannerاز این الگوریتم میتوان برای تعیین کوتاهترین فاصله بین دو نقطه استفاده نمود.در حقیقت یک جستجوی breadth first انجام میدهد.مقدار دهی اولیه:فضای آزاد با ۰ علامت گذاری میشودموانع با ۱ علامت گذاری میشوند.مقصد با ۲ علامت گذاری میشود.

اسلاید ۳۵: The Wavefront planner

اسلاید ۳۶: The Wavefront plannerاز نقطه هدف شروع کرده و سلولهای مجاور آن را یکواحد افزایش میدهیم.

اسلاید ۳۷: The Wavefront plannerبه همین ترتیب برای سلولهای مجاور عمل میکنیم.الگوریتم آنقدر ادامه پیدا میکند تا هیچ سلولی که همسایه برزگتر از ۲ داشته برابر صفر نباشد. مگر سلولی هائی که قابل دسترس نباشند.

اسلاید ۳۸: The Wavefront plannerبرای پیدا کردن کوتاهترین مسیر با شروع از مبدا درجهتی حرکت میکنیم که مقدار عددی سلولها کمتر شود.

اسلاید ۳۹: Potential Field Path Planningاین روش یک میدان و یا گرادیانی در نقشه روبات ایجاد میکند که میتواند روبات را از موقعیت فعلی به سمت هدف هدایت نماید.روبات بصورت یک نقطه فرض میشود که تحت تاثیر یک میدان پتانسیل U(q) قرار دارد. روبات همانند توپی که در سرازیری قرار دارد مسیر میدان را دنبال میکند.نقطه هدف بصورت یک نیروی جاذب و موانع بصورت نیروهای دافع عمل میکنند. برایند نیرو های دوگانه به روبات اعمال خواهد شد. بدین ترتیب روبات همزمان با حرکت بسوی هدف از موانع نیز دور خواهد شد.اگر اشیا جدید در مسیر روبات قرار داده شوند میدان طوری تغییر داده میشود تا تاثیر آنها را در بر داشته باشد.

اسلاید ۴۰: Potential Field Path Planning

اسلاید ۴۱: Potential Field Generation اگر روبات بصورت یک نقطه فرض شود میتوان از qصرفنظر نموده و میدان پتانسیل U(q) را بصورت دو بعدی در نظر گرفت. در اینصورت نیروئی که در نقطهq=(x,y) بر روبات اثر میکند عبارت است از:سرعت روبات (vx, vy) متناسب با نیروی F(q) در نظر گرفته میشود.

اسلاید ۴۲: Attractive Potential Field پتانسیل جذبی را میتوان بصورت یک تابع سهمی گون در نظر گرفت.در این رابطه Katt ضریب مقیاس و rgoal(q) فاصله اقلیدسی || q-qgoal ||تا هدف را مشخص میکند. با مشتق گیری از این رابطه مقدار نیروی جاذ ب بدست خواهد آمد.وقتی که روبات به هدف میرسد مقدار این نیرو صفر خواهد شد.

اسلاید ۴۳: Repulsing Potential Field نیروی دافعه باید روبات را از موانع معلوم دور سازد. از اینرو مقدار آن وقتی که روبات به موانع نزدیک میشود باید زیاد بوده و وقتی که روبات بقدر کافی از موانع دور است تاثیر چندانی نداشته باشد. در این رابطه Krep ضریب مقیاس و r (q) حد اقل فاصله از q به شیئ و r0 فاصله تاثیر شیئ است .مقدار میدان دافعه مثبت و یا صفر بوده و با نزدیک شدن به شیئ مقدار آن بینهایت میشود.اگر مرز شیئ محدب بوده و بصورت تکه تکه مشتق پذیر باشد میتوان از r (q) مشتق گرفت. در اینصورت:

اسلاید ۴۴: Generating the Potential Field A Parabolic Well for Attracting to Goal

اسلاید ۴۵: Gaussian Obstacle Potential Function

اسلاید ۴۶: Parabolic Well for Goal Exponential Source for Obstacle

اسلاید ۴۷: Parabolic Well Goal & Two Exponential Source Obstacles

اسلاید ۴۸: Potential Field Path Planning:محدودیت های این روش:احتمال قرار گرفتن در مینیمم محلی وجود دارد.در اشیا مقعر ممکن است چندین فاصله حد اقل r (q) وجود داشته باشد. این امر ممکن است به نوسان بین دو نقطه نزدیک به شیئ منجر گردد.اگر نتوان روبات را بصورت نقطه ای فرض کرد مسئله بعرنج خواهد شد.

اسلاید ۴۹: Extended Potential Field Method در این روش دو میدان به صورت زیر تعریف میشود:Rotation Potential Field این میدان نیروی دافعه را تابعی از فاصله تا مانع و جهت روبات فرض میکند. طوری که اگر روبات موازی مانع بود نیروی دافعه مانع کمتراثر نماید.بدین ترتیب عمل wall following راحت تر انجام میشود.Task potential field با استفاده از