عنوان پایان‌نامه
باز پیکر بندی توزیع شده در ربات های ماژولار
- رشته تحصیلی
- مهندسی کامپیوتر-هوش مصنوعی- رباتیک
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه دانشکده برق و کامپیوتر شماره ثبت: E1890;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 49054
- تاریخ دفاع
- ۱۰ مرداد ۱۳۹۰
- دانشجو
- کیوان گلستان ایرانی
- استاد راهنما
- مسعود اسدپور, منوچهر مرادی سبزوار
- چکیده
- ربات¬های ماژولار، دسته¬ای از ربات¬ها می¬باشند که متشکل از اجزای کوچکتری تحت عنوان ماژول بوده و دارای قابلیت تغییر شکل در پیکربندی فیزیکی خود هستند. ماژول¬های تشکیل دهنده¬ی این ربات¬ها نیز خود ماشین¬های ساده¬ای از نظر ساختار فیزیکی و سیستم¬های حسی، حرکتی و ارتباطی می¬باشند که می¬توانند با اتصال به یکدیگر ساختارهای مختلفی تشکیل دهند. موارد استفاده¬ی این دسته از ربات¬ها بیشتر در فعالیت-هایی است که در آنها بنا به شرایط خاص محیطی، ربات نیاز به تغییر شکل در پیکربندی خود دارد. به همین رو، بازپیکربندی یکی از مهمترین خصوصیات مطرح در ربات¬های ماژولار، و در واقع اصلی¬ترین چالش پیش روی آنها است. اما مشکل اینجاست که افزایش تعداد ماژول¬های تشکیل دهنده، زمان مورد نیاز برای محاسبه¬ی مراحل بازپیکربندی را به صورت نمایی افزایش داده و عملاً استفاده از این ربات¬ها را در مقایس¬های بالاتر غیر ممکن می¬سازد. در راستای حل این مشکل در این پایان¬نامه، روش مدل¬سازی گراف-محور پیکربندی¬ها به همراه یک روش سریع آزمون همریختی، به نام امضای گراف، را به عنوان پایه¬ی کار خود برگزیده و سپس تلاش نموده¬ایم تا با اعمال تغییرات و تعریف روش¬های جدید، گام موثری در بهبود مسئله¬ی بازپیکربندی برداریم. به همین منظور، در ابتدا مسئله¬ی محاسبه¬ی امضای گراف در پیکربندی¬های متشکل از ماژول¬های متقارن را مد نظر قرار داده و با بهره¬گیری از مفهوم مرکزیت توانی گره¬ها در شبکه¬های اجتماعی، روشی ارائه نمونه¬ایم که با استفاده از آن پیچیدگی زمانی محاسبه¬ی امضای گراف در ماژول¬های متقارن از مرتبه¬ی نمایی به چندجمله¬ای کاهش می¬یابد. در ادامه¬ی کار، اعمال دو روش احتمالاتی به چهارچوب کاری خود را نیز مورد بررسی قرار داده و با استفاده از آنها، ضمن تلاش برای بهبود زمان جستجوی مسیر بازپیکربندی، به عاری از برخورد نمودن آن نیز پرداخته¬ایم. در آخر بحث پیکربندی¬های مرکزی را در شبکه¬ی پیکربندی¬ها پیش کشیده و تلاش نموده¬ایم تا با استفاده از آنها گام دیگری در تسریع روند جستجوی مسیر بازپیکربندی برداریم. نتایج بدست آمده نشان از بالا رفتن کارایی الگوریتم محاسبه¬ی گراف برای کار با ماژول¬های پیچیده¬تر، و همچنین افزایش سرعت جستجوی مسیر بازپیکربندی در مقیاس¬های بالاتر، با استفاده از روش¬های احتمالاتی و بکارگیری پیکربندی¬های مرکزی دارد. کلمات کلیدی: ربات¬های ماژولار، بازپیکربندی، امضای گراف، ناوردا همریختی، مرکزیت توانی، جستجوی نمونه-محور، گام¬های تصادفی
- Abstract
- Modular robots are group of robots which are made from small components called Modules, and have the ability to change their physical configuration. Modules themselves are machinery systems which are designed to have plain body and simple sensory, motory and communication mechanisms, and are able to be attached to each other and make different structures. The most useful application of such robotic systems is in cases where due to particular environmental circumstances, robot needs to change shape and adapt to new conditions. Therefore, changing shape, which we call reconfiguration, is one of the most important and challenging features in modular robots. In fact the problem is that necessary time for finding a feasible path between two configurations increases exponentially with the number of modules and their degrees of freedom. Planning to target this problem, we have decided to establish our proposed methods on a graph-based modeling technique which incorporates a fast isomorphism test called Graph Signatures. In our contributions, we have first concentrated on the calculation of graph signature for configurations being made from symmetric modules. We have used concepts from social networks field, like power centrality, to propose an isomorphism invariant method for graph signature calculation. This method helps the time complexity of graph signature calculation in symmetric modules to be dropped from exponential to polynomial. Moreover, we have applied two probabilistic methods to first decrease the needed time for finding a feasible configuration path and second, to make the found path a collision-free one. Finally, we evaluate the network of configurations to measure the influence of central configurations on reconfiguration planning time. Experimental results show an increase in performance of the graph signature calculation algorithm as well as a significant reduction in the required time for reconfiguration planning procedure by using probabilistic methods and central configurations. Keywords:Modular Robots, Reconfiguration, Graph Signature, Isomorphism Invariant, Power Centrality, Sample-based Search, Random Walks
