بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
کنترل هوشمند شبکه ترافيک بر مبناي عامل به کمک تئوري بازي ها
خلاصه
امروزه با روند رو به رشد افزايش خودروها در شبکه هاي حمل و نقل شهري، روش هاي کلاسيک در کنترل ترافيک شهري قابل استفاده نبوده و نياز به روش هاي هوشمند افزايش مييابد. سيتم هاي چند عامله ابزار مناسبي جهت مدل سازي سيستم هاي توزيع شده به شمار ميروند که ترافيک شهري را نيز ميتوان به کمک آن مدل کرد. نظريه بازيها يک ابزار رياضي است که به بررسي نحوه ي تصميم گيري و رفتار عامل ها در سيستم هاي چند عامله در محيط ميپردازد که نتيجه به دست آمده توسط هر عامل علاوه بر تصميمات خود عامل ،به رفتار و اعمال ساير عامل ها نيز بستگي دارد.يادگيري از تجربيات گذشته نيز ميتواند تصميم گيري بهتري را منتج شود. روش يادگيري Q اين امکان را براي عامل ها فراهم ميآورد که بتوانند با استفاده از تجربيات خود خط مشي مناسب را ياد بگيرند.در اين مقاله روش ترکيبي براي کنترل ترافيک شهري با مدل سيستم هاي چندعامله بر اساس نظريه بازيها و مبتني بر يادگيري Q فازي ارائه شده است .در اين روش عامل با توجه به يادگيري Q فازي و تعامل با عامل هاي ديگر از طريق نظريه بازيها اقدام به يافتن بهترين زمانبندي چراغ راهنمايي ميکند. شبيه سازي روش ارائه شده با هدف کاهش ميزان تأخير در زمان سفر، موفقيت آن را نشان ميدهد.
کلمات کليدي:کنترل ترافيک ،نظريه بازيها، فازي، يادگيري Q فازي
١. مقدمه
گسترش شهر نشيني، افزايش استفاده از خودروهاي شخصي براي عبور و مرور و کمبود زير ساخت هاي حمل و نقل شهري باعث شده زمان سفرهاي شهري، طول صف خودروهاي منتظر حرکت و مصرف سوخت افزايش يابد، هوا آلوده تر شود و زندگي شهري با کاهش هواي پاک، آلودگي صوتي و اتلاف وقت همراه شود. امروزه مسئله ي زمان سفر در شبکه معابر شهري به دليل افزايش تراکم ترافيک ،يکي از مهمترين مسائل کلان شهرها ميباشد.
بخش قابل توجهي از زمان سفر در شبکه ي حمل ونقل شهرهاي بزرگ مربوط به زمان تأخير در تقاطع هاست . در سال هاي اخير استفاده از روش هاي مختلف هوش مصنوعي در حوزه سيستم حمل ونقل هوشمند به طورگسترده مورد توجه قرار گرفته است . از اين رو کنترل هوشمند تقاطع ها به منظور کاهش تأخير از اهميت فوقالعاده اي برخوردار است .
سيستم هاي چندعامله يکي از روش هايي است که ميتوان در مدل سازي ترافيک شهري به کار گرفت . يک سيستم چندعامله ، در برگيرنده جامعه اي از عامل هاي هوشمند و خود مختاراست که در يک محيط درکنار يکديگر درحال کار بوده و سعي در انجام کاري خاص و رسيدن به هدفي مشخص دارند[١]. سيستم هاي چند عامله براي مدل سازي ، تحليل و طراحي سيستم هايي که کنترل بين تصميم گيرنده هاي خود مختار بصورت توزيع شده است مناسب هستند. امروزه در بسياري از کاربردها و در زمينه هاي مختلف صنعتي، نظامي، مخابراتي، اطلاعاتي، از سيستم هاي پيچيده و توزيع شده چندعامله استفاده فراواني ميشود[٣ ,٢]. براي حل بسياري از مسائل مهم دنياي واقعي مانند برخي از کاربردهاي رباتيک ، مسيريابي در شبکه ، زمان بندي
،تصميم گيري اقتصادي نيازمند برنامه ريزي در حالت غيرقطعي هستيم . در زمينه حمل ونقل هوشمند مبتني بر سيستم هاي چند عامله تحقيقات گسترده اي صورت گرفته است [٤]. در[٥]با هدف کاهش مدت انتظار وسايل نقليه پشت چراغ قرمز، با در نظر گرفتن چراغ هاي راهنمايي به عنوان يک عامل و آموزش عامل ها بر اساس يادگيري Q سعيدر کاهش ترافيک شهري داشته است . اين روش عامل ها را طبق الگوريتم Q آموزش داده و با توجه به نرخ
١
يادگيري ،نتايج مختلف به دست آمده را بررسي کرده است . نتايج وي کاهش تأخير در تقاطع ها را نشان ميدهد.براي کاهش تأخير در تقاطع ها، در مقاله ي [٦] از ترکيب روش هاي يادگيري Q و فازي استفاده کردند. در اين روش موتور استنتاج فازي به کمک الگوريتم Q آمده و سعي در کاهش خطاهاي سيستمي در الگوريتم Q دارد. در چارچوب قوانين فازي آموزش سريع تر انجام گرفته و تأخير تقاطع ها به طور قابل توجهي کاهش يافته است .
در [٧] روش ترکيبي تئوري بازيها براي حل مشکل هماهنگي بين دو عامل بر اساس عامل کنترل سيگنال ترافيک با يادگيري Q ارائه شده است . مشابه با اين مقاله ، هماهنگي عامل ها در کنترل چراغ راهنمايي در [٨] با استفاده از تئوري بازيهاي تکاملي و اجازه همکاري به عامل ها ارائه شده است .يادگيري تقويتي تطبيقي در مقالات [٩] و [١٠] جهت کنترل محيط مستقل از مدل ارائه شده است . کنترل تطبيقي در [١١] نيز معرفي شده است که از تقريب تابع به عنوان نگاشتي از حالات و زمان بندي استفاده مي نمايد.
در اين مقاله سعي شده است تا با بکارگيري مزاياي هر يک از تئوريهاي بيان شده ، روشي ترکيبي جهت کنترل چراغ هاي راهنمايي مبتني بر يک سيستم چند عامله ارائه شود.در اين روش عامل با توجه به يادگيري Q فازي و تعامل با عامل هاي ديگر از طريق نظريه بازي ها سعي در يافتن خط مشي بهينه جهت کنترل ترافيک با استفاده از زمانبندي چراغ هاي راهنمايي در تقاطع ها دارد. بدين منظورابتدا شبکه ترافيکي توسط عامل هاي يادگيرنده مدل سازي ميشود.سپس حجم ورودي خودروها در وروديهاي مختلف تقاطع فازيسازي شده و در سيستم استنتاج فازي براي تخمين فاز مورد استفاده قرار ميگيرند و متناسب با آن سيستم پاداشي را از محيط دريافت ميکند. عامل هدف در تعامل با عامل هاي همجوار و پاداش دريافتي خود از محيط اقدام به بروز رساني الگوريتم يادگيري خود ميکند.شبيه سازي روش ارائه شده کاهش زمان تأخير سفر را نشان ميدهد.
در بخش دوم روش يادگيري Q و نسخه ي فازي آن بيان شده و بخش سوم به نظريه ي بازيها اختصاص داده شده است . مسئله ي کنترل
هوشمند ترافيک و روش پيشنهادي در بخش چهارم بيان شده است و در بخش پنجم شبيه سازي روش پيشنهادي و نتايج بدست آمده آورده شده است .
٢. يادگيري Qو Q فازي
يادگيري تقويتي چندعامله به سرعت درحال توسعه بوده و روش هاي متنوع و مختلفي را درحوزه هاي رقابتي ، همکارانه و ترکيبي دربر مي گيرد بطوري که ارتباطي بين حوزه هاي مختلف علوم نظير تئوري بازي ها، بهينه سازي و يادگيري در بازي ها را برقرار ساخته است .در يادگيري تقويتي،سيستم تلاش ميکند تا ارتباط خود با محيط پويا را از طريق سعي و خطا بهينه نمايد. يادگيري تقويتي راهي براي يادگيري به کمک تعامل با محيط بدون داشتن ناظر ميباشد. يادگيري تقويتي در واقع چگونگي نگاشت موقعيت هاي مختلف به اعمال براي دريافت بهترين نتيجه يا بيشترين پاداش ميباشد.در بسياري موارد اعمال نه تنها روي پاداش همان مرحله بلکه مراحل بعد هم تاثير ميگذارد.روش يادگيري Q، يک روش مستقل از مدل است که در آن عامل هيچ نوع دسترسي به مدل انتقال ندارد[١٢].اين روش يکي از بهترين و پرکاربردترين روش هاي يادگيري در حل مسائل يادگيري ميباشد.
دراين روش ، عامل ارزش انتخاب عمل a در حالت s که با نشان داده ميشود را با استفاده از تعامل پيوسته با محيط و با سعي و خطا تخمين ميزند. عامل با مقادير تصادفي از تخمين ها شروع کرده و بعد از هر عمل يک چندتايي به صورت دريافت ميکند که در آن s حالت فعلي،a عمل انجام شده در حالتr,s پاداش فعلي و حالت بعدي از اجراي a ميباشد.عامل براي هرچندتايي ميتواند ارزش حالت -عمل
مربوطه را به صورت زير محاسبه کند :
که در آن نرخ يادگيري عامل است و مشخص ميکند که تا چه حدي اطلاعات جديد بدست آمده جايگزين اطلاعات قديمي شوند. مقدار ١ براي اين نرخ سبب ميشودکه عامل فقط جديدترين اطلاعات را در نظر بگيرد و مقدار صفر باعث ميشود عامل يادگيري نداشته باشد.
فاکتور کاهش ناميده ميشود و براي مشخص کردن پاداش هاي آينده به کار ميرود. مقدار صفر براي اين فاکتور، عامل را فرصت طلب ميکند،يعني عامل فقط پاداش فعلي را در نظر ميگيرد و از سوي ديگر نزديکي به ١ سبب ميشود که عامل براي يک پاداش بالا در طولاني مدت منتظر بماند. اگر تمامي زوج هاي حالت -عمل به صورت مکرر تجربه شوند و نرخ يادگيري در طول زمان کاهش يابد،يادگيري Q با احتمال ١ به مقدار بهينه ي همگرا ميشود.
در حالت کلي يادگيري تقويتي به طور موثر براي حل مسائل با تعدادي از وضعيت ها و عمل هاي گسسته با ابعاد کوچک استفاده ميشود و هنگامي که ابعاد وضعيت ها و عمل هاي گسسته بزرگ ميشود، اندازه جدول جست وجو به حدي بزرگ ميشود که از نظر زمان محاسباتي الگوريتم بسيار کند ميگردد. از طرفي هنگاميکه وضعيت ها يا عامل ها به صورت پيوسته مطرح ميگردند، استفاده از جدول جست وجو امکان پذير نميباشد.
براي حل اين مشکل از روش يادگيري Q فازي استفاده مي شود. اگر عامل هوشمند داراي مجموعه فازي مناسب به عنوان دانش خبره براي حوزه مسئله
مورد نظر باشد، ابهامات قابل برطرف شدن است .بنابراين عامل هوشمند ميتواند اهداف مبهم را بفهمد و محيط نامعلوم را درک کند.در ساختار يادگيري
Q فازي نيازي به ذخيره سازي مقادير نتيجه گيري شده در جدول نيست و در عمل با حذف جدول مقادير Q، امکان فعاليت در فضاهاي بزرگ را فراهم ميسازد. در اين روش همه چيز بر اساس مقادير کيفيت و استنتاج فازي است . سيستم استنتاج فازي با ورودي سروکار دارد و الگوريتم يادگيري Qاز قسمت پيرو قانون هاي فعال آن به عنوان حالت هاي خود استفاده ميکند. سيگنال پاداش الگوريتم Q با توجه به منطق فازي، سيگنال پاداش محيط و تخمين عملکرد واکنش فعلي ساخته ميشود و سعي در انتخاب واکنشي دارد که اين سيگنال را بيشينه ميکند[١٣].
سيستم يادگيري ميتواند يک عمل را از ميان j عمل براي هر قانون انتخاب کند. jامين عمل ممکن در قانون iام را به صورت نشان ميدهند و ارزش آن نيز به صورت نشان داده ميشود. قوانين زير را در نظر بگيريد:
عمل يادگيري بايد بهترين نتيجه را براي هر قانون پيدا کند. اگر عامل عملي را انتخاب کند که مقدار ارزش بالايي را موجب شود، در واقع ميتواند سياست بهينه را ياد بگيرد. بنابراين سيستم استنتاج فازي ميتواند اقدام لازم براي هر قانون را بدست آورد[١٣].
٣. نظريه بازيها
ارتباط بين محيط هاي عامل گرا وتئوري بازيها از اين اصل نشات ميگيرد که هر حالت از محيط هاي عامل گرا را ميتوان به يک بازي تشبيه کرد که تابع سودمندي بازيکنان منحصر به حالت جاري محيط ميشود و هدف بازيکنان در چنين محيطي حرکت به سوي نقطه تعادل و بهينگي است . تعادل نش پرکاربردترين مفهوم راه حل در نظريه بازيها ميباشد. اين مفهوم يک تعبير فضاي حالت گونه از يک بازي راهبردي است که در آن هر عامل پيشبيني
درستي از رفتار ساير عامل ها دارد و بر پايه اين پيشبيني عقلاني عمل مينمايد. راهبرد تعادل نش به شرح زير است :
که عملي است که عامل i ام از مجموعه اقدامات بهينه انتخاب ميکند، برداري است که از مجموعه اقدامات عامل ها به جز عامل i ام تشکيل ି شده ، عملي است که عامل i ام به غير از انتخاب ميکند و تابع سود عامل i ام ناميده ميشود[٨]. در رابطه (٣) هيچ عاملي نميتواند با توجه به اقدامات ديگر عامل ها،حرکتي سودآور بر خلاف آنها انجام دهد.
٤.کنترل هوشمند ترافيک
هـدف عامل هـايي کـه در محيط هاي پويا عمل مي کنند، اين است که تصميم هاي بهينه بگيرند. اگر عامل ها از پاداش هاي متناظر با اعمال مختلف مشترکي که در محيط انجام مي دهند آگاه نباشند، انتخاب عمل مشکل مي شود. يادگيري بـا تنظـيم انتخـاب عمـل عامل هـا براسـاس اطلاعات جمع آوري شده درطي زمان چنين مقصودي را برآورده مي سازد. در يادگيري تقويتي ، عامل نيازي بـه مـدل سـازي صريح محيط ندارد، زيرا اعمالش مي توانند به طور مستقيم براساس پاداش هاي دريافتي از محيط پايه گذاري شوند.عامل در سيستم چندعاملـه ممکـن اسـت بـه علت توزيع شدگي اطلاعات ، آگاهي اندکي از سايرين داشته باشد. حتـي اگـر عامـل اطلاعـات از قبـل دانسـته شـده اي دربـاره ي عامل هاي ديگر داشته باشد، به خاطر اين که عامل هاي ديگر نيز در حال يادگيري هسـتند، محـيط غيرايسـتا مـي باشـد و رفتـار عامل هاي ديگر ممکن است در طي زمان تغييرکند. بايد توجه داشت که در سيستم هاي چندعامله مسئله يادگيري پيچيدگي بيشتري دارد و هر عامل براي تصميم گيري بايد اعمال ساير عامل ها و چگونگي تأثير آن ها را نيز در نظر داشته باشد تا به هدف خود برسد. عدم امکان پيشبيني عامل هاي ديگر باعث عدم قطعيت در فرآيند حل مسئله ميشود.در اين مقاله براي همکاري و تعامل بين عامل ها از نظريه بازي ها استفاده مي کنيم وارزش را به عنوان تابع سود در مدل رياضي عامل کنترل سيگنال ترافيک در نظر ميگيريم .
