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

خلاصه

برنامه کامل ارائه شده به زیان C  را می توانید از روی این سایت به رایگان دانلود کنید .
توجه : از آنجایی که اغلب افراد با کلاس ها در C  آشنا نیستند برنامه با استفاده از روش تابعی و به زبان ساده نوشته شده است

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

  از آنجايي که ابعاد غار  در ابتدا مشخص نيست  يک غار با مشخصات حداکتر ممکن  در نظر مي گيريم ( در اين مسئله با توجه به توافق حداکثر ابعاد 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 پیاده سازی نمود )

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

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

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 بهترین حرکت را انجام می دهیم

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

برنامه کامل ارائه شده به زیان C  را می توانید از روی این سایت به رایگان دانلود کنید
توجه : از آنجایی که اغلب افراد با کلاس ها در C  آشنا نیستند برنامه با استفاده از روش تابعی و به زبان ساده نوشته شده است

لطفا اشکالات این روش را به ایمیل زیر مکتوب کنید  Info@aliarash.com  

حسن رضا آرش 28/4/1382