برنامه ریزی و جهت یابی (Planning and Navigation)
اسلاید 1: Planning and NavigationAmirkabir University of Technology Computer Engineering & Information Technology Departmentدکتر سعید شیری قیداری& فصل 6 کتاب
اسلاید 2: CognitionCognitionعبارت است از تصمیم گیری هدفمندانه و اجرای آن توسط یک سیستم برای نیل به یک هدف سطح بالا.در یک روبات متحرک این امر متوجه مسئله navigation است که باعث میشود تا روبات با داشتن اطلاعات جزئی از محیط و مقادیر سنسورها بتواند به موقعیت هدف برسد.Navigation شامل اجرای یک سری عمليات برای رسیدن به هدف میشود (planing) که در ضمن اجرای آن روبات باید از برخورد با موانع جلوگیری نماید. (reacting)
اسلاید 3: Path planningمسئله مسیریابی برای روباتهای متحرک یک امر اساسی است اما قبل از برای رباتهای صنعتی نیز مطرح بوده و مطالعات زیادی در این زمینه شده است.بعات محدودیت درجات آزادی روباتهای متحرک این مسئله برای آنها ساده تر از روباتهای صنعتی میباشد.در روباتهای صنعتی بعلت سرعت زیاد علاوه بر سینماتیک مسئله دینامیک هم مهم است.
اسلاید 4: Configuration Spaceمسئله مسیریابی برای روباتهای صنعتی و متحرک در فضائی با نام configuration space انجام میشود.برای روباتی با k درجه آزادی هر ترکیب موقعیت آن را میتوان با k مقدار حقیقی q1,…,q k نشان داد. که این مقادیر نقطه ای مثل p را در فضای kبعدی نشان میدهند. این فضا configuration space نامیده میشود.
اسلاید 5: Free Spaceاگر فضای حقیقی (work space ) دارای مانع باشد، عمل مسیریابی باید مسیری از نقطه اولیه به هدف پیدا نماید که بدون مانع باشد.این مسیر فضای آزاد نامیده میشود:F=C-O فضای ازادفضای موقعیتفضای مانع
اسلاید 6: Configuration Spaceیک روبات با دو درجه آزادی در فضای حقیقیفضای موقعیت و فضای آزاد و مسیری که به هدف منجر میشود
اسلاید 7: configuration space of a mobile robotبرای یک روبات متحرک رسم بر این است که آنرا بصورت holomonic فرض کنیم. در اینصورت روبات را میتوان بصورت یک نقطه در نظر گرفت .در نتیجه فضای موقعیت را میتوان بصورت دو بعدی با محورهای x, y نشان داد.در این حالت اشیا موجود در محیط باندازه شعاع روبات بزرگ میشوند تا فرض نقطه ای بودن روبات درست باشد.
اسلاید 8: Example of a World (and Robot)ObstaclesFree SpaceRobotx,y
اسلاید 9: Configuration Space: Accommodate Robot SizeObstaclesFree SpaceRobot(treat as point object)x,y
اسلاید 10: Path Planingفرض میشود که یک نقشه مناسب از محیط وجود داشته باشد:توپولوژیکمتریک یا ترکیبی از این دواولین مرحله از مسیریابی تبدیل نقشه به یک نقشه گسسته است. اینکار به چند طریق ممکن است انجام شود:Visibility GraphVoronoi DiagramCell Decomposition Connectivity GraphPotential Field
اسلاید 11: Road-Map Path Planning:در این روش فضای آزاد بصورت شبکه ای از منحنی ها و یا خطوط که نقشه راه نامیده میشود نشان داده میشود.مسیریابی در این حالت عبارت است از اتصال مبدا و مقصد روبات به نقشه راه و بدنبال آن جستجوی راه هائی که ایندو را به هم متصل میکنند.در این روش فضای حالت روبات با استفاده از هندسه موانع تجزیه میشود.دو روش مختلف برای اینکار: Visibility GraphVoronoi Diagram
اسلاید 12: Visibility GraphVisibility Graph (گراف پدیداری)برای یک فضای موقعیت مرکب از چند ضلعی ها از لبه هائی تشکیل میشود که رئوس چند ضلعیها را دو بدو به هم متصل میکنند.وظیفه مسیریاب پیدا کردن کوتاهترین مسیر از مبدا به مقصد است.پیاده سازی این روش ساده بوده و مسیر پیدا شده توسط آن بهینه است.اگر تعداد اشیا محیط زیاد شود تعداد لبه ها و گره ها زیاد شده و سرعت الگوریتم کاهش می یابد. مشکل جدی این روش این است که مسیر پیدا شده توسط آن روبات را تا حد ممکن به اشیا نزدیک میکند.
اسلاید 13: Visibility GraphG: non-directed graph گره ها عبارتند از نقطه شروع و هدف و رئوس چند ضلعی هایال ها عبارتند از خطوط مستقیمی که از اتصال دو نقطه بدست می آیند و هیچ مانعی را قطع نمیکنند.qinitqGoal
اسلاید 14: الگوریتم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.
اسلاید 15: میتوان با کاهش تعداد یالها مرتبه اجرای الگوریتم را کاهش داد.از G رئوس مقعر و یالهای non-tangentحذف میشوند. یال tangent یالی است که از هر دو گره برموانع مماس باشد.Reduced Visibility GraphsqinitqgoalqinitQgoal Algorithm: O(… + n log n) possible.
اسلاید 16: Voronoi Diagramبرخلاف روش visibility graph این روش سعی دارد تا فاصله روبات تا اشیا را حداکثر نماید.برای ساختن Veronoi graphنقاطی از صفحه که فاصله شان ازدو و یا چند شیئ یکسان است پیدا شده و به هم متصل میشوند. این نموداز شامل خطوط صاف و منحنی خواهد بود.مسیر یافته شده توسط این روش با مسیر بهینه فاصله دارد.اجرای این الگوریتم بر روی روبات ساده است: روبات با استفاده از سنسور های فاصله سعی درحداکثر کردن فاصله اش از اشیا اطراف خواهد نمود تا همیشه در مسیر این نمودار قراربگیرد.این خطر وجود دارد که روبات بعلت محدودیت سنسورهایش قادر به اندازه گیری فاصله تا اشیا دور نباشد.
اسلاید 17: Voronoi Diagram
اسلاید 18: Voronoi diagramVoronoi diagram of floor map
اسلاید 19: نمودار ورونوی برای مجموعه ای از نقاط
اسلاید 20: Generalized Voronoi Diagrams
اسلاید 21: 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
اسلاید 22: Cell Decompositionدر این روش محل های مربوط به فضای آزاد و اشیاء از هم جدا میشوند. برای اینکار:فضا را به نواحی ساده و به هم متصلی به نام سلول تقسیم کنید.سلولهای آزادی که مجاورهم هستند را مشخص نموده ویک گراف اتصال تشکیل دهید.سلولهائی که حاوی نقطه مبدا و مقصدهستند را پیدا کنید.مسیری در گراف اتصال پیدا کنید که این سلولها رابه هم وصل کند.در این سلولها مسیری را پیدا کنید که از آن سلول عبور کند. مثلا مسیری که نقطه وسط سلول را به مرزهایش وصل نماید.
اسلاید 23: Exact Cell Decomposition
اسلاید 24: Cell Decomposition Trapezoidal Decomposition
اسلاید 25: Cell Decomposition Trapezoidal Decompositionبازای هر یک از رئوس موانع خط عمودی در فضای آزاد رسم میشود که یا به مانع دیگری برسد و یا به مرز برخورد کند
اسلاید 26: Cell Decomposition Trapezoidal Decompositionبا تقلیل محیط به سلولها میتوان گراف متناظری را ساختstartgoal
اسلاید 27: Cell Decomposition Trapezoidal Decompositionبا استفاده از یک گراف مجاورت میتوان مسیری را از مبدا به مقصد بدست اورد.startgoal
اسلاید 28: Approximate Cell Decompositionیکی از روشهای متداول در مسیریابی روباتهای متحرک است که بخصوص برای مواردی که محیط بصورت grid based استفاده میشود.فضا به سلولهائی با اندازه ثابت( یا متغیر) تقسیم بندی میشود.در حالت استفاده از سلول با اندازه ثابت ممکن است برخی مسیرها از دست بروند.
اسلاید 29: Approximate Cell Decomposition
اسلاید 30: Adaptive Cell Decomposition
اسلاید 31: Adaptive Cell DecompositionQuadtreeUniform
اسلاید 32: مسائلپیوستگی مسیر تابعی از رزولوشن انتخاب شده است.با افزایش رزلوشن پیچیدگی محاسباتی افزایش می یابد.مواردی وجود دارند که دقت از بین میرود. برای مثال در شکل زیر تشخیص مانع از فضای آزاد مشکل خواهد بود
اسلاید 33: برای جستجو از تکنیک NF1 و یا grassfire استفاده میشود که در آن به هر سلول فاصله آن تا نقطه هدف نسبت داده میشود.سایرروشها:Breadth-First SearchDepth-First SearchGreedy search and A *Path / Graph Search Strategies
اسلاید 34: The Wavefront plannerاز این الگوریتم میتوان برای تعیین کوتاهترین فاصله بین دو نقطه استفاده نمود.در حقیقت یک جستجوی breadth first انجام میدهد.مقدار دهی اولیه:فضای آزاد با 0 علامت گذاری میشودموانع با 1 علامت گذاری میشوند.مقصد با 2 علامت گذاری میشود.
اسلاید 35: The Wavefront planner
اسلاید 36: The Wavefront plannerاز نقطه هدف شروع کرده و سلولهای مجاور آن را یکواحد افزایش میدهیم.
اسلاید 37: The Wavefront plannerبه همین ترتیب برای سلولهای مجاور عمل میکنیم.الگوریتم آنقدر ادامه پیدا میکند تا هیچ سلولی که همسایه برزگتر از 2 داشته برابر صفر نباشد. مگر سلولی هائی که قابل دسترس نباشند.
اسلاید 38: The Wavefront plannerبرای پیدا کردن کوتاهترین مسیر با شروع از مبدا درجهتی حرکت میکنیم که مقدار عددی سلولها کمتر شود.
اسلاید 39: Potential Field Path Planningاین روش یک میدان و یا گرادیانی در نقشه روبات ایجاد میکند که میتواند روبات را از موقعیت فعلی به سمت هدف هدایت نماید.روبات بصورت یک نقطه فرض میشود که تحت تاثیر یک میدان پتانسیل U(q) قرار دارد. روبات همانند توپی که در سرازیری قرار دارد مسیر میدان را دنبال میکند.نقطه هدف بصورت یک نیروی جاذب و موانع بصورت نیروهای دافع عمل میکنند. برایند نیرو های دوگانه به روبات اعمال خواهد شد. بدین ترتیب روبات همزمان با حرکت بسوی هدف از موانع نیز دور خواهد شد.اگر اشیا جدید در مسیر روبات قرار داده شوند میدان طوری تغییر داده میشود تا تاثیر آنها را در بر داشته باشد.
اسلاید 40: Potential Field Path Planning
اسلاید 41: Potential Field Generation اگر روبات بصورت یک نقطه فرض شود میتوان از qصرفنظر نموده و میدان پتانسیل U(q) را بصورت دو بعدی در نظر گرفت. در اینصورت نیروئی که در نقطهq=(x,y) بر روبات اثر میکند عبارت است از:سرعت روبات (vx, vy) متناسب با نیروی F(q) در نظر گرفته میشود.
اسلاید 42: Attractive Potential Field پتانسیل جذبی را میتوان بصورت یک تابع سهمی گون در نظر گرفت.در این رابطه Katt ضریب مقیاس و rgoal(q) فاصله اقلیدسی || q-qgoal ||تا هدف را مشخص میکند. با مشتق گیری از این رابطه مقدار نیروی جاذ ب بدست خواهد آمد.وقتی که روبات به هدف میرسد مقدار این نیرو صفر خواهد شد.
اسلاید 43: Repulsing Potential Field نیروی دافعه باید روبات را از موانع معلوم دور سازد. از اینرو مقدار آن وقتی که روبات به موانع نزدیک میشود باید زیاد بوده و وقتی که روبات بقدر کافی از موانع دور است تاثیر چندانی نداشته باشد. در این رابطه Krep ضریب مقیاس و r (q) حد اقل فاصله از q به شیئ و r0 فاصله تاثیر شیئ است .مقدار میدان دافعه مثبت و یا صفر بوده و با نزدیک شدن به شیئ مقدار آن بینهایت میشود.اگر مرز شیئ محدب بوده و بصورت تکه تکه مشتق پذیر باشد میتوان از r (q) مشتق گرفت. در اینصورت:
اسلاید 44: Generating the Potential Field A Parabolic Well for Attracting to Goal
اسلاید 45: Gaussian Obstacle Potential Function
اسلاید 46: Parabolic Well for Goal Exponential Source for Obstacle
اسلاید 47: Parabolic Well Goal & Two Exponential Source Obstacles
اسلاید 48: Potential Field Path Planning:محدودیت های این روش:احتمال قرار گرفتن در مینیمم محلی وجود دارد.در اشیا مقعر ممکن است چندین فاصله حد اقل r (q) وجود داشته باشد. این امر ممکن است به نوسان بین دو نقطه نزدیک به شیئ منجر گردد.اگر نتوان روبات را بصورت نقطه ای فرض کرد مسئله بعرنج خواهد شد.
اسلاید 49: Extended Potential Field Method در این روش دو میدان به صورت زیر تعریف میشود:Rotation Potential Field این میدان نیروی دافعه را تابعی از فاصله تا مانع و جهت روبات فرض میکند. طوری که اگر روبات موازی مانع بود نیروی دافعه مانع کمتراثر نماید.بدین ترتیب عمل wall following راحت تر انجام میشود.Task potential field با استفاده از سرعت روبات اشیائی را که نباید تاثیری بر میدان پتانسیل داشته باشند را مشخص مینماید. اینکار مسیر هموارتری را ایجاد مینماید.
اسلاید 50: Extended Potential Field Method مقایسه بین دو روش
اسلاید 51: Obstacle Avoidance یک مسیریاب فقط میتواند اشیائی را در نظر بگیرد که از قبل مشخص باشند.در عمل ممکن است در یک محیط پویا بعلت وجود اشیا جدید و یا عدم دقت نقشه قرائت سنسورهای روبات با مقادیر موجود در نقشه همخوانی نداشته باشد.در نتیجه یک روبات متحرک باید قادر به ممانعت از برخورد با اشیا باشد.
اسلاید 52: Obstacle Avoidance عمل پرهیز از اشیا سعی دارد تا مسیر روبات را به محض اینکه سنسورهای روبات آن را از وجود مانعی آگاه کردند تغییر دهد.اینکار وابسته به عوامل زیر است: نقشه محیط، اطلاع دقیق روبات از موقعیت خودش در روی نقشه، مقدار فعلی قرائت سنسورها، نقطه هدف ،سرعت و دینامیک روبات، خطر کنونی و بعدی برخوردمعمولا قابلیت پرهیز از مانع بصورت جداگانه پیاده سازی میشود.
اسلاید 53: Bug Algorithmsالگوریتم های Bug جزو ساده ترین روشهای پرهیز از اشیا هستند.ایده اصلی این است که روبات با مشاهده هر مانع در مسیر خود محیط پیرامون آنرا دور میزند.فرضیات:Point robotContact sensor (Bug1,Bug2) or finite range sensor (Tangent Bug)Bounded environmentRobot position is perfectly knownRobot can measure the distance between two points
اسلاید 54: Obstacle Avoidance: Bug1 در این روش روبات یک دور کامل دور شیئ زده و سپس از نزدیکترین نقطه به هدف از مانع جدا میشود.
اسلاید 55: Obstacle Avoidance: Bug2 در این روش روبات محیط مانع را دور میزند و به محض اینکه راهی بسوی هدف پیدا کرد از آن جدا میشود.
اسلاید 56: Bug AlgorithmsAlgorithm consists of two behaviors:1. Motion to goal – move toward the goal Bug1: move along the line that connects an “initial” point to the goal until you reach the goal or an obstacle (hit point).Bug2: move along the line that connects the start point to the goal until you reach the goal or an obstacle (hit point).
اسلاید 57: Bug Algorithms2. Boundary following – obstacle handling Bug1: circumnavigate the entire perimeter of the obstacle, find the closest point to the goal on the perimeter (leave point), move to that point .Bug2: circumnavigate the obstacle until you reach a new point on the line connecting start and goal, that is closer to the goal (leave point).
اسلاید 58: Bug AlgorithmsBug1Exhaustive searchOptimal leave pointPerforms better with complex obstaclesPath length :n = # of obstaclesPi = perimeter of obstacle iBug2Opportunistic (greedy) searchPerforms better with simple obstaclesPath length :ni = # of times the start-goal line intersects obstacle i
اسلاید 59: Obstacle Avoidance: Vector Field Histogram (VFH)
اسلاید 60: سایر روشهاThe Bubble Band ConceptLane Curvature Velocity MethodsGlobal Dynamic Window ApproachThe Schlegel ApproachThe EPFL-ASL approachFuzzy, Neuro-Fuzzy
اسلاید 61: Navigation Architecturesچگونه میتوان روشهای مختلف مسیریابی، پرهیز از موانع، مکان یابی، و ادراکی را در یک روبات واقعی تحت یک سیستم مجتمع نمود؟روش متداول طراحی یک نرم افزار مخصوص کاربرد مورد نظر است.اما این کار را میتوان به شیوه های ساخت یافته تر ی نیز انجام داد.
اسلاید 62: Control localizationمعمولا در طراحی روبات عملیات کنترلی مختلف به صورت واحد های مشخصی در معماری سیستم پیاده سازی میشوند.مثلا پرهیز از موانع بصورت یک واحد مجزا اجرا میشود.همچنین تصمیم گیری های سطح بالا نظیر planning نیز بصورت مجزا اجرا میشوند. معمولا این بخشها با استفاده از یک شبیه ساز تست میشوند.معمولا از دو روش برای تجزیه عملیات روبات استفاده میشودTemporal decomposition and Control decomposition
اسلاید 63: Temporal decompositionتجزیه زمانی نرم افزار روبات بر اساس عملیاتی که باید بصورت بلادرنگ انجام شوند و عملیاتی که میتوانند بصورت off line انجام میشوند صورت میپذیرد.Strategic decisionsTactical decisionsQuasi real timeHard real timeOff line planning
اسلاید 64: Temporal decompositionدر پائین ترین سطح تصمیم گیری بر اساس مقادیر فوری سنسور ها انجام میگیرد در حالیکه در سطوح بالاتر تصمیم گیری براساس صورت مسئله موجود انجام میگیرد.
اسلاید 65: Control decompositionاین روش نرم افزار را بر اساس ارتباطی که خروجی های یک بخش با قسمت های دیگر دارد تجزیه میکند.سیستم ( شامل روبات و محیط) به m ماجول با یک یا چند ورودی و فقط یک خروجی تجزیه میشود که ورودی هر ماجول از خروی ماجول دیگری تامین شده و یک سیستم بسته ایجاد میشود.ورودی ماجول r و یا روبات کلیه عملیاتی که روبات فیزیکی قادر به انجام آن است را شامل میشود. خروجی آن نیز تمامی ادارکاتی را که روبات قادر به حس آن است در بر میگیرد.
اسلاید 66: Control decompositionاین ایده میتواند بصورت کاملا سریال و یا موازی پیاده سازی شود.
اسلاید 67: کنترل موازیدر حالت موازی لازم است تا روشی برای انتخاب بین خروحی های ماجولهای مختلف تعیین گردد.در روش سوئیچینگ در هر لحظه خروجی یکی از ماجولها بر اساس شرایط موجود انتخاب میشود. ( مثلا در هنگام نزدیک شدن به موانع ماجول پرهیز از موانع انتخاب میشود)در روش ترکیبی خروجی همه ماجولها برای تولید خروجی لازم مورد استفاده قرار میگیرد. مثلا خروجی ماجول پرهیز از موانع همیشه روشن است ولی یک تابع ریاضی تاثیر آن در حرکت روبات را تعیین مینماید.روش کنترل موازی در حقیقت تقلیدی از موجودات زنده است: Biomimetc
اسلاید 68: An architectural example: Functional Decompositionمسیر کمانها ار تباط زمانی بین ماجولها را نشان میدهد
اسلاید 69: General Tiered Architectureمثالی از تجزیه زمانی عملیات روبات:ماجول Path Planning تصمیم گیری های استراتژیک را انجام میدهد. این تصمیم گیری real time نبوده و بر اساس اطلاعات کلی در یافتی از محیط انجام میشود. از طرف دیگرکنترلرهای Real time دارای پهنای باند زیادی بوده و ورودی سنسورها را به عملگرها ربط میدهند.در پائین ترین مرحله کنترلر موتورها قرار میگیرد. لایه اجرائی یا Executive که بین دو لایه path planner و real time قرار میگیرد، مسئول میانجیگری بین ایندو بخش است که رفتار ها را بر اساس مقدار سنسور ها فعال میکند، خرابی را تشخیص میدهد و در صورت لزوم planner را دوباره راه اندازی میکند.
اسلاید 70: A Three-Tiered Episodic Planning Architecture.Planner is triggered when needed: e.g. blockage, failure
اسلاید 71: An integrated planning and execution architectureAll integrated, no temporal between planner and executive layer
اسلاید 72:
اسلاید 73: روبات خودکاربرای داشتن یک روبات کاملا خودکار لازم است تا علاوه بر ایجاد ارتباط بین ورودی سنسورهای روبات و خروجی عملگرهای آن:روبات باید قادر باشد تا هدفی را انجام دهدروبات باید مسئله ای را حل نماید
اسلاید 74: ویژگی های معماریA control architecture provides a set of principles forOrganizing a control systemprovides structureprovides constraintsrefers to software control level, not hardware!
اسلاید 75: دسته بندی معماری های مختلف برای کنترل روبات Deliberativelook-ahead; think, plan, then actReactiveno look-ahead; react!Hybridthink slowly, react quicklyBehavior-baseddistribute thinking over acting
اسلاید 76: Deliberative ControlClassical control architecture (first to be tried)First used in AI to reason about actions in nonphysical domains (like chess)Natural to use this in robotics at firstHigh-level planning architectures including STRIPS, GAPPS, PRS, and RAPS
اسلاید 77: Reactive ControlOperate on a short time scaleDoes not look aheadReactive control is based on a tight loop connecting the robot’s sensors with its effectorsPurely reactive controllers do not use any internal representation; they merely react to the current sensory information.Use a direct mapping between sensor and effectors; minimal state information (if any)
اسلاید 78: Reactive ControlCollection of rules that map situations to actionsSimplest form:divides perceptual world into a set of mutually exclusive situations recognize which situation we are inreact to it Usually too hard to define mutually exclusive situations what if multiple sensors are involved?robot’s entire sensory space could be very large!
اسلاید 79: مثال
اسلاید 80: ArbitrationDeciding between two or more different possible actions or behaviorsCan be done based on: fixed priority hierarchy dynamic hierarchy Learning
اسلاید 81: Universal PlansSuppose: all possible plans for all possible actions can be generated in advance and An optimal reaction for each situation can be identifiedThis is a universal plan also called a complete mapping.Reactive planning is done at compile-time, not run-time.but not viable, because: world must be deterministic world must not change goals must not change world is too complex (state space is too large)
اسلاید 82: Situated AutomataFormal notion of finite state machines (FSM)inputs connected to sensorsoutputs connected to effectors “situated” = interacting with a complex worldUsed to create reactive principled control systemsControl With Situated Automatatwo ways to construct manually e.g., subsumption architecture [Brooks 1986] pre-compiling a complete plan similar to universal plans, but in terms of FSM circuitry
اسلاید 83: Subsumption Architecture Best known reactive control architecture (Q Rodney Brooks, MIT, 1985) principles: systems are built from the bottom up components are task achieving actions/behaviors (not functional modules) components can be executed in parallel components are organized in layers, from the bottom up lowest layers handle most basic tasks newly added components and layers exploit existing ones each component provides and does not disrupt tight coupling between sensing and action no internal models (“the world is its own best model”)
اسلاید 84: Hybrid ControlBasic idea:use the best of both worlds (deliberative and reactive) combine open-loop and closed-loop execution combine different time scales and representationsTypically consists of three components:reactive layerplannerintegration layer to combine (1) and (2) often called three-layer architectures planner and reactive layers are standard
اسلاید 85: StrengthsDeliberative planners rely heavily on world models can readily integrate world knowledgehave broader perspective and scope Reactive and behavior-based systems afford modular development provide real-time robust performance in dynamic world provide for incremental growth tightly coupled to incoming sensory data
اسلاید 86: Behavior-based systemsBBR is founded on the Subsumption ArchitectureReactive systems are limited by their lack of internal state. BBR systems overcome this limitation because their underlying unit of representation behaviors can store state.Information is not centralized instead various forms of distributed representations are used ranging from static table structures and networks to active procedural processes implemented within the behavior networks.
اسلاید 87: Behavior-based systemsLike hybrid systems they also provide both low level control and High level deliberation.The latter is performed by one or more distributed representations that compute over the other behaviors often directly utilizing low level behaviors and their outputs. The resulting system built from the bottom up does not divide into differently represented and independent components but instead constitutes an integrated computational behavior network.
اسلاید 88: Behavior-based systemsThe whole robot control is built upon a family of behaviors, each implementing a set of actions which specify, at each computational step, the most appropriate response to a perceptual stimulus. An arbitration mechanism allows the system to inhibit a behavior which is not currently requested, eventually, reactivating it later .
اسلاید 89: Behavior-based controllersBehavior-based controllers consist of a collection of behaviors. Behaviors are processes or control laws that achieve and/or maintain goals. For example, avoid-obstacles maintains the goal of preventing collisions, go-home achieves the goal of reaching some home destination.
اسلاید 90: Behavior-based controllersEach behavior can take inputs from the robots sensors (e.g., camera, ultrasound, infra-red, tactile) and/or from other behaviors in the system, and send outputs to the robots effectors (e.g, wheels, grippers, arm, speech) and/or to other behaviors.Thus, a behavior-based controller is a structured network of such interacting behaviors. The behaviors themselves can have state, and can form representations when networked together.
اسلاید 91: Behavior-based controllersThe key difference between behavior-based and hybrid systems is in the way representation and time-scale are handled. Hybrid systems typically employ a low-level reactive system that functions on a short time-scale, and a high-level planner that functions on a long time-scale. The two interact through a middle layer. Consequently hybrid systems are often implemented with so-called three-layer architectures.In contrast, behavior-based systems attempt to make the representation, and thus the time-scale, of the system uniform. Behavior-based representations are parallel, distributed, and active, in order to accommodate the real-time demands of other parts of the system. Furthermore, they are implemented using the behavior structure, much like the rest of the system.
اسلاید 92: پیاده سازی رفتارهاBehaviors can be designed at a variety of abstraction levels In general they are higher than the robots atomic actions.Some implemented behaviors include:Go home , Get recharged, Find Landmark, Pickup Object,..Deciding what behavior to execute at each point in time is called behavior arbitration and is one of the central design challenges of BBR Fixed priority for behaviors
اسلاید 93: مثالStructure of the behavior networks for the delivery task
اسلاید 94: معیارهای انتخاب معماریSupport for parallelismthe ability of the architecture to execute parallel processes/behaviors at the same timeHardware targetabilityhow well the architecture can be mapped onto real-robotsensors and effectorshow well the computation can be mapped onto realprocessing elements (i.e., microprocessors)Run-time flexibilitydoes the architecture allow run-time adjustment and reconfiguration?
اسلاید 95: معیارهای انتخاب معماریModularityhow does the architecture address encapsulation of control?how does it treat abstraction?does it allow many levels?e.g., feedback loops, primitives, agentsRobustnesshow well does the architecture perform if individual components fail? how well does it enable and facilitate writing controllers capable of fault tolerance?
اسلاید 96: معیارهای انتخاب معماریEase of usehow easy to use and accessible is the architecture? are there programming tools and expertise? Performance how well does the robot perform using the architecture? does it act in real-time? does it get the job
اسلاید 97: Designing Principles Designing control programs for autonomous robots is a very difficult activity especially if it is compared with the analogous activity of writing computer programs. These difficulties stem from the hard coupling between the robot and its environment which makes input/output operations to play a crucial role inside the program. The consequence is that robot capabilities are deeply affected by the performance of its sensors, which handle inherently noisy data, and its actuators whose reliability is not perfectly predictable.
اسلاید 98: Text Books:Robot Motion Planning, Jean-Claude Latombe, Kluwer, 1991.Behavior-Based Robotics by R. Arkin
اسلاید 99: Example: Task Control ArchitectureIt means the integration and coordination of perception, planning and real-time control to achieve a given set of goals (tasks).TCA has no built-in control functions for particular robots (such as path planning algorithms)It provides control functions, such as task decomposition, monitoring, and resource management, that are common to many mobile robot applications.TCA can be thought of as a robot operating system .Within NASA, TCA has been used on several robots.
اسلاید 100: Inter-Process Communication TCA provides a flexible mechanism for passing coarse-grained messages between processes (which is called modules).The communication mechanisms automatically marshall and unmarshall data, invoke user-defined handlers when a message is received, and include both publish/subscribe and client/server type messages, and both blocking and non-blocking types of messages. TCA also provides orderly access to robot resources so that you dont have to build your own queuing mechanisms.
اسلاید 101: Planning and ExecutionThe fundamental capability of a robot is to achieve its goals. TCA enables developers to easily specify hierarchical task-decomposition strategies, such as how to navigate to a particular location or how to collect a desired sample. This can include temporal constraints between sub-goals, leading to a variety of sequential or concurrent behaviors. TCA schedules the execution of planned behaviors, based on those temporal constraints.
اسلاید 102: Execution Monitoring and Error RecoveryTCA provides constructs that enable the robot system to monitor selected sensors and inform the system when the monitored conditions are triggered. To recover from errors in plans, TCA utilities enable robot systems to reason about plans, terminate or suspend portions of plans, add patches, and retry plans. TCA provides a hierarchical exception-handling mechanism for specifying context-dependent error procedures.
اسلاید 103: Human/Robot InteractionNo robot will be fully autonomous; interaction with humans is a necessity. TCA provides users with the ability to interact with the robot at any level of the task hierarchy. Users may also view the current task decomposition that the robot is executing, and modify it on the fly, if need be. Note that TCA may not be an appropriate framework for real-time control systems.Source: http://www.cs.cmu.edu/~TCA/tca.orig.html
اسلاید 104: موضوعاتی برای ارائهProbabilistic Road Maps Multi-Robot Systems Subsumption Architecture
اسلاید 105: موضوعاتی برای پروژهیادگیری و روباتشبیه سازی: شبیه ساز روبات کوکا، شبیه ساز روباتهای متحرک،پیاه سازی Slam توسط شبیه ساز
اسلاید 106: برخی پروژه های پیشینسه بعدي فوتبال با استفاده از روش کالمن فيلتر تخمين ميزان آب لازم براي خاموش كردن يك ساختمان مشتعل.RoboCup – Rescue تخمين و پيش‌بينی رفتار گسترش آتش در محيط شبيه‌سازی امداد جلوگيري از برخورد به موانع با استفاده از يادگيري تقويتي براي روبات کپرا طراحی و پياده‌سازی محيط شبيه‌سازی رباتهای متحرک حل سینماتیک معکوس برای ربات افزاینده با۴ درجه آزادی با وجود مانع بوسیله مکان‌يابي روبات فوتباليست در محيط شبيه سازي سه بعدي فوتبال با استفاده از روش پارتيکل فيلترينگ پیاده سازی و مقایسه روشهای مسیریابی ربات استفاده از يادگيري تقويتي براي حرکت روبات در يک مسير منحنيبرنامه ریزی حرکت و جلوگیری از برخورد روبات با موانع با استفاده از پارامترهای فازی حل سينماتيک معکوس در روباتهاي افزونه با استفاده از اتوماتاي يادگير سلولي ارائه يک مدل فازي براي تعيين اولويت خاموش کردن ساختمانهاي آتش گرفته توسط عاملهاي اتش نشان تيم امداد
اسلاید 107: برخی پروژه های پیشینفازی کردن معماری Subsumptionيادگيري مهارت ضربه زدن در روبوکاپ پياده سازي يك ربات يادگير موقعيت يابي با استفاده از کالمن فيلترمسيريابي ربات با استفاده از يک روش تغيير يافته میدان نیروی مجازی، ضمن شناسائي و فرار از مينيمم هاي محليMultiple Target Tracking For Mobile Robots Using the JPDAF AlgorithmMobile Robot Global Localization using Differential Evolution and Particle Swarm Optimizatio
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.