بررسی یک الگوریتم مسیریابی در هوش مصنوعی

راهکاری برای حل مسئله بسیار مهم و حساس مسیریابی در بازی ها و نرم افزارهای مهندسی

*در این مقاله قصد داریم، یکی از مهمترین و در واقع رایج ترین الگوریتم های مورد استفاده در فرآیندهای مسیریابی هوشمند را مورد بررسی قرار دهیم. این الگوریتم *A (به صورت A Star خوانده می شود) نام دارد و همان طور که خودتان در ادامه مشاهده خواهید نمود، به قدری ارزش دارد که عده ای آن را ستاره الگوریتم های مسیریابی و هوش مصنوعی خوانده اند. این الگوریتم اگرچه از نظر طراحی و عملکرد نسبتاً ساده می باشد و طرز کار آن را می توان تقریباً به راحتی درک کرد، اما پیاده سازی آن بر حسب شرایط مختلف و قابلیت های مورد نظر، بسیار متنوع و تا حدودی پیچیده است.
لازم به ذکر است، این الگوریتم که از قدمت نسبتاً طولانی در صنعت کامپیوتر برخوردار است، در طول سالیان گذشته، به اشکال مختلفی پیاده سازی شده است. البته شما نیز می توانید این الگوریتم را به شیوه مورد نظر خودتان پیاده سازی کنید. به طور کلی *A به عنوان راهکاری برای حل مسئله بسیار مهم و حساس مسیریابی در بازی ها و نرم افزارهای مهندسی و شبیه سازی محسوب می شود و نحوه اجرا و استفاده از آن کاملاً به شرایط بستگی دارد.
*این الگوریتم به گونه ای کار می کند که می توان از آن در هر محیطی بهره گرفت. اگرچه محدودیت های خاص خود را نیز دارد، اما *A می تواند شما را در ساخت بازی های کاملاً دو بعدی، بازی های اول شخص و سوم شخص سه بعدی، بازی های استراتژی و حتی بازی هایی در محیط های بیرونی (زمین و تپه، رودخانه و دریا، جنگل و...) یاری کند. برای اعمال *A در یک بازی (و یا هر محیط دیگری)، شما ابتدا باید یک ناحیه جستجو برای خود تعریف کنید. این ناحیه (Search Area)، همان محدوده ای است که *A قرار است با انجام یک سلسله تست های تکراری آن را مورد بررسی قرار داده و بهترین (و کوتاهترین مسیر) را در آن بیابد. البته در این مقاله قصد نداریم وارد جزئیات پیاده سازی شویم، بلکه صرفاً می خواهیم با توضیح مفهوم این الگوریتم، شما را در حل مسائل مربوطه یاری کنیم.
در یک کلام *A الگوریتمی قدرتمند برای یافتن نزدیکترین مسیر بین دو نقطه می باشد که می توان با انجام برخی تغییرات، آن را برای اهداف دیگری از جمله حل مسائل گراف ها نیز به کار برد.
این ناحیه جستجو می تواند محیط داخلی یک خانه (کلیه اتاق ها، آشپزخانه، حمام و دستشویی و راهروها و دیوارها و اشیا داخل آن، یعنی به صورت یک مستطیل که کل مساحت خانه را در بر می گیرد)، یک دشت یا یک جنگل، و یا یک کارخانه باشد. البته این محیط قطعاً دارای نقاطی می باشد که امکان ورود به آنها وجود ندارد. همین اشیا نیز باعث پیچیده شدن فرآیند مسیریابی می شوند. (مثلاً کاراکتر شما نمی تواند وارد دیوار یا یخچال شود، از طرفی در هنگام حرکت در اتاق ها، باید مبلمان را تشخیص داده و از کنار آنها - و نه از درون آنها - عبور کند، همان طوری که انسانها در دنیای واقعی حرکت می کنند، که البته همین عبور از کنار موانع، بخش دشوار الگوریتم است)
*پس از اینکه ناحیه جستجو مشخص شد، باید این ناحیه را به قسمت های کوچکتری تبدیل کنید.
این نواحی کوچک که به عنوان سلول (cell) یا گره (node) شناخته می شوند، اساس کار این الگوریتم هستند. به طور معمول هرچه تعداد این قسمت های کوچک بیشتر باشد، دقت عملیات نیز افزایش خواهد یافت (که باعث کاهش سرعت پردازش نیز خواهد شد). برای درک بهتر روند کار این الگوریتم، مراحل کار در قالب چند شکل نشان داده شده اند. اگرچه ما در اینجا ناحیه جستجوی خود را به تعدادی مربع کوچک تقسیم کرده ایم (تصویر 1) ولی در حالت کلی، این سلول ها می توانند هر شکلی داشته باشند (تعیین شکل و اندازه این سلول ها به شکل محیط و نحوه حرکت بستگی دارد، اما عموماً تقسیم ناحیه جستجو به مربع های کوچک، بهترین نتیجه را دارد). در این شکل مربع سبز مبدأ حرکت، خانه های آبی دیوار (یعنی مانع حرکت)، و مربع قرمز نیز مقصد می باشد.
*همان طور که گفته شد، این الگوریتم یک سری تست های تکراری را انجام می دهد تا در نهایت به هدف مورد نظر برسد (البته در صورت امکان، یعنی در صورت وجود یک مسیر). در تصویر دوم 8 خانه اطراف خانه سبز، با فلش های مخصوصی نشان داده شده اند. ما در اولین گام، فاصله هر یک از این 8 خانه تا مقصد (یعنی سلول قرمز) را بررسی می کنیم.
سپس از بین این 8 خانه، نزدیکترین خانه را نسبت به مقصد انتخاب می کنیم. سپس موقعیت این خانه را ثبت می کنیم، زیرا در مرحله بعدی تست، باید از این خانه به عنوان مبدأ جدید حرکت استفاده کنیم. مجدداً این تست را برای خانه جدید انتخاب شده انجام می دهیم (یعنی هشت خانه اطراف آن را بررسی کرده و از بین آنها نزدیکترین سلول را به مقصد می یابیم). این تست تا زمانی ادامه می یابد که به مقصد برسیم.
البته دو نکته را نباید فراموش کنیم. مسئله اول اینکه در هنگام بررسی خانه های اطراف، نباید خانه های مانع را به حساب آوریم. این سلول ها می توانند دیوار، اشیاء داخل منزل، درخت، رودخانه و یا هر شیء دیگری باشند که شما در حین حرکت نباید درون آن وارد شوید. اما مسئله دوم هم اینکه نباید بیش از یک بار وارد هیچ سلولی شوید. یعنی در حالت کلی نباید هیچ خانه ای را بیش از یک بار در مسیر خود طی کنید. به این منظور می توانید کلیه خانه های مورد استفاده در مسیر را در یک آرایه ثبت کنید، سپس در هنگام انجام مراحل بعدی تست، آن خانه ها را مورد بررسی قرار ندهید.
در حقیقت این تئوری پشت پرده الگوریتم *A است که پیاده سازی آن به اشکال گوناگونی، امکان پذیر است. در تصویر 3 شما می توانید فرآیند تست سلول های اطراف خانه سبز را مشاهده کنید.
ضمن اینکه در گوشه هر خانه، فاصله آن خانه تا سلول مقصد، مشخص شده است. شکل 4 نیز کلیه تست های انجام گرفته برای حرکت از مبداء به مقصد را نشان می دهد. به این ترتیب شما می توانید هوشمندانه مسیر خود را در بین انبوهی از اشیاء و در محیط های ناشناخته نیز بیابید. البته کار در همین جا تمام نمی شود! کما اینکه پیاده سازی این الگوریتم بر حسب شرایط مختلف می تواند بسیار متفاوت باشد.
در ادامه به برخی از نکات مهم در هنگام پیاده سازی این الگوریتم اشاره شده است:
1))یافتن فاصله بین سلول ها در این الگوریتم اهمیت زیادی دارد، اما منظور از فاصله چیست؟ آیا می توان از فرمول فیثاغورث به این منظور استفاده کرد؟ یا باید تعداد مجموع خانه های عمودی و افقی موجود در مسیر را به عنوان فاصله محسوب نمود؟ این مسئله ای است که بر حسب نوع محیط و مسیر می تواند متفاوت باشد.
2))اگرچه در بسیاری از پیاده سازی های این الگوریتم، از لیست های پیوندی و انواع آرایه ها برای ثبت و ذخیره کلیه نقاط مسیر (و انجام تغییرات احتمالی بعدی بر روی آنها) استفاده می شود، اما شما می توانید در ساده ترین حالت، صرفاً شیء مورد نظر خود را بر روی نقطه بعدی مسیر قرار دهید. به این ترتیب احتیاج به ثبت هیچ داده ای نخواهید داشت. البته در مسیرهای پیچیده معمولاً اولین مسیر یافت شده، بهترین مسیر نمی باشد، پس باید آن را به نحوی اصلاح کنید.
3))این الگوریتم از نظر محاسباتی می تواند زمان بر باشد. پس درصورت امکان از تکنیک های دیگری نیز به صورت ترکیبی برای کاهش هزینه محاسباتی استفاده کنید (مثلاًَ می توانید برخی مسیرهای پیچیده و طولانی را با کدنویسی به صورت توکار در برنامه قرار دهید، به گونه ای که حرکت بر روی یک سری نقاط از پیش مشخص شده انجام گیرد و احتیاجی به انجام تست های الگوریتم *A نباشد).
4))اگرچه این الگوریتم، کوتاهترین مسیر را به شما می دهد، اما این مسیر دارای نقاط شکست بسیاری می باشد. یعنی اگر بدون انجام بهینه سازی و برخی تغییرات محاسباتی، آن را بر روی کاراکترهای خود اعمال کنید، خواهید دید که در هنگام چرخش، حرکاتی بسیار ناگهانی خواهند داشت، علاوه بر این، برخی اوقات مسیرهای به دست آمده چندان بهینه نمی باشند. در نتیجه باید آنها را مورد بهینه سازی قرار دهید (فرآیندی که اغلب ازپیاده سازی اولیه الگوریتم، دشوارتر است).
5))یکی از راه حل های رفع مشکل چرخش ناگهانی، ذخیره کلیه نقاط حرکتی و حذف نقاطی است که زاویه تندی می سازند. در نهایت شما می توانید مسیر اصلاح شده را مورد استفاده قرار دهید. به این منظور می توانید از لیست های پیوندی یا حتی آرایه های ساده استفاده کنید. بی شک پیاده سازی زیبای حرکت یک کاراکتر، فرآیندی دشوار می باشد که انواع محاسبات مثلثاتی، ماتریسی و برداری را در بر می گیرد.
6))ما در این تست، هیچ تمایزی بین خانه های مختلف قائل نشدیم، یعنی احتمال انتخاب هر یک از خانه ها (البته نزدیکترین خانه ها به مقصد)، مساوی می باشد.
اما بیشتر اوقات شما باید بین خانه های مختلف، فرق قائل شوید. این تمایز قائل شدن بین خانه ها که در اصطلاح برنامه نویسی، به هزینه دهی (Costing) معروف است، یکی از پیچیده ترین بخش های این الگوریتم است. مثلاً می توانید هزینه های ورود به خانه های مورب و مستقیم را نامساوی در نظر بگیرید.
7))همچنین شما می توانید با تهیه یک نقشه از محیط مورد نظر خود از دید بالا، نقاط قابل حرکت و نقاط غیرقابل حرکت را به الگوریتم ارائه کنید. به این منظور می توانید از فرمت فایل RAW (که در فوتوشاپ قابل ساخت است) استفاده کنید. این فرمت هیچ داده ای به عنوان سرباره (header) ندارد و شما می توانید با تهیه یک فایل سیاه و سفید از محیط مورد نظر خود (یعنی رندر صحنه به صورت Plan با رنگ های سیاه و سفید.مثلاً رنگ های سیاه مشخص کننده موانع و نقاط غیرقابل ورود، و مناطق سفید مناطق قابل حرکت باشد. حتی می توانید هزینه ورود به نقاط مختلف نقشه را با رنگ های خاصی مشخص کنید)، به راحتی داده های محدوده جستجوی مورد نظر خود را برنامه بدهید.
8))یکی از مهمترین بخش های این الگوریتم، فرآیند محاسبه نزدیکترین مسیر می باشد. به این منظور راهکارهای گوناگونی از جمله روش منهتن، روش نیوتن، روش فیثاغورث و نیز روش جستجوی عمقی (Heuristic) وجود دارد، ضمن اینکه در بسیاری از بازی ها، برنامه نویسان روش های اختصاصی را برای محیط های مورد نظر ایجاد کرده اند.
هدف از این مقاله، صرفاً معرفی اولیه الگوریتم قدرتمند و کارآمد بود. ضمن اینکه اگر شما بتوانید به خوبی مفهوم این الگوریتم را دریابید، می توانید از آن برای اهدافی به غیر از هوشمندسازی کاراکترها (همچنین فعالیت های پردازش تصویر) نیز استفاده کنید. این الگوریتم در مسائل نظری و از جمله حل مسائل ریاضی (محاسبه مساحت و حجم اشکال و اشیاء سه بعدی پیچیده) نیز کاربرد دارد. به طور کلی می توان گفت *A مفهومی می باشد که در بسیاری از شاخه های علوم گسترش یافته و با توجه به انعطاف بالا در پیاده سازی، هنوز نیز امکان بهره گیری بیشتر از آن وجود دارد.
منبع:ماهنامه دانش و کامپیوتر، شماره 85 /س