پیشرفته ترین روبات چهارپای دنیا (سگ بزرگ) big dog

ربات BigDog یک از اعضای خانواده‌ی ربات‌های بوستون داینامیکز است. این یک ربات چهارپا است که می‌توان راه برود، بدود، روی نواحی ناهموار حرکت کند و یا بارهای سنگین را جابه‌جا نماید. ربات BigDog توان حرکت خود را از یک موتور بنزینی دریافت می‌کند. این موتور محرک‌ها و عمل‌گرهای هیدرولیکی موجود بر روی این ربات را کنترل می‌نماید. پاهای او هم‌چون پاهای حیوانات طراحی شده است. این پاها دارای عناصری هستند که می‌توانند ضربات ناگهانی را جذب کرده و مانع واژگونی ربات در اثر این ضربات شوند. ابعاد این ربات که به اندازه‌ی یک سگ بزرگ و یا یک قاطر کوچک است، حدود یک متر طول، هفتاد سانتی متر بلندی و هفتاد و پنج کیلوگرم وزن است.

ادامه نوشته

رونمایی ازخودروی خورشیدی پیشرفته ایرانی

خودروی خورشیدی دانشگاه آزاد که سرعت آن ۱۳۵ کیلومتر در ساعت است، رونمایی شد.

          

خودروی خورشیدی دانشگاه آزاد صبح امروز (پنج‏شنبه) در حاشیه افتتاحیه ششمین دوره از مسابقات روبوکاپ آزاد ایران در نمایشگاه بین المللی تهران رونمایی شد.

این خودرو توسط محققان واحد قزوین دانشگاه آزاد طراحی و ساخته شده است و وزن آن ۱۶۰ کیلو گرم و جنس آن فیبر کربن است.

قالب این خودرو فایبرگلاس بوده و توانایی سرعت آن ۱۳۵ کیلومتر در ساعت است.

جنس باطری این خودرو لیتیوم یون بوده و همچنین سیستم ارتباطی آن cambus است و ۲۲.۶دهم درصد بازدهی دارد.

ربات های ايران با 11 گل چين را درهم كوبيدند

تيم رباتيك MRL از دانشگاه آزاد قزوين با نتيجه 11 بر صفر تيم چين را شكست داد.

          

در ليگ ربات‌هاي فوتباليست متوسط دو تيم متشكل از پنج ربات در يك زمين داخل سالن به ابعاد 12 در 18 متر فوتبال بازي مي‌كنند.

هر ربات مجهز به سنسورهاي مختلف و كامپيوتر جهت تحويل وضعيت كنوني بازي و انجام يك بازي موفق است. ربات‌ها با استفاده از ارتباط بي‌سيم با يكديگر در تماس هستند و همچنين از اين طريق پيام‌هاي داور را دريافت مي‌كنند اما هرگونه دخالت انسان در هر بازي از هر طريقي كاملا ممنوع است مگر زمان تعويض يك بازيكن (ربات).

در اين دوره از مسابقات سه تيم از كشور ايران، چين و ژاپن در ليگ ربات فوتباليست سايز متوسط شركت كرده‌اند.

در نخستين بازي تيم MRL از ايران موفق به شكست تيم استرايو از كشور چين با نتيجه 11 بر صفر شد.

ساخت روباتی که بر روی DNA راه می رود!!

دانشمند‌ان می‌گویند این ربات كه دو پا دارد و در مقیاس نانو طراحی شده بسیار بهتر و كارآمدتر از تمام نمونه‌های ساخته شده قبلی قادر است روی رشته دی ان ای راه برود... محققان ادعا كرده‌اند، این ربات جدید بر خلاف نمونه های قبلی بی‌هدف به عقب و جلو نمی رود، از مسیر خود خارج نمی‌شود و مسیری را كه بر روی آن راه می‌رود، تخریب نمی کند
این محققان هم چنین مدعی شده‌اند كه نیروی نانوربات جدید به روشی هوشمندانه تامین می‌شود به طوری كه به این وسیله مینیاتوری امكان داده می‌شود آزادانه بتواند حركت كند
این تیم پژوهشی اعلام كردند: نانو ربات دارای دو پای متصل به هم است كه هر كدام از یك رشته كوتاه رشته دی ان ای ساخته شده كه به یك رشته كامل روی مسیر رشته دی ان ای متصل می‌شوند
محققان خاطر نشان كردند: انرژی این نانوربات از طریق مولكول‌هایی كه در نزدیكی آن در جریان و شناور هستند، تامین می‌شود

یک ربات تمیزکننده به شکل کرم!!

از آنجایی که بشر به فکر رفاه بیشتر است ساخت ربات ها در همه جهات برای رفاه هر چه بیشتر انسانها به پیش می رود از ایده ساخت ربات هایی جهت خدمت در منزل و انجام کارهای روزمره استقبال خوبی شده و روز به روز بر تعداد و گونه ربات ها و عملکردهای بهتر آنها افزوده می شود این بار متخصصان ژاپنی رباتی کرم مانند ابداع کرده اند که می تواند به صورت خودکار بر روی زمین حرکت کرده و قسمتهای آلوده سطوح مختلف را پاک کند. به گزارش خبرگزاری مهر، شرکت پاناسونیک محصولی جالب توجه را به منظور کمک در نظافت سطوح سالنهای بزرگ ارائه کرده است.

این محصول رباتی به شکل یک کرم بزرگ سفید رنگ با نام "فوکیتوریموشی" ( کرم تمیز کننده) است که توسط لایه ای نانویی پوشش داده شده است. این لایه از رشته های پلی استری تشکیل شده است که می تواند ذرات غبار را با قدرتی بالا ربوده و سطوح را پاک کند.
به گفته تولید کنندگان این ربات، هر یک از نانوفیبرهای پلی استری استفاده شده در این پوشش 7 هزار و 500 بار از تار موی انسان نازکتر هستند.

ادامه نوشته

کوچکترین هواپیمای جهان به اندازه یک مگس!!

محققان تا به حال در چـنـدین گـروه پژوهـشی برای ساخت حشـرات كـوچك رباتیـك كه طـول، عـرض و ارتـفاع آنها كمتر از ۱۵ سانـتی متر باشد، تلاش های زیادی کرده ان د و میلیون ها دلار صرف این پروژه نموده اند؛ این ربات های پرنده كوچك، در اصل كوچك ترین هواپیمای جاسوسی بدون سرنشین در جهان است. نوعی از این ربات های پرنده كوچك به تقلید از حركات پرواز و نحوه بال زدن حشرات مشخصی در حال طراحی هستند. از جمله این حشرات می توان به مگس و زنبورعسل اشاره كرد زیرا پرواز مگس نكات بی شماری از هوانوردی را به بشر می آموزد كه همه آنها با بررسی بال های ثابت هواپیما قابل دریافت نیست. چرا كه اصول و قواعد پرواز حشرات و بال های متحرك آنها با اصول و قواعد پرواز با بال های ثابت هواپیما تفاوت دارد.

ادامه نوشته

روش های جستجوی متاهیوریستیکی

روش های جستجوی متاهیوریستیکی
در مسائل NP زمانی که اندازه مسئله بزرگ باشد، استفاده از روش های جستجوی آگاهانه و ناآگاهانه میسسر نخواهد بود. چراکه در این رده مسائل فضای حالت مسئله چنان بزرگ می باشد که رسیدن به جواب مسئله در مدت زمان قابل قبول با استفاده این روش های جستجو غیرممکن خواهد بود. از اینرو نیاز به روش هایی داریم که بتواند در بخش های مختلف فضای حالت حرکت کرده و بتواند عمل جستجو را انجام دهد. در اینجا روش هایی جستجو مطرح می شوند که به آنها روش های جستجوی متاهیوریستیکی خواهیم گفت. به همه روش های جستجوی متاهیوریستیکی که در اینجا به بررسی آنها خواهیم پرداخت، در اصطلاح روش های
تصادفی هدایت شده گوییم. همانطور که از نام آنها پیداست هریک از این روش های جستجو به طور تصادفی در فضای حالت مسئله حرکت می کنند. البته باید گفت که انجام حرکات تصادفی با کنترل و هدایت الگوریتم انجام می پذیرد. ممکن است چنین تصور شود که به علت تصادفی بودن حرکت ، کارآیی این الگوریتم ها پایین باشد. در حالی در بیشتر مسائل بهینه سازی این روش های جستجو تنها روش حل مساله خواهند بود.

روش های جستجوی محلی
برای معرفی هریک از روش های جستجویی که در فصل به بررسی آن ها می پردازیم از مسئله 8 وزیر استفاده خواهیم کرد. در مسئله 8 وزیر هدف قرار دادن 8 وزیر بر روی صفحه شطرنج به گونه ای است که هیچیک از وزیرها همدیگر را گارد ندهند. تعمیم یافته مسئله 8 وزیر، مسئله n وزیر است که در آن بر روی یک صفحه شطرنج n*n باید n وزیر را به گونه ای قرار دهیم که هیچیک همدیگر را گارد ندهند. مسئله n وزیر از جمله مسائل NP در هوش مصنوعی است که روش های جستجوی معمولی قادر به حل آن ها نخواهد بود. از سوی دیگر می توان به مسئله 8 وزیر به عنوان یک مسئله بهینه سازی نیز نگریست که در آن هدف بهینه کردن تعداد گاردهای جفت وزیرها می باشد. به عنوان مثال فرض کنید در صفحه شطرنج معمولی ، 8 وزیر را به دو روش زیر قرار دهیم :

در روش چینش سمت چپ 3 وزیر و در روش چینش سمت راست 4 وزیر همدیگر را گارد می دهند. بنابراین روش چینش قبلی بهینه تر از روش چینش فعلی است. در واقع می توان مسئله بهینه سازی را به صورت زیر تعریف کرد. فرض کنید S مجموعه همه جواب های ممکن برای مسئله باشد. در صورتی S* می تواند جواب مسئله باشد که به ازای همه جواب های موجود در S ، S* بهینه تر از دیگر جواب ها باشد. در مسئله 8 وزیر دیدیم که جوابی بهینه است که تعداد گاردهای جفت وزیر آن کمتر باشد.

روش های جستجوی محلی همگی حالت های همسایه حالت فعلی را برای رسیدن به بهینه ترین جواب بررسی می کنند. از این رو وجود دو تابع در همه این روش های جستجو الزامی است. اولین تابع میزان بهینگی جواب مسئله ارزیابی می کند و تابع دوم یکی از حالت های همسایه حالت فعلی را انتخاب می کند.

سخن آخر اینکه نحوه پیاده سازی و طراحی الگوریتم برای انتخاب حالت هسایه در این روش های جستجو از اهمیت ویژه ای برخوردار است. به عنوان مثال برای مسئله 8 وزیر می توان به شکل های زیر حالت های همسایگی را تولید کرد :
1) دو وزیر به تصادف انتخاب شده و جای آن دو باهم عوض گردد.
2) یکی از وزیر ها به تصادف انتخاب شده و شماره سطر آن به تصادف تغییر کند.
3) ویزیری به تصادف انتخاب شده و یک خانه به سمت بالا یا پایین حرکت کند

روش های جستجوی ناآگاهانه

روش های جستجوی ناآگاهانه

روش های جستجوی ناآگاهانه

مسئله یافتن کوتاهترین مسیرها در یک گراف جهت دار را در نظر بگیرید . یکی از روش های یافتن کوتاهترین مسیر در یک گراف جهت دار استفاده از الگوریتم فلوید می باشد . مسئله کوتاهترین مسیر بین شهرها حالت خاصی از مسئله کوتاهترین مسیر در یک گراف جهت دار است که در آن در صورتی که بین دو گره مسیری وجود داشته باشد ، این مسیر حتما در دوجهت می باشد . در این مسئله نیز می توان از الگوریتم فلوید استفاده کرد . اما در حال حاضر هدف استفاده از روش های جستجوی ناآگاهانه و آگاهانه برای یافتن کوتاهرین مسیر است . جستجوهای ناآگاهانه استفاده شده در این برنامه شامل روش های جستجوای زیر می باشد :
1 ) جستجوی سطحی
2 ) جستجوی سطحی یکنواخت
3 ) جستجوی عمقی
4 ) جستجوی عمقی محدود
5 ) جستجو عمقی تکراری

هریک از این جستجوها معایب و محاسن خاص خود را دارند ، اما از میان این روش های جستجو ، جستجوی سطحی یکنواخت ، همیشه بهینه است . با این حال این روش نیز مشکل زمانبر بودن را داراست . جستجوی آگاهانه ای که در این برنامه از آن استفاده شده است روش جستجوی A* می باشد . این روش جستجو با بهره گیری از روش های جستجوی سطحی و حریصانه اقدام به حل مسائل می کند . مهمترین نکته در مورد این روش جستجو این است که هیوریستیک استفاده شده در این روش باید یک هیوریستیک قابل قبول باشد .

نحوه استفاده از برنامه
برنامه فقط شامل یک پنجره اصلی است که همه ورودی ها در این پنجره وارد می شوند . پنجره اصلی برنامه از سه قسمت تشکیل یافته است . در سمت راست صفحه ترسیم نقشه قرار دارد . در این صفحه می توانید گراف بدون جهت مورد نظر را ترسیم کنید . در سمت چپ نیز یالهای خارج شده و وارد شده از هر گره به همراه وزن هریک از یالها و همچنین فاصله مستقیم هر گره از بقیه گره ها نشان داده می شود . قسمت بالایی فرم نیز شامل نوار ابزاری است که همه عملیات توسط دگمه های قرار گرفته بر روی نوار ابزار انجام می شوند .

ترسیم گراف در صفحه ترسیم
صفحه ترسیم در سمت راست فرم قرار دارد . برای قرار دادن گره ها بر روی این صفحه کافی است بر روی نقطه مورد نظر یک بار کلیک کنید . با یک بار کلیلک کردن بر روی صفحه ترسیم گره ای به صفحه اضافه می شود . برای حذف گره نیز می توانید بر روی گره مورد نظر دابل کلیک کنید . برای انتخاب گره نیز کافی است بر روی گره یک بار کلیک کنید . گره انتخاب شده رنگ متفاوتی نسبت به سایر گره ها خواهد داشت .

زمانی که گره ای را انتخاب می کنید ، نام آن گره به همراه همه یالهای متصل به این گره در قسمت بالای سمت چپ پنجره به نمایش در می آیند . نام گره و وزن یال ها را می توانید در این قسمت تغییر دهید . در صورتی که یالی از گره انتخاب شده به دیگر گره ها وجود نداشته باشد ، بخش بالایی سمت چپ فقط نام گره را نشان خواهد داد . در قسمت پایینی سمت چپ نیز فاصله مستقیم گره انتخاب شده از بقیه گره ها به نمایش در می آیند . این مقادیر را نیز می توانید تغییر دهید . به صورت پیش فرض هنگامی که یالی بین دو گره رسم می شود ، فاصله بین این دو گره ( وزن یال ) فاصله اقلیدسی بین آن ها در نظر گرفته می شود.

ترسیم یال از گره 1 به گره 2
ابتدا با کلیک کردن بر روی گره 1 آن گره را انتخاب کنید . سپس کلید Ctrl را فشار داده و و بر روی گره 2 کلیک کنید . در این هنگام یالی بین گره 1 و گره 2 ترسیم می شود . در صورتی که یالی بین گره اول و گره دوم وجود داشته باشد و سعی در ترسیم دوباره یال داشته باشید ، برنامه از ترسیم یال خودداری کرده و سیگنالی را برای آگاهی شما پخش می کند .

می توانید نقشه ترسیم شده را ذخیره کرده و یا نقشه ذخیره شده ای را باز کنید . برای این منظور می توانید از دکمه های قرار گرفته بر روی فرم استفاده کنید . دکمه New یک صفحه ترسیم جدید باز می کند . دکمه Load فایل نقشه را باز می کند و دکمه Save نقشه ترسیم شده را ذخیره می کند .

الگوریتم Threhsold Acceptance

قبل از شرح این روش جستجو پیشنهاد می کنیم در صورتی که با الگوریتم SA آشنایی ندارید، ابتدا مقاله مربوط به این روش جستجو را مطالعه کنید. روش TA نیز همانند روش SA می باشد و تنها تفاوت آن در نحوه قبول کردن جواب های غیر بهینه است. شبه کد زیر نحوه اجرای الگوریتم TA را نشان می دهد:
Procedure Threhsold Acceptance
C = Choose an initial solution
T = Choose a positive initial threshold
REPEAT
S' = Generate a neighbor of the solution C
ΔE = objective( S' ) – objective( C )
IF (ΔE > -T ) THEN // S' better than C
C = S'
END IF
T = lower the T using linear/ non-linear techniques
UNTIL meet the stop criteria
End
الگوریتم TA جواب هایی را می پذیرد که از جواب قبلی خیلی بدتر نیستند. همانند کاری که دما در اگوریتم SA انجام می دهد. همانطور که در روش SA بررسی کردیم، دما در این الگوریتم باید به گونه ای انتخاب شود که بیشتر جواب های غیربهینه در ابتدا توسط الگوریتم پذیرفته شوند. این اصل در مورد روش TA نیز صادق است و در این روش نیز مقدار آستانه ( T ) باید به نحوه انتخاب گردد که بیشتر جواب های غیربهینه در ابتدا توسط الگوریتم مورد پذیرش واقع شوند.

الگوریتم Simulated Annealing

الگوریتم Simulated Annealing

روش SA یکی از روش های متاهیوریستیکی احتمالی است که ایده آن از عمل سرد کردن تدریجی فلزات برای استحاکم بیشتر آن ها نشات گرفته است. همانند روش های تپه نوردی و تپه نوردی تعمیم یافته ، در این روش نیز مسئله از یک حالت مانند S در فضای حالت مسئله شروع کرده و با گذر از حالتی به حالت دیگر به جواب بهینه مسئله نزدیک می شود. انتخاب حالت شروع هم می تواند به صورت تصادفی انجام پذیرد و هم می تواند بر اساس یک قاعده حالت اولیه مسئله را انتخاب کنیم. در اینجا نیز تابع Objective میزان بهینگی حالت فعلی را محاسبه کرده و Neighbor یک حالت همسایه برای حالت فعلی تولید می کند.

روش کلی کار به این صورت است که در هر تکرار ، الگوریتم SA حالت همسایه ای مانند s' ایجاد می کند و بر اساس یک احتمال ، مسئله از حالت s به حالت s' می رود و یا اینکه در همان حالت s باقی می ماند . این روند تا زمانی تکرار می شود که به یک جواب نسبتا بهینه برسیم یا اینکه ماکزیمم تعداد تکرار ها را انجام داده باشیم. همانطور که قبلا نیز بررسی کردیم نحوه تولید حالت همسایه از اهمیت به سزایی برخوردار است.
در روش کلی الگوریتم بیان کردیم که قبولی حالت همسایه تولید شده بر اساس یک احتمال صورت می پذیرد . تابع ( P(e,e',T تعیین کننده احتمال قبولی حالت همسایه می باشد . e بهینگی حالت فعلی و e' بهینگی حالت همسایه می باشد . در صورتی که حالت همسایه از حالت فعلی بدتر باشد ، مقدار پارامتر T تعیین کننده احتمال قبولی جواب می باشد . در ابتدای امر مقدار پارامتر T را طوری انتخاب می کنیم که اکثر حالت های همسایه را مورد پذیرش قرار دهیم ، پارامتر T نشانگر دما بوده و مقدار این پارامتر به تدریج کاهش می یابد . مقدار پارامتر T را طوری انتخاب می کنیم که قبل از انجام گرفتن ماکزیمم تعداد تکرارها ، مقدار آن تقریبا صفر گردد . مستنداتی که برای الگوریتم SA وجود دارد، نشان می دهند که در ابتدای امر مقدار T بهتر است به گونه ای تعیین گردد که در ابتدا 80% جواب ها مورد پذیرش الگوریتم واقع شود. روش کلی این الگوریتم به صورت زیر خواهد بود : Procedure Simulated Annealing
C = Choose an initial solution
T = Choose an initial temperature
REPEAT
S' = Generate a neighbor of the solution C
ΔE = objective( S' ) – objective( C )
IF (ΔE > 0 ) THEN // S' better than C
C = S'
ELSE with probability EXP( ΔE/ T )
C = S'
END IF
T = lower the T using linear/ non-linear techniques
UNTIL meet the stop criteria
End در روش تپه نوردی برای گریز از بهینگی های محلی عمل جهش در فضای حالت را انجام دادیم . اما در روش SA به شکل دیگری به مقابله با این مشکل می پردازیم. در این روش وجود پارامتر T باعث می شود حتی در صورتی که بهینگی جواب همسایه بدتر از حالت فعلی باشد بر اساس مقدار T احتمال قبولی همین حالت نیز وجود دارد . قبول کردن جواب های غیربهینه باعث می شوند که این الگوریتم با موفقیت از بهینگی های محلی عبور کند.

در صورتی که e'< e باشد ، تابع P مقدار 1 برمی گرداند ( یعنی احتمال قبولی حالت همسایه 100% است ) . در غیر این صورت ( e'>e ) تابع P بر اساس مقدار T و اختلاف بین e' و e مقداری بین صفر و یک بر می گرداند که نشان دهنده احتمال قبولی حالت همسایه است .

در روش سرد کردن تدریجی فلزات ، برای استحکام هرچه بیشتر فلز ، دما به تدریج کاهش می یابد . در روش SA نیز مقدار T را به تدریج کاهش می دهیم . مقدار T به هرمیزانی که زیاد باشد ، باعث می شود که احتمال قبولی جواب های بد نیز بالا باشد . اما چون مقدار T رفته رفته کاهش می یابد ، بنابراین زمانی که مقدار T به اندازه کافی کم شد ( دما به اندازه کافی پایین آمد ) احتمال قبولی جواب های بد نیز به صفر میل می کند . از این لحظه به بعد فقط حالت هایی مورد پذیرش قرار می گیرند که هزینه آن ها بهتر از هزینه حالت فعلی باشند . به عبارت دیگر زمانی که مقدار T به صفر نزدیک شود ، در صورتی حالت همسایه به عنوان حالت فعلی انتخاب می شود که e' < e باشد . مقدار T باید به گونه ای انتخاب گردد که هنگام رسیدن به دمای صفر ، الگوریتم از بهینگی های محلی عبور کرده و در نزدیکی بهینگی سراسری قرار گرفته باشد.

برای کاهش دما، T را در یک ضریب همانند r که مقدار بین 0 و 1 دارد، ضرب می کنیم. کاهش دادن سریع دما موجب خواهد شد که همچنان با مشکل بهینگی های محلی مواجه باشیم. بنابراین مقدار این پارامتر را همیشه نزدیک به عدد 1 انتخاب می کنیم. ( مثلا 0.998 ). در الگوریتم SA انتخاب دما نقس بسیار زیادی در موفقیت الگوریتم دارد. انتخاب دمای اولیه بسیار بزرگ موجب کندی الگوریتم و انتخاب دمای کم موجب قرار گرفتن در نقاط بهینگی محلی می شود. استفاده از دمای بسیار زیاد در صورتی که مدت زمان کافی برای حل مساله داشته باشیم ، بهتر به نظر می رسد. با این حال هنگام پیاده سازی الگوریتم SA برای یک مساله خاص بهتر آن است که دمای اولیه الگوریتم با توجه به بزرگی مساله تعیین گردد. با اینکه مشکل بهینگی های محلی در الگوریتم SA حل شده است، با این حال در برخی مسائل هنگام استفاده از این الگوریتم به مشکلاتی بر خواهیم خورد. در الگوریتم SA ممکن است هنگام تولید حالت همسایگی به حالتی گذر کنیم که قبلا یکبار این حالت را مشاهده کرده ایم. البته نمی توان برگشت به حالت تکراری را مشکلی برای الگوریتم تلقی کرد. چرا که در برخی موارد همین برگشت به حالت قبلی ممکن است موجب بهبود الگوریتم گردد. اما برای رفع این مشکل نیز روش جستجوی Tabu پیشنهاد گردید که در ادامه به بررسی آن نیز می پردازیم.

جستجوی پرتو محلی

جستجوی پرتو محلی
در الگوریتم تپه نوردی ابتدا یک جواب تصادفی برای مسئله تولید می کردیم و سپس سعی بر آن داشتیم که با تولید حالت های همسایه حالت فعلی و انتخاب بهترین حالت همسایه ، به سمت جواب بهینه حرکت کنیم. همچنین با تغییر کوچکی که بر روی الگوریتم تپه نوردی انجام دادیم ، مشکل قرار گرفتن الگوریتم در بهینگی محلی را حل کردیم ( این روش تنها در مورد مسائل کوچک جوابگو خواهد بود ).
روش جستجوی دیگری بر پایه جستجوی تپه نوردی به نام جستجو پرتو محلی نیز وجود دارد که در حل مسائل از قدرت بسیار بیشتری نسبت به جستجوی تپه نوردی برخوردار می باشد. در این روش برخلاف روش تپه نوردی ابتدا k جواب برای مساله تولید می کنیم. سپس برای هریک از این K حالت همسایه های آن ها را تولید کرده و از میان همه همسایه ها K تا از بهترین همسایه ها را انتخاب می کنیم که این فرآیند تا رسیدن به شرط توقف ادامه می یابد. بنابراین الگوریتم روش جستجوی پرتو محلی به را به صورت زیر می توان بیان کرد :
Procedure LoacBeamSearch
Generate K solution
Do
For each solution generate its neighbors
Select K best solution from whole neighbors
Replace current solutions by selected solutions
Loop until stop criterion satisfied
End
هرچند که الگوریتم جستجوی پرتو محلی در مقایسه با الگوریتم تپه نوردی از کارآیی بیشتری برخوردار است، با این حال هر دو این روش ها از قرار گرفتن در بهینگی های محلی مصون نیستند. از اینرو نیاز به روش های دیگری داریم که بتوانند از بهینگی های محلی گذر کرده و به سمت بهینگی سراسری حرکت کنند. از جمله این روش ها می توان به روش Simulated Annealing ، Tabu Search و Threshold Acceptance اشاره کرد که در مقالات دیگری به بررسی هریک از این روش ها پرداخته ایم.

الگوریتم تپه نوردی

الگوریتم تپه نوردی

الگوریتم تپه نوردی بدین صورت است که ابتدا جوابی به شکل تصادفی برای مساله تولید می شود. سپس در یک حلقه و تا زمانی که شرط توقف الگوریتم برقرار نشده است، به طور مکرر تعدادی همسایه برای حالت فعلی تولید شده و از میان حالت های همسایه بهترین آن ها انتخاب شده و جایگزین حالت فعلی می شود ( البته تالگوریتم په نوردی به شکل دیگری نیز تعریف شده است).
در حالت کلی بهینگی جوابی که این الگوریتم پیدا می کند محلی است. لازم بذکر است که منظور از بهینگی مینیمم سازی یا ماکزیمم سازی یک مسئله بهینه سازی می باشد. مفهوم محلی بودن بهینگی را در شکل روبرو شرح می دهیم . فرض کنید مسئله ای که می خواهیم به
بهینه سازی آن بپردازیم ، یک مسئله ماکزیمم سازی باشد. ماکزیمم سازی در تصویر فوق بدین معنی است که شخص نشان داده شده در پایان اجرای الگوریتم بر روی بلندترین قله قرار گیرد.

در صورتی که از الگوریتم بهبود تکراری برای ماکزیمم سازی استفاده کنیم ، ممکن است تنها به جواب هایی دست یابیم که این جواب ها ماکزیمم های محلی هستند و نه ماکزیمم های سراسری. چرا که الگوریتم بهبود تکراری بهترین همسایه جواب فعلی را به عنوان جواب بهینه تر بر می گزیند. فرض کنید الگوریتم بهبود تکراری برای شروع نسمت چپ ترین نقطه تصویر را انتخاب می کند، در هربار تکرار حلقه ، همواره همسایه ای برای نقطه فعلی وجود دارد که بهینگی آن بهتر از جواب فعلی است. بنابراین در ابتدا الگوریتم اجرا شده و مرتبا به طرف بالا حرکت می کند. تا اینکه به نقطه ماکزیمم محلی می رسد ( قله ای که شخص در تصویر بر روی آن قرار دارد ). در این نقطه هیچ همسایه ای که بهتر از جواب فعلی باشد، وجود ندارد. از اینرو الگوریتم در این نقطه به پایان می رسد و جواب فعلی را به عنوان بهینه ترین جواب بر می گرداند.

بنابراین نقطه شروع در الگوریتم های جستجو محلی بسیار در ادامه اجرای الگوریتم تاثیرگذار خواهد بود. البته ممکن است با اجرای چندباره الگوریتم به جواب بهینه سراسری دست یابیم، اما در کل استفاده از روش بهبود تکراری برای مسایل پیچیده توصیه نمی شود. حال به نحوه استفاده از این الگوریتم برای حل مساله 8 وزیر می پردازیم و نشان می دهیم که الگوریتم بهبود تکراری حتی جوابگوی مسئله 8 وزیر نخواهد بود.

برای پیاده سازی روش تپه نوردی نیاز به دو تابع Objective و Neighbor داریم. تابع Objective میزان بهینگی جواب مسئله را تعیین می کند که در مورد مسئله 8 وزیر تعداد گاردهای جفت وزیرها بر روی صفحه شطرنج را بر می گرداند. تابع Neighbor نیز همسایه های حالت فعلی را تولید می کند که در مسئله 8 وزیر برای تولید حالت های همسایه، هریک از وزیرها را انتخاب کرده و یکبار به سمت بالا و باردیگر به سمت پایین حرکت می دهیم. این بدان معنی است که در بدترین حالت هر حالت، 16 حالت همسایه خواهد داشت که در هر تکرار از حلقه بهترین حالت همسایه به عنوان جواب جایگزین خواهد شد. الگوریتم نیز زمانی به اتمام می رسد که حالت بهتری نسبت به حالت فعلی تولید نشود. شبه کد زیر نحوه پیاده سازی الگوریتم تپه نوردی را نشان می دهد:
Procedure HillClimbing
Generate a solution ( s' )
Best = S'
Loop
S = Best
S' = Neighbors (S)
Best = SelectBest (S')
Until stop criterion satisfied
End

جستجوی *A

روش جستجوی *A یکی از الگوریتم های پیچیده جستجو در هوش مصنوعی است. با وجود اینکه مقالات زیادی در مورد این روش جستجو می توان بر روی اینترنت پیدا کرد ، اما اغلب این مقالات به گونه ای هستند که درک صحیح آن ها برای افراد تازه کار در زمینه جستجوی *A مشکل است. این مقاله با بیان کردن مفاهیم بنیادی شما را در درک هرچه بهتر روش جستجوی*A یاری می کند.

روش جستجوی*A تلفیقی از روش جستجوی هزینه یکنواخت ( UCS ) و روش جستجوی

حریصانه ( Greedy ) است. در جستجوی هزینه یکنواخت بر اساس هزینه تا گره فعلی ، کم هزینه ترین گره را انتخاب کرده و گسترش می دهیم. جستجوی هزینه یکنواخت بهینه است ، یعنی جواب بهینه مسئله را پیدا می کند ولی در مقابل بسیاز زمانبر است. جستجوی حریصانه نیز بر اساس هزینه تا مقصد ، کم هزینه ترین گره را برای گسترش انتخاب می کند. یافتن جواب با استفاده از جستجوی حریصانه به سرعت انجام می گیرد. ولی این روش نیز از مشکلاتی همچون بهینه نبودن جواب رنج می برد. روش جستجوی *A ، سرعت روش حریصانه در رسیدن به جواب و بیهنگی روش هزینه یکنواخت در پیدا کردن جواب را باهم ترکیب کرده و به جستجوی هدف خود می پردازد.

جستجوی *A سعی می کند مجموع هزینه پرداخت شده تا گره فعلی و هزینه باقی مانده از گره فعلی تا هدف را مینیمم کند. تخمین هزینه باقی مانده تا هدف را هیوریستیک مسئله می گویند. طراحی هیوریستیک مسئله در روش جستجوی *A از اهمیت بسزایی برخوردار است و بهینیگی روش *A تحت تاثیر طراحی هیوریستیک مسئله قرار دارد.

هیوریستیک در روش *A هرینه قابل پرداخت از نقطه فعلی تا نقطه هدف را تخمین می زند. با این توصیف هیوریستیک قابل قبول را چنین تعریف می کنیم : هیوریستیکی قابل قبول ( admissible ) است که هزینه تخمینی آن از نقطه فعلی تا نقطه هدف ، از هزینه واقعی قابل پرداخت از نقطه فعلی تا نقطه هدف کمتر باشد. هیوریستیکی که این شرط را برآورده نکند ، هیوریستیک غیرقابل قبول ( inadmissible ) می نامند.

با توجه به مطالب فوق چنین بیان می کنیم که هزینه هر گره در روش جستجوی *A با استفاده از فرمول زیر محاسبه می شود : F = G + H که در آن F هزینه کل گره ، G هزینه تا گره فعلی و H هزینه تخمینی تا گره هدف را نشان می دهد. در جستجوی *A گره بعدی جهت گسترش گره ای است که کمترین هزینه F را در میان گره های گسترش نیافته دیگر داشته باشد. شبه کد زیر نحوه اجرای الگوریتم *A را نشان می دهد:
1. نقطه شروع را به صف fringe اضافه کن
2. مراحل زیر را تکرار کن
1. گره موجود در سر صف fringe را انتخاب کن.
2. آن را از صف fringe حذف کرده و فلگ آن را جهت بررسی نکردن دوباره آن ، ست کن
3. به ازای هر هشت همسایه مربع برداشته شده از صف ( نام مربع را parent فرض کنید ) انجام بده :
• در صورتی که فلگ مربع ست شده باشد آن را نادیده بگیر ، در غیر اینصورت به مرحله بعد برو
• اگر این مربع در صف fringe نباشد ، آن را به صف اضافه کن ، مربع parent را پدر مربع اضافه شده به صف قرار بده و هزینه های F ، G و H مربع را محاسبه کن
• اگر این مربع از قبل در صف باشد ، هزینه G آن را با استفاده از مربع parent محاسبه کن. در صورتی که این هزینه کمتر از هزینه G این مربع در حال حاضر باشد ، مربع parent را ، پدر مربع قرار بده.
4. صف fringe را به ترتیب صعودی هزینه ها مرتب کن
5. توقف کن در صورتی که
• مربع مقصد به صف fringe اضافه شود که در این صورت مسیر پیدا شده است یا
• صف fringe خالی باشد ( مسیری از مبدا به مقصد وجود ندارد )
3 . مسیر را ذخیره کن. با حرکت عقبگرد از نقطه پایانی و با استفاده از مربع های پدر هر مربع ، تا رسیدن به مربع شروع ، مربع ها را پیمایش کن.

جستجوی حریصانه

یکبار دیگر گراف روبرو را در نظر بگیرید. در سایر روش های جستجو که در این سایت آمده اند نیز گراف روبرو را می توانید مشاهده کنید. در صورتی که از روش جستجوی هزینه یکنواخت برای حل این مساله استفاده کنیم، می توانیم هزینه پیموده شده تا گره فعلی را در نظر بگیریم و هنگام گسترش ، گره با کمترین هزینه را انتخاب نماییم. با روش جستجوی حریصانه از ایده دیگری می توان استفاده کرد. می توانیم به جای اینکه هزینه پیموده شده تا گره فعلی را به عنوان سنجه ای برای میزان بهینگی گره در نظر بگیریم ، فاصله گره فعلی تا مقصد را به عنوان تخمینی برای

سنجش میزان بهینگی هر گره انتخاب کنیم. به عبارت دیگر هنگام گسترش ، گره ای از درخت را گسترش دهیم که کمترین فاصله را تا مقصد دارد. منظور از فاصله نیز فاصله خط مستقیم بین گره فعلی و مقصد است که با استفاده از فاصله اقلیدسی می توان آن را محاسبه کرد. روش دیگر برای محاسبه فاصله از گره فعلی تا مقصد می تواند محاسبه فاصله بلوک شهری بین این دو گره باشد. لازم به ذکر است که در اینجا فرض می کنیم از هر خانه تنها یکبار می توانیم عبور کنیم.


همانطور که در ابتدای مساله فرض کردیم ، از هر خانه تنها یکبار می توان عبور کرد. این بدان معنی است که هر گره تنها یکبار می تواند در درخت می تواند گسترش یابد. علت گسترش نیافتن گره 8 در سطح 1 از درخت نیز به همین دلیل است. چرا که همه فرزندان این گره قبلا در درخت ( سطح 1 ) گسترش یافته اند.

درخت تشکیل شده از جستجوی حریصانه را با درخت تشکیل شده از جستجوی هزینه یکنواخت مقایسه کنید. می بینیم که جستجوی حزیصانه با گسترش گره های کمتر ، سریعتر به جواب مساله دست پیدا می کند. با این حال هنگام استفاده از جستجوی حریصانه باید دقت کنیم چرا که جستجوی حریصانه با دو مشکل بزرگ همراه است. مشکل اول اینکه نمی توان با استفاده از جستجوی حریصانه مطمئن بود که همیشه به جواب بهینه دست پیدا خواهیم کرد. همچنین جستجوی حریصانه ممکن است در یک حلقه بینهایت به دام افتد. به عنوان مثال در مسئله مسیریابی فرض کنید از هر خانه می توان چندین بار عبور کرد و با این فرض درخت جسنجو را تشکیل دهید. مشاهده خواهید کرد که گره شماره 8 در یک حلقه بینهایت گسترش یافته و در واقع هیچگاه به جواب مسئله دست پیدا نخواهیم کرد. حال می توان علت نامگذاری این روش به جستجوی حریصانه را حدس زد.

دیدیم که جستجوی هزینه یکنواخت در صورتی که هزینه گام ها به درستی انتخاب شود، موجب یافتن جواب بهینه مسئله خواهد شد. در مقابل این روش با مشکل کند بودن عمل جستجو همراه است. در مقابل جستجوی حریصانه در یافتن جواب مسئله بسیار سریع بوده اما با مشکل حلقه بینهایت و عدم بهینگی جواب مواجه است ( لازم به ذکر است که بهینگی جستجوی حریصانه در برخی مسائل همانند الگوریتم های پریم و کروسکال اثبات شده است. اما در حالت کلی نمی توان ادعا کرد همیشه جستجوی حریصانه منجر به یافتن جواب بهینه خواهد شد). حال این سوال مطرح می شود که چگونه می توان این دو روش را باهم ترکیب کرده و روش جستجویی را طراحی کنیم که هم سریع بوده و هم جواب بهینه مسئله را بتواند پیدا کند؟ جواب مسئله در روش جستجو A* که در ادامه بررسی خواهیم کرد، می بینیم.

جستجوی هزینه یکنواخت

جستجوی هزینه یکنواخت
جستجوی هزینه یکنواخت را از آن جهت که در هر لحظه کم هزینه ترین گره را گسترش می دهد ، نه می توان در رده روش های جستجوی عمقی دانست ، نه می توان آن را یک روش جستجوی سطحی تلقی کرد. در این روش جستجو هر گره هزینه حرکت از ریشه تا گره فعلی را در خود نگه می دارد. هنگامی که می خواهیم فرزندان گره گسترش نیافته ای را تولید کنیم، گره ای از درخت برای گسترش انتخاب می شود که کم هزینه ترین گره در میان گره های گسترش نیافته باشد. به عنوان مثال شکل روبرو را در نظر بگیرید :


مسئله یافتن مسیری از مستطیل آبی رنگ به مستطیل قرمز رنگ می باشد. همچنین مستطیل های بنفش نشان دهنده دیوار هستند که نمی توان بر روی آن ها حرکت کرد. در این مسئله به ازای هر خانه، 8 خانه همسایه وجود دارد که در شکل روبرو نشان داده شده اند ( اعداد ترتیب گسترش گره ها را نشان می دهند ) . این بدان معناست که هنگام تولید فرزندان یک گره ، 8 خانه همسایه برای گسترش وجود خواهد داشت. از طرف دیگر حرکات قطری مجاز بوده و از یک خانه می توان چندبار عبور کرد. قبل از بررسی روش جستجوی هزینه یکنواخت با روش های جستجوی عمقی ، سطحی و عمقی محدود شده به حل این مساله می پردازیم. برای روش جستجوی عمقی بسته به اینکه ترتیب گسترش گره ها به چه نحوی باشد و همچنین مبدا و مقصد در کدام قسمت نقشه قرار گیرند، امکان قرار گرفتن در حلقه بینهایت وجود خواهد داشت. بنابراین از این روش استفاده نمی کنیم. در صورتی که از جستجوی سطحی برای حل مساله استفاده کنیم ، مسیر پیدا شده بدین صورت خواهد بود : مسیری که با روش جستجوس سطحی از مبدا به مقصد به دست می آید در حالت کلی غیر بهینه بوده و گره های اضافی بسیاری را نیز برای یافتن مسیر گسترش می دهد. که این امر در مورد مسائل پیچیده تر خوشایند نخواهد بود. حال فرض کنید از روش جستجوی عمقی محدود شده به عمق 20 برای یافتن مسیر استفاده کنیم. شکل زیر نحوه گسترش گره ها را نشان می دهد : بنابراین مسیر پیدا شده از مبدا به مقصد به صورت روبرو خواهد بود . در مورد جستجوی عمقی محدود شده نیز با دو مشکل مواجه هستیم ، مشکل اول تعیین عمق محدود شده و مشکل دوم عدم بهینگی مسیر پیدا شده از مبدا به مقصد می باشد. در هیچیک از روش های جستجو فوق هزینه از ریشه تا گره فعلی در نظر گرفته نشده است. حال فرض کنید هزینه انتقال از یک خانه به خانه دیگر در جهت افقی و عمودی 1 و در جهت قطری 1.5 باشد. حال با این تعریف می توانیم از روش جستجوی هزینه یکنواخت برای یافتن مسیر استفاده کنیم. همانطور که در ابتدای بخش بیان کردیم ، در روش جستجوی هزینه یکنواخت در هر لحظه گره ای از درخت گسترش می یابد که کمترین هزینه را در میان دیگر گره ها داشته باشد. قبل از نمایش نحوه تشکیل درخت جستجو به هر خانه شماره ای را انتساب می دهیم.

درختی که از جستجو به روش هزینه یکنواخت در هر مرحله به دست می آید به شکل زیر خواهد بود :

نکته قابل توجه در مورد جستجوی هزینه یکنواخت این است که این روش جستجو در صورتی جواب بهینه را پیدا می کند که هزینه های هر گام به درستی انتخاب شوند. مشکلی که همچنان در این روش باقی مانده ، گسترش گره های اضافی است که این امر موجب می شود پیدا کردن جواب برای مسئله زیاد سریع نباشد. به جای جستجوی هزینه یکنواخت می توان از جستجوی حریصانه نیز برای حل این مساله استفاده کرد که در بخش بعد به بررسی آن خواهیم پرداخت.

جستجوی عمقی تکرار شونده

جستجوی عمقی تکرار شونده

در روش جستجوی عمقی تکرار شونده ، از عمق A شروع کرده و تا رسیدن به جواب یا حداکثر عمق B درخت را گسترش می دهیم. بدین معنی که ابتدا درخت را بطور کامل تا عمق A گسترش می دهیم. در صورتی که همه درخت تا عمق A به روش عمقی تولید شد و جوابی برای مسئله پیدا نکردیم ، یکبار دیگر درخت را تا سطح A+1 به طور کامل و به روش عمقی گسترش می دهیم. در صورتی که ایمبار نیز جواب پیدا نشد ، دوباره درخت را تا یک سطح پایین تر از سطح فعلی گسترش می دهیم. و این عمل تا رسیدن به جواب یا حداکثر عمق B تکرار می شود.

در ابتدا به نظر می رسد که این روش نسبت به سایر روش ها از سرعت اجرای کمتری برخوردار است. اما بطور قطع نمی توان زمانبر بودن این الگوریتم را اثبات کرد. چرا که ممکن است به سبب ماهیت مسئله این روش بسیار سریعتر از دیگر روش ها عمل کند. به عنوان مثال فرض کنید درخت مربوط به فضای جستجو به صورت زیر باشد :
اعمال روش جستجوی عمقی تکرار شونده در این درخت سریعتر از جستجوی عمقی بوده اما سرعت اجرای آن نسبت به روش جستجوی سطحی در این درخت کمتر خواهد بود. با این حال میزان حافظه استفاده شده آن نسبت به روش جستجوی سطحی بهینه تر خواهد بود. روش جستجوی عمقی محدود شده نیز در صورتی از سرعت بیشتری برخوردار خواهد بود که حداکثر عمق درخت به درستی انتخاب شود. در کل می توان چنین نتیجه گرفت : سرعت اجرای هریک از روش های جستجو بستگی به شرایط مسئله و شکل درخت فضای جستجو دارد.

در هیچ یک از روش های جستجوی عمقی ، سطحی ، عمقی محدود شده و عمقی تکرار شونده هزینه ای که تا به حال از ریشه تا گره فعلی صرف شده است ، در نظر گرفته نمی شود. همین امر موجب می گردد تا در مسائل بهینه سازی نتوان از این روش ها برای جستجوی فضای جستجو استفاده کرد. چرا که هیچ استراتژی برای گسترش گره های بعدی وجود ندارد. از دیگر روش های جستجوی ناآگاهانه که بر روی درخت های وزن دار می توانیم از آن استفاده کنیم، روش جستجوی هزینه یکنواخت می باشد.

جستجوی سطحی

جستجوی سطحی

همانطور که در روش جستجوی عمقی محدودشده بررسی کردیم، جستجوی سطحی مشکل حلقه بینهایت و یال های تکراری مربوط به مسئله روبرو را حل خواهد کرد ( یافتن مسیری از گره 1 به گره 5 ). البته این بدان معنا نیست که مشکل حالت های تکراری در جستجوی سطحی به طور کامل رفع شده است. بلکه هیچیک از روش های جستجو در مقابل حالت های تکراری مصون نیستند. این وظیفه طراح الگوریتم است که با اتخاذ روشی از بروز حالت های تکراری جلوگیری کند. یکبار دیگر گراف روبرو را در نظر بگیرید.


می خواهیم مسیری از گره 1 به گره 5 پیدا کنیم. در صورتی که از جستجوی سطحی برای پیمایش فضای جستجو بخواهیم استفاده کنیم، بدین روش عمل می کنیم : در هر سطح از درخت جستجو ، به ازای هر گره در آن سطح همه فرزندان گره جاری تولید شده و در سطح بعدی درخت قرار می گیرند. با این تعریف حال می توانیم نحوه پیمایش درخت جستجوی مساله مذکور را نشان دهیم :

در ابتدا همه فرزندان گره 1 تولید شده و به سطح بعدی درخت اضافه می گردند. در سطح بعدی درخت نیز به ازای هر گره فرزندان آن گره تولید و به درخت جستجو اضافه می شوند. همانطور که از شکل پیداست، در سطح 3 از درخت مسیری از گره 1 به گره 5 پیدا می شود. همچنین مشکل یال های تکراری روش های قبلی نیز در این درخت وجود ندارد. یکی از بزرگترین مشکلات روش جستجوی سطحی مرتبه مکانی یا میران حافظه مصرفی این روش جستجو است. در روش های جستجو عمقی و عمقی محدود شده در هر لحظه تنها گره های مربوط به شاخه فعلی در حافظه وجود دارد. این در حالی است که روش جستجوی سطحی همه گره های بالاتر از سطح فعلی از فضای جستجو را در حافظه نگه خواهد داشت. می توان روش جستجوی عمقی و سطحی را باهم ترکیب کنیم تا با ترکیب این دو ، معایب موجود در هریک از روش ها را رفع کرده و مزایای آن ها را باهم ترکیب کنیم. این روش جستجو را که در بخش بعد به بررسی آن خواهیم پرداخت، جستجوی عمقی تکرار شونده می نامیم.

جستجوی عمقی محدود شده

مهمترین مشکل روش جستجوی عمقی را که در برخی از مسائل با آن مواجه خواهیم بود، قرار گرفتن این روش جستجو در حلقه بینهایت می باشد. به عنوان مثال گراف شکل روبرو را در نظر بگیرید . فرض کنید می خواهیم مسیری از گره 1 به گره 5 با استفاده از روش جستجوی عمقی پیدا کنیم. شکل زیر مراحل مختلف تشکیل درخت جستجو را نشان می دهد :



همانطور که از شکل پیداست ، استفاده از روش جستجوی عمقی برای حل این مساله هیچگاه به یافتن جواب منجر نخواهد شد. چرا که حلقه بینهایتی از گسترش گره های 1 و 2 تشکیل می شود. مشکل قرار گرفتن در حلقه بینهایت از گسترش حالت های تکراری در هنگام جستجو حاصل شده است. بنابراین یکی از روش های حل این مشکل تشخیص حالت های تکراری هنگام گسترش فرزندان یک گره می باشد.

تشخیص حالت های تکراری یکی از مهمترین نکات طراحی الگوریتم های هوش مصنوعی می باشد که وابستگی بسیاری به نحوه نمایش راه حل مساله دارد. نحوه نمایش مساله و تشخیص حالت های تکراری را در انتهای فصل و در مثال های مختلف مورد بررسی قرار خواهیم داد. در حال حاضر با روش دیگری به رفع این مشکل خواهیم پرداخت.

می دانیم در صورتی که مسیری از گره 1 به گره 5 در گراف وجود داشته باشد، طول این مسیر نمی تواند بیش از 5 یال باشد. بنابراین می توان با اتخاذ یک محدودیت به روش جستجوی عمقی از گسترش گره هایی که در عمق 5 از درخت جستجو قرار دارند، جلوگیری کرد. به عبارت دیگر برای گره هایی که در عمق 5 از درخت جستجو قرار دارند ، هیچ فرزندی تولید نکنیم. پیمایش در فضای جستجوی مساله با این روش را روش جستجوی عمقی محدود شده می نامیم. یکبار دیگر با استفاده از روش جستجوی عمقی محدود شده به عمق 5 به حل مساله فوق می پردازیم. شکل زیر مراحل مختلف تشکیل درخت جستجو را نشان می دهد ( ادامه درخت جستجوی شکل بالا) :
با توجه به گراف شکل بالا ، مسیر 5-4-3-1-2-1 ما را از گره 1 به گره شماره 5 هدایت می کند. با وجود اینکه محدود کردن عمق درخت مشکل حلقه بینهایت را رفع کرد، اما هنوز مشکل حالت تکراری در روش جستجوی عمقی محدود شده وجود دارد. برای حل همزمان مشکل حلقه بینهایت و حالت تکراری، می توان از روش جستجوی سطحی استفاده کرد

جستجوی عمقی

از اسم این روش جستجو پیداست که پیمایش گراف فضای جستجو با حرکت در عمق انجام می پذیرد. به عنوان مثال فرض کنید با سه کلمه "جستجو" ، "گراف" و "عمقی" می خواهیم یک جمله معنی دار بسازیم. شکل زیر مراحل مختلف تشکیل گراف هنگام جستجوی عمقی گراف را نشان می دهد :
الگوریتم جستجو چنین است : ابتدا فرزندان ریشه درخت تولید شده و در سطح بعدی درخت قرار می گیرند. در ابتدای کار هریک از کلمات می تواند برای شروع جمله بکار روند. سپس اولین گره دارای کلمه "عمقی" در سطح 1 از درخت انتخاب شده و همه فزرندان قابل تولید آن در سطح 2 درخت تشکیل می شوند(شکل 2 ). سپس در سطح 2 از درخت گره شامل کلمه "جستجو" انتخاب شده و همه فرزندان آن در سطح 3 درخت تشکیل می شوند(شکل 3 ). در نهایت نیز کلمه "گراف" انتخاب شده ور همه فزرندان آن تولید می شوند. با توجه به اینکه دیگر هیچ فزرندی برای این گره وجود ندارد، بنابراین جمله "عمقی جستجوی گراف" که از پیمایش درخت از ریشه تا گره فعلی به دست می آید بررسی می شود تا صیحیح بودن این جمله را تعیین کند. همانطور که می دانیم این جمله از نظر قواعدی جمله صحیحی نمی باشد. بنابراین گره فعلی از حافظه حذف شده ( شکل 4 ) و گره "جستجو" در سطح 2 بررسی می شود تا اگر فزرند دیگری برای این گره وجود داشته باشد، ادامه جستجو از آن فرزند ادامه یابد. اما فرزند دیگری برای این گره وجود ندارد. از اینرو این گره نیز از حافظه حذف می شود ( شکل 5 )

حال فرزندان گره "گراف" در سطح 2 تولید می شوند (شکل 6 ). همانطور که می بینیم فرزند دیگری برای گره "جسجتو" در سطح 3 وجود ندارد. بنابراین این گره نیز به همراه گره پدر از حافظه حذف خواهد شد ( شکل 7 و 8 ). سپس به سطح 1 بازگشته و فرزندان گره "جستجو" را گسترش می دهیم( شکل 9 ). سپس فرزندادن گره "عمقی" در سطح 2 گسترش یافته صحت جمله ساخته شده از آن کلمات بررسی می شوند. در این مرحله جمله از نظر قواعدی درست تشخیص داده شده و عبارت "جستجوی عمقی درخت" به عنوان جواب مسئله پیدا می شود ( شکل 10 ).

در مسئله فوق از دو تابع گسترش و تست هدف برای گسترش دادن فرزندان گره و تعیین صحت جواب مسئله استفاده کردیم. این توابع در مسائل مختلف به روش های گوناگونی پیاده سازی می شوند و الگوریتم کلی برای آن ها وجود ندارد.

انواع روش های جستجو

در حالت کلی روش های جستجو را می توان به سه دسته زیر تقسیم کرد
• ناآگاهانه
• هیوریستیکی
• متاهیوریستیکی

مسائلی وجود دارند که فضای جستجوی آنها به اندازه ای بزرگ می باشد که استفاده از روش های جستجوی ناآگاهانه و هیوریستیکی را برایمان غیرممکن می سازند. در چنین مواردی از روش های متاهیوریستیکی یا فرامکاشفه ای استفاده خواهیم کرد.

در ادامه این بخش ابتدا به بررسی انواع مسائل هوش مصنوعی خواهیم پرداخت، سپس روش های جستجوی ناآگاهانه را بررسی کرده و به دنبال آن با روش های جستجوی هیوریستیکی آشنا خواهیم شد.

مسائل مطرح شده در هوش مصنوعی را از چند دیدگاه مختلف می توان مورد بررسی قرار دارد :
• هدف یافتن تنها یک جواب برای مسئله است یا همه جواب های ممکن برای مسئله باید جستجو شوند؟
• پاسخ دهی الگوریتم جستجو برای حل مسئله بلادرنگ خواهد بود یا زمان بیشتری برای حل مساله می توان اختیار کرد
• آیا در مسئله محدودیت هایی وجود دارد یا نه ؟

همه اینها سوالاتی هستند که هنگام طراحی الگوریتمی برای پویش در فضای جستجو باید به آنها توجه کنیم. به عنوان مثال در صورتی که همه جواب های مسئله مدنظر ما باشد، در اینصورت حتی در صورت آگاهانه بودن ماهیت مسئله نیز نمی توان از روش های هیوریستیکی استفاده کرد. به عنوان مثال در صورتی که هدف یافتن همه مسیرهای ممکن از تبریز به شیراز باشد، استفاده از هیوریستیک تنها موجب پیچیده شدن الگوریتم و حتی موجب ناقص بودن جواب های مسئله خواهد شد.

سیستم های پویا سیستم هایی هستند که در آنها به طور مداوم ورودی ها و حالت مسئله در حال تغییر است و هربار تغییر در یکی از پارامترها موجب خواهد شد که عمل جستجوی مجددی در فضای جستجو انجام پذیرد. در چنین مواردی ممکن است مدت زمان پاسخ دهی سیستم برای حل مساله بسیار کم باشد. همچنین ممکن است سیستم مدت زمان کافی برای حل مساله در اختیار داشته باشد که هریک از این موارد تاثیر بسزایی در طراحی الگوریتم جستجو خواهند داشت.

فرض کنید می خواهیم در یک صفحه شطرنج استاندارد، 8 وزیر را به گونه بر روی صفحه شطرن قرار دهیم که هیچیک از آنها وزیر دیگری را گارد ندهند. در این مسئله که به مسئله 8 وزیر معروف است، محدودیتی وجود دارد که بر اساس آن هیچ وزیری باید همدیگر را گارد ندهند. به صورت تجربی می توان چنین گفت که بیشتر مسائلی که با آنها سروکار داریم دارای محدویت هایی در مسئله هستند. به چنین مسائلی مسائل ارضای محدودیت نیز می گوییم. وجود محدودیت در مسئله قدری موجب پیچیدگی مسئله می شود اما در اکثر موارد نیز موجب خواهد شد فضای جستجو مسئله بسیار کوچکتر از حالتی باشد که در آن مسئله هیچ محدودیتی در خود ندارد.

مسائلی که در عمل با آنها مواجه هستیم ترکیبی از موارد فوق را در خود دارند. به عنوان مثال در مسئله ی 8 وزیر ، مسئله دارای محدودیت بوده ولی در مقابل هدف یافتن تنها یک جواب در مدت زمان معقول است و در واقع یافتن جواب در آن نیازی به بلادرنگ بودن ندارد.

تضاد رباتیک با مکاترونیک

مکاترونیک یک رشته ی چند تخصصی ، شامل رشته های مهندسی مکانیک ، مهندسی الکترونیک و مهندسی کامپیوتر است . مکاترونیک از دو کلمه ی "مکا" مخفف مکانیک و "ترونیک" مخفف الکترونیک مشتق شده است . رباتیک نیز همانند مکاترونیک از سه رشته ی هندسی مکانیک ، مهندسی الکترونیک و مهندسی کامپیوتر بوجود آمده است . تفاوت اصلی در آن است که سیستم های مکاترونیکی ورودی هایشان فراهم شده است (تمام ورودی ها از قبل تعریف شده و شناخته شده است) ؛ در حالی که سیستم های رباتیکی باید خودشان ورودی ها را از محیط دریافت نمایند. به عنوان مثال چراغ راهنمایی و رانندگی و ماشین لباسشویی ، سیستم های مکاترونیکی هستند . در چراغ راهنمایی و رانندگی وقتی انسان دکمه ای را فشار می دهد رنگ چراغ تغییر می کند و در ماشین لباسشویی دمای آب ، زمان و ... به آن داده شده است. حتی وقتی چراغ راهنمایی و رانندگی در حالت خودکار قرار می گیرد و بدون نیاز به فشردن دکمه ای ، کار می نماید . هنوز به عنوان سیستم مکاترونیکی شناخته می شود چون ورودی هایش (زمان روشن بودن هر رنگ) برایش فراهم گردیده است . این فرایند ، خوکار (اتوماتیک) نامیده می شود . آن چه گفته شد در تضاد است با حالتی که چراغ راهنمایی و رانندگی دارای یک دوربین جهت تشخیص مردمی که می خواهند از عرض خیابان شوند باشد و رنگ چراغ را با توجه به فشردگی جمعیت تغییر دهد. آن چه گفته شد یک سیستم رباتیک است . این فرایند را خودمختاری (اتونوموس) گویند .


نتیجه


* سیستم های مکاترونیکی ورودی هایشان فراهم شده است در حالی که سیستم های رباتیکی باید خودشان ورودی ها را از محیط دریافت نمایند.
* سیستم های مکاترونیکی خودکار هستند در حالی که سیستم های رباتیکی خودمختار هستند.
* سیستم های رباتیکی نیازی به دید انسان ها (فکر و محاسبات بشر) ندارند ، در حالی سیستم های مکاترونیکی نیازمند فکر انسان ها از قبل یا همزمان می باشند.


-------------------------
پی نوشت مترجم : امروزه دو علم مکاترونیک و رباتیک در ایران یک علم جدید شناخته می شود ، مهندسی مکاترونیک در مقطع کارشناسی و کارشناسی ارشد تدریس می شود ، اما متاسفانه مهندسی رباتیک فقط در مقطع کارشناسی تدریس می شود و خبری از تدریس مهندسی رباتیک در مقطع کارشناسی ارشد حتی در آینده نیز به گوش نمی رسد . این در حالی است که در کشور های پیشرفته صنعتی دنیا مانند ایالات متحده آمریکا رشته ی مهندسی رباتیک به طور مجزا از مکاترونیک و رشته های دیگر از مقطع کارشناسی تا مقطع پست دکتری تدریس می شود . متاسفانه بعضی ها در ایران این دو رشته را یکی می دانند یا دیده شده است که مهندسی رباتیک را یکی از گرایش های مکاترونیک نام می برند . این درست است که یکی از گرایش های مکاترونیک در مقطع کارشناسی ارشد رباتیک است اما رشته های مکانیک طراحی کاربردی ، مکانیک ساخت و تولید ، کنترل ، هوش مصنوعی نیز دارای گرایش رباتیک در مقطع کارشناسی ارشد می باشند . این در حالی است که رشته ی رباتیک با رشته های مکاترونیک ، مکانیک طراحی کاربردی ، مکانیک ساخت و تولید ، کنترل و هوش مصنوعی متفاوت است. چون رباتیک یکی از گرایش های رشته ی مذکور است دلیل نمی شود که رباتیک را زیر مجموعه ی آن رشته بنامیم. امیدواریم با خواندن این مقاله تفاوت مکاترونیک با رباتیک بر خوانندگان روشن شده باشد و این مقاله جرقه ای باشد برای گسترش مهندسی رباتیک در مقاطع بالاتر در دانشگاه های کشور .

به همت یک مخترع معلول ربات مخزن پیما طراحی شد

خبرگزاری فارس: ربات مخزن پیما برای استفاده در مخازن عظیم نفتی به همت یک مخترع معلول ایرانی طراحی شد.

حسین خوران، مخترع معلول ایرانی در گفت.وگو با خبرنگار اجتماعی فارس گفت: با توجه به اینکه مخازن نفتی بسیار عظیم هستند و نقطه به نقطه آن.ها باید اندازه.گیری و تست شود و اینکه این کارها را یک نفر انجام می.دهد بسیار مشکل خواهد بود که این ربات این مشکلات را حل می.کند.
وی افزود: تعیین ضخامت و قطر لوله و مخزن.ها، میزان خوردگی روی آن.ها و جوشکاری این مخازن به کمک این ربات مخزن پیما امکان.پذیر است.
خوران تصریح کرد: این ربات به صورت عمومی و به حالت نیم.دایره.ای و به صورت مگنتیک روی مخزن.ها متصل می.شود و روی سطح عمومی این مخازن حرکت می.کند تا نمونه.گیری را انجام دهد.
وی گفت: این ربات بدون نیاز به هیچ.گونه سیمی به مخازن متصل می.شود و اطلاعات را اندازه.گیری و منتقل می.کند و از طریق کاربر و اپراتوری که در مکان دورتر از مخزن هستند این اطلاعات دریافت و ثبت می.شود.

ربات ها نیز میتوانند برقصند

ربات ها نیز میتوانند برقصند

اگر پیشرفت علم و تکنو لوژی چنین باشد دیگر نمی توان در آینده ای نه چندان دور محدودیتی در انجام امور برای انسان و ربات ها قائل شد. امروزه ربات ها در امور فنی – مهندسی , خانه داری , پرستاری و خدمات پزشکی و ... به انسان یاری می رسانند. و اکنون ژاپنی ها موفق به ساخت رباتی شدند که میتواند همراه با انسان رقصیدن و یا حتی ورزش کردن را آموخته و در این حیطه نیز وارد عرصه رقابت با انسان شوند. این ربات توانایی حرکت دادن مفاصل زانو و آرنج را به گونه ای دارد که هرگز در ضمن اجرای فعالیت تعادل خود را از دست نخواهد داد. زوایای چرخش با بهترین شیوه های مهندسی برنامه ریزی شده است.هنوز از قیمت تمام شده این محصول خبری در دسترس نیست. آنچه که بیشتر باعث نگرانیست, وحشت از روزیست که قرار باشد ربات ها به جای انسان نفس بکشند.

کاوش در اعماق دریاها با «سفره ماهی رباتیک» محقق ایرانی

کاوش در اعماق دریاها با «سفره ماهی رباتیک» محقق ایرانی


فرشاد خرمی، استاد دانشگاه پلی تکنیک در بروکلین نیویورک موفق به ابداع «سفره ماهی رباتیک» با قابلیت جاسوسی در اعماق آب شد. «سفره ماهی رباتیک» یک ربات جدید زیر دریایی است که به گشت.های دریایی امکان می.دهد مین.ها را شناسایی کرده یا از آب.های آلوده به منظور انجام مطالعات آزمایشگاهی نمونه.گیری کنند. این ربات که جدیدترین دستاورد خرمی، رییس آزمایشگاه تحقیقات کنترل - رباتیک دانشگاه پلی تکنیک نیویورک در زمینه ساخت ربات.ها محسوب می شود، با دمی شبیه به دم گونه.ای سفره ماهی برقی به راحتی در زیر آب شنا می.کند و مهندس خرمی می.تواند در این وضعیت آن را روی صفحه نمایش لپ تاپ ببیند. به گفته خرمی، دم این ربات به آن امکان می.دهد که نیروی رانشی در زیر آب ایجاد کرده و طوری در میان حرکات موجی خود سر بخورد که شبیه سفره ماهی به نظر می.رسد. تاکنون نمونه اولیه این ربات تهیه شده و تحقیقات طرح ادامه دارد. قرار است خرمی و تیم تحقیقاتی وی طی دو سال آینده نسخه دومی از بدن ربات را جایگزین نمونه فعلی کنند. بدن دوکی شکل ربات شبیه به یک فیریزبی است و باله.هایی شبیه به بال پرنده در پهلوی آن قرار دارد. البته نمونه اولیه این ربات هنوز تا حدودی با مشکل مکانیکی مواجه است که خرمی در نظر دارد این مشکل را با یک برنامه هدایت خودکار در یک سیستم رانشی منحصر به فرد برطرف کند. این برنامه با استفاده از الگوریتم هایی کنترل می.شود که فرایند تصمیم.گیری در مغز را شبیه.سازی می.کنند. هم اکنون کار مهندس خرمی تکمیل محاسبات الگوریتمی در این برنامه و رسیدن به روابط محاسبه.یی درست و قابل قبول است. ابداعات این محقق ایرانی، کاربردهای نظامی و شهری مختلفی دارد. وی در مدت بیش از دو دهه روی پروژه.هایی شبیه مونتاژ کننده.های الکترونیک پرسرعت، کنترل.های ماهواره.یی و هواپیماهای رباتیک، هلی.کوپتر و قایق.های رباتیک کارکرده است. خرمی که در دانشگاه اوهایوی آمریکا، توامان در دو رشته ریاضیات و مهندسی الکترونیک تحصیل کرده و از نوجوانی و زمانی که در ایران زندگی می.کرده علاقه زیادی به ابتکارات الکترونیکی داشته می.گوید به این رشته.ها دلبستگی ویژه.ای دارد و آن را ترکیب مناسبی بین علوم و حاصل آن همیاری.های بسیاری است. در آزمایشگاه رباتیک، خرمی و تیم وی حسگرها و تجهیزات روی بدنه این سفره ماهی رباتیک شامل دوربین.ها، یک قطب نما و یک موتور مغناطیسی سه بعدی برای کمک به ردیابی را نصب می.کنند. این تجهیزات می.تواند موقعیت ربات و راستای حرکت آن را در زیر آب و در نقاطی که سیستم ماهواره.ای GPS. وجود دارد، مشخص کنند. خرمی پرتوهای الکترویکی را تحسین می.کند اما آنها را کند می.داند. وی می.گوید: این ویژگی توانایی را به نمونه.های رباتیک به عنوان جاسوس.های زیر آبی می.دهد. این ربات.ها می.توانند با دراز کشیدن در شن.های کف دریا، عملکرد پرتوهای واقعی حاصل از دریازیان برقی را تقلید کنند و با حسگرهای خود کف دریا را بکاوند. به گزارش ایسنا، خرمی می.گوید: حرکات بسیار آرام و خفیف در دم می.تواند بسیار محتاطانه باشد و یکی از زیبایی.های این ربات.ها است. وی تصریح کرد: با خلق دوباره این توانایی و دستکاری آن توسط برخی مهندسان، می.توان قابلیت.های مکانیکی آنرا نسبت به سایر جانوران دریایی که اشعه تولید می.کنند، افزایش داد. همچنین روبات مزبور از آلیاژ خاصی به نام «نیتینول» ساخته می شود که تلفیقی از نیکل و تیتانیوم است. این آلیاژ دارای خاصیت «حافظه شکلی» است که پس از خمیده شدن وضعیت قبلی ربات را به آن یادآوری می.کند تا دوباره به حالت اولیه بازگردد. خرمی در نظر دارد تمام این سیستم.ها را روی سفره ماهی رباتیک خود اعمال کند.