Artificial Intelligence - هوش مصنوعی - دنيای هيولا (Wumpus World)

آيا مي توانيم بدون درگير شدن با قوانين استنتاج ومپوس و چاله هاي موجود در غار را بيابيم و به طلا دسترسي پيدا کنيم؟؟؟
:105::39:

در بررسي غار ومپوس به اين نتيجه رسيدم که براي يافتن چاله ها و ومپوس ها با توجه به پرسپت ها مي توانيم به روش زير عمل کنيم

از آنجايي که ابعاد غار در ابتدا مشخص نيست يک غار با مشخصات حداکتر ممکن در نظر مي گيريم ( در اين مسئله با توجه به توافق حداکثر ابعاد 10 در 10 هستند) برای اسن منظور می توان یک آرایه از اعدا د صحیح با مشخصات فوق تعریف کنید .

برای وضعیت خانه ها ثابت هاي رير را فرض مي کنيم

كد:

#define WUMPUS       1

#define PIT                    2

#define OK                    4

#define VISITED           8

یک تابت برای حداکثر تعداد ومپوس های ممکن در غار تعریف می کنیم

كد:

#define WUMPUS_RATE 1

چون حرکات عامل به صورت حرکت به جلو ، چرخش 90 درجه به چپ ، چرخش 90 درجه به راست ، رها کردن تير ، ربودن طلا و بالا رفتن از غار می باشد واز آنجا که از بیشتر حرکات با استفاده از حرکت به جلو ، چرخش 90 درجه به چپ ، چرخش 90 درجه به راست امکان پذیر است برای راحتی کار 4 حرکت سطح بالا به صورت : حرکت به سمت چپ ، حرکت به سمت راست ، حرکت به سمت بالا و حرکت به سمت پایین را تعریف می کنیم
حرکات ممکن سطح پایین ، جهت های جغرافیایی و حرمات سطح بالا را به صورت زیر تعریف می کنیم

كد:

enum Direction {East=0,North,West,South};

enum Actions {None=0, Forward, TurnLeft, TurnRight, Shoot, Grab, Climb};

enum Move_Agent {Right= 0,Left,Up,Down };

چون این حرکت های سطح بالا وابسته به جهت عامل ( شمال ، حنوب ، شرق و غرب ) و حرکت های اصلی آن می باشد پس با توجه به جهت عامل 16 حالت مختلف برای حرکات سطح بالا و جود دارد مثلا اگر جهت عامل رو به شرق باشد حرکت به راست معادل حرکت به جلو و اگر جهت عامل رو به شمال باشد حرکت به راست معادل دو حرکت ، چرخش 90 درجه به راست و سپس حرکت به جلو و اگر جهت عامل رو به غرب باشد حرکت راست معادل دو چرخش به چپ با دو چرخش به راست و سپس حرکت به جلو خواهد بود و اگر جهت عامل رو به جنوب باشد ، حرکت به راست معادل یک چرخش به چپ و سپس حرکت به جلو می باشد. بنابراین یک جدول تعریف می کنیم که سطرها معادل حرکات سطح بالا و ستونها معرف جهت و خانه ها حاوی دستورات مورد نیاز برای انجام حرکت خواهد بود ( این جدول را می توان با استفاده از ساختارهای if then و یا switch case پیاده سازی نمود )

http://artificial3.persiangig.com/image/jadval1.JPG

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

http://artificial3.persiangig.com/image/jadval2.JPG

ساختارداده ای مورد نیاز برای عامل به صورت زیر می باشد

كد:

struct Agent

{

bool Gold ; // true if agent Find Gold

bool Gun ; // true if agent not shoot

int x,y; // agent cordinate

Direction dir; // agent direction

};

Agent agent;

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

كد:

 struct  Percepts

{

bool breeze ; // true if agent near a PIT

bool stench ; // true if agent near a Wumpus

bool glitter; // true if agent Find Gold

bool scream ; // true if agent shoot killnear wumpus

bool bumb ; // true if agent go throgh the wall

};

حل مسئله :

از آنجايي که وجود ومپوس و يا چاله خطرناک می باشد . در ابتدا فرض مي کنيم همه خانه هاي غار بجز خانه شروع داري ومپوس وچاله است پس در ابتداي کار بجز خانه شروع تمام خانه ها را با مقدار PIT+WUMPUS مقدار دهي مي کنيم .

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

همواره با توجه به استراتژی یک هدف مشخص را دنبال می کنیم و با توجه به هدف بر اساس الگوریتم *A بهترین حرکت را انجام می دهیم

هدف با توجه به استراتژی می تواند یکی از موارد زیر باشد

http://artificial3.persiangig.com/image/jadval3.JPG

در هر زمان با توجه به هدف دو نوع هزینه را محاسبه می کنیم ( هزینه تخمینی + هزینه حرکت به سمت نزدیک ترین خانه مجاور دارای تخمین کمتر )
هزینه حرکت همان هزینه حرکت سطح بالای مورد نیاز برای رسیدن به خانه مجاور با توجه به جهت عامل می باشد که در جدول هزینه حرکت های سطح بالا مخاسبه شد . البته 2 و یا 3 واحد هزینه سربار برای خانه های VISIT شده در نطر می گیریم تا عامل را ترغیب به انتخاب خانه های کاوش نشده نماییم.
ناگفته نماند این هزینه ها برای خانه های امن است . و هزینه حرکت به سمت خانه های دارای احتمال چاله / ومپوس و یا خانه های غیر واقعی برابر بی نهایت فرض می شود

تابع تخمین حداقل هزینه ممکن برای حرکت مستقیم به سمت هدف را برای هر خانه حساب می کند وبه صورت زیر عمل می کند

H=abs( goal.x - agent.x) + abs( goal.y - agent.y)

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

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

1. پرسپت را از برنامه محيط دريافت کنيد

2. در هر خانه با توجه به پرسپت داده شده وضعيت خانه هاي بالا ، پايين ، چپ ، راست و يا خود خانه اي که عامل در آن قرار دارد را به روش زير بروز درآوريد

الف ) اگر نسيم احساس نشده وجود PIT در خانه هاي بالا ، پايين ، چپ و راست عامل را از بين ببريد

ب ) اگر بو احساس نشده وجود WUMPUS در خانه هاي بالا ، پايين ، چپ و راست عامل را از بين ببريد
ج ) اگر وجود ومپوس و چاله در خانه از بین رفت آن خانه را به عنوان خانه امن علامت بزنید

چ) اگر درخشش احساس شده طلا را برداريد و با يک تابع هيورستيک بهترين مسير برگشت را از ميان حانه هاي امن بدست آورده و برگرديد.

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

ه ) اگر به ديواري خورديد که براي تان جديد است ( ديواره سمت چپ و پايين غار از اول مشخص است ) ، ابعاد غار را با توجه به ديوار محدود کنيد تا بتوانيد در مراحل بعدي بهتر تصميم بگيريد .

3 . باتوجه به استراتژي یک ( دنباله ) حرکت مناسب را انتخاب کنید
4. وضعیت موحودتان را با حرکت انتخابی به روز درآورید
5. حرکت را به برنامه محیط ارجاع داده تا بر روی محیط واقعی اعمال نماید.

6 مجددا به مرحله 1 برگرديد

دانلود برنامه کامل ارائه شده به زبان C
:53: