بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
پياده سازي کنترل نظارتي نامتمرکز کراندار در يک پتري نت
چکيده
مقاله حاضر روشي نو جهت برقراري کنترل نظارتي نامتمرکز در يک پتري نت را ارائه مي نمايد. روش غالب و معمول اعمال کنترل نظارتي نامتمرکز در سيستم هاي رخداد گسسته استفاده از برنامه ريزي خطي اعداد صحيح مي باشد. لازم به ذکر است که اين روش کراندار بودن نت کنترل شده را مد نظر قرار نمي دهد به طوري که اين مسئله مي تواند در برخي موارد سبب ناپايداري و يا عملکرد نادرست نت هاي تحت بررسي گردد. اين مقاله روشي را ارائه مي نمايد که نه تنها برنامه ريزي خطي اعداد صحيح را حذف مي کند بلکه کراندار بودن کليه مکانها را پس از اعمال اين روش تضمين مي نمايد. در راستاي نيل به اين هدف، روشي جديد براي افزايش تعداد p-invariantها در يک پترينت معرفي شده است که چگونگي اين افزايش با ارائه يک قضيه و دو لم بيان مي شود. سودمندي قضيه و دو لم اخير در الگوريتم ارائه شده به نام "الگوريتم تبديل قيد" کاملاً آشکار مي گردد. همچنين الگوريتمي براي تقسيم نت بر اساس دسته انتقال هاي داده شده ارائه مي گردد تا حوزه عملکرد محلي را افزايش دهد. سرانجام الگوريتمي با نام "الگوريتم کنترل نظارتي نامتمرکز" ارائه مي گردد که با بهره جويي از قضيه ، لم ها و "الگوريتم تبديل قيد"
کنترل نظارتي نامتمرکز کراندار را پياده مي نمايد.
کليد واژه - پترينت - کراندار- کنترل نظارتي نامتمرکز- p-invariant
١- مقدمه
کنترل نظارتي سيستم هاي رخداد گسسته توسط رامج و وانهام معرفي شد [١]. اکثر قضايا و نتايج آنها براي سيستم هاي مدل شده توسط آتومتا در [٢] و [٣] بيان شده است ، در حاليکه استفاده از پتري نت براي کنترل نظارتي سيستم هاي رخداد گسسته با استفاده از پتري نت معرفي شده در [٤] پس از ارائه مقاله [٥] آغاز گرديد. نتايج اين مقاله با ارائه روشي موسوم به کنترل فيدبک پتري نت بر اساس p-invariant در [٦ تعميم داده شد. کنترل نظارتي اعمال شده توسط اين روش با فرض کنترل پذير بودن و رويت پذير بودن تمامي انتقال ها صورت م گيرد در حاليکه [٧] راهکاري براي غلبه بر وجود چنين پيش فرضها ارائه مي دهد. روشهاي ارائه شده [٦] و [٧] توسط [٨]، [٩ و سرانجام [١٠ تکميل مي گردند. روشهاي کنترل نظارتي متمرکز ارائه شده در [١٠]-[٦] بر اساس مفهومي به نام p-invariant پايه گذاري شده اند. از جمله مقالات ديگري که م توان در زمينه کنترل نظارتي متمرکز سيستم هاي رخداد گسسته نام برد مقاله [١١] مي باشد. عليرغم فعاليت هاي بسزايي که در زمينه کنترل نظارتي متمرکز سيستم هاي رخداد گسسته توسط پترينت صورت گرفته است تعداد مقالات منتشر شده در زمينه کنترل نظارتي نامتمرکز بسيار اندک بوده که از جمله آنها مي توان به [١٢]، [١٣] و [١٤] اشاره نمود. مقاله [١٢] عليرغم استفاده از برنامه ريزي خطي اعداد صحيح که روشي معمول در کنترل نظارتي نامتمرکز سيستم هاي رخداد گسسته مدل شده توسط پتري نت مي باشد، به مسئله کرانداري پس از اعمال کنترل نظارتي توجهي ننموده و به همين منظور روشي قابل اتکاء به شمار نخواهد آمد. همچنين مقاله [١٣] پيش شرطهاي بسياري از جمله کنترلپذير بودن و رويت پذير بودن تمامي انتقالها بيان مي دارد که عملاً در بررسي مسائل جامع تر کارآمد نخواهد بود.
سر انجام مقاله [١٤] روشي را با استفاده از تقسيم نت ارائه مي دهد که اين روش تنها قابل اعمال به نت هايي با خواص مشخص مي باشد.
در اين مقاله روشي جديد براي ايجاد p-invariant ارائه مي دهيم که به کمک الگوريتم هاي ارائه شده ، کنترل نظارتي نامتمرکز کراندار را بر يک شبکه پتري نت اعمال مي نمايد. بدين منظور در بخش ٢ ابتدا مرور مختصري بر پتري نت انجام مي دهيم و در بخش سوم به طور مختصر تفاوت ميان کنترل نظارتي متمرکز و نامتمرکز را توضيح داده و سپس در بخش چهارم نتايج ارائه مي گردند.
٢- نمايش تصويري
پتري نت به سبب برخورداري از اجزايي که نمايش تصويري اين مدلساز قدرتمند سيستم هاي رخداد گسسته را فراهم مي آورند، ابزاري مناسب براي مطالعه چنين سيستم هايي مي باشد. يک ساختار پتري نت چهارگانه اي به صورت (F,W ,P,T N
است که P مجموعه مکانها، T مجموعه انتقالها، (PT T P ⊇F مجموعه يالهاي انتقال و W تابع وزني است که با دريافت آرگومانهايي از دو مجموعه P وT عدد طبيعي مثبتي را به آنها نگاشت مي نمايد. تابع وزني را مي توان به صورت رياضي به شکل {٠} \N→F :W تعريف نمود. ودرسينلمه يمش يله تهاصيويرکيو،چ مکک،انياهلهباه يواسنتيقلاه لدباوايپرکتاونخهااليي ي ، انجتهقات لدهاار باه مکان به انتقال و يا از انتقال به مکان و وزنها به صورت اعدادي بر روي يالهاي انتقال نمايش داده مي شوند. لازم به ذکر است زماني که وزن يال انتقال برابر واحد است ، از نمايش آن خودداري مي نماييم .
علاوه بر بيان پتري نت با استفاده از ساختار چهارگانه ، بيان پتري نت با استفاده از ماتريس ورودي + D و ماتريس خروجي − D به صورت (−D ,D ,P,T N در بررسي خواص پتري نت بسيار کارآمد خواهد بود، در حقيقت اين نحوه نمايش معادل ساختار چهارگانه (F,W ,P,T N مي باشد. براي روشن شدن مطلب ، پتري نت با ساختار(F,W ,P,T N که دارايm مکان به صورت { L,pm, p2 ,p1P وn انتقال به صورت L,tn, t t2T را در نظر بگيريد. ماتريس تلاقي که به صورت − D−D D تعريف مي گردد، ماتريسي nm بوده که در آن +dij و−dij عناصر+D و−D بدين شکل تعريف مي شوند:
+dij برابر( pi ,t j w خواهد بود اگر( pi ,tj ) عضوF باشد، در غير اينصورت برابر صفر خواهد بود. به عبارت ساده تر dij وزن يال انتقال ورودي از انتقال j ام به مکان iام مي باشد. به طور مشابه −dij برابر( tj,pi w خواهد بود اگر( tj,pi ) عضوF باشد، در غير اينصورت برابر صفر خواهد بود. به بيان سادهتر −dij وزن يال انتقال خروجي از مکان iام به انتقال jام مي باشد.
٢-١- مارکينگ
مارکينگ که با نمايش داده مي شود، نگاشتي از مکان ها به مجموعه اعداد صحيح غير منفي به صورت مي باشد.
به عبارت ديگر مارکينگ به هر مکان در پتري نت ، عددي صحيح و غير منفي تخصيص مي دهد. مارکينگ در نمايش تصويري به صورت دوايري توپر نمايش داده مي شود.
٢-٢- توانمند سازي انتقال و قانون شليک
مارکينگ (مارکينگ مکان ورودي به ti) انتقال ti را توانمند مي سازد اگر مارکينگ بزرگتر يا مساوي وزن يال انتقال ورودي به ti باشد، به عبارت ديگر چنانچه باشد، انتقال ti توانمند خواهد شد.
زماني که مارکينگ μ انتقال ti را توانمند مي سازد اين انتقال مي تواند شليک گردد. ti پس از شليک، مارکينگ ساير مکان ها را تغيير مي دهد، اين تغيير بر اساس قانون شليک به صورت زير خواهد بود:
موقعيت هاي (٤)-(١) به ترتيب مربوط به حالاتي هستند که (١): مکان p داراي هيچ انتقال ورودي يا خروجي نباشد، (٢): انتقال
ti فقط ورودي به p باشد، (٣): ti فقط خروجي از p باشد، (٤): ti هم ورودي و هم خروجي p باشد.
٢-٣- معادله ديناميک پتري نت
ماتريس تلاقي مي تواند براي توصيفي جبري از تغيير مارکينگ يک پتري نت مورد استفاده قرار گيرد:
در اين معادله بردار شليک ناميده مي شود و تمامي عناصر آن به جز برابر صفر مي باشد، iنشان دهنده انديس انتقالي است که توانمند گشته و مي بايست شليک گردد. توجه داشته باشيد که ti توامند است اگر و تنها اگر:
معادله (١) به عنوان معادله حالت پتري نت شناخته مي شود و مارکينگ (متغير حالت ) را به بردار شليک (ورودي کنترل) ارتباط مي دهد. علاوه بر اين ، با انجام محاسبات مي توان اين معادله را بر حسب شرايط اوليه و مجموع بردارهاي شليک در مراحل مختلف که با نمايش داده مي شود به صورت زير نوشت :
در اين صورت مارکينگ هر لحظه با در دست داشتن شرايط اوليه و مجموع بردارهاي شليک تا آن لحظه قابل حصول مي باشد.
٢-٤- بردار شمارنده شليک و بردار پاريخ
با مشخص بودن تعداد تکرار شليک هر انتقال مي توان برداري ساخت که بردار شمارنده شليک نام دارد. مفهوم ديگري که مرتبط با بردار شمارنده شليک است بردار پاريخ بوده و با v نمايش داده مي شود، مي توان با کمک آن معادله (٣) را به صورت زير نوشت
٢-٥- انتقال هاي کنترل پذير و رويت پذير
در پترينت يک انتقال کنترل ناپذير است چنانچه ناظر اجازه منع مستقيم اين انتقال را از شليک نداشته باشد، در غير اين صورت کنترل پذير است . همچنين يک انتقال رويت ناپذير است چنانچه ناظر اجازه رويت مستقيم شليک اين انتقال را نداشته باشد، در غير اينصورت اين انتقال رويت پذير است .
P-invariant -6-2
p-invariant مجموعه اي از مکانهاي يک نت مي باشد که جمع وزن داده شده مارکينگ اين مکانها ثابت باشد. از نظر رياضي يک p-invariant يک بردار (١× n) غير منفي x است ، به طوري که :
در معادله بالا بردار مارکينگ اوليه و بردار مارکينگ مکانها در هر لحظه زماني مي باشد. همچنين n تعداد مکانهاي پتري نت داده شده بوده و تعبير فيزيکي معادله (٤) بدين قرار است :
مجموع نشانه هاي وزن داده شده مکانهاي متناظر با عناصر غير صفر در بردارx همواره مقدار ثابتي مي باشد و با مارکينگ اوليه تعيين مي شود.
سوالي که در اينجا مطرح مي شود اين است که در چه صورت -pinvariant وجود دارد و در صورت وجود نداشتن چگونه ايجاد مي گردد. براي روشن شدن اين موضوع از معادله (٣) استفاده مي نماييم . با ضرب در معادله ي (٣) داريم :
حال با توجه به معادلات (٤) و (٥) مي توان گفت در صورت وجود p-invariant رابطه زير برقرار است :
و چون مي باشد، داريم :
در صورتي که D داراي رتبه ي کامل باشد معادله بالا فقط حل جزيي ٠ = x را خواهد داشت که فاقد ارزش مي باشد، به عبارت ديگر هيچ p-invariant اي وجود نخواهد داشت . از طرفي هنگامي که D داراي نقص رتبه مي باشد پتري نت مزبور به تعداد نقص رتبه D، داراي p-invariant است . از اين نکته به عنوان راهکاري در بخش نتايج استفاده خواهيم نمود و روشي جديد براي ايجاد p-invariant ارائه مي نماييم .
٢-٧- قيدها در پترينت
قيدها در پترينت توسط نامساويهايي شامل ترکيب خطي مارکينگ مکانها، بردار شليک و بردار پاريخ مي باشند [١٥]. اين قيدها به صورت زير مي باشند:
در اين قيد مجموعه اعداد صحيح ، m تعداد مکان ها وn تعداد قيدها مي باشد. اين گونه قيدها، محدوديت بر تعداد نشانه هاي مکانهايي خاص را بيان مي نمايند. قيدهايي به فرم (٨) به صورت زير تعميم داده شده اند:
در اين نامعادله مجموعه اعداد صحيح مثبت و n تعداد انتقالها مي باشد. حالت تعميم يافته قيدهاي (٩) به
گونه اي است که بردار پاريخ را نيز در بر مي گيرد:
در اين قيد مي باشد. در (١٠) vi عنصرi ام بردار پاريخ ، بردار شمارنده تعداد شليکهاي انتقالها از شرايط اوليه ، مي باشد.
٣- کنترل نظارتي
تفاوت کنترل نظارتي متمرکز و نامتمرکز در چگونگي رويت و کنترل انتقال هاست . در کنترل نظارتي متمرکز ناظري وجود دارد که بر اساس محدوديت هاي مهندسي مسئله ، قادر به کنترل و رويت تعداد خاصي از انتقالها است و بنابراين تمامي قيدهايي که اين ناظر بايد برقرار سازد، توسط کنترل و رويت همين انتقال صورت مي پذيرد. از اين رو، هنگامي که در کنترل نظارتي متمرکز از کنترل پذير يا رويت پذير بودن انتقالها صحبت به عمل مي آيد اشاره به کل انتقال هاي کنترلپذير و رويت پذير در نت مي شود. بر خلاف کنترل نظارتي متمرکز چهارچوب مسئله در کنترل نظارتي نامتمرکز به صورت ناظرهايي تعريف مي شود که هر ناظر توانايي دسترسي به تعدادي از انتقالهاي کنترلپذير و رويت پذير نت را دارد. همين تفاوت سبب به وجود آمدن دو گونه کنترل نظارتي متفاوت شده است . تعريف زير چگونگي افراز اين انتقالها را در چهارچوب کنترل نظارتي نامتمرکز بيان مي کند.
تعريف : مجموعه انتقا هاي در دسترس براي هر ناظر نامتمرکز در پتري نت دسته انتقال ناميده مي شود.
٣-١- قيدهاي قابل قبول
چنانچه براي پياده سازي قيدهاي موجود در مسئله کنترل نظارتي متمرکز و يا نامتمرکز نياز به دسترسي به انتقال هاي کنترل ناپذير و يا رويت ناپذير داشته باشيم ، قيد مزبور قيدي غير قابل قبول خواهد بود [١٦]. اين قيدها در مقالات مختلف به صورت غير قابل قبول متمرکز (c-admissible) يا غير قابل قبول نامتمرکز (d-admissible) شناخته مي شوند.
٤- نتايج
٤-١- ايجاد p-invariant
در اين بخش قضيه اي به همراه دو لم ارائه مي گردد که چگونگي ايجاد p-invarint را در حالات مختلف مورد بررسي قرار مي دهد.
به دليل طولاني بودن اثباتها از بيان آنها خودداري مي نماييم .
اثبات قضايا و لم ها در [١٦] موجود مي باشد. قضيه ١: براي يک پترينت داده شده يک مکان اختياري pi همراه با انتقالهاي ورودي و خروجي اش را در نظر گرفته و مجموعه ي p و انتقالهاي در نظر گرفته شده را Net بناميد.
(شکل ٢ را ملاحظه بفرماييد). فرض کنيد انتقال هاي ورودي و خروجي pi به ترتيب کنترل پذير و رويت پذير باشند. با اضافه
pe به Nets طبق الگوريتم زير يک -p کردن يک place خارجي invariant ايجاد مي شود.
١- انتقال (هاي) خروجي pi را به عنوان انتقال (هاي) ورودي pe در نظر بگيريد.
٢- انتقال (هاي) ورودي pi را به عنوان انتقال (هاي) خروجي pe در نظر بگيريد.
٣- وزن (هاي) يال(هاي) انتقال ورودي pe را متناظر با وزن (هاي) يال(هاي) انتقال خروجي pi در نظر بگيريد. pe را متناظر با وزن (هاي) يال(هاي) انتقال خروجي وزن (هاي) يال(هاي) انتقال ورودي pi در نظر بگيريد.
بنابراين معادله حاکم بر اين بردار p-invariant بر اساس معادله (٤) به صورت زير خواهد بود:
نتيجه ١: به سادگي مي توان ديد که اگر a برابر وزن يالهاي انتقال خروجي pi را به عنوان وزن يال هاي انتقال ورودي pe و نيز a برابر وزن يالهاي انتقال ورودي p را به عنوان وزن يال هاي انتقال خروجي pe انتخاب کنيم بردار p-invariant حاصل به صورت زير خواهد بود:
