نوع فایل: word
قابل ویرایش 120 صفحه
چکیده:
این مقاله الگوریتمی جدید برای مسئله برنامه ریزی مسیرکلی به یک هدف ، برای ربات متحرک را با استفاده از الگوریتم ژنتیک ارائه می دهد .الگوریتم ژنتیک برای یافتن مسیر بهینه برای ربات متحرک جهت حرکت در محیط استاتیک که توسط نقشه ای با گره ها و لینک ها بیان شده است ،بکار گرفته شده است.موقعیت هدف و موانع برای یافتن یک مسیر بهینه در محیط دو بعدی داده شدهاست .هر نقطه اتصال در شبکه ژنی است که با استفاده از کد باینری ارائه شده است.تعداد ژن ها در یک کروموزوم تابعی از تعداد موانع در نقشه (نمودار)می باشد.
بنابراین از یک کروموزوم با طول ثابت استفاده کردیم.مسیر ربات ایجاد شده ، در مفهوم کوتاهترین مسیر ،بهینه است .ربات دارای محل آغاز و محل هدف تحت فرضیه ای است که ربات از هر محل فقط یکبار می گذرد یا اصلا نمی گذرد.نتایج بدست آمده در شبیه سازی ؛قدرت الگوریتم پیشنهادی را تایید می نماید.
مقدمه:
مسئله طراحی مسیر ربات متحرک را می توان بصورت ذیل بیان کرد:
داده های مسئله (محل شروع،محل هدف، نقشه اي دو بعدی مسیرهاكه شامل موانع ساكن می باشد).هدف بدست آوردن یک مسير بدون تصادم بین دو نقطه خاص در ایفای معیار بهینه سازی با در نظر گرفتن محدودیت ها (به احتمال زیاد:کوتاهترین مسیر)می باشد. مسئله طراحی مسیر از نظر محاسباتی بسیار پر هزینه است.
با اینکه حجم زیادی از تحقیقات برای حل بیشتر این مسائل انجام شده است،با این وجود،روش های معمول ،غیر قابل انعطاف می باشند.
1.اهداف مختلف بهينه سازي و تغييرات اهداف
2. عدم قطعیت ها در محیط ها
3. محدوديت هاي متفاوت براي منابع محاسباتي
مرور و بازنگری روش های موجود برای حل مسئله طراحی مسیر ،در [1] ارائه شده است . روش هاي زيادي براي ايجاد يك مسير بهينه از قبيل برنامه ريزي ديناميك و روش هاي تبدیل مسافت گزارش شده است .
در روش برنامه ريزي ديناميك اگر نقطه ي شروعSP و نقطه ي هدف GP باشد ، نقطه ي زیر هدف IP است.و روش توليد مسیر ،نحوه تعیین توالی زیر اهداف است که زیر اهداف خود از مجموعه IP (I=1,2,3,…) انتخاب می شوند.ما بايد تمام مسیرهای ممکن را بررسی کرده و مسیر با کمترینمقدار هزینه را به عنوان مسیر بهینه انتخاب نمائیم.توان محاسباتی بسیار فراوانی بویژه در محیط های دارای زیر اهداف فراوان مورد نیاز است . در روش تبدیل مسافت ،کارطراحی مسیر ،محیطی را با شبکه یکنواخت می پوشاند و فواصل را از طریق فضای خالی ،از سلول هدف،منتشر می کند.قسمت پیشین موج مسافت ،حول موانع و در نهایت از طریق تمامی فضاهای آزاد در محیط جریان می یابد.برای هر نقطه شروع در محیط نمایانگر محل اولیه ربات متحرک ،کوتاهترین مسیر به مقصد،از طریق رفتن به قسمت پائین و از طریق شیب دارترین مسیر نزولی رسم شده است.با این وجود به هنگام وجود دو سلول یا بیشتر جهت گزینش با همان حداقل تبدیل فاصله ابهام مسیرهای بهینه وجود دارد. دو روش مذکور ملزم توان محاسباتی بسیار بالا در محیطی است که دارای تعداد زیاد اهداف فرعی (زیر اهداف)و موانع است.
محققان روش های فراوان را برای حل مسائل طراحی مسیر ربات های متحرک با وجود موانع ایستا و متحرک بر مبنای soft computing ،بیان کرده اند. soft computing متشکل از منطق فازی،شبکه های عصبی و محاسبات تکاملی است (الگوریتم های ژنتیک و تکاملی GA & EA).تاکنون تلاش های زیادی در استفاده از منطق فازی برای طراحی و برنامه ریزی حرکت ربات متحرک وجود داشته است .اخیرا استفادهاز محاسبات تکاملی رواج فراوانی پیدا کرده و در واقع روشی است که به منظور بکارگیری در موقعیت هایی که دانش اولیه راجع حل مسئله وجود نداشته و یا اطلاعات محدود می باشد،قابلیت استفاده به گونه ای موثرتر،عمومی تر و راحت تر را داراست.
الگوریتم های ژنتیکی و تکامکلی نیازمند اطلاعات اشتقاقی یا برآوردهای فرمال اولیه از راه حل نیستند و از آنجائیکه طبیعتا تصادفی می باشند دارای قابلیت جستجوی کل فضای جواب با احتمال بیشتر پیدا کردن بهینه عمومی می باشند
فهرست مطالب:
1.مسیریابی
2.الگوریتم ژنتیک
3.فرمول سازی مسئله
4.الگوریتم طراحی مسیر پیشنهادی
كروموزوم ها و جمعیت اولیه
ارزیابی
عملگرها
5.نتايج شبيه سازي
بررسی بیشتر
طراحی مسیر در فضای مسیر گلوله
طراحی مسیر با طراحهای محلی
منابع
منابع و مأخذ:
[1] J. C. Latombe, "Robot Motion Planning", Norwell, MA: Kluwer, 1991.
[2] Memetic Algorithm Based Path Planning for aMobile Robot
Neda Shahidi, Hadi Esmaeilzadeh, Marziye Abdollahi, Caro Lucas
INTERNATIONAL JOURNAL OF INFORMATION TECHNOLOGY VOLUME 1 NUMBER 3 2004 ISSN 1305-2403
[3] GENETIC ALGORITHM FOR ROBOT PATH ESTIMATION
Ćurković, P.; Jerbić, B. & Vranješ, B.
THE 17TH INTERNATIONAL DAAM SYMPOSIUM
"INTELLIGENT MANUFACTURING & AUTOMATION: FOCUS ON MECHATRONICS & ROBOTICS"
8-11TH NOVEMBER 2006
[4] C. Hocaoglu, A.C. Sanderson, "Planning Multiple Paths with Evolutionary Speciation", IEEE Trans.on Evolutionary Computation, Vol.5, No. 3, JUNE2001.
[5] A Comparison of Genetic Programming and Genetic Algorithms forAuto-tuning Mobile Robot Motion Control
M. Walker, C. H. Messom
Institute of Information and Mathematical Sciences,
Massey University, Albany Campus, Auckland, New Zealand.
fM.G.Walker, C.H.Messomg@massey.ac.nz
[6] ROBOT PATH PLANNING INUNSTRUCTURED ENVIRONMENTS USING A
KNOWLEDGE-BASED GENETIC ALGORITHM
Simon X. Yang ∗,∗∗ Yanrong Hu∗∗
Institute of Computer Science and Technology, Chongqing
University of Posts and Telecommunications, China School of Engineering, University of Guelph, Canada
[7] D. E. Goldberg, "Genetic Algorithms in Search,Optimization, and Machine Learning", Addison-Wesley Publishing Company, 1989.
[8] "OBSTACLES AVOIDANCE IN A SELF PATH PLANNING
OF A POLAR ROBOT"JUAN CARLOS ROSETE FONSECA1, EFRÉN GORROSTIETA HURTADO2,JOAQUIN PEREZ MENESES3.
9] Intelligent Automation and Soft Computing, Vol. 10, No. 1, pp. 51-64, 2004 Copyright © 2004, TSI®Press Printed in the USA. All rights reserved 51
MOBILE ROBOT PATH PLANNING USING HYBRID GENETIC ALGORITHM
AND TRAVERSABILITY VECTORS METHOD
C.-K. LOO 1,2 M. RAJESWARI 2 E. K. WONG1 M. V. C. RAO1
Faculty of Engineering and Technology Multimedia University (Melaka)75450 Melaka, Malaysia
e-mail: ckloo@mmu.edu.my
School of Industrial Technology Universiti Sains MalaysiaPenang, Malaysiae-mail:mandava@cs.usm.my
[10]A Comparison of Genetic Programming and Genetic Algorithms for
Auto-tuning Mobile Robot Motion Control
M. Walker, C. H. MessomInstitute of Information and Mathematical Sciences,
Massey University, Albany Campus, Auckland, New Zealand.{M.G.Walker,