عنوان پایان‌نامه
بهبود روش جستجوی گراف برای خود باز پیکربندی ربات های پودمانی
- رشته تحصیلی
- مهندسی کامپیوتر-هوش مصنوعی- رباتیک
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی پردیس 2 فنی شماره ثبت: E 2858;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 72174
- تاریخ دفاع
- ۱۰ شهریور ۱۳۹۴
- دانشجو
- خلیل طاهری
- استاد راهنما
- مسعود اسدپور, منوچهر مرادی سبزوار
- چکیده
- در این پایان نامه، حل مساله خود بازپیکربندی ربات های پودمانی مورد بررسی قرارگرفته است. این مساله جزء مسائل NP-کامل بوده و هدف آن یافتن توالی از اَعمال اتصال و یا انفصال پودمان ها، برای تبدیل یک پیکربندی اولیه از پودمان ها به یک پیکربندی پایانی از آنها است. از دهه گذشته تا اکنون، حل این مساله، به عنوان یک مساله اصلی محسوب شده و رویکردهای متفاوتی برای حل آن پیشنهاد شده-اند. یکی از رویکردهای پیشنهاد شده، مدلسازی پیکربندی پودمان ها در قالب گراف های پیکربندی و استفاده از روش های جستجوی آگاهانه است. در این رویکرد، جستجوی آگاهانه با دریافت گراف پیکربندی اولیه و با بکارگیری اَعمال اتصال و یا انفصال، مسیری از گراف های پیکربندی میانی را برای تبدیل گراف پیکربندی اولیه به گراف پیکربندی پایانی می یابد. در هر مرحله از جستجو، هر گراف پیکربندی میانی بابکارگیری یک آزمون هم ریختی و معیار شباهت، با گراف پیکربندی پایانی مقایسه می شود. درصورتی که گراف پیکربندی میانی با گراف پیکربندی پایانی هم ریخت باشد، جستجو پایان یافته و مسیر بدست آمده به عنوان پاسخ اعلام می شود. در صورت عدم هم ریختی، بابکارگیری معیار شباهت، شبیه ترین گراف پیکربندی میانی به گراف پیکربندی پایانی برای بسط داده شدن در مرحله بعدی جستجو، انتخاب می شود. این روند تا یافتن پاسخ ادامه می یابد. در این پایان نامه، یک امضای گراف مبتنی بر نظریه چند منظری در انسان ها، امضای گراف چند منظری، برای آزمون هم ریختی گراف های پیکربندی ارائه می شود. در تولید امضای پیشنهادی، پیچیدگی زمانی از O(n^2) مربوط به بهترین روش ها به O(logn) که n تعداد پودمان های پیکربندی است، کاهش می یابد. علاوه براین، بر مبنای امضای پیشنهادی، معیار شباهت جدیدی بین گراف های پیکربندی، برای هدایت بهتر جستجوی آگاهانه ارائه می شود. رویکرد پیشنهادی در یک شبیه ساز پیاده سازی شده و نتایج بدست آمده از شبیه سازی نشان می دهد امضای پیشنهادی با اختلاف معناداری نسبت به روش های قبلی بهتر عمل می کند. سرانجام، امضای گراف پیشنهادی به عنوان تطبیق دهنده گرافی نادقیق برای کاربردهایی نظیر تشخیص اشیاء، توسعه می یابد. واژه‌های کلیدی: ربات های پودمانی، خود بازپیکربندی، امضای گراف، معیار شباهت، نظریه چند منظری
- Abstract
- In this thesis, the problem of Self-Reconfiguration Planning (SRP) of modular robots is studied. SRP is an NP-Complete problem and its goal is to find a sequence of attach or detach actions to reconfigure an initial configuration of modules to a final configuration. For the past decade until now, solving SRP has been a major research issue and different approaches has been proposed to solve it. One of these approaches is based on the modeling of the modules configuration into a graph, called configuration graph, and then informed searches are used. In this approach, the informed search receives an initial configuration graph and by applying the attach or detach actions, tries to find a path consists of intermediate configuration graphs which reconfigure the initial configuration graph to the final configuration graph. In each step of the search process, each intermediate graph is compared with the final configuration graph using a graph isomorphism test. If the intermediate configuration graph and the final configuration graph are isomorphic, the search process is terminated and the current path to the final configuration graph is returned as a solution. Otherwise, the most similar one of the intermediate configuration graphs to the final configuration graph, using a similarity metric, is selected to expand in the next iteration of the search process. The search continues until a solution found. In this thesis, a novel graph signature based on the multiple views theory in humans, called Multi-View Graph Signature (MVGS), is proposed. The time complexity of the graph signature generation is O(logn), in which n is the number of modules, from the best solutions with O(n^2). Also, a new similarity metric between configuration graphs, based on the MVGS, is introduced to guide the informed search more efficient than the previous methods. The proposed approach has been implemented in a simulator and the results show significantly better performance than other previously proposed methods. Finally, the proposed graph signature is generalized as an inexact graph matching approach with applications in object recognition. Keywords: modular robots, Self-Reconfiguration Planning (SRP), graph signature, similarity metric, multiple views theory
