تعريف مسأله
هواپيمـا به هدف (Assigning Vehicles to Targets) ، با در نظر گرفتن قيود مختلفي كه در مسأله وجود دارد، يك مسألهي بهينهسازي است كه به روشهاي مختلفي قابل انجام است. از جملهي اين روشها ميتوان به روش الگوريتم ژنتيك و تئوري كنترل بهينه (برنامهريزي ديناميكي) اشاره كرد.
از اين روشها، خصوصـاً روش كنترل بهينه، اگر چه تا حد زيـادي تضمينكنندهي رسيدن به حل بهينهي مسألهي مورد نظر است، اما حل مسأله از اين طريق، خصوصـاً با افزايش ابعاد مسأله، زمان زيادي را ميطلبد. از طرفي به دليل اينكه8 توسعهي اين سيستم در آينده براي استفـادههاي زمان واقعي (Real Time) و در محيطهاي ديناميك، مورد نظر ميباشد، كاهش زمان حل تا حد ممكن، مطلوب ميباشد.
حل اين مسأله، بـا استفـاده از الگوريتمهاي ابتكاري (كه از فرضيـات سادهكننده و تقريب استفـاده ميكند) صورت ميگيرد. اين روشها گر چه در حالت كلّي از بهينگي نتايج ميكاهند، امّـا در بسياري از مواقع به دليل ناپيوسته بودن مسأله، اين نتايج با نتايج حل بهينه يكي هستند. تعريف مسأله، در حالت كلّي به صورت زير است (شكل1):
N وسيلهي پرنده به Mهدف، در شرايطي كه در منطقهي عمليات، تعداد P منطقهي تهـديـدزا وجـود داشته باشد. اين اختصـاص بـا در نظر گرفتن چهـار قيد زير صورت ميگيرد:
- كردن مسافتي كه هر وسيله بايد طي كند (قيد مسير كوتاه - Short Path)؛
- كردن حداقل فاصلهي مسير بين پرنده و هدف تـا مناطق تهديد (قيد اجتناب از تهديد- Avoid Threats)؛
- كردن تعداد پرندههايي كه به هر هدف اختصاص داده ميشود (قيد فشار بيشينه - Max Force)؛
- كردن تعداد اهدافي كه مورد حمله قرار ميگيرند (قيد گسترش بيشينه - Max Spread)؛
شكل 1 - نماي كلي مسألهي اختصاص پرندهها به اهداف
بين معيارهاي ارائه شده، دو معيار نخست، "معيارهاي فردي" در انتخاب هدف هستند. به عبارت ديگر نزديك بودن هدف و كمخطر بودن مسير نكاتي هستند كه براي هر كدام از هواپيماها، صرف نظر از وضعيت ساير اعضاي گروه، مطرح هستند. اما معيارهاي 3 و 4، "معيارهاي گروهي" در انتخاب هدف هستند و براي ارضاي اين معيارها بايد وضعيت تمام اعضاي تيم را به صورت همزمان بررسي كرد. همچنين لازم به ذكر است كه معيارهـاي 3 و 4 با يكديگر در تعارض هستند. امّـا در فرايند حل، الگوريتمي اتخـاذ ميشود كه شرايط بهينهاي براي ارضـاي همزمان اين معيارهـا محاسبه شود.
ارائهي الگوريتم حل مسأله
ي اختصاص پرندههـا به اهداف در يك مأموريت مشاركتي، براي اولين بـار توسط "ميكاييل گودريك" در سال 2001، مورد بررسي قرار گرفت [1]. ايشان طي مقالهاي كه در اين سال ارائه كردند، الگوريتم راضيكنندهاي (Satisficing) (=/ بهينـه) را براي حل مسألهي مورد نظر، مطرح كردند. البته در مقالهي ايشان ميزان اهميت تمام اهداف و نيز ميزان تهديد تمام نقاط تهديدزا يكسان در نظر گرفته شده است. در پروژهي حاضر الگوريتم ارائه شده توسط ميكائيل گودريك با لحاظ كردن ضرايب وزني براي اهداف مختلف و نيز نقاط تهديدزا توسعه داده ميشود.
كلّي انجام كـار به صورت زير است:
- ابتدا با فرموله كردن قيد مسير كوتاه براي هر هواپيما، امتيازي بين صفر تا يك به هر كدام از اهداف نسبت داده ميشود: امتياز صفر به دورترين هدف (نسبت به هواپيماي مورد بررسي) و امتياز يك به نزديكترين هدف؛
- مرحلهي بعد با فرموله كردن قيد اجتناب از تهديد براي هر هواپيما، امتيازي بين صفر تا يك به هر كدام از اهداف نسبت داده ميشود: امتياز صفر به هدفي كه كمترين تهديد را در مسير مستقيم در بر دارد و امتياز يك به هدفي كه بيشترين تهديد را در مسير مستقيم در بر دارد؛
- دليل تعارض دو قيد فشار بيشينه و گسترش بيشينه، اين دو قيد هم زمان با يكديگر در نظر گرفته ميشوند. در اين مرحله، پس از تعيين تمام انواع اختصاصهاي ممكن، امتياز هر نوع اختصاص (و به عبارت بهتر تمام انواع "گروهبندي") با استفاده از تابع "تأمين اجتماعي" محاسبه ميشود؛
- نهايت، نوعي از اختصاص كه با توجه به معيارهاي فوق بيشترين امتياز را كسب كند به عنوان اختصاص بهينه معرفي ميگردد.
شكل 2 - مثالي از توزيع هواپيماها، اهداف و نقاط تهديد در يك منطقه
اعمال قيد مسير كوتاه
ديدگاه فردي (Individual) (=/ تيمي، مشاركتي)، هر هواپيما فقط ميتواند به يك هدف حمله كند و از طرف ديگر، منطقيترين انتخاب، انتخاب نزديكترين هدف به هواپيمـا ميباشد. امّـا در يك فعاليت تيمي، با در نظر گرفتن سـاير قيودي كه در مسأله وجود دارد، ممكن است انتخاب نزديكترين هدف، انتخاب درستي نباشد.
ّـا در هر صورت، در يك فعاليت مشاركتي نيز، اولويت هر پرنده، انتخاب اهداف نزديكتر ميباشد. براي اعمـال قيد مسير كوتاه (Short Path) ، ميبايد در ابتدا آن را به صورت كمّي تعريف كنيم. واضح است كه هر قدر فاصلهي هدف تا وسيلهي پرنده كمتر باشد، اختصاص هواپيما به آن هدف، پذيرفتنيتر (Acceptable) است. اگر فاصلهي هواپيماي Ui با هدف Tj را با نمـاد d[SUB]A[/SUB](U[SUB]i[/SUB],T[SUB]j[/SUB])o و معيـار پذيرفتني بودن (ميزان كم بودن طول مسير) آن را با mu[SUB]Ai[/SUB](T[SUB]j[/SUB])o نمايش دهيم، اين معيار به صورت زير قابل تعريف است:
استفاده از اين تعريف، كه معياري كمّي و بيبعد است، نزديكترين هدف، بيشترين مقدار معيار پذيرفتني را خواهـد داشت (= 1) و دورترين هدف كمترين مقدار معيار پذيرفتني را خواهد داشت (= 0).
3 - فاصلهي هواپيما تا هدف در اين مرحله، بر اساس طول خط راست واصل بين آنها تعريف ميشود.
مثال مورد بررسي ميتوان با استفاده از رابطهي (1)، مقدار mu[SUB]A[/SUB] را براي اختصاص هر هواپيما به اهداف مختلف محاسبه كرد. نتايج اين محاسبات در ماتريسي به همين نام (mu[SUB]A[/SUB]) ذخيره ميشود. اين ماتريس داراي 3 سطر (به تعداد اهداف) و 6 ستون (به تعداد هواپيماها) خواهد بود. ماتريس mu[SUB]A[/SUB] براي مثال مورد بررسي به صورت زير است:
توجه به ماتريس فوق، براي هواپيماهاي 1 تا 3، هدف 1 نزديكترين هدف (امتياز 1) و هدف 3 دورترين هدف (امتياز صفر) ميباشد. همچنين براي هواپيماهاي 4 تا 6، هدف 3 نزديكترين هدف (امتياز 1) و هدف 1 دورترين هدف (امتياز صفر) ميباشد.
اعمال قيد اجتناب از تهديد
منظر فردي، مسير منطقي براي هر هواپيمـا، مسيري است كه در آن كمترين تهديدات از جانب محيط اطراف پرنده را تهديد كند. براي كمّي كردن قيد اجتناب از تهديد (Avoid Threats) ، از تعريف زير استفاده ميكنيم:
[SUB]R[/SUB](U[SUB]i[/SUB],T[SUB]j[/SUB],R[SUB]k[/SUB])o: كمترين فاصلهي نقطهي تهديدزاي R[SUB]k[/SUB] تا پارهخط واصل بين هواپيماي U[SUB]i[/SUB] و هدف T[SUB]j[/SUB] تقسيم بر ضريب وزني نقطهي تهديدزاي R[SUB]k[/SUB]؛ در صورتي كه فاصلهي منطقهي تهديدزا از هواپيماي U[SUB]i[/SUB] بيش از فاصلهي هدف تا هواپيما باشد، آنگاه فاصلهي منطقهي تهديدزا تا هدف در نظر گرفته ميشود.
عنوان مثال براي حالت ارائه شده در شكل 4 داريم:
شكل4 - حالات مختلف قرارگيري رادار نسبت به هدف و هواپيما
پارامتر d[SUB]R[/SUB](U[SUB]i[/SUB],T[SUB]j[/SUB])[SUB]o[/SUB] را به صورت زير تعريف ميكنيم:
استفاده از تعاريف فوق، معيار اجتناب از تهديد را به صورت زير تعريف ميكنيم:
رابطه به تعداد M*Nبار محاسبه ميشود. (براي N هواپيما، و در هر هواپيما براي M هدف). معيار كمّي و بيبعد فوق، نشاندهندهي ميزان تهديد موجود در اختصاص هواپيماي U[SUB]i[/SUB] به هدف T[SUB]j[/SUB] ميباشد. اين معيار به ازاي بيشترين تهديد برابر 1 و به ازاي كمترين تهديد برابر صفر خواهد بود.
مثال مورد بررسي ميتوان با استفاده از رابطهي (3)، مقدار mu[SUB]R[/SUB] را براي اختصاص هر هواپيما به اهداف مختلف محاسبه كرد. نتايج اين محاسبات در ماتريسي به همين نام (mu[SUB]R[/SUB]) ذخيره ميشود. اين ماتريس داراي 3 سطر (به تعداد اهداف) و 6 ستون (به تعداد هواپيماها) خواهد بود. ماتريس mu[SUB]R[/SUB] براي مثال مورد بررسي به صورت زير است:
توجه به ماتريس فوق، به عنوان مثال براي هواپيماي 2، هدف 3 بيشترين تهديد (امتياز 1) و هدف 2 كمترين تهديد (امتياز صفر) را در بر خواهد داشت.
اختصاص هدفهاي مناسب از ديدگاه فردي
معيار اخير كه در قسمتهاي قبل ارائه شدند، هدفهاي مناسب براي هر هواپيما را از ديدگاه فردي ارائه ميكردند. با جمعبندي دو معيار فوق، ميتوان هدفهاي مناسب براي هر هواپيما را به صورت زير تعريف كرد:
"هدفهايي براي يك هواپيما مناسبند كه معيار مسير كوتاه در مورد آنها بيش از معيار اجتناب از تهديد باشد". بيان رياضي اين عبارت به صورت زير است:
مثال مورد بررسي، با كم كردن ماتريس mu[SUB]R[/SUB] از ماتريس mu[SUB]A[/SUB] ميتوانيم اختصاصهاي مناسب از ديدگاه فردي را بررسي كنيم:
ماتريس فوق (mu)، عناصر مثبت نشاندهندهي اختصاصهاي مناسب از ديدگاه فردي هستند. به عنوان مثال براي هواپيماي شماره 2، اهداف 1 و 2 مناسبند.
آنجايي كه در اين مرحله هنوز مسير قطعي بين هواپيما تا هدف مشخص نيست، در تعيين فاصلهي هواپيما و هدف و همچنين فاصلهي رادار تا مسير، خط مستقيم واصل بين هواپيما و هدف را معيار قرار داديم. اما در بخش بعدي و پس از ارائهي روش طراحي مسير، اين محاسبات بر اساس مسير نهايي انجام خواهند شد.
بررسي قيود فشار بيشينه و گسترش بيشينه
كه پيشتر نيز اشاره شد، دو قيد فشار بيشينه (Max Force) -يعني اختصاص تعداد زيادي پرنده به يك هدف- و گسترش بيشينه (Max Spread) -يعني تحت پوشش قرار دادن اهداف بيشتر- در تعارض با يكديگر قرار دارند. لذا اعمال اين دو قيد بايد به صورت همزمان صورت گيرد. حل چنين مسألهاي تحت عنوان مسألهي "تأمين اجتماعي" (Social Welfare) شناخته ميشود؛ چرا كه در سيستم "تأمين اجتماعي" نيز هدف رساندن حداكثر امكـانـات به حداكثر افراد است.
اين مسأله با تعريف تابع "تأمين اجتماعي" كه خود از حاصلضرب دو تابع تشكيل شده، نوعي از "اختصاص" كه تابع "تأمين اجتماعي" را بيشينه كند، به عنوان جواب مسأله برگزيده ميشود. از دو تابع مذكور نيز يكي نمايندهي "گسترش بيشينه" (افراد تحت پوشش) و ديگري نمايندهي "فشار بيشينه" (امكانات ارائه شده به هر فرد) ميباشند.
"فشار بيشينه" به گونهاي تعريف ميشود كه با افزايش تعداد هواپيماهاي اختصاص يافته به هر هدف، به صورت تصاعدي رشد كند و با كاهش هواپيماهاي اختصاص يافته به هر هدف، به شدت كاهش يابد. تابع "گسترش بيشينه"
به سادگي برابر با مجموع ضرايب اهميت اهدافي است كه به هر كدام آنها حداقل يك هواپيما اختصاص پيدا كرده است.
عنوان مثال، در صورتي كه T={T[SUB]1[/SUB], T[SUB]2[/SUB], ...,T[SUB]j[/SUB]}o مجموعهي اهدافي باشد كه به هر كدام آنها حداقل يك هواپيما اختصاص يافته است، و در صورتي كه بخواهيم به هر هدف حداقل 2 هواپيما اختصاص يـابد، تابع "فشار بيشينه" را براي هدف T[SUB]j[/SUB] به صورت زير تعريف ميكنيم (m(T[SUB]j[/SUB])o برابر با تعداد هواپيماهايي است كه به هدف T[SUB]j[/SUB] اختصاص يافته است):
"فشار بيشينه" براي كل مجموعه نيز به سادگي به صورت حاصلضرب U[SUB]MaxForce[/SUB] براي كليهي اهدافي كه حداقل يك هواپيما به آنها اختصاص يافته به صورت زير تعريف ميشود:
"گسترش بيشينه" نيز همانطور كه پيشتر اشاره شد، برابر با مجموع ضرايب اهميت اهدافي است كه حداقل يك هواپيما به آنها اختصاص داده شده است:
تابع "تأمين اجتماعي" را به صورت زير تعريف ميكنيم:
استفاده از تابع فوق، صرف نظر از اينكه هر هواپيما به كدام هدف اختصاص پيدا ميكند، ميتوان تركيب بهينهاي را در "گروهبندي" هواپيماهـا ارائه كرد. به عنوان مثال در صورتي كه 6 هواپيما داشته باشيم، ميتوان گروهبنديهايي به صورت زير را تعريف كرد:
توجه به جدول فوق، در يك تيم 6 تايي از هواپيما، انتخاب "گروهبندي" به صورت دو گروه سه تـايي از هواپيماها، منجر به بيشترين مقدار براي تابع "تأمين اجتماعي" خواهد شد.
انتخاب "اختصاص" بهينه
اينجا مسألهي اختصاص هواپيما به هدف را از دو ديدگاه فردي و گروهي مورد بررسي قرار داديم. در ديدگاه فردي، قيود "مسير كوتاه" و "اجتناب از تهديد" و در ديدگاه گروهي، قيود "فشار بيشينه" و "گسترش بيشينه" مورد بررسي قرار گرفتند. از ديدگاه فردي اهدافي مناسبند كه امتياز معيار "مسير كوتاه" در آنها بيش از امتياز معيار "اجتناب از تهديد" باشد. اما در ديدگاه گروهي، "گروهبندي" بهينه صرف نظر از محل اهداف و مناطق تهديدزا صورت ميگيرد.
انتخاب اختصاص بهينه، نيازمند تعريف تابعي هستيم كه معيارهاي فردي و گروهي را همزمان در نظر بگيرد. به اين منظور تابع زير توسط ميكائيل گودريك [1] پيشنهاد شده است:
رابطهي اخير، ترم اول همان تابع تأمين اجتماعي بوده كه نشاندهندهي نوع گروهبندي (معيارهاي گروهي) ميباشد و ترم دوم نشاندهندهي وضعيت اين اختصاص از ديدگاه معيارهاي فردي ميباشد. با توجه به مطالب بخش 2-2-3، از ديدگاه فردي (از ديد هواپيما) اهدافي مناسبند كه در آنها معيار مسير كوتاه (mu[SUB]A[/SUB](T[SUB]j[/SUB])o) بزرگتر از معيار اجتناب از تهديد (mu[SUB]R[/SUB](T[SUB]j[/SUB])o) باشد و طبيعتاً هر قدر اين اختلاف بيشتر باشد، از ديد هواپيما، آن هدف مناسبتر است. لذا براي اصلاح تابع "تأمين اجتماعي"، اين اختلاف با ضريب eps، به عنوان يك عامل مثبت در افزايش تابع "تأمين اجتماعي" ايفاي نقش ميكند. به عبارت ديگر، اگر معيارهـاي "مسير كوتاه" و "اجتناب از تهديد" نسبت به معيارهاي "فشار بيشينه" و "گسترش بيشينه" براي ما اهميت بيشتري داشته باشد، ميتوان با افزايش ضريب eps، اولويت چنين "اختصاص"هايي را بالا آورد.
رابطهي اخير كه توسط گودريك براي محاسبهي امتياز "اختصاص" پيشنهاد شده، كمترين مقدار mu=mu[SUB]A[/SUB]-mu[SUB]R[/SUB] در هر اختصاص به عنوان عامل مثبت به تابع V اضافه ميشود. اما در اين پروژه، مقدار ميانگين mu در هر اختصاص به تابع V اضافه ميشود:
استفاده از روابطي كه در اين بخش ارائه شد ميتوان امتياز اختصاصهاي مختلف را با توجه به معيارهاي چهارگانهاي كه در ابتداي اين فصل معرفي شدند محاسبه كرد. در بخش بعدي، نحوهي اجراي اين الگوريتم با استفاده از كدي كه در نرمافزار MATLAB نوشته شده معرفي ميگردد.
معرفي كد "اختصاص"
بخش قبل نحوهي محاسبهي امتياز هر اختصاص معرفي شد. در اين پروژه محاسبهي امتياز هر "اختصاص" و نيز انتخاب "اختصاص بهينه" توسط كدي كه در نرمافزار MATLAB نوشته شده انجام ميگيرد.
اين كد، در ابتدا ماتريسهاي mu[SUB]A[/SUB]، mu[SUB]R[/SUB] و mu توليد ميشوند. اين ماتريسها داراي ابعاد M*N هستند (M: تعداد اهداف و N: تعداد هواپيماها). پس از توليد اين سه ماتريس طبق الگوي معرفي شده در بخشهاي پيشين، براي انتخاب اختصاص بهينه، ميبايد انواع اختصاصهاي ممكن را توليد كرد و سپس با محاسبهي امتياز هر كدام، اختصاصي كه بيشترين امتياز را كسب ميكند، به عنوان اختصاص بهينه معرفي كرد.
توليد انواع اختصاصهاي ممكن، ماتريس A با ابعاد M*N تشكيل ميشود. ستونهاي اين ماتريس به تعداد هواپيماها و سطرهاي آن به تعداد اهداف ميباشد. در هر ستون اين ماتريس فقط يك عضو با مقدار 1 وجود دارد و بقيهي صفر هستند. وجود عنصر 1 در ستون i و سطر j به معناي اختصاص يافتن هواپيماي i به هدف شمارهي j است. در ابتداي كار، تمامي عناصر سطر اول اين ماتريس 1 هستند و بقيه صفر ميباشند (يعني تمام هواپيماها به هدف شمارهي يك اختصاص يافتهاند). براي مثال قبلي كه در آن 6 هواپيما و 3 هدف وجود داشتند، اولين اختصاص به صورت زير است:
توليد اختصاصهاي بعدي، عدد 1 در آخرين ستون به سمت پايين حركت ميكند تا به آخرين سطر برسد. پس از اينكه عدد 1 در آخرين ستون به سطر آخر رسيد، عدد 1 ستون قبلي، اگر در آخرين سطر نباشد، به پايين ميآيد و عدد 1 ستونهاي بعدي به سطر اول برميگردند. در ادامه نتايج اين روند براي توليد اختصاصهاي بعدي نمايش داده شده است:
به همين ترتيب خواهيم داشت:
... .
كل اختصاصهاي توليد شده برابر M[SUP]N[/SUP] ميباشد (هر كدام از N هواپيماي ما داراي M گزينه هستند). پس از توليد هر "اختصاص" امتياز آن با استفاده از رابطههاي قبلي محاسبه ميشود و با امتياز اختصاصهاي قبلي مقايسه ميشود. در صورتي امتياز اختصاص جديد بيشتر از اختصاصهاي قبلي باشد، به عنوان "اختصاص بهتر" برگزيده ميشود. با انجام اين روند تا انتها، اختصاصي كه بيشترين امتياز را كسب كند به عنوان اختصاص بهينه معرفي ميشود.
مثال مورد بررسي پس از انجام محاسبات و طي روند، نتايج زير براي اختصاص هواپيماها به اهداف حاصل شدند:
اين اختصاص نيز برابر است با:
شكل 5 - اختصاص بهينهي هواپيماها به اهداف با توجه به معيارهاي چهارگانه
[1] Michael A. Goodrich. "A Satisficing Approach to Assigning Vehicles to Targets" International Conference on Systems, Man and Cybernetics.
منبع : موسسه خدمات فنی و مهندسی رها