درخواست راهنمایی در مورد مساله Race Track
 

سلام به همه دوستان گرامی ، توی درس یادگیری ماشین یه پروژه گفته شده بنام Race Track

که مربوط میشه به بحث یادگیری تقویتی ، میخواستم ببینم دوستان میتونن در مورد الگوریتم

مساله راهنمایی کنند ؟

مساله از این قراره که یه ماشینی میخواد از یه خط شروعی به خط پایان برسه ، به ازای هر حرکت

درست امتیاز 1- میگیره و به ازای برخورد به دیوار امتیاز 5- میگیره ، حال ما میخوایم تعداد

امتیازهای منفی رو به حداقل برسونیم !

http://salarcpp.persiangig.com/3/race%20track.JPG

سلام دوست عزیز
این تصویر اصلا واضح نیست.
این دو قسمت جدا از هم آیا دو مسیر مختلف هستند یا با هم مرتبط هستند؟؟
و نوع حرکت ماشین به چه شکل می تواند باشد؟؟ بالا و راست فقط؟؟؟؟؟

ممون از دوست عزیز mardin200 ، که پاسخ دادن . دیگه داشتم واقعا ناامید میشدم .

بفرمائید اینم لینک عکس بصورت واضحتر :

http://salarcpp.persiangig.com/3/Race%20Track_2.png

دوست عزیز این مساله قراره بروش Mont Carlo حل بشه .

نوع حرکت فقط به بالا و راست مجاز است .

و آن دو مسیر جدا از هم هستند .

دوست عزیز خواهشا اگه تو این برنامه منو راهنمایی کنید ، یه عمر دعا گوی شما میشیم .

سریعا بهش نیاز دارم . با تشکر .

اینم توضیح مساله :

Racetrack (programming) Consider driving a race car around a turn like those shown in Figure 5.8. You want to go as fast as possible, but not so fast as to run off the track. In our simplified racetrack, the car is at one of a discrete set of grid positions, the cells in the diagram. The velocity is also discrete, a number of grid cells moved horizontally and vertically per time step. The actions are increments to the velocity components. Each may be changed by , , or in one step, for a total of nine actions. Both velocity components are restricted to be nonnegative and less than 5, and they cannot both be zero. Each episode begins in one of the randomly selected start states and ends when the car crosses the finish line. The rewards are for each step that stays on the track, and if the agent tries to drive off the track. Actually leaving the track is not allowed, but the position is always advanced by at least one cell along either the horizontal or vertical axes. With these restrictions and considering only right turns, such as shown in the figure, all episodes are guaranteed to terminate, yet the optimal policy is unlikely to be excluded. To make the task more challenging, we assume that on half of the time steps the position is displaced forward or to the right by one additional cell beyond that specified by the velocity. Apply the on-policy Monte Carlo control method to this task to compute the optimal policy from each starting state. Exhibit several trajectories following the optimal policy.

شما حتما باید از مونت کارلو استفاده کنید؟
آیا فکر نمی کنید تکنیک های reinforcement learning موثر تر باشند؟؟

حالا شما به هر روشی خواستین ، حل مساله رو مطرح کنید .

(فقط خیلی سریع ، چون 2 روز بیشتر وقت ندارم)

سلام
من روش مونت کارلو رو خیلی یادم نمیاد، ولی الان که توضیحات انگلیسی مسئله رو خوندم به نظرم میاد که با توضیحاتی که شما توی چند تا پستتون دادید خیلی فرق میکنه. بعنوان نمونه صورت مسئله کاملا واضح توضیح میده که هر حرکت از 2 بخش حرکت افقی و حرکت عمودی تشکیل شده و غیر از محدودیت تعداد خونه هایی که میشه به هر سمت حرکت کرد و محدودیت مجموع دو بخش حرکت، هیچ محدودیتی روی جهت حرکت وجود نداره. تنها یه محدودیت اضافه برای مشکل تر کردن مسئله اضافه شده و اونم این پیش فرض هست که در 50% مواقع ماشین یک خونه اضافه تر (از محدودیت ذکر شده در مسئله) به جلو یا راست حرکت میکنه. این یعنی اینکه مثلا اگر در یه زمان انتخاب حرکت بصورت 4 خانه به جلو و 2 خانه به چپ باشه، اگر این حرکت رو جزء اون 50% حساب کنیم میتونه یه خانه اضافه مثلا به جلو حرکت کنه، ولو اینکه با این اقدام تعداد خانه های حرکت به جلو به 5 میرسه که پیش فرض اولیه مسئله رو (که تعداد حرکت در هر جهت کمتر از 5 تا خانه هست) رو نقض میکنه. به نظرم خوبه صورت مسئله رو با دقت بیشتری بررسی کنید. با فهم دقیق مسئله ایشالا راه حل مناسبش رو هم میتونید پیدا کنید.

دوست عزیز ، مشکل همینجاست که اصلا صورت مساله خودش مبهمه ، حالا شما هیچ

روشی رو واسه حل مساله در نظر ندارید ؟

راستش صورت مسئله خیلی هم مبهم نیست. در واقع تنها نکته مبهم صورت مسئله برای من اینه که اگر ماشین در حرکتی بخواد از grid خارج بشه - که حرکت قابل قبولی نیست - دقیقا چه حرکتی بجاش انجام میشه، که اینم با توجه صورت مسئله اینطور میشه برداشت کرد که دقیقا یک حرکت یک خانه ای به یکی از 4 جهت (در صورت قابل قبول بودن) انجام میشه (البته مسئله میگه حداقل یک خانه که برای من مبهمه).
به هر حال یه راه حل برای این مسئله میتونه reinforcement learning باشه. به این صورت که برای هر کدوم از نقاط شروع مختلف، برنامه حرکت رو چندین مرتبه (100 بار، 1000 بار، 10000 بار) اجرا کنید. در هر بار اجرای برنامه، در هر مرحله بصورت random و با در نظر گرفتن تمام محدودیت های گفته شده حرکت بعدی انتخاب میشه. اگر حرکت انتخاب شده حرکت قابل قبولی باشه، اون حرکت رو بهمراه خانه ای (cell) که ماشین در اون لحظه در اون قرار داره ذخیره میکنید. هر کدوم از این رکورد ها یک example محسوب میشه. با اجرای برنامه به دفعات زیاد برای هر خونه چندین example تولید میشه. در نهایت چند راه برای جمع بندی این example ها دارید. ساده ترین اونها اینه که برای هر خانه اون حرکتی رو که بیشتر از همه تولید و استفاده شده، انتخاب کنید.
به این روش learning from positive examples میگن که در اون agent از حرکتهای صحیح و قابل قبول قبلی برای یادگیری استفاده میکنه. البته reinforcement learning بخش استفاده از negative examples هم داره که در راه حلهای کاملتر میشه اون رو هم اضافه کرد و برای افزایش optimality بکار برد.