دنيای هيولا (Wumpus World) - Artificial Intelligence

**Astaraki** · ۰۴-۱۷-۱۳۸۹, ۰۸:۵۸ بعد از ظهر

دنياي WUMPUS:
مشابه دنياي مکش، دنياي Wumpus شبکه‌اي از مربع است که توسط ديوارهايي احاطه شده‌اند، که هر مربع مي‌تواند شامل عامل‌ها و اشياء باشد.

وظيفه عامل يافتن طلا و بازگشتن به نقطه شروع و بالا رفتن از غار است.

براي مشخص نمودن وظيفه عامل، ادراکات، عمليات و اهداف آن را بايد مشخص کنيم. در دنياي Wumpus، اينها به صورت زير هستند:

از مربعي که شامل Wumpus است و مربع‌هاي مجاور (نه قطري) عامل بوي بدي را دريافت مي‌کند .

در مربعهايي که مستقيماً مجاور با چاله‌ها هستند، عامل نسيمي را دريافت مي‌کند.

در مربعي که طلا وجود دارد، عامل يک درخششي را درک مي‌کند.

زماني که يک عامل به داخل ديواره قدم بر مي‌دارد، ضربه‌اي را دريافت مي‌کند.

زماني که Wumpus کشته مي‌شود، فريادي سر مي‌دهد که هر جايي از غار شنيده مي‌شود.

ادراکات به عامل به صورت ليستي از پنج سيمبول داده مي‌شود.

مانند دنياي مکش، عملايتي براي جلو رفتن، چرخيدن 90 به سمت چپ، چرخيدن 90 به سمت راست وجود دارد.

عامل نابود خواهد شد زماني که وارد يک مربع شامل سياده چاله و يا کي Wumpus زنده مي‌‌شود.

هدف عامل يافتن طلا و برگرداندن آن به خانه شروع با سرعت تمام است، بدون آنکه کشته شود

**Astaraki** · ۰۴-۱۷-۱۳۸۹, ۰۹:۰۱ بعد از ظهر

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

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

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

**Astaraki** · ۰۴-۱۷-۱۳۸۹, ۰۹:۵۷ بعد از ظهر

برنامه هیولا Wumpus در فصل ۷ کتاب هست به زبان برنامه نویسی #Visual Stadio C و زبان c تقديم شما

**Astaraki** · ۰۴-۱۷-۱۳۸۹, ۱۰:۰۸ بعد از ظهر

Wumpus World به زبان پرولوگ!

is_omid · ۱۱-۱۴-۱۳۸۹, ۱۱:۱۷ قبل از ظهر

سلام
اگر امکان داره کد wampus با پرولوگ رو توضیح بدید
ممنون

honey · ۰۳-۱-۱۳۹۰, ۱۲:۰۹ قبل از ظهر

سلام دوستان
من این ترم هوش مصنوعی دارم ولی هیچی بلد نیستم؛کلاسامون هم خیلی بد و دیر به دیر تشکیل میشه.

حل مسئله (شکلی رو که گذاشتم)رو با منطق گزاره ای میخواستم.

ممنون میشم کمکم کنید

nazliii · ۰۵-۳۰-۱۳۹۱, ۱۱:۰۱ قبل از ظهر

سلام
کسی برنامه wumpus رو با متلب نداره که بتونه به من کمک کنه؟

ellat · ۰۵-۳۰-۱۳۹۱, ۰۳:۴۲ بعد از ظهر

نقل قول:

نوشته اصلي بوسيله is_omid

سلام
اگر امکان داره کد wampus با پرولوگ رو توضیح بدید
ممنون

سلام دوست عزیز
به لینک زیر مراجعه کنید. در مورد این الگوریتم در پرولوگ کاملا توضیح داده شده است
Prolog implementation of the wumpus world
موفق باشید.

zahra124 · ۰۷-۱۲-۱۳۹۱, ۱۱:۱۸ قبل از ظهر

سلام میشه راجع به الگوریتمش هم توضیح بدید این که با چه الگوریتمی نوشته شده و اسمش چیه

mkh22@hushmail.com · ۰۹-۲۲-۱۳۹۲, ۰۷:۱۸ بعد از ظهر

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

صفحه مون n*n باشه و n از کاربر گرفته بشه
حرکات بصورت بالا پایین چپ و راست باشد (چرخش لازم نیست)
چاله ها و ومپوس و طلا بصورت تصادفی پخش شوند
هدف عامل فقط يافتن طلا است
کشتن ومپوس لازم نیست
عامل منطق گرا باشد(منطق مرتبه 0)
اطراف خانه شروع هیچ چیزی وجود ندارد
عامل فقط به خانه های امن میرود
عامل اطلاعات را به khowleg base خود اضافه میکند و بر اساس آن تصمیم گیری میکند

کسی میتونه کمک کنه