عنوان پایان‌نامه
ارائه ی روشی برای بهبود بهروری بازپیکر بندی ربات های پودمانی با استفاده از پیکربندی های قطب
- رشته تحصیلی
- مهندسی کامپیوتر- هوش مصنوعی - رباتیک
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی پردیس 2 فنی شماره ثبت: E 3191;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 81178;کتابخانه مرکزی پردیس 2 فنی شماره ثبت: E 3191;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 81178
- تاریخ دفاع
- ۱۵ شهریور ۱۳۹۴
- دانشجو
- پریسا پرهامی علمداری
- استاد راهنما
- مسعود اسدپور, منوچهر مرادی سبزوار
- چکیده
- ربات‌های پودمانی گونه‌ای از ربات‌ها هستند، که توان تطبیق ساختار خود با نیازها و ویژگی‌های محیط را دارند. یکی از مسایل مهم مطرح در عرصه‌ی این ربات‌ها، بازپیکربندی آن‌ها است. منظور از حل این مساله یافتن مجموعه‌ی عملیاتی است که به واسطه‌ی آن‌ها تبدیل ساختار میسر می‌شود. چالش پیش‌روی پژوهشگران برای حل این مساله، بزرگی فضای جستجو و رشد نمایی آن متناسب با پیچیده‌تر شدن ربات است. غالب روش‌های جستجویی که تا کنون ارائه شده‌اند نیازمند مدت زمان زیاد برای انجام محاسبات خود هستند. در این پژوهش با الهام‌گرفتن از سازوکار تصمیم‌گیری انسان در مسیریابی میان مکان‌ها در نقشه، می‌کوشیم راه حلی برای این مساله ارائه دهیم. انسان‌ها در مواجه با فضاهای بزرگ جستجوی مسیر میان دو مکان، می‌کوشند نقشه را با استفاده از نقاط کلیدی آن خلاصه نمایند. به این ترتیب با کاهش اندازه‌ی فضای جستجو، یافتن پاسخ آسان‌تر و سریع‌تر می‌شود. در مساله‌ی بازپیکربندی ربات‌های پودمانی نیز می‌توانیم با یافتن پیکربندی‌های مهم، زمان یافتن پاسخ را بهبود دهیم. چنین پیکربندی‌هایی را پیکربندی‌های قطب می‌نامیم و برای یافتن آن‌ها، روش نمونه‌برداری‌ای مبتنی بردرخت تصادفی کاوشگر سریع و معیاری ترکیبی ارائه می‌نماییم. همچنین روش دیگری برای ساخت تدریجی و برخط ساختار قطب پیشنهاد می‌کنیم. در این روش ساختار قطب تولید شده تطابق بیش‌تری با نیازهای محیطی خواهد داشت. با مدل کردن فضای پیکربندی‌های ربات‌های پودمانی به شکل یک گراف، و نشان دادن خاصیت مستقل از مقیاس آن، مقیاس‌پذیری روش‌های ارائه شده را نشان دادیم. در نهایت با پیاده‌سازی روش‌های پیشنهاد شده برای دو نوع از پودمان‌ها به ارزیابی ایده‌ی مطرح شده پرداختیم. نتایج نشان می‌دهد که روش پیشنهاد شده، پاسخ‌های نزدیک به بهینه را در مدت زمان کم‌تری بدست می‌آورد. زمان یافتن پاسخ در انواع مختلف ربات‌ها ? تا ? برابر کاهش داشته‌است. ضمنا می‌توان دید که زمان یافتن پاسخ در مسائل مختلف، تقریبا مستقل از طول مسیر پاسخ است. روش‌های ارائه شده در این رساله توان بالایی در شناسایی نقاط مهم فضاهای بزرگ دارند .از این‌روی این روش‌ها را می‌توان پاسخی برای مساله‌ی کلی‌تر و مهم یافتن گره‌هایی با بینابینی بالا در گراف‌های شبکه‌های اجتماعی دانست. در همین راستا روش‌های پیشنهاد شده را در حوزه‌ی شبکه‌های اجتماعی نیز به کاربستیم. نتایج حاصل از پیاده‌سازی‌ها و آزمایشات نشان از عملکرد بالای روش‌ها دارد. مجموعه‌ی گره‌های بدست‌آمده از روش ارائه شده تا ?? درصد پوشش بر روی مجموعه داده‌های بدست آمده از روش‌های دقیق دارد. این در حالی است که برای رسیدن به این نتیجه نیازمند نمونه‌برداری زیاد و صرفه هزینه‌های هنگفت نیستیم.
- Abstract
- Self-Reconfigurale modular robots or in short modular robots are composed of a large number of simple and small elements called modules. Each module can attach or detach itself from the others. By means of reconfiguration, modular robots can adapt themselvs with environmental constraints and its requirements. Therefore self-reconfiguration of modular robots is an important aspect of this area and it is considered as a major problem in this field. Solving self-reconfiguration problem (SRP) means finding a plan to change the morphology of robot from an initial configuration to a goal configuration. Because of huge search space, solution finding is a challenge. To the best of our knowledge there is no scalable and time efficient approach to solve this problem. In this paper we model this problem in the form of a graph search, in which nodes are configurations and edges are attachment and detachment actions. We propose a human-inspired approach that abstract the search space and speeds up the reconfiguration planning. In this method, we create a hub-graph containing the major nodes of the graph, which are called the hubs. We propose an RRT-based approach to select the hubs which efficiently cover the configuration space. During the search for a path between two nodes of the graph, an optimal route from a hub to another one is used. Also we proposed an incremental approach to construct hub-graph online. In this approach hubs are select during different searchs. Therefore they are adapted to the robots environment and most used reconfiguration tasks. These methods have been simulated for two different modular robots and the results show that, time spent to find solution are independent of solution length. Experiments show 5 to 8 fold speed up in search time, while founded solutions are near-optimal. Also it has been shown that the transition graph is scale free therefore using hubs is extendable to larger number of modules. Our proposed approaches can be used in general as a way to find important nodes in a graph. In context of social networks finding nodes with high betweenness is a major chalenge. Our RRT-based sampling approach and combinational metric can be used as a method to select a set of nodes with this quality. Results on real problem of SRP and constructed graph prooves our claim. Selected set using our approach covers nearly 65 persent of the nodes with high betweenness centrality. Keywords: Modular robots, Self-Reconfiguration, hub graph, betweenness centrality, human-inspired, Transition graph
