جزوه هوش مصنوعی-قربعلی پور.pdf

‫واحد صومعه سرا‬ ‫ع‬ ‫ن‬‫مص‬ ‫جزوه هوش و ی‬ ‫گردآورنده‪ :‬مهدی قربعلی پور‬ ‫اتبستان ‪79‬‬  ‫فهرست‬ ‫فصل اول ‪1............................................................................................

‫واحد صومعه سرا‬ ‫ع‬ ‫ن‬‫مص‬ ‫جزوه هوش و ی‬ ‫گردآورنده‪ :‬مهدی قربعلی پور‬ ‫اتبستان ‪79‬‬  ‫فهرست‬ ‫فصل اول ‪1.....................................................................................................................................................................................‬‬ ‫مقدمه ‪1..........................................................................................................................................................................................‬‬ ‫‪ -1‬هوش مصنوعی چیست؟‪2.........................................................................................................................................................‬‬ ‫‪ -2‬چهار رویکرد عمده به هوش مصنوعی ‪2...................................................................................................................................‬‬ ‫‪ -1-2‬عمل کردن انسان گونه‪2..................................................................................................................................................‬‬ ‫‪ -2-2‬فکر کردن انسان گونه ‪3...................................................................................................................................................‬‬ ‫‪ -3-2‬فکر کردن عقالنی‪3.........................................................................................................................................................‬‬ ‫‪ -4-2‬عمل کردن عقالنی‪4........................................................................................................................................................‬‬ ‫فصل دوم‪5.....................................................................................................................................................................................‬‬ ‫عامل های هوشمند ‪5......................................................................................................................................................................‬‬ ‫‪ -1‬عامل ها و محیط ها ‪6................................................................................................................................................................‬‬ ‫‪ -2‬رفتار درست‪ :‬مفهوم عقالنی بودن‪7...........................................................................................................................................‬‬ ‫‪ -1-2‬همه چیزدانی‪ ،‬یادگیری‪ ،‬خودمختاری‪8............................................................................................................................‬‬ ‫‪ -3‬محیط کار‪8.............................................................................................................................................................................‬‬ ‫‪ -4‬انواع محیط کاری ‪9..................................................................................................................................................................‬‬ ‫‪ -1-4‬کامال مشاهده پذیر در مقابل کمی مشاهده پذیر‪9.............................................................................................................‬‬ ‫‪ -2-4‬قطعی در مقابل غیر قطعی ‪11...........................................................................................................................................‬‬ ‫‪ -3-4‬تقسیم پذیر (اپیزودیک) در مقابل ترتیبی (پی در پی) ‪11.................................................................................................‬‬ ‫‪ -4-4‬ایستا در مقابل پویا‪11......................................................................................................................................................‬‬ ‫‪ -5-4‬گسسته در مقابل پیوسته‪11..............................................................................................................................................‬‬ ‫‪ -6-4‬تک عاملی در برابر چند عاملی‪11...................................................................................................................................‬‬ ‫‪ -7-4‬محیط چند عامله رقابتی‪11..............................................................................................................................................‬‬ ‫‪ -8-4‬محیط چند عامله همکاری‪12..........................................................................................................................................‬‬ ‫‪ -5‬انواع عامل ها ‪12......................................................................................................................................................................‬‬ ‫‪ -1-5‬عامل های واکنشی ساده‪13.............................................................................................................................................‬‬ ‫‪ -2-5‬عامل های مبتنی بر مدل‪14..............................................................................................................................................‬‬ ‫‪ -3-5‬عامل های هدفگرا‪15......................................................................................................................................................‬‬ ‫‪ -4-5‬عامل های مبتنی بر سودمندی ‪15.....................................................................................................................................‬‬ ‫‪ -6‬عاملهای یادگیرنده ‪16..............................................................................................................................................................‬‬ ‫‪ -1-6‬شکل های یادگیری‪17....................................................................................................................................................‬‬ ‫فصل سوم ‪19.................................................................................................................................................................................‬‬ ‫حل مساله با جستجو‪19..................................................................................................................................................................‬‬ ‫‪ -1‬عامل حل مساله ‪21...................................................................................................................................................................‬‬ ‫‪ -2‬تعریف مسئله‪21.......................................................................................................................................................................‬‬ ‫‪ -3‬انواع مساله ‪21..........................................................................................................................................................................‬‬ ‫‪ -1-3‬مساله تک حالتی ( ‪21.............................................................................................................................. )single-state‬‬ ‫‪ -2-3‬مساله با اطالعات ناقص(‪24.........................................................................................................................)sensorless‬‬ ‫‪ -3-3‬مساله احتمالی (‪26.................................................................................................................................. )contingency‬‬ ‫‪ -4-3‬مساله اکتشافی ‪26............................................................................................................................................................‬‬ ‫‪ -4‬الگوریتم های جستجوی درختی‪27..........................................................................................................................................‬‬ ‫‪ -1-4‬جستجوی اول سطح ‪29...................................................................................................................................................‬‬ ‫‪ -2-4‬جستجوی هزینه یکنواخت‪31..........................................................................................................................................‬‬ ‫‪ -3-4‬جستجوی اول عمق ‪32...................................................................................................................................................‬‬ ‫‪ -4-4‬جستجوی اول عمق با عمق محدود‪34.............................................................................................................................‬‬ ‫‪ -5-4‬جستجوی عمیق کننده تکراری‪34...................................................................................................................................‬‬ ‫‪ -6-4‬جستجوی دوسویه ‪36......................................................................................................................................................‬‬ ‫‪ -7-4‬مقایسه الگوریتم های جستجوی درختی ناآگاهانه‪37.......................................................................................................‬‬ ‫‪ -8-4‬جلوگیری از حالت های تکراری‪38................................................................................................................................‬‬ ‫‪2‬‬ ‫فصل چهارم‪41..............................................................................................................................................................................‬‬ ‫جستجوی آگاهانه‪41.....................................................................................................................................................................‬‬ ‫‪ -1‬راهبردهای جستجوی آگاهانه (اکتشافی)‪42.............................................................................................................................‬‬ ‫‪ -1-1‬جستجوی اول بهترین حریصانه‪42..................................................................................................................................‬‬ ‫‪ -2-1‬جستجوی *‪44............................................................................................................................................................ A‬‬ ‫‪ -3-1‬جستجوی اکتشافی با حافظه محدود ‪48...........................................................................................................................‬‬ ‫‪ 1-3-1‬جستجوی *‪ A‬عمیق کننده تکراری (*‪48.......................................................................................................)IDA‬‬ ‫‪ 2-3-1‬جستجوی اول بهترین بازگشتی (‪49.............................................................................................................)RBFS‬‬ ‫‪ 3-3-1‬جستجوی *‪ A‬با حافظه محدود شده ساده ( *‪52.......................... )Simplified Memory-Bounded A* -SMA‬‬ ‫‪ -2‬توابع اکتشافی (توابع هیوریستیک) ‪54......................................................................................................................................‬‬ ‫‪ -1-2‬تاثیر دقت هیوریستیک بر کارایی ‪54...............................................................................................................................‬‬ ‫‪ -2-2‬ابداع توابع هیوریستیک قابل قبول‪54...............................................................................................................................‬‬ ‫‪ -3‬الگوریتم های جستجوی محلی و مسائل بهینه سازی ‪55............................................................................................................‬‬ ‫‪ -1-3‬جستجوی تپه نوردی ‪55..................................................................................................................................................‬‬ ‫‪ -2-3‬جستجوی شبه تاب کاری (=سردسازی شبیه سازی شده)‪58............................................................................................‬‬ ‫‪ -3-3‬جستجوی پرتو محلی ‪59.................................................................................................................................................‬‬ ‫‪ -4-3‬الگوریتم های ژنتیک ‪61.................................................................................................................................................‬‬ ‫‪ -4‬عامل های جستجوی برخط و محیط های ناشناخته ‪62..............................................................................................................‬‬ ‫‪ -1-4‬مسائل جستجوی برخط ‪62..............................................................................................................................................‬‬ ‫‪ -2-4‬عامل های جستجوی برخط ‪62........................................................................................................................................‬‬ ‫‪ -3-4‬جستجوی محلی برخط‪63...............................................................................................................................................‬‬ ‫‪3‬‬  ‫فص‬ ‫ل اول‬ ‫مقدهم‬ ‫‪1‬‬  ‫‪ -1‬هوش مصنوعی چیست؟‬ ‫هوش مصنوعی نه تنها برای درک موجودات هوشمندی می کوشد‪ ،‬بلکه قصد دارد موجودات هوشمند نیز بسازد‪.‬‬ ‫‪ -2‬چهار رویکرد عمده هب هوش مصنوعی‬ ‫تعاریفی که ‪ 8‬کتاب مرجع از هوش مصنوعی ارائه داده اند را می توان به ‪ 4‬دسته تقسیم نمود‪:‬‬ ‫‪.1‬سامانه هایی که مانند انسان فکر می کنند‬ ‫‪.2‬سامانه هایی که مانند انسان عمل می کنند‬ ‫‪.3‬سامانه هایی که عقالنی فکر می کنند‬ ‫‪.4‬سامانه هایی که عقالنی عمل می کنند‬ ‫دو رویکرد اول موفقیتت را بر مبنتای وفا دار بودن به عملکرد انستتتان اندازه گیری می کنند ولی دو رویکرد آخری موفقیت را بر‬ ‫مبنای عقالنیت اندازه گیری می کنند‪.‬‬ ‫رویکردهتای انستتتان محور در زمره علوم تجربی (کته بتا نظریه و اثبات تجربی ستتتروکار دارند) قرار می گیرند ولی رویکردهای‬ ‫عقالنی با ترکیبی از ریاضی و مهندسی سروکار دارند‪.‬‬ ‫ع‬ ‫‪ -1-2‬مل کردن انسان گوهن‬ ‫آزمون تورینگ‪ :‬برنامه کامپیوتری توستط یک مصتاحبه گر انستانی مورد ستوال قرار می گیرد‪ ،‬اگر مصاحبه گر پس از طرح چند‬ ‫کتبی نتواند از طریق پاست ها تشتخیص دهد که مخاطب او انستان است یا یک سیستم هوش مصنوعی‪ ،‬آن وقت سیستم‬ ‫پرست‬ ‫هوش مصنوعی در آزمون هوشمندی موفق شده است‪.‬‬ ‫کامپیوتری که در آزمون تورینگ شرکت می کند باید توانایی های زیر را داشته باشد‪:‬‬ ‫‪2‬‬  ‫‪.1‬پردازش زبان طبیعی‪ :‬به منظور برقراری ارتباطی موثر به زبان انگلیسی‬ ‫‪.2‬بازنمایی دان ‪ :‬به منظور ذخیره سازی آنجه می داند یا می شنود‬ ‫‪.3‬استدالل خودکار‪ :‬به منظور استفاده از اطالعات ذخیره سازی شده در راستای پاس به پرسشها و نتیجه گیری های جدید‬ ‫‪.4‬یادگیری ماشین‪ :‬برای سازگاری با شرایط جدید و شناسایی و برون یابی‪ 1‬الگوها‬ ‫آزمون جامع تورینگ شتامل یک ستیگنال ویدئویی می شود که مصاحبه کننده توسط آن تواناییهای ادراکی آزمون دهنده را می‬ ‫آزماید‪.‬همچنین مصتاحبه کننده می تواند از طریق یک دریچه اشتیایی را به دست آزمون دهنده برساند‪.‬برای موفقیت در آزمون‬ ‫جامع تورینگ‪ ،‬سیستم هوش مصنوعی باید دو توانایی زیر را عالوه بر چهار توانایی باال داشته باشد‪:‬‬ ‫‪.5‬بینایی ماشین‪ :‬برای درک اشیا‬ ‫اشیا و حرکت در محیط‬ ‫‪.6‬رباتیک‪ :‬برای پای‬ ‫نکته‪ :‬در آزمون تورینگ و آزمون جامع تورینگ مصتتتاحبه کننده تعامل فیزیکی مستتتتقیم بین مصتتتاحبه کننده و ستتتیستتتتم هوش‬ ‫مصنوعی وجود ندارد‪.‬‬ ‫‪ -2-2‬فکر کردن انسان گوهن‬ ‫رویکرد مدلستازی شناختی‪ :‬هوش مصنوعی باید مانند انسان فکر کند‪.‬مدلسازی شناختی‪ ،‬مدلهای کامپیوتری هوش مصنوعی‬ ‫و فنون تجربی روان شناسی را با هم ترکیب می کند تا نظریه هایی دقیق و آزمون پذیر از طرز کار ذهن انسان به دست آورد‪.‬‬ ‫در انستتان گونه عمل کردن‪ ،‬خروجی هوش مصتتنوعی مورد توجه استتت اما در انستتان گونه فکرکردن اینکه هوش مصتتنوعی‬ ‫چگونه خروجی را تولید می کند (فکر می کند) مورد نظر است‪.‬‬ ‫خود را در مورد اینکه انسان ها چگونه فکر می کنند افزای‬ ‫برای تولید ماشین هایی که مانند انسان فکر می کنند‪ ،‬باید دان‬ ‫دهیم‪.‬برای این کار می توانیم از روش های زیر استفاده کنیم‪:‬‬ ‫‪.1‬درون نگاری‪ :‬ثبت و بررسی افکار درونی خود (تجربه های یک فرد از خودش)‬ ‫‪.2‬تجربیات و آزمایشهای روانشناسی (تجربه های یک روانشناس از افراد دیگر)‬ ‫‪ -3-2‬فکر کردن عقالنی‬ ‫درستتت‬ ‫رویکرد قوانین تفکر‪ :‬در این رویکرد به دنبال فرآیندهای استتتدالل همیشتته درستتت هستتتیم که به کمک آن بر پایه دان‬ ‫درست جدید دست یافت‪.‬برای مثال می توان از گزاره های »سقراط یک انسان است» و «هر انسانی مردنی‬ ‫اولیه می توان به دان‬ ‫است» نتیجه گرفت که «سقراط هم مردنی است»‪.‬‬ ‫‪1‬‬ ‫‪Extrapolation‬‬ ‫‪3‬‬  ‫دو مشکل در رویکرد قوانین تفکر وجود دارد‪:‬‬ ‫غیررسمی و تبدیل آن به شکل عالئم منطقی دشوار است‪.‬‬ ‫‪.1‬دریافت دان‬ ‫‪.2‬گاهی فاصله بین قابل حل بودن مساله در تئوری و انجام آن در عمل زیاد است‪.‬‬ ‫ن‬ ‫ع‬ ‫ک‬ ‫م‬‫ع‬ ‫ق‬ ‫‪ -4-2‬ل ردن ال ی‬ ‫رویکرد عتامتل های عقالنی‪ :‬عامل عقالنی‪ ،‬عاملی استتتت که همواره کاری را که انتظار می رود هر چه بیشتتتتر اهداف عامل را‬ ‫برآورده کند ( یعنی کار درست را) انجام می دهد‪.‬‬ ‫در رویکرد قوانین تفکر تاکید بر استتنتا صحیح بود‪.‬گاهی اوقات استنتا صحیح فقط قسمتی از وظایف یک عامل منطقی است‬ ‫زیرا موقعیتت هتایی وجود دارد کته هیا کتار خوب قتابتل اثباتی وجود ندارد ولی باید عملی انجام بگیردی همچنین راههایی برای‬ ‫عقالنی عمل کردن وجود دارند که ربطی به استنتا ندارند مانند عقب کشیدن فوری دست از اجاق گاز داغ‪.‬‬ ‫همه مهارتهای مورد نیاز در آزمون تورینگ برای امکان پذیر کردن اقدامات عقالنی هستتتتند‪.‬در این جزوه بر اصتتتول کلی عامل‬ ‫های عقالنی و اجزای سازنده آنها تمرکز شده است‪.‬‬ ‫(‪ )Sensors‬دریافت می کند و اعمالی در محیط خود از‬ ‫عامل نهادی استتت که اطالعاتی از محیط خود را توستتط حستتگرهای‬ ‫(‪ )Actuators‬انجام می دهد‪.‬‬ ‫طریق عملگرهای‬ ‫عامل های عقالنی برای انجام کار درستت گاهی انسان گونه عمل می کنند‪ ،‬گاهی انسان گونه فکر می کنند و گاهی منطقی فکر‬ ‫می کنند بنابراین رویکرد عقالنی عمل کردن جامع تر از سه رویکرد پیشین است‪.‬‬ ‫تعریف عقالنیت محدود‪ :‬درست عمل کردن زمانی که وقت کافی برای انجام تمام محاسبات وجود ندارد‪.‬‬ ‫‪4‬‬  ‫فص‬ ‫ل دوم‬ ‫شم‬ ‫ه‬ ‫م‬ ‫عا ل اهی و ند‬  ‫‪ -1‬عامل اه و محیط اه‬ ‫(‪ )Sensors‬دریافت می کند و اعمالی در محیط خود از‬ ‫عامل نهادی استتتت که اطالعاتی از محیط خود را توستتتط حستتتگرهای‬ ‫(‪ )Actuators‬انجام می دهد‪.‬‬ ‫طریق عملگرهای‬ ‫مثال‪( :‬عامل انسانی حسگرها‪ :‬گوش‪ ،‬چشم‪ ،‬دیگر ارگا نهای عملگرها‪ :‬دست‪ ،‬پا‪ ،‬بینی‪ ،‬اندامهای دیگر)‬ ‫مثال‪( :‬عامل ربات مری نوردی حسگرها‪ :‬دوربین ها و ردیاب های مادون قرمزی عملگرها‪ :‬موتورهای گوناگون)‬ ‫مثال‪ :‬یک عامل نرم افزاری‪ ،‬کلیدهای فشترده شده‪ ،‬محتویات فایل و بسته های شبکه را به عنوان ورودی حسگر دریافت می کند‬ ‫روی صفحه نمای ‪ ،‬نوشتن در فایلها و ارسال بسته های شبکه عمل (=اقدام) می کند‪.‬‬ ‫و در محیط با نمای‬ ‫اگر بتوانیم عمل انتخاب شده عامل به ازای هر دنباله از مشاهدات را مشخص کنیم آنگاه همه چیز را در مورد عامل بیان کرده ایم‪.‬‬ ‫به زبان ریاضی‪ ،‬رفتار یک عامل توسط تابع عامل توصیف می شود‪.‬‬ ‫تابع عامل‪ :‬یک دنباله از مشاهدات را دریافت کرده و سپس یک عمل (اقدام) از مجموعه عمل ها (اقدام ها) را برمی گرداند‪.‬‬ ‫𝐴 → ∗𝑃 ‪𝑓:‬‬ ‫‪ :f‬تابع عامل‬ ‫‪ :P‬مجموعه تمام مقادیری که یک مشاهده می تواند بگیرد‪.‬‬ ‫‪ :A‬مجموعه تمام مقادیری که یک عمل (اقدام) می تواند بگیرد‪.‬‬ ‫*‪ :P‬مجموعه تمام دنباله ها از مقادیر مشاهده شده (دنباله مشاهدات)‬ ‫اصلی تشکیل شده است‪ :‬معماری ‪ +‬برنامه (‪)Agent=Program+Architecture‬‬ ‫یک عامل از دو بخ‬ ‫‪6‬‬ ‫وظیفه هوش مصتتتنوعی طراحی برنامه عامل برای پیاده ستتتازی تابع کارگزار (که ادراکات (=مشتتتاهدات) را به اقدامات نگاشتتتت‬ ‫میکند) می باشد‪.‬‬ ‫تفاوت تابع عامل و برنامه عامل‪ :‬تابع عامل(‪ )f‬یک توصیف انتزاعی ریاضی است‪ ،‬در حالی که برنامه عامل یک پیاده سازی واقعی‬ ‫می باشد که روی معماری قابل اجراست‪.‬‬ ‫آیا ورودی برنامه عامل همان ورودی تابع عامل معادل است؟‬ ‫خیر‪ ،‬برنامه عامل فقط نیاز به دریافت آخرین مشتاهده از محیط دارد ولی تابع عامل نیاز به دریافت همه مشاهداتی که تا االن روی‬ ‫داده دارد و بنابراین نیاز به فضای حافظه بسیار زیاد برای ذخیره سازی مشاهدات دارد‪.‬‬ ‫مثال‪ :‬عامل جاروبرقی‬ ‫عملگرها‪ :‬موتوری‬ ‫عمل ها (اقدام ها)‪ :‬حرکت به چپ‪ ،‬حرکت به راست‪ ،‬بدون حرکت و مک‬ ‫حسگرها‪ :‬حسگر مکان‪ ،‬حسگر تشخیص کثیفی و تمیزیی‬ ‫مشتاهدات حسگر مکان‪ :‬خانه فعلی ‪ A‬هست‪ ،‬خانه فعلی ‪ B‬هستی مشاهدات حسگر کثیفی و تمیزی‪ :‬خانه فعلی کثیف است‪ ،‬خانه‬ ‫فعلی تمیز استی‬ ‫محیط‪ :‬دو خانه دارد (خانه ‪ A‬و خانه ‪ ،)B‬هر خانه می تواند تمیز یا کثیف باشد‪.‬‬ ‫مف‬ ‫‪ -2‬رفتار ردست‪ :‬هوم عقالنی بودن‬ ‫معیار کارایی (‪: )performance measure‬معیاری که میزان موفقیت یک عامل را می ستتنجد‪.‬این معیار خار از عامل و توستتط‬ ‫طراح عامل تعیین می شود‪.‬‬ ‫مثال‪ :‬برای جاروبرقی مثال قبلی معیار کارایی می تواند هر یک از معیارهای زیر باشد‬ ‫تمیز شتتدن هر دو خانه‪ ،‬تمیز شتتدن هر دو خانه با کمترین حرکت (حرکت اضتتافه کارایی را پایین می آورد)‪ ،‬تمیز شتتدن خانه با‬ ‫کمترین حرکت و کمترین سروصدا‪... ،‬‬ ‫‪7‬‬ ‫قبلی عامل در مورد محیط‪،‬‬ ‫عقالنی بودن عتامتل بتایتد بته چهار گزینه توجه داشتتتت‪ :‬معیار کارایی عامل‪ ،‬دان‬ ‫هنگتام ستتتنج‬ ‫عملگرهای عامل‪ ،‬رشته ادراکات (=دنباله مشادات) عامل‬ ‫تعریف کامل عامل عقالنی‪ :‬یک عامل عقالنی (‪ )rational agent‬برای هر رشتتته ادراکات (=دنباله مشتتاهدات) ممکن‪ ،‬بر استتاس‬ ‫درونی او فراهم آمده عملی را برمیگزیند که انتظار می رود معیار کارایی اش را بیشینه‬ ‫شواهدی که توسط رشته ادراکات و دان‬ ‫کند‪.‬‬ ‫‪ -1-2‬همه چیزدانی‪ ،‬یادگیری‪ ،‬خودمختاری‬ ‫بی نهایت دارد) و‬ ‫تفاوت بین عقالنی بودن و دانای کل بودن‪ :‬عامل دانای کل همیشتته بهترین عمل را انجام می دهد (نیاز به دان‬ ‫می باشتتتدی به عبارت دیگر عامل عقالنی‬ ‫را می داند ولی عقالنی بودن به معنای انتظار به اندازه تزریق دان‬ ‫نتیجه واقعی اعمال‬ ‫کارایی مورد انتظار(‪ )expected performance‬را بیشینه می کند در حالی که دانای کل کارایی واقعی را بیشینه می کند‪.‬‬ ‫اولیه‪ ،‬مشاهدات و تجربه خود عمل می کند‪.‬‬ ‫عامل عقالنی بر مبنای دان‬ ‫عامل های موفق‪ ،‬محاسبه تابع عامل را به سه دوره مختلف تقسیم می کنند‪:‬‬ ‫‪ -1‬هنگامی که عامل طراحی می شود (دانشی که طراح در عامل می گنجاند)‬ ‫‪ -2‬هنگامی که به اقدام بعدی خود می اندیشد‬ ‫چیزی یاد می گیرد‬ ‫‪ -3‬هنگامی که از تجربیات‬ ‫اولیه بر پایه تجربه‬ ‫غلط یا ناقص قبلی و افزودن به دان‬ ‫تعریف یادگیری‪ :‬اصالح دان‬ ‫درونی و یادگیری عمل می کند‪.‬‬ ‫تعریف عامل خودمختار‪ :‬عاملی است که براساس دان‬ ‫‪ -3‬محیط کار‬ ‫یتک محیط کار (‪ ،)task environment‬محیطی استتتت که عامل در آن کار(عمل) می کندی یعنی محیط کار از (محیط‪ +‬عامل)‬ ‫تشکیل شده است‪.‬‬ ‫زیر را مشخص کرد‪:‬‬ ‫در یک محیط کار باید چهار بخ‬ ‫‪ -1‬معیار کارایی (‪ :)performance measure‬برای ارزیابی عملکرد عامل مورد نیاز است و خار از عامل تعریف می شود‪.‬‬ ‫‪ -2‬محیط (‪ :)environment‬محیطی که عامل فرار است در آن کار کند‬ ‫‪ -3‬عملگرهای عامل (‪)actuators‬‬ ‫‪ -4‬حسگرهای عامل (‪)sensors‬‬ ‫‪8‬‬  ‫نکته‪ :‬اصطالحا به محیط کار ‪ peas‬می گویند که یک سرنام است‪.‬‬ ‫مثال‪ :‬محیط کار راننده تاکسی‬ ‫نام عامل‬ ‫معیار کارایی‬ ‫حسگرهای عامل‬ ‫عمل های عامل‬ ‫محیط‬ ‫( که توستتتط عملگرها‬ ‫انجام می شود)‬ ‫بوق زدن‪ ،‬چراغ زدن‪ ،‬دوربتتیتتن هتتا‪ ،GPS ،‬ایتتمتتنتتی‪ ،‬ستتتترعتتت‪ ،‬راننده تاکسی‬ ‫جاده‪ ،‬پیاده رو‪،‬‬ ‫راهنمایی کردن‪ ،‬شتاب ستترعت ستتن ‪ ،‬شتتتاب قتتانتونتمنتتدی‪ ،‬راحتی‪،‬‬ ‫ترافیک‪ ،‬مشتری‬ ‫سودمندی‬ ‫دادن‪ ،‬ترمز‪ ،‬صتتحبت با ستتن ‪ ،‬کیلومتر شتتمار‪ ،‬افزای‬ ‫حسگر های موتور‬ ‫مسافر‬ ‫محیط کار مصنوعی جیست؟‬ ‫یک محیط غیر واقعی مانند یک محیط شبیه سازی شده است‪.‬مانند محیط بازی شطرن رایانه ای‬ ‫دو نمونه از عامل هایی که در محیط مصنوعی کار می کنند‪:‬‬ ‫‪ -1‬ربات های فوتبالیست شبیه سازی شده در محیط زمین فوتبال شبیه سازی شده‬ ‫‪ -2‬ربات انتخاب گر اخبار با توجه به عالیق کاربر در ‪Gmail‬‬ ‫طبیعی یا مصتنوعی بودن محیط چندان مهم نیست‪ ،‬بلکه پیچیدگی ارتباط بین رفتار عامل‪ ،‬رشته ادراکات دریافتی از محیط و معیار‬ ‫کارایی دارای اهمیت است‪.‬‬ ‫‪ -4‬انواع محیط کاری‬ ‫ب کم‬ ‫‪ -1-4‬کامال مشاهده پذری رد مقا ل ی مشاهده پذری‬ ‫در محیط کامال مشتتاهده پذیر (قابل دستتترس)‪ ،‬حستتگرها وضتتعیت کامل محیط را در اختیار عامل قرار می دهند‪.‬در محیط جزیی‬ ‫مشاهده پذیر‪ ،‬حسگرها بخشی از وضعیت محیط را در اختیار عامل قرار می دهند‪.‬‬ ‫محیط کار به طور موثر مشتاهده پذیر (‪ :)effectively fully observable‬در محیط کار به طور موثر مشتاهده پذیر‪ ،‬حسگرها همه‬ ‫عمل مناستتب الزم استتت را فراهم می کنند و اطالعاتی که در انتخاب عمل درستتت نقشتی ندارند دور‬ ‫اطالعاتی که برای گزین‬ ‫ریخته می شوند‪.‬‬ ‫‪9‬‬ ‫طراحی عامل ها در محیط های کامال مشتتاهده پذیر ستتاده استتت‪ ،‬چرا که عامل نیازی به نگهداری اطالعات گذشتتته (مدل محیط)‬ ‫ندارد و فقط بر مبنای مشاهده فعلی خود می تواند عقالنی عمل کند‪.‬‬ ‫ب‬ ‫‪ -2-4‬قطعی رد مقا ل غیر قطعی‬ ‫اگر امکان تعیین دقیق حالت بعدی محیط بر پایه حالت فعلی و عمل انجام شده توسط عامل وجود داشته باشد‪ ،‬گوییم محیط قطعی‬ ‫است‪.‬‬ ‫بینی باشد‪).‬‬ ‫یعنی (حالت فعلی محیط معلوم ‪ +‬عمل عامل معلوم ‪ ‬حالت بعدی محیط صد در صد قابل پی‬ ‫محیط استراتژیک‪ :‬محیطی است که عدم قطعیت در آن مربوط به ناآگاهی از اعمال آینده دیگر عامل ها است‪.‬‬ ‫بینی‬ ‫یعنی (حالت فعلی محیط معلوم ‪ +‬عمل عامل معلوم ‪ +‬عمل ستایر عامل ها معلوم ‪ ‬حالت بعدی محیط صد در صد قابل پی‬ ‫باشد‪).‬‬ ‫ممکن است اتاق‬ ‫مثال‪ :‬محیط کار جارو برقی در باال قطعی استت‪.‬محیط کار جاروبرقی با این فرض که پس از انجام عمل مک‬ ‫همچنان کثیف باقی بماند غیرقطعی است‪.‬محیط کار بازی منا استراتژیک است‪.‬‬ ‫ب‬ ‫‪ -3-4‬میسقت پذری (اپیزودیک) رد مقا ل رتتیبی (پی رد پی)‬ ‫در محیط کار تقستیم پذیر (‪ )episodic‬تجربه عامل به بخشتهایی تقستیم می شتود که هر کدام مستتقل از دیگری است‪.‬در محیط‬ ‫(‪ )episode‬فکر کند‪.‬‬ ‫تقسیم پذیر نیازی نیست که عامل به خار از یک بخ‬ ‫در محیط های ترتیبی (‪ )sequential‬یا تقسیم ناپذیر‪ ،‬تصمیم جاری بر همه تصمیم های آینده تاثیر می گذارد‪.‬‬ ‫‪11‬‬  ‫مثال‪ :‬محیط کار بازی شطرن ترتیبی است‪.‬محیط کار ربات تشخیص قطعات معیوب تقسیم پذیر است‪.‬‬ ‫ب‬ ‫‪ -4-4‬ایستا رد مقا ل پویا‬ ‫اگر محیط هنگام تصتتمیم گیری عامل برای عمل بعدی تغییر کند‪ ،‬محیط پویا استتتی به عبارتی بدون اینکه عامل عملی در محیط‬ ‫انجام دهد محیط تغییر می کند‪.‬در محیط ایستا تا عامل عملی انجام ندهد محیط تغییر نمی کند‪.‬‬ ‫در محیط های ایستا‪ ،‬عامل نیازی به نگهداری رویدادها هنگام تصمیم گیری ندارد و عامل نگران گذر زمان نیست‪.‬‬ ‫محیط کاری نیمه پویا‪ :‬اگر محیط با گذر زمان تغییر نکند اما کارایی عامل پایین بیایدی به عبارتی محیط ایستتتایی استتت که با گذر‬ ‫زمان کارایی عامل پایین می آید‪.‬‬ ‫مثال‪ :‬محیط راننده تاکستی هوشتمند پویا استت‪.‬محیط بازی منا ایستتا استت‪.‬محیط بازی شطرن ایستا است‪.‬محیط بازی شطرن‬ ‫زماندار نیمه پویا است‪.‬محیط جدول کلمات متقاطع ایستا است‪.‬‬ ‫ب‬ ‫‪ -5-4‬گسسته رد مقا ل ویپسته‬ ‫اگر مشاهدات و اعمال عامل با اعداد گسسته قابل بیان باشند‪ ،‬محیط گسسته نامیده می شود‪.‬‬ ‫مثال‪ :‬بازی شطرن گسسته است چون تعداد محدودی حالت متمایز داردی همچنین مجموعه گسسته ای از مشاهدات و اعمال دارد‪.‬‬ ‫رانندگی تاکسی مسئله ای با حالت و زمان پیوسته است‪.‬‬ ‫‪ -6-4‬تک عاملی رد ربارب چند عاملی‬ ‫در محیط چند عامله‪ ،‬عالوه بر عامل اصتتلی عاملهای دیگری نیز وجود دارند که تالش می کنند کارایی خود را بیشتتینه کنند مانند‬ ‫محیط بازی شطرن ‪ ،‬محیط راننده تاکسی و ‪...‬‬ ‫ستوال‪ :‬عامل ‪( A‬مثال راننده تاکستی) از کجا می تواند تشخیص بدهد که یک شی ‪( B‬مثال یک خودرو دیگر) قسمتی از محیط‬ ‫است یا یک عامل در محیط؟‬ ‫جواب‪ :‬اگر شتی ‪ B‬برای بیشتینه کردن معیار کارایی خود تالش کند حتما یک عامل است وگرنه جزو محیط عامل ‪ A‬حساب می‬ ‫شود‪.‬‬ ‫‪ -9-4‬محیط چند عامله راقبتی‬ ‫در این محیط بیشتتینه شتتدن کارایی یک عامل به کمینه شتتدن کارایی عامل دیگر می انجامد‪.‬مانند محیط بازی شتتطرن یا محیط‬ ‫راننده تاکسی آنجا که رانندگان برای پارک کردن خودروی خود با هم رقابت دارند‪.‬‬ ‫‪11‬‬ ‫بینی پذیری‬ ‫نکته‪ :‬رفتار اتفاقی در برخی محیط های رقابتی کمی مشتتاهده پذیر عقالنی محستتوب می شتتود زیرا از مشتتکل پی‬ ‫جلوگیری می کند‪.‬‬ ‫‪ -8-4‬محیط چند عامله هم کاری‬ ‫در این محیط بیشتینه شتدن کارایی عاملها به هم وابسته است و همزمان با بیشینه شدن کارایی یک عامل‪ ،‬کارایی عامل یا عاملهای‬ ‫دیگر نیز بیشینه می شود‪.‬مانند محیط راننده تاکسی آنجا که رانندگان تالش می کنند از تصادف جلوگیری کنند‪.‬‬ ‫چند مثال از محیط های کاری‬ ‫‪ -5‬انواع عامل اه‬ ‫عامل ها را می توان براستتاس برنامه عامل به ‪ 4‬دستتته تقس تیم نمود‪ :‬عامل های واکنش تی ستتاده‪ ،‬عامل های مبتنی بر مدل‪ ،‬عامل های‬ ‫هدف گرا‪ ،‬عامل های مبتنی بر سودمندی‬ ‫همه این عامل ها مشاهده فعلی را از حسگرها دریافت و یک اقدام (=عمل) را به عملگرها بر می گردانند‪.‬هر ‪ 4‬دسته از این عامل ا‬ ‫را می توان به عامل یادگیرنده تبدیل کرد‪.‬‬ ‫‪12‬‬  ‫ک نش‬ ‫‪ -1-5‬عامل اهی وا ی ساده‬ ‫این عامل ها حافظه ندارند به عبارت دیگر چیزی از گذشته به خاطر نمی سپارند‪.‬این عامل ها مشاهدات جاری را تفسیر و بر مبنای‬ ‫آن عمل مناستب را انتخاب می کنند مانند عامل جاروبرقی‪.‬این عامل ها فقط می توانند در محیط های کامال مشاهده پذیر عقالنی‬ ‫عمل کنند‪.‬‬ ‫از آنجا که عامل واکنشتی هیا مدلی از محیط خود نمی ستازد بنابراین در محیط های جزیی قابل مشاهده که عقالنی عمل کردن‬ ‫در آنها نیازمند ساخت مدل است با مشکل مواجه می شوند و نمی توانند عقالنی عمل کنند‪.‬مثال تشخیص ترمز زدن ماشین جلویی‬ ‫از روی تغییر سترعت وابستته به بررسی مشاهده های پیشین است است که عامل واکنشی ساده هیا اطالعاتی از مشاهده های قبل‬ ‫ندارد‪.‬‬ ‫مثال‪ :‬فرض کنید در مثال محیط کار عامل جارو برقی‪ ،‬حالت آغازین موقعیت عامل و وضعیت اتاق ها به تصادف انتخاب شود و‬ ‫معیار کارایی به صورت زیر تعریف شده باشد‪:‬‬ ‫‪ ‬انجام هر حرکت فیزیکی ‪ - 1‬و تمیز کردن هر اتاق کثیف ‪5‬‬ ‫عامل واکنشی ساده زیر می تواند برای این مثال عقالنی عمل کند‪.‬‬ ‫‪13‬‬  ‫مب‬ ‫‪ -2-5‬عامل اهی تنی رب مدل‬ ‫گاهی تصتمیم گیری درست بر مبنای مشاهدات جاری ممکن نیست مانند تشخیص ترمز گرفتن ماشین جلویی توسط عامل راننده‬ ‫تاکسی (چون نیاز به مشاهدات قبلی دارد تا تغییر سرعت را بفهمد)‪.‬عامل های مبتنی بر مدل با استفاده از دنباله مشاهده ها‪ ،‬مدلی از‬ ‫جهان را می سازند‪.‬‬ ‫‪14‬‬  ‫‪ -3-5‬عامل اهی هدفگرا‬ ‫در عامل های واکنشی (چه ساده و چه مبتنی بر مدل)‪ ،‬هدف هنگام طراحی عامل به صورت ضمنی درقوانین تعبیه می شود‪.‬عامل‬ ‫قابل توجهی از قواعد حالت‪-‬عمل خود هستند‪.‬‬ ‫های واکنشی برای تغییر هدف‪ ،‬نیازمند بازنویسی بخ‬ ‫عامل های هدف گرا می توانند هم بر مبنای حالت جاری و هم بر مبنای هدف‪ ،‬تصتتتمیم مناستتتب بگیرندی در این عامل ها‪ ،‬برنامه‬ ‫عامل با آگاهی از هدف (یا هدف ها) و اینکه نتیجه اعمال او چیست دنباله اعمالی را بر می گزیند که او را به هدف برساند‪.‬‬ ‫عامل های جستجو که در فصل ‪ 3‬بررسی می شوند و عامل های برنامه ریزی از نوع عامل های هدف گرا هستند‪.‬‬ ‫مب‬ ‫‪ -4-5‬عامل اهی تنی رب سودمندی‬ ‫اهداف تنها می توانند دو وضتتعیت «ناخشتتتنود» و «خوشتتتنود» را از هم متمایز کنند‪ ،‬برای اینکه بتوانیم بین حالتهای مختلف تمایز‬ ‫بیشتری ایجاد کنیم‪ ،‬باید میزان سودمندی هر یک از آنها را مشخص کنیم‪.‬‬ ‫تعریف تابع ستودمندی‪ :‬یک حالت (یا چند حالت) را به یک عدد حقیقی که درجه رضتایت نامیده می شتود نگاشت می کند‪.‬در‬ ‫واقع میزان خوشنودی عامل از بودن در آن حالت را نشان می دهد‪.‬‬ ‫عامل های مبتنی بر سودمندی تالش می کنند متوسط تابع سودمندی را بیشینه کنند‪.‬‬ ‫دو مزیت عامل مبتنی بر سودمندی نسبت به عامل مبتنی بر هدف‬ ‫‪ -1‬گاهی اهداف با هم مغایرت دارند (مانند سرعت و ایمنی در سفر) که سودمندی موازنه ای بین آنها برقرار می کند‪.‬‬ ‫‪ -2‬زمتانی کته چند هدف وجود دارد و عامل باید بین آنها انتخاب کند آگاهی از ستتتودمندی هر یک از هدف ها می تواند‬ ‫راهگشا باشد‪.‬‬ ‫تفتاوت معیتار کتارایی و تتابع ستتتودمنتدی‪ :‬معیتار کارایی خار از عامل برای ارزیابی عملکرد عامل تعریف می شتتتود ولی تابع‬ ‫سودمندی در خود عامل تعریف شده تا میزان خوشنودی عامل از بودن در یک حالت را بسنجد‪.‬‬ ‫‪15‬‬ ‫مثال‪ :‬عامل راننده تاکسی در دو پیاده سازی (به صورت عامل مبتنی بر هدف و عامل مبتنی بر سودمندی)‬ ‫‪ -6‬عاملهای یادگیرنده‬ ‫عامل های موفق‪ ،‬محاسبه تابع عامل را به سه دوره گوناگون تقسیم می کنند‬ ‫‪ -1‬هنگامی که عامل طراحی می شود (دانشی که طراح در عامل می گنجاند)‬ ‫‪ -2‬هنگامی که به اقدام بعدی خود می اندیشد‬ ‫‪16‬‬  ‫چیزی یاد میگیرد‬ ‫‪ -3‬هنگامی که از تجربیات‬ ‫عامل هایی که تا کنون بررسی شدند فقط دو مورد اول را انجام می دهند‪.‬‬ ‫منظور از یادگیری در عامل های هوشمند جیست؟‬ ‫فرآیند تغییر هر جز از عامل به این منظور که آن جز ستتتازگاری بیشتتتتر با اطالعات بازخورد پیدا کند و از این طریق کارایی کل‬ ‫عامل بهبود یابد‪.‬‬ ‫منتقد مشتخص می کند که عنصتر یادگیری با توجه به استاندارد کارایی چگونه عمل کرده است‪.‬اگر منتقد نباشد عامل نمی تواند‬ ‫نادرست است و یا کاستی دارد‪.‬‬ ‫بفهمد که چه بخشی از دانش‬ ‫عنصر یادگیری با توجه به بازخورد منتقد تعیین می کند که عنصر کارایی چگونه باید تغییر کند تا در آینده بهتر عمل کند‪.‬‬ ‫عنصر کارایی مسئول انتخاب فعالیت های خارجی است‪.‬‬ ‫مولد مساله‪ ،‬مسوول پیشنهاد فعالیت هایی است که منجر به تجربیات آموزنده جدیدی می شود‪.‬‬ ‫ش‬ ‫‪ -1-6‬کل اهی یادگیری‬ ‫یادگیری در مورد اینکه دنیا چگونه تغییر می کند با بررسی دنباله مشاهدات صورت می گیرد‪.‬‬ ‫یادگیری در مورد اینکه اقدامات من چه کار می کنند با بررس تی اقدامات انجام شتتده و مشتتاهدات قبل و پس از آنها صتتورت می‬ ‫گیرد‪.‬‬ ‫‪17‬‬ ‫یادگیری در مورد ستتودمندی‪ :‬منتقد ندادن انعام توستتط مستتافر و ارتباط آن با ستترعت باال هنگام جابجایی را به صتتورت بازخورد‬ ‫اطالع می دهد و عنصر یادگیری تغییراتی در عنصر کارایی ایجاد می کند تا از این پس مسافران را با سرعت باال جابجا نکند‪.‬‬ ‫‪18‬‬  ‫فص‬ ‫ل سوم‬ ‫حل مساهل با جست وج‬ ‫‪19‬‬  ‫ح‬ ‫‪ -1‬عامل ل مساهل‬ ‫نوع ویژه ای از عامل مبتنی بر هدف است که هنگام طراحی عامل تنها تعریف مساله در آن گنجانده می شود‪.‬هدف برای این نوع‬ ‫از عامل ها به صتتورت مجموعه ای از حالت های هدف تعریف می شتتود‪.‬در اینجا عامل باید به راه هایی برای رستتیدن به هدف‬ ‫بیاندیشد (اندیشیدن=جستجو کردن)‬ ‫مثال‪ :‬مساله سفر در رومانی‬ ‫‪ ‬صورت مسئله ‪ :‬رفتن از آراد به بخارست‬ ‫‪ ‬حالت ها‪ :‬بودن در شهرها‬ ‫‪ ‬حالت هدف‪ :‬بودن در بخارست‬ ‫‪ ‬راه حل‪ :‬دنباله ای از اعمال که ما را از حالت آغازین (بودن در آراد) به حالت هدف (بودن در بخارست) می رساند‪.‬‬ ‫‪ ‬برای مثال (آراد‪-‬سیبیو‪-‬فاگاراس‪-‬بخارست) یک راه حل است‪.‬‬ ‫‪ -2‬تعریف مسئله‬ ‫یک مساله بر پایه ‪ 4‬عنصر تعریف می شود‪:‬‬ ‫‪.1‬حالت آغازین (‪)initial state‬‬ ‫مثال‪at Arad :‬‬ ‫‪.2‬اعمال یا تابع پستین(‪ :)successor function‬تابع )‪ S(x‬که حالت ‪ x‬را گرفته و حالتهای ممکن پس از آن را مشخص می‬ ‫کند‪.‬‬ ‫‪21‬‬  ‫مثال‪S(Arad)= { Zerind, Sibiu, Timisuara} :‬‬ ‫‪.3‬آزمون هدف‪ :‬آیا حالت فعلی‪ ،‬حالت هدف است؟‬ ‫صریح‪at Bucharest :‬‬ ‫ضمنی‪checkmate(x) :‬‬ ‫‪.4‬هزینه مسیر (‪C(x,a,y) :)path cost‬‬ ‫مثال‪ :‬مسافت بین دو شهر‪ ،‬تعداد حرکت های انجام شده‬ ‫یک راه حل‪ ،‬دنبال های از اعمال است که از حالت آغازین به یک حالت هدف می رسد‪.‬‬ ‫مستتایل دنیای واقعی معموال بستتیار پیچیده تر از آن هستتتند که بتوان با همه جزییات آنها را حل کرد بنابراین باید آنها را انتزاعی‬ ‫کرد‪.‬برای مثال در مسئله رفتن از آراد به بخارست‪ ،‬پس از انتزاع‪ ،‬اعمال به صورت رفتن از شهری به شهر دیگر تعریف می شوند‪.‬‬ ‫نکته‪ :‬انجام هر عمل انتزاعی باید ساده تر از مساله باشد‪.‬‬ ‫‪ -3‬انواع مساهل‬ ‫‪ -1-3‬مساهل تک حالتی ( ‪)single-state‬‬ ‫در اینجتا محیط قطعی و کتامال مشتتتاهده پذیر استتتت و عامل می داند دقیقا در چه حالتی خواهد بود‪.‬در اینجا عامل فقط یک بار‬ ‫جستجو می کند و سپس تنها یک بار اجرا (اقدام) می کند‪.‬‬ ‫نکته‪ :‬راه حل های مستتائل‪ ،‬رشتتته های ستتاده ای از اقدامات هستتتند بنابراین نمی توانند از عهده هیا رویداد غیرمنتظره ای برآیند‪.‬‬ ‫همچنین راه حلها بدون توجه به ادراکات (مشاهدات) اجرا می شوند! چنین سامانه هایی را حلقه باز (‪ )open loop‬می گویند چون‬ ‫بی توجهی به مشاهدات حلقه بین عامل و محیط را ازبین می برد‪.‬‬ ‫‪21‬‬  ‫مثال‪ :‬فرض می شتتود که محیط کامال مشتتاهده پذیر استتت یعنی عامل اطالعات مربوط به‬ ‫کثیفی و تمیزی و مکان همه خانه ها را در هر لحظه دارد‪.‬‬ ‫شروع از حالت شماره ‪5‬‬ ‫راه حل‪]right, suck[ :‬‬ ‫مثال‪:‬‬ ‫فضتای حالت‪ :‬مجموعه همه حالت های قابل دستترس از حالت آغازین را فضتای حالت گویند‪.‬فضای حالت را می توان با داشتن‬ ‫حالت آغازین و تابع پسین به دست آورد‪.‬‬ ‫گراف فضای حالت‪ :‬گرافی است که در گره های آن حالتها هستند و یالهای آن مشخص کننده وجود ارتباط پسینی بین حالتها می‬ ‫باشند‪.‬در صورتی که ‪ y‬پسین ‪ x‬باشد یالی از ‪ x‬به ‪ y‬در گراف فضای حالت وجود دارد‪.‬‬ ‫مساله نمونه ‪ :1‬دنیای جاروبرقی‬ ‫فضای حالت شامل ‪ 8‬حالت است که از ترکیب های مختلف موقعیت و کثیفی دو اتاق به دست می آید‪.‬‬ ‫تعریف مساله‪:‬‬ ‫‪.1‬حتالتت آغازین‪ :‬یکی از حالت های‬ ‫مستتتالته (بستتتتگی بته شتتترایط اولیه‬ ‫مفروض دارد)‬ ‫‪.2‬تابع پستتتین (اعمال)‪ :‬چپ‪ ،‬راستتتت‪،‬‬ ‫مک‬ ‫‪.3‬آزمون هدف‪ :‬هر دو خانه تمیز باشتتد‬ ‫(حالت های هدف ‪ 2‬تاست)‬ ‫‪22‬‬  ‫‪.4‬هزینه مسیر‪ :‬یک واحد برای هر عمل‬ ‫مساله نمونه ‪ :2‬معمای ‪8‬‬ ‫فضای حالت‪ :‬هر چیدمان ممکن‪ ،‬یک گره در گراف فضای حالت است‪.‬‬ ‫تعریف مسئله‬ ‫‪.1‬حالت آغازین‪ :‬هر حالت در فضای حالت می تواند‬ ‫باشد‪.‬‬ ‫نکتته‪ :‬اثبتات می شتتتود که دقیقا از نیمی از حالت‬ ‫های اولیه می توان به یک حالت هدف مشتتتخص‬ ‫رسید‪.‬‬ ‫‪.2‬تابع پست تین (اعمال)‪ :‬حرکت فضتتتای خالی به باال‪،‬‬ ‫پایین‪ ،‬چپ و راست (در صورت امکان)‬ ‫‪.3‬آزمون هدف‪ :‬آیا حالت مورد نظر همان چیدمان هدف است؟‬ ‫‪.4‬هزینه مسیر‪ :‬یک واحد برای هر عمل‬ ‫مستاله پازل ‪ 8‬تایی جزو خانواده پازلهای بلوک لغزنده (‪ )Sliding-block puzzles‬هستتند که از دستته مسائل ‪ NP-complete‬می‬ ‫باشند‪.‬‬ ‫مساله نمونه ‪ n :3‬وزیر‬ ‫تعریف مسئله (تعریف اول‪ :‬تدوین افزایشی)‬ ‫‪.1‬حالت آغازین‪ :‬صفحه شطرن خالی‬ ‫‪.2‬تابع پسین (اعمال)‪ :‬افزودن یک وزیر به یکی از سطرهای سمت چپ ترین ستون‬ ‫خالی‬ ‫‪.3‬آزمون هدف‪ :‬آیا همه وزیرها بدون اینکه همدیگر را تهدید کنند روی صتتتفحه‬ ‫قرار گرفته اند؟‬ ‫‪.4‬هزینه مسیر‪ :‬هر حرکت یک واحد‬ ‫نکته‪ :‬می توان تابع پستین را به شکلهای دیگری نیز تعریف کرد مثال افزودن یکی از مهره های باقیمانده به یکی از خانه های خالی‬ ‫(تعریف دوم) که موجب می شود تعداد پسینها به شدت زیاد شود و کارایی عامل جستجو کاسته شود‪.‬‬ ‫در تعریف دیگری از این مستتئله (تعریف ستتوم‪ :‬تدوین حالت کامل) می توان حالت آغازین و تابع پس تین را به شتتکل زیر تعریف‬ ‫کرد‪:‬‬ ‫‪23‬‬  ‫‪ ‬حالت آغازین‪ :‬یک حالت تصادفی که در آن همه مهره ها روی صفحه اند‬ ‫‪ ‬تابع پسین‪ :‬جابجایی یک مهره (انتخاب یک مهره و قرار دادن آن در یکی از خانه های خالی)‬ ‫البته تعاریف زیادی می توان برای این مسئله نوشت‪.‬تعریف مناسب می تواند بسیار در کارآمدی عامل جستجو موثر باشد‪.‬‬ ‫مساله نمونه ‪ :4‬ربات سرهم سازی قطعه‬ ‫تعریف مساله‬ ‫‪.1‬حتالتت آغتازین‪ :‬ربات و قطعه ها‬ ‫در وضعیت آغازین‬ ‫‪.2‬تابع پسین‪ :‬دوران یا جابجایی یکی‬ ‫از مفصلهای ربات‬ ‫‪.3‬آزمون هدف‪ :‬آیا ستترهم ستتازی‬ ‫قطعه ها به انجام رسیده است؟‬ ‫‪.4‬هزینه مسیر‪ :‬مدت زمان به پایان رساندن فرآیند سرهم سازی‬ ‫‪ -2-3‬مساهل با اطالعات انقص(‪)sensorless‬‬ ‫در اینجا محیط جزیی مشتاهده پذیر و یا گاهی غیرقابل مشتاهده است و عامل نمی داند دقیقا کجاست‪.‬در اینجا عامل باید به جای‬ ‫یک حالت درباره مجموعه حالتهایی که ممکن استتتت در آنها قرار گیرد استتتتدالل کند‪.‬به چنین مجموعه حالتی‪ ،‬حالت باور می‬ ‫گوییم‪.‬برای حل مستائل بدون حستگر به جای فضای حالت های فیزیکی در فضای حالت های باور جستجو می کنیم‪.‬اگر فضای‬ ‫حالت ‪ n‬حالت داشته باشد فضای باور ‪ 2n‬حالت خواهد داشت‪.‬‬ ‫‪ ‬اگر محیط غیر قابل مشاهده باشد آنگاه عامل یک بار جستجو و سپس تنها یک بار اجرا (اقدام) می کند‪.‬‬ ‫‪ ‬اگر محیط جزیی مشاهده پذیر باشد آنگاه عامل یک در میان جستجو و اجرا را انجام می دهد‪.‬‬ ‫مثال‪ :‬برای مسئله جارو برقی در سه حالت زیر یک راه حل ارائه دهید‪.‬‬ ‫الف‪.‬محیط برای جاروبرقی غیر قابل مشاهده باشد‪.‬‬ ‫ب‪.‬محیط برای جاروبرقی کامال مشاهده پذیر باشد‪.‬‬ ‫‪.‬محیط برای جاروبرقی جزئی مشتتاهده پذیر باشتتد (ستتنستتورهای جاروبرقی فقط مکان فعلی‬ ‫جتاروبرقی (ختانته ‪ A‬هستتتت یتا ‪ B‬؟) و تمیزی و کثیفی مکان فعلی را در اختیار جاروبرقی قرار‬ ‫دهند) ‪.‬‬ ‫جواب‪:‬‬ ‫‪24‬‬ ‫الف‪.‬در این حالت چون محیط مشتاهده پذیر نیستت عامل نمی داند که در کدام حالت خاق قرار گرفته است و در ابتدا فکر می‬ ‫کند که امکان دارد در هر کدام از این ‪ 8‬حالت باشتد بنابراین کل این ‪ 8‬حالت معادل یک حالت باور برای عامل است‪.‬اگر عامل‬ ‫حتما در راستت است پس می داند در یکی از حاالت خاق‬ ‫جارو بخواهد راستت برود می داند در حالتی خواهد بود که مکان‬ ‫‪ 6 ،4 ،2‬یتا ‪ 8‬خواهد بود که کل این ‪ 4‬حالت یک حالت باور برای عامل خواهد بود‪.‬در اینجا عامل جارو برقی کال ‪ 12‬حالت باور‬ ‫دارد که در نمودار زیر آمده است‪(.‬توجه کنید با وجود اینکه ‪ 8‬حالت خاق داریم ولی تعداد حاالت باور ‪ 12‬می باشد)‪.‬اگر عامل‬ ‫به هر کدام از دو حالت باور که در پایینترین سطح نمودار وجود دارد برسد یک راه حل پیدا گرده است‪.‬‬ ‫به طور خالصه راه حلهای زیر هنگام مشاهده ناپذیر بودن محیط برای عامل وجود دارد که هر راه حل می تواند جواب مسئله باشد‪.‬‬ ‫]‪[left, suck, right, suck‬‬ ‫]‪[right, suck, left, suck‬‬ ‫]‪[suck, left, suck, right, suck‬‬ ‫]‪[suck right, suck, left, suck‬‬ ‫راه حل های اول و دوم از نظر تعداد اعمال عامل بهینه هستند‪.‬‬ ‫‪25‬‬ ‫ب‪.‬اگر محیط کامال مشتتتاهده پذیر باشتتتد عامل چون وضتتتعیت هر دو خانه از نظر تمیزی و کثیفی را می داندو هم چنین موقعیت‬ ‫مکانی خود را می داند می تواند با یکبار حس محیط راه حل را ارائه کند‪.‬‬ ‫بر فرض اگر عامل در یکی از حاالت ‪ 3‬و ‪ 6‬باشتتد ]‪ ،[suck‬اگر در حالت ‪ 4‬باشتتد ]‪ ،[left, suck‬اگر در حالت ‪ 1‬باشتتد ‪[suck,‬‬ ‫]‪ right, suck‬و اگر در حاالت ‪ 7‬و ‪ 8‬باشد ][ یک راه حل است‪.‬دقت کنید که اگر عامل در حاالت ‪ 7‬و ‪ 8‬باشد نیازی به هیا‬ ‫گونه اقدام ندارد‪.‬‬ ‫‪.‬فرض کنید عامل جاروبرقی تنها از موقعیت خود و تمیزی اتاق کنونی آگاه است و اطالعات بقیه اتاق ها را ندارد (محیط جزیی‬ ‫مشاهده پذیر)ی در این حالت نیز مجموعه ای از حاالت باور داریم و می توان به راه حل رسید‪.‬برای مثال اگر جارو برقی در حالت‬ ‫]‪ [A, Clean‬باشتد یعنی می داند در خانه ‪ A‬هستت و می داند این خانه تمیز است ولی نمی داند که خانه مجاور چه خبر است‪.‬در‬ ‫این حالت‪ ،‬حالت باور از دو حالت خاق تشکیل شده است‪.‬شکل زیر را ببینید‪.‬‬ ‫با فرض شتروع از حالت باور باال‪ ،‬عامل تصتمیم خواهد گرفت که به ستمت راست برود اگر تمیز بود عملی انجام نمی دهد و اگر‬ ‫می کند (در حالتی که عامل حافظه داشتته باشد و حالت قبل خود را به یاد آورد) ‪.‬اگر عامل حافظه نداشته باشد‬ ‫کثیف بود مک‬ ‫بی نهایت بار از اتاق چپ به راست و از راست به چپ خواهد رفت‪.‬‬ ‫‪ -3-3‬مساهل احتمالی (‪)contingency‬‬ ‫اگر محیط کمی مشتتتاهتده پتذیر یا اقدامات غیرقطعی باشتتتند آنگاه مشتتتاهدات اطالعات جدیدی را در مورد حالت فعلی فراهم‬ ‫میکنند‪.‬در اینجا عامل یک در میان جستجو و اجرا را انجام می دهد‪.‬‬ ‫مثال‬ ‫با احتمال ‪ 1.8‬اتاق را تمیز می کند و با احتمال ‪ 1.2‬بی اثر است‪.‬‬ ‫عدم قطعیت‪ :‬مک‬ ‫محیط جزیی مشاهده پذیر است‪ :‬فقط مکان و کثیفی اتاق جاری معلوم است و از اتاق (های) دیگر اطالعی در دسترس نیست‪.‬‬ ‫‪ -4-3‬مساهل اکتشافی‬ ‫در اینجا فضتای حالت و اقدامات محیط ناشتناخته است و مشاهدات اطالعات جدیدی را در مورد حالت فعلی فراهم می کنند‪.‬در‬ ‫اینجا عامل یک در میان جستجو و اجرا را انجام می دهد‪.‬مسائل اکتشافی را می توان حد نهایی مسائل احتمالی دانست‪.‬‬ ‫‪26‬‬  ‫ج‬ ‫جست‬ ‫‪ -4‬الگوریتم اهی وی رد ی‬ ‫خت‬ ‫با جستتجوی درختی می توان همه مسیرهای ممکن مورد نظر را بررسی کرد‪.‬به ازای هر گره در درخت جستجو‪ ،‬یک و تنها یک‬ ‫مسیر از حالت آغازین به آن وجود دارد‪.‬راه حل‪ ،‬مسیری از گره آغازین به یک گره هدف می باشد‪.‬‬ ‫نکته‪ :‬وردودی الگوریتم جستجو‪ ،‬گراف فضای حالت مسئله است که با حالت اولیه و تابع پسین به طور صریح نشان داده می شود‪.‬‬ ‫ایده پایه الگوریتم های جستجوی درختی‪ ،‬جستجوی فضای حالت با تولید حالتهای پسین حالت کنونی می باشد‪.‬‬ ‫‪27‬‬  ‫الگوریتم جستجوی درختی‬ ‫تابع گسترش (‪ )expand function‬گره های جدیدی ایجاد می کند و فیلدهای گوناگون گره های جدید را مقدار می دهد‪.‬‬ ‫تابع گسترش از تابع پسین برای ایجاد حالت های مربوط به هر گره استفاده می کند‪.‬‬ ‫گره ساختمان داده ای است که بخشی از درخت جستجو را تشکیل می دهد و اطالعات حالت‪ ،‬گره پدر‪ ،‬عمل‪ ،‬هزینه مسیر (‪ )g‬و‬ ‫عمق را در بردارد‪.‬‬ ‫‪28‬‬ ‫الگوریتمهای جستتتجوی ناآگاهانه تنها از اطالعات موجود در تعریف مستتاله استتتفاده می کنند‪.‬این الگوریتم ها تنها قادر به تولید‬ ‫پسین ها و تشخیص یک حالت هدف از یک حالت غیر هدف می باشند‪.‬الگوریتم هایی که می دانند یک حالت غیرهدف شانس‬ ‫موفقیت بیشتری نسبت به دیگران دارد الگوریتم های جستجوی آگاهانه ( یا جستجوی هیوریستیک) خوانده می شوند‪.‬‬ ‫معروفترین الگوریتم های ناآگاهانه عبارتند از‪:‬‬ ‫‪ ‬جستجوی اول سطح‬ ‫‪ ‬جستجوی هزینه یکنواخت‬ ‫‪ ‬جستجوی اول عمق‬ ‫‪ ‬جستجوی با عمق محدود‬ ‫‪ ‬جستجوی عمیق کننده تکراری‬ ‫مهمترین تفاوت الگوریتمهای جستتجو‪ ،‬ستاختمان داده ‪( fringe‬حاشیه=لبه) به کار رفته در آنهاست که ترتیب گسترش گره ها را‬ ‫مشخص می کند‪ fringe.‬مجموعه گره هایی که تولید شده اند ولی هنوز گسترش نیافته اند را نشان می دهدی هر عضو ‪ fringe‬یک‬ ‫گره برگ است چون پسینی در درخت ندارد‪.‬‬ ‫الگوریتم های جستجو بر پایه ی عامل های زیر ارزیابی می شود‪:‬‬ ‫‪ ‬کامل بودن‪ :‬آیا چنانچه راه حلی موجود باشد الگوریتم آن را پیدا می کند؟‬ ‫‪ ‬پیچیدگی زمانی‪ :‬تعداد گره هایی که تولید می شوند‪.‬‬ ‫‪ ‬پیچیدگی فضا (حافظه)‪ :‬بیشینه تعداد گره های نگهداری شده در حافظه‬ ‫‪ ‬بهینگی‪ :‬آیا همیشه کم هزینه ترین راه حل را پیدا می کند؟‬ ‫زمان و پیچیدگی الگوریتم جستجو بر پایه سه پارامتر زیر مشخص می شود‪:‬‬ ‫‪ :b ‬بیشینه فاکتور انشعاب درخت جستجو که بیشترین تعداد گره فرزند در میان تمام گره های درخت را نشان می دهد‪.‬‬ ‫‪ ‬فاکتور انشعاب میانگین‪ :‬میانگین تعداد گره های فرزند در میان تمام گره های درخت‬ ‫‪ :d ‬عمق کم هزینه ترین راه حل (کم هزینه ترین گره هدف)‬ ‫‪ :m ‬بیشینه عمق فضای حالت (طوالنی ترین مسیر در فضای حالت)‬ ‫سط‬ ‫ج‬‫جست‬ ‫‪ -1-4‬وی اول ح‬ ‫کم عمق ترین گره گسترش نیافته را گسترش می دهد‪.‬‬ ‫‪29‬‬  ‫در پیاده سازی جستجوی اول سطح‪ ،‬ساختمان داده ‪ ،fringe‬یک صف ‪ FIFO‬است‪.‬‬ ‫مثال‪:‬‬ ‫بهینگی؟‬ ‫پیچیدگی فضایی (حافظه)؟‬ ‫پیچیدگی زمانی؟‬ ‫کامل بودن؟‬ ‫…‪ 1+b+b +b d+‬از آنجتا که همه گره ها را در خیر مگر اینکتته هزین ته‬ ‫جستجوی اول بلتته‪ ،‬اگتتر فتتاکتتتور ‪+bd+‬‬ ‫‪2‬‬ ‫‪3‬‬ ‫)‪b(b -1) = O(bd+1‬‬ ‫حافظه نگه می دارد )‪ O(bd+1‬همه اعمال یکسان باشد‬ ‫انشتتتعتتاب محتتدود‬ ‫سطح‬ ‫باشد‪.‬‬ ‫‪31‬‬  ‫بزرگ ترین مشکل الگوریتم اول سطح‪ ،‬پیچیدگی حافظه باال است‪.‬‬ ‫مثالی از پیچیدگی زمانی و حافظه جستجوی اول سطح‬ ‫جست‬ ‫‪ -2-4‬جوی زهینه یکنواخت‬ ‫این الگوریتم گره ای را گستترش می دهد که کمترین هزینه مستیر را دارد‪.‬در پیاده ستازی جستتجوی هزینه یکنواخت‪ ،‬ساختمان‬ ‫داده ‪ ،fringe‬یک صتف مرتب بر حستب هزینه مستیر استت‪.‬اگر هزینه همه عمل ها یکستان باشتد‪ ،‬با جستجوی اول سطح معادل‬ ‫است‪.‬‬ ‫پیچیدگی فضایی بهینگی؟‬ ‫پیچیدگی زمانی؟‬ ‫کامل بودن؟‬ ‫(حافظه)؟‬ ‫بلتته‪ ،‬چتتون الگوریتم راه‬ ‫))‪O(bceiling(C*/ ε‬‬ ‫جستتتتتتتجتتوی بلتته‪ ،‬اگر ‪ )1‬فتتاکتور انشتتتعتتاب ))‪O(bceiling(C*/ ε‬‬ ‫حل ها را بر استتاس هزینه‬ ‫هتتتتزیتتتتنتتتته محتدود بتاشتتتد‪ )2.‬هزینه همه *‪ :C‬کتتل هزینتته از گره‬ ‫مسیر بررسی می کند‪.‬‬ ‫اعمتال بزرگتر از یک عدد ثابت آغتاز تا هدف (هزینه راه‬ ‫یکنواخت‬ ‫حل بهینه)‬ ‫مثبت باشد‪.‬‬ ‫‪ :ε‬حداقل هزینه هر عمل‬ ‫مثال‪:‬‬ ‫‪31‬‬  ‫عم‬ ‫ج‬‫جست‬ ‫‪ -3-4‬وی اول ق‬ ‫جستتتتجوی اول عمق‪ ،‬عمیقترین گره را گستتتترش می دهتتد‪.‬در پیتتاده ستتتازی‬ ‫جستجوی اول عمق‪ ،‬ساختمان داده ‪ ،fringe‬یک پشته (‪ )stack‬است‪.‬‬ ‫مثال‪:‬‬ ‫‪32‬‬ ‫بهینگی؟‬ ‫پیچیدگی‬ ‫پیچیدگی زمانی؟‬ ‫کامل بودن؟‬ ‫فضایی‬ ‫(حافظه)؟‬ ‫خیر‬ ‫)‪O(bm‬‬ ‫)‪O(bm‬‬ ‫خیر‪ ،‬مگر آنکه از تکرار حالتها‬ ‫جستجوی‬ ‫‪ ‬اگر ‪ m‬خیلی بزرگ تر از ‪ d‬باشتتد‪،‬‬ ‫جلوگیری شود و تعداد گره های‬ ‫اول عمق‬ ‫وحشتناک است‪.‬‬ ‫فضای حالت محدود باشد‪.‬‬ ‫‪ ‬اگر تعتداد راه حل ها زیاد باشتتتد‪،‬‬ ‫ممکن است به طور میانگین بهتر از‬ ‫اول سطح عمل کند‪.‬‬ ‫‪33‬‬ ‫نوع خاصتی از جستجوی اول عمق به نام جستجوی پسگرد (‪ )backtracking search‬به جای تمام پسین ها در هر لحظه فقط یک‬ ‫پستین تولید می کند‪.‬هر گره نیمه گسترش یافته به خاطر می سپارد که در مرحله بعدی باید کدام پسین را تولید کند‪.‬بدین ترتیب‬ ‫به جای )‪ O(bm‬به )‪ O(m‬حافظه نیاز داریم‪.‬جستتجوی پسگرد از ترفند دیگری نیز برای صرفه جویی در حافظه استفاده می کند و‬ ‫آن تولید پسین با تغییرمستقیم توصیف حالت فعلی است‪.‬‬ ‫عم عم‬ ‫جست‬ ‫‪ -4-4‬جوی اول ق با ق محدود‬ ‫از‬ ‫گره های پایین از عمق مشتخص (مثال ‪ )l‬بررستی و تولید نمی شتوند‪.‬محدود کردن عمق باعث می شود تا مانع از پیشروی بی‬ ‫حد جستجو در عمق شود‪.‬‬ ‫کامل بودن؟ پیچیدگی زمانی؟ پیچیدگی فضایی (حافظه)؟ بهینگی؟‬ ‫خیر‬