1. انگیزه
با پیشرفت فناوری های مکان یابی داخلی مانند موقعیت یابی داخلی [ 1 ، 2 ، 3 ، 4 ] و حسگرهای LiDAR داخلی [ 5 ]، تقاضا برای تجزیه و تحلیل محاسباتی در فضاهای داخلی به سرعت در حال افزایش است. به عنوان مثال، مدیران ایمنی ساختمان می توانند سازه های ساختمان را برای برنامه ریزی مسیرهای فرار برای تخلیه موثر در شرایط اضطراری بازرسی کنند [ 6 ، 7 ]. مدیران امنیتی ممکن است بخواهند موقعیت بهینه دوربین های نظارتی را برای محافظت از یک مرکز مهم یا شناسایی برخی بازدیدکنندگان مشکوک که رفتار غیرعادی از خود نشان می دهند پیدا کنند [ 8 ، 9]]. همچنین می توان حرکت جمعیت در مرکز خرید را تحلیل کرد تا کالاها را به طور موثر در معرض دید مشتریان قرار دهد [ 10 ].
برای پاسخگویی به این الزامات، تجزیه و تحلیل، پردازش و مدیریت موثر اطلاعات مربوط به فضای داخلی بسیار مهم است. پارتیشن بندی فضای داخلی یکی از این الزامات ضروری است که فضای داخلی پیچیده و بزرگ باشد مانند ایستگاه های مترو با راهروهای طولانی، مراکز خرید پیچیده، یا مراکز بزرگ همایش. در حالی که بسیاری از برنامه های کاربردی داخلی بر اساس مشکلات پارتیشن بندی خاص خود توسعه یافته اند [ 1 ، 11 ، 12 ]، آنها با مفروضات خاص محدود شده اند و به طور کلی برای سایر حوزه ها قابل اجرا نیستند. این ما را به ضرورت یک چارچوب یکپارچه برای پارتیشن بندی فضای داخلی هدایت می کند.
در این مقاله، ما یک چارچوب انعطافپذیر برای پارتیشنبندی فضای داخلی به منظور پر کردن شکافها بین روشهای مختلف پارتیشن بندی برای کاربردهای مختلف ارائه میکنیم. ما بهویژه روی دو کاربرد مهم داخلی تمرکز میکنیم: (i) مشکل قرار دادن دستگاه و (ii) مشکل برنامهریزی مسیر. با این حال، ما تأکید می کنیم که چارچوب ما به این برنامه ها محدود نمی شود، بلکه می توان آن را با تنظیمات مناسب به سایر برنامه ها نیز گسترش داد.
مدل های دو بعدی و سه بعدی زیادی وجود دارد که ساختارهای جغرافیایی از جمله فضاهای داخلی را نشان می دهد. طراحی به کمک کامپیوتر (CAD) به طور گسترده ای برای طراحی محصولات و سازه های معماری به صورت دو بعدی و سه بعدی استفاده شده است [ 13 ، 14 ]. پلان های طبقه ساختمان و هندسه های سه بعدی آنها نیز در قالب های CAD طراحی و مدیریت شده اند [ 13 ، 14 ]. فرمت مدل سازی اطلاعات ساختمان (BIM) یک مدل پرکاربرد در ساخت و مدیریت سازه های ساختمانی و پردازش هندسه سه بعدی سازه های معماری است [ 15 ، 16 ]. کلاس های بنیاد صنعت (IFC) یک مدل استاندارد تبادل داده برای این منظور است [ 17 ]. CityGML [ 18] یک مدل استاندارد تبادل داده برای مدلسازی دیجیتال شهرها است که توسط OGC صادر شده است. اگرچه عمدتاً هندسههای سهبعدی اشیاء شهری مانند زمینها، جادهها و ساختمانها را کنترل میکند، اما ردپای دوبعدی را در مدل سطح جزئیات (LOD) مشخصی نیز ارائه میکند. IndoorGML [ 19 ] یک مدل تبادل داده برای فضاهای داخلی است که ساختارهای هندسی و توپولوژیکی و معناشناسی را برای کاربردهای داخلی مدیریت می کند. هندسه دو بعدی و سه بعدی فضاهای داخلی را کنترل می کند. با توجه به قابلیت همکاری، سازگاری با این مدل های استاندارد نیز مهم است. به طور خاص، ما نمایش سازگار با IndoorGML از فضاهای پارتیشن بندی شده را ارائه می دهیم. علاوه بر این، اگرچه این مدلها از هندسههای سهبعدی پشتیبانی میکنند، اما در نظر گرفتن فضاهای دو بعدی در بسیاری از کاربردها در مسائل جغرافیایی نیز رایج است [ 20 ,21 ]. بنابراین ما در این مقاله بر روی پوشش و پارتیشن بندی در فضای دو بعدی تمرکز می کنیم.
مشارکت های ما در این مقاله به شرح زیر است:
-
یک چارچوب یکپارچه برای مشکلات پوشش و پارتیشن بندی در فضاهای دوبعدی که انعطاف پذیر است به این معنا که می توانیم پارتیشن های مناسب برای بسیاری از مسائل مختلف را با محدودیت های مناسب بدست آوریم.
-
یک فرمول برنامه ریزی خطی باینری برای پوشش و پارتیشن بندی مسائل، که به طور موثر راه حل هایی را برای نیازهای داده شده پیدا می کند.
-
یک روش برای برنامه ریزی مسیر بر اساس پارتیشن بندی محدب. روش ما نه تنها فضا کارآمد است، بلکه یک نمایش سازگار با IndoorGML را نیز ارائه می دهد. ما همچنین به طور تجربی اثربخشی روش مسیریابی را با چارچوب پیشنهادی نشان میدهیم.
ادامه این مقاله به شرح زیر سازماندهی شده است. در بخش 2 ، ما به طور خلاصه رویکردهای موجود در مورد مشکلات قرارگیری دستگاه و ناوبری داخلی را که کاربردهای مهمی در فضاهای داخلی هستند، مرور می کنیم. سپس یک نمای کلی از ساختار چند مرحله ای چارچوب پیشنهادی برای پوشش و پارتیشن بندی وظایف در بخش 3 ارائه می دهیم . در بخش 4 ، ما به جزئیات یک مرحله خاص، به نام محاسبه حداکثر گسترش، که ورودی ضروری مرحله زیر را تولید می کند، نگاه می کنیم. ما به مشکل پوشش و مشکل پارتیشن بندی در بخش 5 و بخش 6 می پردازیمبه ترتیب، که در آن فرمول های برنامه ریزی خطی باینری را برای حل مسائل ارائه می دهیم. پس از ارائه نتایج تجربی در بخش 7 , ما چندین موضوع را مورد بحث قرار می دهیم که باید برای بهبود بیشتر در بخش 8 به آنها پرداخته شود . بخش 9 مقاله را به پایان می رساند.
2. کارهای مرتبط
در این بخش، مطالعات قبلی مرتبط با کار خود را مرور می کنیم. ابتدا مروری کوتاه بر مشکلات پوشش و پارتیشن بندی ارائه می دهیم تا سهم کار خود را روشن کنیم ( جدول 1 را ببینید ). سپس کار موجود در مورد برنامه های کاربردی مهم داخلی را مورد بحث قرار می دهیم: مشکل قرار دادن دستگاه و مشکل برنامه ریزی مسیر.
کارها و تغییرات زیادی در مورد مسائل پوشش و پارتیشن بندی چند ضلعی ها به ویژه در زمینه هندسه محاسباتی وجود دارد و بسیاری از مسائل مرتبط با NP-hard شناخته می شوند [ 29 ، 30 ، 31 ]. مطالعات نظری [ 22 ، 24 ] معمولاً با چند ضلعی های ساده سروکار دارند زیرا چند ضلعی های دارای سوراخ مسئله را به طور قابل توجهی پیچیده می کنند. بسیاری از مشکلات پوششی [ 24 ، 25 ، 28 ] به مشکلات دید مرتبط هستند. با این حال، آنها پارتیشن های چند ضلعی با محدودیت دید را در نظر نمی گیرند. تقسیم یک چند ضلعی به شکل ستاره به NP-hard [ 30] معروف است] و چندین الگوریتم برای چند ضلعی های ساده ارائه شده است [ 26 ، 32 ]. پارتیشن بندی با محدودیت های دیگر مانند محدوده [ 22 ] و تحدب [ 23 ] نیز مورد مطالعه قرار گرفته است. به عنوان یک روش عمومی، بوچین و همکاران. [ 28 ] اخیراً یک روش پارتیشن بندی چند ضلعی مبتنی بر اسکلت ارائه کرده است که می تواند به راحتی برای محدودیت های مختلف اصلاح شود، اما این روش به چند ضلعی های ساده بدون سوراخ محدود می شود. روش ما می تواند به عنوان یک روش خارج از قفسه استفاده شود که می تواند با یک اصلاح کوچک و ساده با طیف گسترده ای از مشکلات مقابله کند. اگرچه تضمینی برای ارائه راه حل بهینه نیست، اما خروجی هایی با کیفیت قابل قبولی ارائه می دهد که بعداً در مورد آن صحبت خواهیم کرد.
2.1. مشکلات قرار دادن دستگاه
مشکل پوشش یکی از الزامات اساسی بسیاری از کاربردها در فضاهای داخلی است. به طور خاص، ارتباط نزدیکی با دستگاه های موقعیت یابی دارد، جایی که هر دستگاه دارای یک منطقه موثر محدود است و باید کل فضای داخلی را با تعداد کمتری دستگاه پوشش دهیم. مکان یابی دوربین های مداربسته یک مثال است. برای سادهترین نسخه آن، ممکن است فرض کنیم که دوربینهای omni با وضوح نامحدود داریم تا زمانی که خط دید مختل نشده است، بتواند آن را مشاهده کند. این مشکل، مسئله گالری هنری نامیده می شود، یک مسئله به خوبی مطالعه شده در زمینه هندسه محاسباتی، که نشان داده شده است که NP-hard است حتی اگر مکان ها در رئوس چند ضلعی محدود شده باشند (نگاه کنید به [31 ]] برای جزئیات). برای ملاحظات واقع بینانه، ممکن است عوامل دیگری مانند میدان دید (FOV)، وضوح پیکسل، و اعوجاج پرسپکتیو را نیز در نظر بگیریم (برای بررسی جامع، [ 33 ] را ببینید).
قرار دادن سنسورها و بیکن ها نیز مشکلات مشابهی هستند، زیرا آنها نیز چندین ویژگی مشکل قرار دادن دوربین را به اشتراک می گذارند. برخلاف فضاهای بیرونی، دستگاههای ساطع و پردازش سیگنال در فضاهای داخلی باید مسائل نفوذپذیری و پراش را در نظر بگیرند زیرا دیوارها، ستونها و موانع زیادی وجود دارد که خط دید دستگاه را مسدود میکند [34 ] . همچنین مسائل دیگری در رابطه با ویژگیهای دستگاههای مختلف مانند بیکنها با محدودههای مؤثر محدود و محدودیتهای زاویهای [ 35 ] و با سطوح توان متفاوت [ 36 ] وجود دارد.
همچنین انواع دیگری در مورد مشکلات قرارگیری دوربین و دستگاه با تمرکز بر فضاهای هدف و همچنین ویژگی های دستگاه وجود دارد. در برخی از کاربردها، دوربینهای نظارتی باید بتوانند قسمتهای مهمی مانند ورودیهای ساختمان و درهای اتاق خزانه بانک را زیر نظر داشته باشند. می توان آن را به سادگی با وزن دادن به زیرمنطقه هایی که باید بر اساس اهمیت آنها تحت پوشش قرار گیرند [ 37 ، 38 ]، که می تواند مستقیماً در چارچوب ما نیز اعمال شود، مورد بررسی قرار گیرد.
2.2. مشکل برنامه ریزی مسیر
از آنجایی که سیستم های موقعیت یابی داخلی با فناوری های مختلف سنجش مانند اثرانگشت Wifi [ 1 ]، حسگرهای نور [ 2 ] و چراغ های کم انرژی بلوتوث (BLE) [ 3 ] پیشرفت کرده اند، خدمات ناوبری در فضاهای داخلی امکان پذیر شده است.
نمایه سازی فضاهای داخلی برای برنامه ریزی مسیر به روشی کارآمد یک موضوع مهم برای سیستم های خدمات آنلاین و تبادل داده است. با توجه به بسیاری از مسائل از جمله الزامات خاص برنامه های کاربردی هدف مانند پویایی، ارزیابی کیفیت و مبادله بین پیچیدگی و دقت شاخص، انواع روش های نمایه سازی برای نمودارهای ناوبری وجود دارد (نگاه کنید به [39] ) . خو و همکاران [ 40 ] چند ضلعی ورودی را مثلث کرد و یک گره برای هر وجه مثلثی و یک پیوند بین هر جفت وجه مجاور ایجاد کرد، اگر توسط اشیاء داخلی مسدود نشود. کرومینایت و همکاران [ 11] پویایی زمانی را در نظر گرفت، که باید مسیرها را در ساعات اوج و خارج از اوج به طور متفاوتی پیدا کند. آنها از مثلث سازی محدود دلونی برای تقسیم فضا استفاده کردند و با اتصال مرکز وجوه مجاور، یک نمودار ناوبری ساختند. حبیبی و همکاران [ 41 ] یک فرمول برنامه ریزی عدد صحیح باینری را برای یافتن مسیری بر اساس وجوه مثلثی پیشنهاد کرد. آنها یک تابع هدف را با ترکیب چندین عامل از جمله تعداد وجوه، مساحت و طول محیط برای ارزیابی کیفیت مسیر ارائه کردند. آنها همچنین از مسیرهای اتصال وسط لبه قطعات محدب استفاده کردند. مورتاری و همکاران [ 42 ] همچنین یک روش ساخت نمودار مبتنی بر مثلث را ارائه کرد که مزایای هر دو روش مبتنی بر محور میانی و نمودار دید را دارد. یانگ و همکاران [43 ] یک روش ساخت گراف ناوبری بر اساس نمودار دوگانه پوانکاره از نقشه های ترکیبی که فضای داخلی را نشان می دهد، پیشنهاد کرد.
روش های مبتنی بر شبکه نیز به دلیل سادگی و کاربردی بودن به طور گسترده مورد استفاده قرار گرفته اند. لین و همکاران [ 44 ] یک روش برنامه ریزی مسیر مبتنی بر شبکه را با استفاده از الگوریتم A* ارائه کرد. آنها از نمودار مجاورت که توپولوژی زیرمنطقه ها را نشان می دهد برای کاهش فضای جستجو استفاده کردند. فریاس و همکاران [ 45 ] از یک روش مبتنی بر شبکه (و همچنین مثلث بندی) برای برنامه ریزی مسیر اسکن برای وظیفه گرفتن ابر نقطه ای فضاهای داخلی استفاده کرد.
3. بررسی اجمالی
در این بخش، معماری کلی چارچوب خود را، همانطور که در شکل 1 نشان داده شده است، شرح می دهیم .
ما فرض می کنیم که فضای ورودی با یک چند ضلعی نشان داده می شود که یک تنظیم رایج در ادبیات است [ 43 ، 46 ]. اگرچه بسیاری از مدل های داده از نمایش هندسه های منحنی در مشخصات خود پشتیبانی می کنند، داده ها معمولاً از اجزای مسطح (در سه بعدی) و چند ضلعی (در دو بعدی) در عمل تشکیل می شوند [15 ] . اگر ساختارهای غیرچند ضلعی ساختمان مانند دیوارهای منحنی وجود داشته باشد، می توانیم آنها را با قطعات خط تقریب بزنیم [ 47 ].
در بالاترین سطح، روش ما با تقسیم چند ضلعی ورودی به وجوه کوچک و ادغام آنها به چند ضلعی های بزرگتر با قوانین مناسب شروع می شود. ما از چند ضلعی های ادغام شده به عنوان واحدهای اساسی مرحله بعدی استفاده می کنیم که به مسائل پوشش و پارتیشن بندی می پردازد. هر مرحله از شکل 1 در زیر توضیح داده شده است.
3.1. تقسیم بندی لبه و مثلث بندی
برای هر لبه مرزی چند ضلعی فضای داخلی، آن را به بخش های کوتاه تقسیم می کنیم. به طور خاص، با توجه به طول آستانه θ، یک یال به طول l را به d قسمت تقسیم می کنیم که در آن د=⌈ل/θ⌉. به عنوان مثال، اگر θ=5، یک یال با طول 13 به سه بخش خط تقسیم می شود زیرا ⌈13/5⌉=3. تعیین مقدار بهینه از θبستگی به وظیفه هدف دارد در میان تنظیمات مثال در بخش بعدی، تحدب به آن حساس نیست θدر حالی که محدودیت برد نسبتا حساس تر است زیرا هر وجه مثلثی باید در دایره ای با شعاع محدود داده شده در مرکز مرکز قرار گیرد. از نظر اکتشافی، می توانیم تنظیم کنیم θبا توجه به عرض راهرو، به عنوان مثال، نصف عرض راهرو، که نتایج قابل قبولی را بدون رنج بردن از آن ارائه می دهد.
با استفاده از قطعات خط و رئوس آنها به عنوان قید، مثلث دلونای مقید آن را محاسبه می کنیم. توجه داشته باشید که ما فقط روی مرز چند ضلعی ورودی محدود می کنیم که هیچ نقطه ای در داخل چند ضلعی ایجاد نمی کند. هنگامی که چند ضلعی ورودی دارای یک فضای خالی بزرگ مانند یک سالن کنفرانس بزرگ و راهروهای بیش از حد گسترده در داخل خود باشد، ممکن است مثلث های بزرگ و طولانی ایجاد کند. برای برخی تنظیمات خاص که در زیر به آن ها خواهیم پرداخت، این مثلث های بزرگ و بلند ممکن است نتایج نامطلوبی را به همراه داشته باشند. برای جلوگیری از این امر، ممکن است محدودیتهای بیشتری مانند سوراخهایی در داخل چند ضلعی اضافه کنیم که نشاندهنده برخی از تاسیسات داخلی مانند ستونها و مبلمان شبه ثابت (مانند میز و صندلی) است.
3.2. گسترش
پس از مثلث سازی، وجه های مثلثی را در چند ضلعی های بزرگتر ادغام می کنیم. با شروع با یک وجه مثلثی منفرد، منطقه را با ادغام آن با وجوه مجاور گسترش می دهیم. به منظور تعیین جنبه های مورد ادغام، مجموعه ای از قوانین را اعمال می کنیم که می توانیم آنها را به عنوان پارامتر کنترل کنیم. این قوانین و پارامترها چارچوب پیشنهادی را انعطافپذیر و سازگارتر با انواع مختلف برنامهها میسازد. با تنظیم صحیح قوانین و پارامترها، میتوانیم با بازتاب ویژگیها و الزامات برنامههای هدف، یک راهحل پارتیشن بندی مناسب را اعمال کنیم. برای مثال، میتوانیم از قوانین محدودیت دید برای مسئله قرارگیری دوربینهای نظارتی استفاده کنیم، به طوری که هر چند ضلعی ادغام شده حاوی نقطهای باشد که از آن خط دید در چند ضلعی کاملاً اطمینان حاصل شود. در نتیجه مرحله گسترش، مجموعه ای از مناطق توسعه یافته تولید می شود. توجه داشته باشید که ممکن است با یکدیگر همپوشانی داشته باشند و در مرحله بعد از آنها برای محاسبه پوشش و پارتیشن بهینه استفاده خواهیم کرد. جزئیات این مرحله ادغام در بخش بعدی توضیح داده خواهد شد.
3.3. پوشش و پارتیشن بندی
اکنون از مجموعه مناطق توسعه یافته محاسبه شده در مرحله قبل برای ایجاد نتیجه نهایی برای مسئله پوشش یا پارتیشن بندی استفاده می کنیم. در مسئله پوشش، از ما خواسته می شود که زیرمجموعه ای از مناطق گسترش یافته را پیدا کنیم که اتحاد هندسی آنها کل فضای داخلی را پوشش می دهد. از سوی دیگر، برای مشکل پارتیشن بندی، باید فضای داخلی را به زیرمنطقه های مجزا تقسیم کنیم که هر کدام زیرمجموعه ای از یک توسعه هستند. از آنجایی که این دو مسئله اساساً شبیه یکدیگر هستند، می توان از خروجی یک مسئله برای محاسبه حل مسئله دیگر استفاده کرد. به عنوان مثال، ما می توانیم پارتیشن یک چند ضلعی را با پیدا کردن پوشش آن و توزیع مناسب مناطق مشترک برای جلوگیری از همپوشانی آنها پیدا کنیم. با این حال، رویه توزیع ممکن است بسیار پیچیده شود، به ویژه زمانی که نواحی حاصل از یکدیگر عبور می کنند، بنابراین در وسط مناطق دیگر بریده می شوند، که منجر به تعداد زیادی پارتیشن نامزد می شود. به همین دلیل، با ارائه راه حل های مربوط به آنها از نظر فرمول برنامه ریزی خطی باینری، این دو مسئله را جداگانه در نظر می گیریم.
4. حداکثر گسترش
این بخش به تشریح مفهوم بسط و روش محاسبه آنها اختصاص یافته است. بسط یک اتحاد از وجوه مثلثی است و به عنوان یک جزء واحد از برنامه ریزی خطی باینری برای پوشش نهایی و کار پارتیشن بندی نقش دارد. انعطافپذیری چارچوب ما بر این واقعیت استوار است که میتوانیم با تنظیم قوانین دقیق در محاسبه بسطها و تعریف یک تابع بررسی محدودیت جدید، نمونههای مختلفی از بسطها ایجاد کنیم. در این بخش، یک الگوریتم محاسباتی بسط ساده و چندین محدودیت را ارائه میکنیم که میتواند در بسیاری از کاربردها در فضاهای داخلی وجود داشته باشد.
4.1. بسط محاسباتی
مجموعه ای از وجوه مثلثی تولید شده توسط مثلث سازی محدود دلون به عنوان واحدهای اساسی در مراحل بعدی پوشش یا پارتیشن بندی استفاده می شود. ما از یک وجه مثلثی شروع می کنیم تا با وجوه مجاور ادغام شویم. وجه اولیه یک وجه بذر و چندضلعی ادغام شده وجوه متصل بسط نامیده می شود.
تعریف 1 (بسط) .
با توجه به یک چند ضلعی ورودی P به صورت مثلثی به مجموعه ای از وجوه تی، یک مجموعه ایکس⊂تیانبساط از یک جنبه دانه است س∈ایکساگر اتحاد هندسی همه وجوه باشد ایکس∈ایکسیک چند ضلعی واحد (متصل) را تشکیل می دهد.
در این مرحله حداکثر بسطها را با جنبههای seed محاسبه میکنیم و یک تابع بررسی محدودیت f را برای تعیین حداکثری یک بسط معرفی میکنیم.
تعریف 2 (بسط حداکثر) .
یک بسط ایکس⊂تیاز یک جنبه بذر س∈ایکسبا توجه به یک تابع بررسی محدودیت حداکثر است f:تی×2تی×تی→{درست است، واقعی،نادرست}، اگر f(س،ایکس،y)بازده – محصول نادرستبرای تمام جنبه ها y∈تیکه در مجاورت برخی از جنبه های توسعه یافته کنونی هستند ایکس∈ایکس.
محاسبه حداکثر بسط یک وجه بذر به شرح زیر توضیح داده شده است. این به صورت پیمایش تکراری روی نمودار دوتایی انجام میشود، که در آن هر وجه با یک گره مشخص میشود و اگر وجههای مربوطه یک لبه از وجوه را به اشتراک بگذارند، دو گره از طریق یک پیوند به هم متصل میشوند. پیمایش تکراری نمودار برای محاسبه حداکثر بسط ها همانطور که در الگوریتم 1 توضیح داده شده است.
الگوریتم 1 حداکثر بسط را محاسبه کنید |
1: رویه گسترش ( s : seed facet، S : مجموعه ای از وجوه برای پوشش: f : تابع بررسی محدودیت) |
2: صف C را مقداردهی کنید |
3: یک عنصر s را به صف C اضافه کنید |
4: E←ϕ. |
5: در حالی که |سی|>0 انجام // را تکرار کنید تا صف C خالی نباشد |
6: ایکس←حذف یک عنصر از صف C |
7: اگر f(س،E،تی)=درست است، واقعی سپس |
8: E←E∪{تی} |
9: برای هر جنبه بازدید نشده تی”در مجاورت t ، اضافه کنید تی”در صف C |
10: پایان اگر |
11: پایان در حالی که |
12: بازگشت E |
13: پایان روند |
این الگوریتم یک Seed Fat را به عنوان ورودی دریافت می کند. با شروع از وجه دانه، ناحیه E را با گنجاندن وجوه جدیدی که تابع بررسی محدودیت f را برآورده میکنند و با وجه دانه یا یکی از وجوه در بسط فعلی مجاور هستند، گسترش میدهیم. ما فرض می کنیم که هر جنبه بذری محدودیت را به عنوان خودش برآورده می کند، به عنوان مثال، f(س،ϕ،س)=درست است، واقعیبرای هرچی س∈تی; در غیر این صورت ممکن است در برخی موارد چند ضلعی به طور کامل پوشش داده نشود. وقتی جنبه دیگری برای گنجاندن وجود نداشته باشد، چند ضلعی ادغام شده فعلی را به عنوان حداکثر بسط برمی گرداند. تابع بررسی محدودیت f سه آرگومان دارد: جنبه seed، بسط فعلی، و وجهی برای اضافه کردن جدید. دلیل اینکه تابع را جدا از آرگومانهایش میگیریم این است که میتوانیم تابع بررسی محدودیت را به روشی بسیار کارآمد تعریف کنیم تا حالتی که در آن تابع فقط هندسه ادغام شده را میگیرد. اگر تابع بررسی محدودیت f(س،E،تی)false می دهد ، یعنی اضافه کردن t شرط را برآورده نمی کند و آن را به مجموعه بسط نمی دهیم. این کار را تا زمانی که تمام وجوه مجاور به طور کامل پردازش شوند تکرار می کنیم.
الگوریتم 1 تمام جنبه ها را تکرار می کند و تابع بررسی محدودیت را فراخوانی می کند، در اجرا می شود O(nφ(n))زمانی که n تعداد وجوه و φ(n)زمان صرف شده توسط تابع بررسی محدودیت با حداکثر n وجه است. برای محدودیت هایی که در این مقاله مورد بحث قرار می دهیم، داریم φ(n)=O(1)، بنابراین الگوریتم 1 در زمان خطی اجرا می شود.
ما حداکثر انبساط را برای هر وجه به صورت دانه محاسبه می کنیم. سپس میتوانیم حداکثر بسط به تعداد وجهها را به دست آوریم. با استفاده از برنامه خطی باینری که در بخش بعدی به آن پرداخته خواهد شد، میتوانیم از این حداکثر بسطها برای بدست آوردن کاورها یا پارتیشنها استفاده کنیم. با این حال، زمانی که ما روی همه وجوه به عنوان دانه تکرار میکنیم، زمان درجه دوم طول میکشد، زیرا در زمان خطی برای هر وجه دانه اجرا میشود. از طرف دیگر، ما می توانیم فقط از یک زیر مجموعه از جنبه ها استفاده کنیم. ما می توانیم انتخاب کنیم ρnوجوه به صورت تصادفی برای برخی 0<ρ≤1و حداکثر بسط آنها را محاسبه کنید. ما به طور تجربی عملکرد این استراتژی را با توجه به ρدر بخش 7 .
شکل 2 روند محاسبه حداکثر گسترش یک وجه بذر را نشان می دهد. فرض کنید محدودیت داده شده محدب است، بنابراین بسط حاصل باید یک چندضلعی محدب باشد. با شروع از یک وجه دانه A همانطور که در شکل 2 a نشان داده شده است، آن را به صف اضافه می کنیم. در شکل 2 ب، دو وجه در مجاورت A قرار دارند . از آنجا که آ∪بهنوز محدب است، ما B را وارد بسط می کنیم. مجدداً، اجازه دهید فرض کنیم که وجهی را که با C در شکل 2c نشان داده شده است، انتخاب می کنیم ، که به حالت بعدی همانطور که در شکل 2 d توضیح داده شده است، منتهی می شود. هنگامی که وجه نشان داده شده با D را انتخاب می کنیم ، انبساط حاصل یک چندضلعی را تشکیل می دهد که با مرز ضخیم در شکل 2 d توصیف شده است، که دارای یک راس مقعر است که با یک دایره قرمز نشان داده شده است. محدودیت تحدب را نقض می کند، بنابراین ما این وجه انتخاب شده را حذف می کنیم. در شکل 2 e، می بینیم که وجه از صف وجه کاندید حذف شده است (زیرا با رنگ سبز نشان داده نمی شود). هنگامی که این فرآیند را تا زمانی که صف خالی شود تکرار می کنیم، می توانیم حداکثر بسط را مانند شکل زیر بدست آوریمشکل 2 f.
توجه داشته باشید که میتوانیم یک وجه سبز دیگر را انتخاب کنیم که محدودیت تحدب را به جای C در شکل 2 برآورده میکند.ج در این مورد، ممکن است ماکزیمم بسط متفاوتی به دست آوریم. ممکن است کسی بترسد که برخی از بسط های ماکزیمم ضروری را که برای پوشش چند ضلعی ورودی با حداقل هزینه ضروری هستند، از دست بدهیم. با این حال، اگر از تعداد کافی از وجوه بذر (احتمالاً همه وجوه) استفاده کنیم، این حداکثر انبساط ضروری احتمالاً به دست می آید. به عنوان مثال، با محدودیت تحدب، با شروع از هر یک از وجوه در آن، حداکثر بسط را می توان به دست آورد. یک انبساط حداکثری زیاد که برای پوشاندن فضا مفیدتر است، احتمالاً دارای تعداد زیادی وجوه در آن است. به این معنی که این انبساط حداکثری دارای وجوه بذری بیشتری است که می توان آن را گسترش داد. به عبارت دیگر، حتی اگر زمانی که انبساط را از یک وجه بذر شروع می کنیم، نتوانیم به حداکثر انبساط مطلوب خاصی دست یابیم،
اگرچه برای سادگی در اینجا یک انتخاب تصادفی داریم، میتوانیم از یک استراتژی خاص برای انتخاب جنبه در طول فرآیند بسط استفاده کنیم. به عنوان مثال، ما میتوانیم از یک استراتژی قطعی استفاده کنیم که یک بسط حداکثر منحصر به فرد را از یک وجه بذر ایجاد میکند، مانند انتخاب وجهی که یک لبه بلندتر را با بسط فعلی به اشتراک میگذارد. در حالی که گزینه های جایگزین زیادی وجود دارد، ما مطالعه گسترده در مورد استراتژی های توسعه را به عنوان کار آینده ترک می کنیم.
4.2. طراحی محدودیت
در این بخش فرعی، ما در مورد تابع بررسی محدودیت الگوریتم 1 در بخش 4.1 بحث می کنیم . همانطور که اشاره کردیم، حداکثر بسط های حاصل، و همچنین نتایج پوشش و پارتیشن بندی، به محدودیت داده شده بستگی دارد. بنابراین، طراحی یک محدودیت که متناسب با نیاز برنامه هدف باشد، مهم است. به عنوان مثال، ما سه محدودیت ساده را در این بخش ارائه می کنیم که انتظار می رود در بسیاری از برنامه ها به طور مکرر مورد استفاده قرار گیرند. ما همچنین برخی از ترفندها را ارائه می کنیم که به طور موثر عملکردهای بررسی محدودیت را ارزیابی می کنند، که در شکل 3 نشان داده شده است .
4.2.1. محدودیت برد
ابتدا یک تابع بررسی محدودیت f برای محدودیت محدوده طراحی می کنیم. به یاد بیاورید که f سه آرگومان می گیرد: seed facet s ، بسط جریان E ، و facet t برای اضافه کردن، و بررسی می کند که آیا وقتی t را به E اضافه می کنیم، محدودیت داده شده را نقض نمی کند .
از آنجایی که قبلاً چند ضلعی ورودی را مثلث کرده ایم، t یک مثلث است و دو رأس آن در مرز بسط جریان E قرار دارند . بنابراین کافی است بررسی کنیم که آیا راس دیگری که در قسمت بیرونی E قرار دارد در محدوده محدود r از s قرار دارد یا خیر . با قرار دادن مرکز صفحه s به عنوان مرکز محدوده تحت پوشش، می توانیم تابع بررسی را تعریف کنیم. fدامنهبه شرح زیر است:
که در آن، v راس t است که در قسمت بیرونی E قرار دارد ، r محدوده محدود شده است.
4.2.2. محدودیت دید
محدودیت دید، انبساط حاصل را وادار می کند تا از یک نقطه خاص در داخل وجه بذر قابل مشاهده باشد. برای سادگی، از مرکز وجه دانه برای بررسی دید استفاده می کنیم. ما باید تابع بررسی محدودیت را پیاده سازی کنیم fدر مقابل(س،E،تی)برای تعیین اینکه آیا E∪{تی}از مرکز c مثلث s قابل مشاهده است .
به یاد بیاورید که E از s و یک یال t ، مثلاً منبسط شده استتوv¯، در مرز E و از c قابل مشاهده است . اجازه دهید راس دیگر t را با w نشان دهیم . سپس ما می توانیم آن را ببینیم E∪{تی}از c قابل مشاهده است اگر و فقط اگر دو بخش باشد توv¯و جw¯در یک نقطه قطع می شود
تابع حاصل fدر مقابلرا می توان به صورت زیر تعریف کرد:
جایی که تو،vرئوس روی مرز E ، w راس t است که در قسمت بیرونی E قرار دارد ، و c مرکز s است .
4.2.3. محدودیت تحدب
با محدودیت تحدب، بسط های حاصل به چند ضلعی محدب محدود می شوند. هنگامی که یک مثلث را از چند ضلعی بسط فعلی منبسط می کنیم، دو رأس مثلث در مرز چند ضلعی بسط فعلی قرار دارند. باید بررسی کنیم که آیا با وارد کردن راس دیگر مثلث در وسط لبه، زوایای مقعر با چند ضلعی ایجاد می شود یا خیر. اجازه دهید تو،vاین دو راس با چند ضلعی بسط فعلی و مثلثی که باید اضافه شود مشترک باشند و راس دیگر مثلث با w نشان داده شود . همانطور که در شکل 3 c نشان داده شده است ، رئوس قبلی و بعدی u و v به ترتیب با x و y نشان داده می شوند. پس از افزودن مثلث به چند ضلعی بسط، چند ضلعی حاصل دارای دنباله ای از رئوس متوالی است. ایکس→تو→w→v→yخاکستر نشان داده شده در شکل 2 ج. برای بررسی تحدب، تعیین اینکه آیا کافی است ∠(ایکستوw)≤180∘و ∠(wvy)≤180∘. حالا تابع checking را تعریف می کنیم fcvxبرای تحدب به صورت زیر:
که در آن u و v رئوس مشترک E هستند ، و w رأس دیگر مثلث t برای جمع کردن است، و x (و y ) رأس قبلی (و بعدی) u (و v ، به عبارت دیگر) است.
5. پوشش مشکلات
در این بخش برنامه خطی باینری را برای مسئله پوشش ارائه می کنیم. هدف این است که چند ضلعی ورودی را با استفاده از بسط هایی که در بخش قبل محاسبه کردیم، پوشش دهیم.
5.1. تعریف مشکل
ما به طور رسمی مشکل را به صورت زیر تعریف می کنیم. به یاد بیاورید که ما یک مجموعه داریم ایکس={ایکسمن}از بسط های محاسبه شده در بخش قبل با گسترش وجوه مجاور از هر وجه دانه. ما میتوانیم ترکیبی از نواحی منبسط شده را پیدا کنیم که اتحادیه آنها هر وجهی از چند ضلعی مثلثی زیرین را شامل میشود:
تعریف 3 ( جلد ) .
یک مجموعه داده شده است ایکس={ایکسمن⊂تی}انبساط یک چند ضلعی مثلثی تی، یک مجموعه سی⊂ایکسپوششی است از تیاگر ⋃ج∈سیج=تی.
در مسئله حداقل پوشش، از ما خواسته می شود که پوششی با حداقل کاردینالیته پیدا کنیم.
تعریف 4 (حداقل مشکل پوشش) .
حداقل مشکل پوشش (تی،ایکس)می خواهد پوششی پیدا کند سیاز تیزیر ایکسبه طوری که |سی|≤|سی”|برای هر پوشش سی”.
در برخی از برنامه ها تعداد دستگاه ها محدود است به طوری که از ما خواسته می شود مکان آنها را پیدا کنیم تا فضای مورد نظر را تا حد امکان پوشش دهیم. با توجه به یک زیر مجموعه سیاز مجموعه گسترش ایکس={ایکسمن}، می توانیم مساحت مربوطه را با جمع مساحت وجوه مثلثی در اتحاد آن اندازه گیری کنیم ⋃ج∈سیج. با این معیار می توان مشکل پوشش حداکثر را به صورت زیر تعریف کرد.
تعریف 5 (مشکل حداکثر پوشش) .
مشکل حداکثر پوشش (ایکس،متر)می خواهد زیر مجموعه ای را پیدا کند سی⊂ایکسکاردینالیتی m به طوری که هیچ زیر مجموعه ای از اندازه-m وجود ندارد سی”⊂ایکسکه مساحت متناظر آن بیشتر از سی‘s
شکل 4 مشکلات پوشش حداقل و حداکثر پوشش را نشان می دهد. نقطه ها جنبه ها را نشان می دهند و هر وجه با حداکثر گسترش خود با محدودیت دید همراه است. در مسئله حداقل پوشش، ما باید حداقل تعداد وجوه را انتخاب کنیم تا کل چند ضلعی را با حداکثر بسط آنها پوشش دهیم. ما میتوانیم دو نقطه سبز را در شکل 4 a انتخاب کنیم، که هر کدام به ترتیب با انبساطهایی همراه هستند که به ترتیب با آبی و زرد نشان داده شدهاند. در مسئله پوشش حداکثر، تعداد وجوه بذر محدود می شود. در این مثال، فرض کنید ما مجاز به انتخاب تنها یک جنبه هستیم. هنگامی که وجه نشان داده شده با نقطه طمع در شکل 4 ب را انتخاب می کنیم، می توانیم 70٪ از چند ضلعی را پوشش دهیم که نتیجه مطلوب است.
5.2. فرمول های برنامه ریزی خطی باینری
اکنون آماده ارائه فرمول های دو مسئله فوق الذکر با استفاده از برنامه ریزی خطی باینری هستیم.
مشکل حداقل پوشش: متغیرهای باینری را تعریف می کنیم بمنکه نشان دهنده گسترش است ایکسمن∈ایکسانتخاب شده است. یک جنبه تی∈تیحداقل با یک بسط پوشش داده شده است. به عبارت دیگر، برای هر تی∈تی، باید من وجود داشته باشد که بمن=1و تی∈ایکسمن. از آنجایی که می خواهیم تعداد بسط ها را به حداقل برسانیم، در نهایت برنامه خطی باینری زیر را به دست می آوریم:
مشکل حداکثر پوشش: به طور مشابه، متغیرهای باینری بمننشان می دهد ایکسمن∈ایکسانتخاب شده است. مجموعه دیگری از متغیرهای باینری را معرفی می کنیم آjبرای نشان دادن یک وجه تیj∈تیحداقل توسط یکی پوشش داده شده است ایکسمن. ما می خواهیم مجموع مساحت وجوه پوشیده شده را به حداکثر برسانیم و برنامه خطی باینری زیر را داریم:
شکل 5 فرمولاسیون را نشان می دهد. هر جنبه تیjبا وجوه مرتبط است تیمنکبه طوری که حداکثر انبساط ایکسمنککه وجه بذر آن است تیمنکشامل وجه است تیj. در حداقل مشکل پوشش، حداقل یکی از تیمنکباید انتخاب شود در حالی که تعداد وجوه انتخاب شده به حداقل برسد. در مسئله پوشش حداکثر، مجموع وزنی وجوه پوشش داده شده باید حداکثر شود.
5.3. نمونه پوشش
در این بخش، چندین نتیجه از آزمایشهای خود را ارائه میدهیم تا نشان دهیم چگونه نتایج متفاوتی توسط تنظیمات مختلف تولید میشوند. همانطور که در شکل 6 الف نشان داده شده است، از طبقه یک ساختمان در محوطه دانشگاه خود استفاده کردیم و مثلث ریز دانه آن در شکل 6 ب نشان داده شده است. ما وظیفه پوششی را که قبلاً توضیح داده شد در این چند ضلعی ورودی انجام دادیم.
شکل 7 الف نتایج حداقل تعداد پوشش ها را با محدودیت های مختلف نشان می دهد: دید و برد. ما برنامهریزی خطی باینری را برای حل مسئله پوشش حداقل و مسئله پوشش حداکثر تعریف شده در بخش فرعی قبل اعمال کردیم. نقاط قرمز مرکز وجوه دانه ای را نشان می دهد که برای پوشاندن چند ضلعی ورودی انتخاب شده اند. از این نقاط می توان به عنوان محل واقعی سنسورها و دوربین های نظارتی استفاده کرد.
شکل 7 ب حداکثر پوشش را با تعداد محدودی دستگاه نشان می دهد. مناطقی که با خاکستری رنگ شده اند، ناحیه بدون پوشش را نشان می دهند. این مشکل خاص را می توان برای چنین برنامه هایی مانند قرار دادن نقطه دسترسی Wi-Fi با تعداد محدودی دستگاه و قرار دادن دوربین نظارتی با تعداد محدودی دوربین استفاده کرد.
5.4. کاربرد: مشکل قرار دادن دستگاه
مشکل قرار دادن دستگاه، کاربرد مستقیم مشکل پوشش است. ما باید موقعیتهای بهینه دستگاههایی را که دارای ناحیه مؤثر محدودی هستند، تعیین کنیم. در مسئله حداقل پوشش، باید تعداد دستگاه ها را برای پوشش کل فضا (چند ضلعی ورودی) به حداقل برسانیم. از طرفی در مشکل پوشش حداکثری تعداد محدودی دستگاه داریم و از ما خواسته می شود تا حد امکان فضا را با استفاده از آنها پوشش دهیم. بسته به ویژگی های یک منطقه موثر از دستگاه ها، می توانیم محدودیت های مناسب آنها را طراحی کنیم. جدول 2نمونه هایی از محدودیت ها را با توجه به ویژگی های دستگاه نشان می دهد. برای مثال، میتوانیم از محدودیت بردی که قبلاً ارائه کردهایم برای دستگاههایی استفاده کنیم که میتوانند سیگنالها را در محدوده محدودی ارسال کنند و سیگنالها نمیتوانند نفوذ کنند اما میتوانند دیوارها را منحرف کنند. برای دوربین های نظارتی، اگر جهت و وضوح آن را در نظر نگیریم، می توانیم از محدودیت دید استفاده کنیم. دوربین های همه جهته با وضوح محدود را می توان با ترکیب دو محدودیت دید و برد مدل کرد. اگر میدان دید را در نظر بگیریم، ممکن است محدودیت جدیدی با توجه به جهت و زاویه طراحی کنیم.
6. مشکلات پارتیشن بندی
6.1. تعاریف مسئله
پارتیشن بندی یکی از موثرترین روش ها برای نمایش خود فضا و اطلاعات مربوط به آن است. بسیاری از ساختارهای داده مکانی و روششناسی برای پارتیشن بندی فضا پیشنهاد شدهاند. تفاوت بین مشکل پوشش و مشکل پارتیشن بندی در این است که هر وجه باید دقیقاً توسط یک بسط در مسئله پارتیشن بندی پوشش داده شود. به عنوان مثال، هیچ همپوشانی بین بسط های انتخابی مجاز نیست. در حالی که ما حداکثر بسط ها را محاسبه کرده ایم، صرفاً انتخاب برخی از بسط های حداکثری که چند ضلعی هدف را پوشش می دهند منجر به همپوشانی می شود. برای جلوگیری از همپوشانی، باید به درستی یک بسط برای هر وجه مشخص کنیم، اگر وجه را بتوان با تعداد زیادی از بسط های انتخابی پوشش داد.
شکل 8 تفاوت بین مشکلات پوشش و پارتیشن بندی را نشان می دهد. در مسئله پوشش، یک وجه را می توان با بیش از یک بسط پوشش داد. در شکل 8الف، دو وجه در نقطه تقاطع دو راهرو توسط دو انبساط پوشیده شده است. با این حال، مشکل پارتیشن اجازه نمی دهد که هیچ جنبه ای با بیش از یک بسط پوشش داده شود. برای هر یک از وجوهی که می توانند توسط بسط های زیادی پوشش داده شوند، باید تصمیم بگیریم که کدام بسط آن را پوشش دهد. این تصمیم گسترش تحت پوشش ممکن است گسترش دیگری را جدا کند. از آنجایی که تعداد پارتیشنها را با تعداد وجههای بذر انتخابی کنترل خواهیم کرد، قسمت جدا شدهای که دارای وجه بذری نیست نباید تحت پوشش انبساط قطع شده در نظر گرفته شود و وجههای موجود در آن باید با برخی انبساطهای دیگر پوشانده شوند. ما باید این اتصال را در مسئله پارتیشن بندی در نظر بگیریم که ما را به مفهوم زیر هدایت می کند.
تعریف 6 (بسط جزئی متصل) .
با توجه به بسط X از یک وجه دانه s، یک زیر مجموعه Y⊂ایکسانبساط جزئی متصل آن است اگر س∈Yو اتحاد هندسی وجوه yمن∈Yیک چند ضلعی واحد تشکیل دهید .
ما فرآیند تصمیمگیری در مورد بسط پوششدادهشده یک وجه را بهعنوان گرفتن زیرمجموعهای از هر یک از بسطهای انتخابی در نظر میگیریم، به طوری که هر بسط زیر مجموعهای به هم متصل شده و شامل وجه اولیه خود است. به عنوان مثال، اگر ما یک وجه با حداکثر بسط آن X مانند شکل 9 a داشته باشیم، ناحیه نشان داده شده با A در شکل 9 b، انبساط جزئی متصل آن است. اگر از A برای پوشش چند ضلعی استفاده کنیم ، قسمت باقیمانده از بسط حداکثری اصلی باید توسط بسط های جزئی متصل سایر بسط ها پوشانده شود. B یک بسط جزئی متصل به X نیست زیرا حاوی وجه دانه نیست که با یک نقطه سبز در نشان داده شده است.شکل 9 الف. آ∪ببسط جزئی متصل X نیست زیرا متصل نیست.
اکنون میتوانیم پارتیشنی را در نظر بگیریم که با انتخاب برخی بسطها و زیرمجموعهسازی آنها بهگونهای که هر یک از این مجموعههای وجهی ناپیوسته دارای وجه دانه مربوطه و وجوه متصل به آن باشد، به دست میآید:
تعریف 7 (پارتیشن القایی) .
یک مجموعه داده شده است ایکسانبساط یک چند ضلعی مثلثی تی، یک مجموعه Y={Y1،⋯،Yمتر}گفته می شود پارتیشن القایی اگر Yمن∩Yj=ϕبرای همه من≠jو ⋃منYمن=تی.
بر اساس این تعریف، میتوان مسئله حداقل پارتیشن و مشکل پوشش حداکثر را به صورت زیر تعریف کرد:
تعریف 8 (حداقل مشکل پارتیشن) .
حداقل مشکل پارتیشن (تی،ایکس)می خواهد یک پارتیشن القایی پیدا کند Yاز ایکسبا حداقل کاردینالیته .
تعریف 9 (مشکل پارتیشن حداکثر پوشش) .
مشکل پارتیشن پوشش حداکثر (ایکس،متر)می خواهد یک پارتیشن القایی پیدا کند Yاز ایکسبه طوری که |Y|=مترو پارتیشن القایی وجود ندارد Y”اندازه m به گونه ای که حوزه(Y)<حوزه(Y”)، جایی که حوزه(·)مجموع مساحت وجوه در مجموعه است .
6.2. برنامه خطی باینری برای موارد عمومی
ما ابتدا برنامه خطی باینری را ارائه می کنیم که می تواند بدون هیچ محدودیتی تحت چارچوب پیشنهادی استفاده شود. پس از آن، فرمول سادهتری را برای یک مورد خاص که در آن انبساطها دارای خاصیت خاصی به نام غیر چرخهای هستند در زیربخش زیر پیشنهاد میکنیم.
اجازه دهید بj(من)متغیرهای باینری باشند که یک وجه را نشان می دهند تیj∈تیتوسط یک گسترش پوشیده شده است ایکسمن∈ایکس. بمن(من)یک وجه بذر با انبساط متناظر آن است و به تنهایی می تواند 1 باشد. برای سایر متغیرها بک(من)برای ک≠من، مقدار آن را فقط در صورتی می توان روی 1 تنظیم کرد که j وجود داشته باشدتیjیک وجه مجاور است تیکو بj(من)=1. این کار به گونه ای عمل می کند که مانند ما دوباره نواحی را از وجه دانه به وجوه مجاور آن گسترش می دهیم. برای توصیف این، اجازه دهید wj،ک(من)همچنین متغیرهای باینری برای نشان دادن اینکه آیا جنبه تیjمی تواند بر مجاور آن تأثیر بگذارد تیکدر مورد گسترش ایکسمن; به عبارت دیگر، برای هر ک≠من، بک(من)فقط اگر می تواند 1 باشد بj(من)=1و wj،ک(من)=1.
جایی که آ(ک)مجموعه همه جفت ها است (j،ک)به طوری که تیjو تیکوجوه مجاور هستند
شکل 10 برنامه خطی باینری ارائه شده را نشان می دهد. هر جنبه تیjمتغیر دارد بj(من)اگر بتوان آن را با انبساط حداکثری که وجه بذر آن است پوشاند تیمن. برای وجوه مجاور تیjو تیک، متغیر wک،j(من)با یک لبه از مرتبط است تیکبه تیj. تنظیم می شود فقط اگر بک(من)تنظیم شده است، و بj(من)تنها در صورتی می توان تنظیم کرد که حداقل یک متغیر برای یال های ورودی آن تنظیم شده باشد.
اولین محدودیت (∑منبj(من)=1)هر وجه را وادار می کند که دقیقاً به یک بسط تعلق داشته باشد تا بسط های انتخاب شده پارتیشنی از چند ضلعی ورودی را تشکیل دهند. محدودیت دوم (wj،ک(من)≤بj(من))در مورد لبه خروجی است. wj،ک(من)را می توان روی 1 تنظیم کرد فقط اگر بj(من)به طوری که بj(من)مقادیر ‘s فقط در امتداد متغیرهای فعال شده می توانند منتشر شوند. سومی (∑(j،ک)∈آ(ک)wj،ک(من)≥بک(من))یک محدودیت در لبه های ورودی از جنبه های غیر دانه است. بک(من)تنها در صورتی می توان روی 1 تنظیم کرد که حداقل یکی از لبه های ورودی آن فعال باشد. دو قید آخر ( ∑jایکسj،ک(من)+yک،j(من)<2-ϵو ایکسj،ک(من)+yک،j(من)=2wj،ک(من)) برای جلوگیری از چرخه های جریان تشکیل شده توسط wj،ک(من). بدون این محدودیت ها، وقتی wj،ک(من)یک چرخه را تشکیل می دهد، محدودیت های فوق را نقض نمی کند (به جز موارد بررسی چرخه) حتی اگر جنبه seed از چرخه جدا شده باشد، که ممکن است یک پارتیشن نامطلوب ایجاد کند.
اگرچه این برنامهنویسی خطی باینری از نظر تئوری میتواند راهحلی را برای مسئله حداقل پارتیشن بیابد، به ویژه با محدودیتهای حذف چرخه، هزینه زیادی را میطلبد. اگر تضمین شود که هیچ چرخه ای در بسط وجود ندارد، می توانیم فرمول را بیشتر ساده کنیم.
6.3. برنامه خطی باینری ساده تر برای موارد خاص: بسط غیر چرخه ای
قبل از ایجاد راهحلی برای مواردی که هیچ چرخهای در بسطها ندارند، اجازه دهید از نمودار زیربنایی آن که توسط مجاورت وجوه مثلثی که یک بسط را تشکیل میدهند، شروع کنیم.
تعریف 10 (گراف مجاورت) .
نمودار مجاورت جیمناز یک گسترش ایکسمنیک گراف مسطح است که مجموعه گره آن است ایکسمن، و پیوندها بین دو گره ایجاد می شوند تیjو تیکاگر وجوه متناظر دو گره دارای یک لبه باشند .
تعریف 11 (انبساط غیر چرخه ای) .
یک بسط ایکسمناگر نمودار مجاورت آن یک درخت باشد، غیر چرخه ای است .
به یاد بیاورید که زمانی که چند ضلعی ورودی مثلثی باشد، فقط مرز آن را محدود کردیم. بنابراین تمام رئوس وجوه مثلثی در مرز چند ضلعی ورودی قرار دارند. این ما را به این واقعیت هدایت می کند که برای یک چندضلعی ساده بدون سوراخ، نمودار مجاورت مثلث آن یک درخت است. از زمان گسترش ایکسمنزیرمجموعه ای از وجوه مثلثی است، نمودار مجاورت آن اساساً زیردرختی از درخت کل چند ضلعی است که طبیعتاً ما را به موارد زیر می رساند:
مثال 1 (چند ضلعی ساده) .
هر بسط یک چند ضلعی ساده غیر حلقوی است .
حتی اگر چند ضلعی ورودی دارای سوراخ هایی در داخل خود باشد، رئوس وجوه مثلثی هنوز در مرزهای بیرونی یا داخلی قرار دارند، نه در داخل چند ضلعی. محدودیت (به عنوان مثال، تحدب و دید) مورد استفاده در به دست آوردن انبساط می تواند آنها را غیر چرخه ای کند. به عنوان مثال، هنگامی که بسط ها را با محدودیت دید ذکر شده در ( 2 ) محاسبه می کنیم، نمودار مجاور حاصل نمی تواند یک چرخه داشته باشد. هنگامی که یک گره به بیش از یک گره فرزند منشعب می شود، باید مرزی از چند ضلعی در تقاطع وجود داشته باشد. این بدان معناست که خط دید از مرکز وجه بذر توسط این مرز مسدود شده است و مسیرهای منشعب دیگر نمی توانند به یکدیگر متصل شوند.
مثال 2 (محدودیت دید) .
هر گونه گسترش با محدودیت دید غیر چرخه ای است .
از آنجایی که قید تحدب قید قویتری نسبت به دید است، برای آن نیز اعمال میشود.
مثال 3 (محدودیت تحدب) .
هر انبساط با محدودیت تحدب غیر حلقوی است .
اجازه دهید ایکسمن∈ایکسحداکثر گسترش از یک جنبه باشد تیمن∈تی. اجازه دهید فرض کنیم که همه بسط های داده شده غیر چرخه ای هستند. سپس نمودار مجاورت بسط به صورت درختی نمایش داده می شود. اجازه دادن تیمنباشد ریشه درخت مشتق شده از ایکسمن، می توانیم مجموعه لبه را تعریف کنیم Eمناز این درخت ریشه دار:
اکنون ما آماده هستیم تا برنامه خطی باینری را برای مسائل پارتیشن فرموله کنیم.
حداقل مشکل پارتیشن: اجازه دهید بj(من)متغیرهای باینری باشد که نشان می دهد تیjبرای گسترش فعال می شود ایکسمن. این فعال سازی در امتداد لبه ها منتشر می شود Eمن. جنبه بذر تیمنگره ریشه است و هیچ لبه ورودی ندارد. بدین ترتیب بمن(من)می تواند به خودی خود فعال شود. وجوه باقی مانده در بسط ایکسمنفقط در صورتی فعال می شود که وجه والد آن روی درخت ریشه دار تشکیل شده توسط Eمنفعال شده. هر وجه باید فقط برای یک بسط فعال شود. اکنون فرمول زیر را داریم:
مشکل پارتیشن حداکثر پوشش: برای مسئله پارتیشن پوشش حداکثر، میتوانیم به راحتی فرمول را با اعمال تغییرات کوچک از برنامه خطی باینری قبلی استخراج کنیم. بدیهی است که جایگزین تابع هدف برای به حداکثر رساندن مجموع وجوه فعال شده است. برای اولین محدودیت ( ∑منبj(من)≤1)، معادله را با یک نامساوی جایگزین می کنیم زیرا لازم نیست همه وجوه فعال شوند. در نهایت، با اضافه کردن محدودیت ( ∑منبمن(من)≤متر) در مورد تعداد پارتیشن ها فرمول را کامل می کند:
6.4. نمونه های پارتیشن بندی
شکل 11 حداقل تعداد پارتیشن های محاسبه شده با روش پیشنهادی را نشان می دهد. در مقایسه با حداقل پوشش نشان داده شده در شکل 7 ، مناطقی که توسط یک وجه بذری پوشیده شده اند کاملاً به هم متصل شده اند. ما وجه دانه انتخاب شده را با نقاط قرمز برای مورد محدودیت محدوده نشان می دهیم. با فرض اینکه ما از این روش برای قرار دادن نقطه دسترسی Wi-Fi استفاده می کنیم، به نظر می رسد که توضیحات شهودی تری برای یافتن اینکه کدام نقطه دسترسی Wi-Fi یک منطقه خاص را پوشش می دهد در مقایسه با حداقل نتیجه پوشش ساده، که ممکن است شامل بسیاری از مناطق ناپیوسته اختصاص داده شده باشد، ارائه می دهد. به یک نقطه دسترسی واحد میتوانیم مشاهده کنیم که پارتیشنبندی حاصل احتمالاً واحدهای معنایی واقعی ساختمان مانند اتاقها و راهروها را نشان میدهد.
6.5. کاربرد در مسئله برنامه ریزی مسیر
6.5.1. برنامه ریزی مسیر با پارتیشن محدب
ما روشی را برای یافتن مسیر در یک چند ضلعی که به پارتیشن های محدب تجزیه شده است ارائه می کنیم. اگرچه مسیر حاصل کوتاهترین مسیر بهینه نیست، اما روشی سازشدهنده برای نمایش ساختار گراف زیربنایی برای مسیریابی به شیوهای کارآمد از نظر فضا است، همانطور که به طور تجربی در بخش 7 نشان خواهیم داد .
ایده اصلی ساده است. ما کوتاه ترین مسیر را در سطح پارتیشن پیدا می کنیم، سپس مسیر واقعی را محاسبه می کنیم. این استراتژی مسیریابی سلسله مراتبی به طور گسترده ای مورد استفاده قرار می گیرد، به ویژه برای هوش مصنوعی بازی اگرچه جزئیات خاص آنها متفاوت است. ما از استراتژی زیر برای مکان یابی مسیر واقعی استفاده می کنیم: حرکت رو به جلو تا نزدیکترین نقطه به سلول بعدی. شکل 12این رویه را نشان می دهد. این بر این واقعیت استوار است که کوتاه ترین مسیر بین هر دو نقطه در یک چند ضلعی محدب، خط مستقیم است. ممکن است شخصی بخواهد از مرکز سلولها برای مسیر واقعی استفاده کند، اما صرفاً اتصال مرکز سلولهای همسایه در مسیر یافت شده از نمودار مجاورت، تضمین نمیکند که بخشهای خط مسیر واقعی در چند ضلعی ورودی قرار دارند. علاوه بر این، در ابتدا و انتهای مسیر حاصل، اتصال نقاط شروع/هدف واقعی به مرکز سلول های اول و آخر در طول مسیر ممکن است باعث ایجاد یک مسیر طولانی غیر ضروری شود. اگرچه روش پیشنهادی ما برای محاسبه مسیر واقعی را میتوان بیشتر بهبود بخشید، سادهترین نسخه آن را ارائه میکنیم و بحث بیشتری را در کار آینده باقی میگذاریم.
روش کار دقیق در الگوریتم 2 توضیح داده شده است. فرض کنید مجموعه ای به ما داده شده است Πاز چند ضلعی های محدب و نقاط پرس و جو s و t که به ترتیب نقطه شروع و مقصد را نشان می دهند. در مرحله اول نمودار را می سازیم جی=(V،E)که در آن مجموعه V از گره ها نشان دهنده چند ضلعی های پارتیشن بندی شده است، و مجموعه E از پیوندها مجاورت آنها را نشان می دهد. سپس کوتاه ترین مسیر را در این نمودار پیدا می کنیم. اجازه دهید u و v گره های مربوط به پارتیشن ها باشند س∈پتوو تی∈پv. کوتاه ترین مسیر در نمودار دنباله را به ما می دهد (تو=w1،w2،⋯،wn=v)از گره ها، که به معنی پارتیشن ها است (پwمن)مسیر حاصل باید از آن عبور کند. اکنون مسیر دقیق را محاسبه می کنیم (س=پ1،پ2،⋯،پn،پn+1=تی)از نظر نقاط هندسی تغییر ناپذیر در محاسبه مسیر دقیق این است پمنمتعلق به پارتیشن i-ام استپwمندر مرحله I ما نقطه را محاسبه می کنیم پمن+1برای رسیدن به پارتیشن بعدی پwمن+1. این نکته پمن+1نقطه ای در تقاطع دو پارتیشن است پwمنو پwمن+1، که یک پاره خط است و به سادگی می توانیم این نقطه را با محاسبه نزدیکترین نقطه روی پاره خط از پمن. زیرا این هر دو نکته است پمنو پمن+1داخل چند ضلعی محدب هستند پwمن، قطعه ای که دو نقطه را به هم وصل می کند به طور طبیعی در داخل است پwمن. در مرحله نهایی، ما داریم پnدر مرز پwnکه حاوی نقطه مقصد t نیز می باشد . اتصال دو نقطه پnو t مسیر حاصل را کامل می کند.
الگوریتم 2 پیدا کردن یک مسیر در چند ضلعی محدب تجزیه شده |
1: روش یافتن ( Π: پارتیشن محدب یک چند ضلعی، s : نقطه شروع، t : مقصد) |
2: G را با توجه به مجاورت چند ضلعی ها در پارتیشن محاسبه کنیدΠ. |
3: گره های u و v را به ترتیب مربوط به s و t پیدا کنید . |
4: کوتاه ترین مسیر را پیدا کنید (تو=w1،w2،⋯،wn=v)در G . |
5: پ←س |
6: آر←[ ] |
7: برای من∈{1،⋯،n-1} انجام دادن |
8: ل←پwمن∩پwمن+1 |
9: نزدیکترین نقطه q را در l از p پیدا کنید . |
10: R.add (Line( پ،q)) |
11: پ←q. |
12: پایان برای |
13: R .add(Line( پ،تی)) |
14: بازگشت R |
15: پایان مراحل ) |
اجازه دهید Πمجموعه ای از m چند ضلعی های محدب باشد که توسط وظیفه پارتیشن بندی تجزیه می شوند. وقتی نمودار مجاورت G را از آن محاسبه می کنیمΠدر خط 2، میتوانیم مجاورت دو پارتیشن (سلول) را با بررسی اینکه آیا هر راس مشترکی دارند یا خیر، تعیین کنیم. با استفاده از جدول هش کلید شده با شاخص راس، طول می کشد O(v)زمانی که v مجموع تعداد رئوس چند ضلعی های تقسیم شده است. یافتن گره های مربوطه در خط 3 نیز طول می کشد O(v)زمان، زیرا ما می توانیم یک پرس و جو نقطه در چند ضلعی را در زمان خطی به تعداد رئوس یک چند ضلعی انجام دهیم. با نشان می دهیم f(Π)زمان صرف شده برای یافتن کوتاهترین مسیر در نمودار مجاورت القا شده از Π. اگر از الگوریتم Dijkstra برای یافتن کوتاه ترین مسیر استفاده کنیم، f(Π)=O(مترال جیمتر)، زیرا پیچیدگی زمانی الگوریتم Dijkstra است O(ه+مترال جیمتر)که در آن e و m تعداد یال ها و رئوس نمودار داده شده است و ه≤3v-6به دلیل مسطح بودن برای هر تکرار حلقه، محاسبه مسیر واقعی اجرا می شود O(n)زمانی که n طول مسیر در نمودار مجاورت است. زیرا n=O(متر)، قسمت حلقه وارد می شود O(متر)زمان. با کنار هم قرار دادن همه اینها، الگوریتم 2 می گیرد O(v+مترال جیمتر)که در آن m تعداد چند ضلعی ها در آن است Πو v مجموع تعداد رئوس چند ضلعی در است Π.
6.5.2. سازگاری IndoorGML
به عنوان یک استاندارد بین المللی منتشر شده توسط Open Geospatial Consortium، IndoorGML یک مدل تبادل داده به خوبی تعریف شده برای فضاهای داخلی ارائه می دهد [ 19 ]. مدل فضا را به عنوان مجموعه ای از فضاهای فرعی غیر همپوشانی که اساساً پارتیشن هایی از فضای زیرین هستند، اتخاذ می کند. هر پارتیشن هندسی یا معنایی به عنوان یک فضای سلولی به نام CellSpace مدلسازی میشود و CellSpaceBoundary یک هندسه مرزی مانند درها و پنجرههای یک CellSpace را نشان میدهد. IndoorGML به عنوان فضای دوگانه Poincaré، اطلاعات توپولوژیکی را با استفاده از ساختار گراف با حالت برای گره ها و Transition برای پیوندها توصیف می کند.
روش مسیریابی پیشنهادی مبتنی بر پارتیشن بندی تحدب با IndoorGML سازگار است در حالی که سایر روشهای نمایهسازی معمولا نمودارهای ناوبری را جدا از هندسه CellSpace نشان میدهند. در واقع، هر فضای پارتیشن بندی شده با محدودیت های دیگر مانند محدوده و دید را می توان به همان شکل نشان داد، اگرچه کاربرد آنها نامشخص است. جدول 3 مطابقت بین شاخص مبتنی بر پارتیشن برای مسیریابی و مفاهیم IndoorGML را نشان می دهد.
شکل 13 نمونه ای از نمایش فضاهای پارتیشن بندی شده با استفاده از IndoorGML را نشان می دهد. برای هر فضاهای سلولی معنایی، میتوانیم آن را در زیرمنطقههای محدب قرار دهیم. هر یک از زیرمنطقه ها به عنوان یک CellSpace نشان داده می شوند و مرزهای مشترک آنها باید CellSpaceBoundarys باشد. گره ها و لبه ها در گراف مجاورت پارتیشن ها از نظر مفاهیم IndoorGML با حالت ها و انتقال ها مطابقت دارند. به منظور ایجاد ارتباط بین فضای پارتیشن بندی شده جدید ایجاد شده و فضای ساختمان زیربنایی، ما بین لایه های اصلی و ایالت های زیرمنطقه های تقسیم بندی شده آن ارتباط بین لایه ها برقرار می کنیم.
7. نتایج تجربی
ما آزمایش هایی را با تنظیمات مختلف انجام دادیم تا اثربخشی چارچوب خود را به روش کمی ارزیابی کنیم. ما وظایف پوشش و پارتیشن بندی را با چارچوب خود با استفاده از داده های مصنوعی تولید شده انجام دادیم و آنها را با چندین روش پایه مقایسه کردیم.
7.1. تنظیمات
برای ارزیابی اثربخشی روش پیشنهادی به روش کمی، ما سه نوع مختلف از مجموعه داده های مصنوعی را همانطور که در شکل 14 توضیح داده شده است، ساختیم .
به یاد داشته باشید که مسائل پوشش و پارتیشن بندی به طور کلی مسائل NP-hard هستند، بنابراین دستیابی به راه حل بهینه غیرممکن است. این مجموعه دادههای مصنوعی به این منظور طراحی شدهاند که با آن بتوانیم به سادگی راهحلهای بصری را دریافت کنیم که حداقل به عنوان خطوط پایه امیدوارکننده هستند. نوع اول یک راهرو طولانی است که در شکل 14 نشان داده شده است . یک راهرو از تعداد کمی از بخش های کوتاه تراز محور تشکیل شده است. نوع دوم دارای راهروهای فرعی کوتاه اضافی به همراه یک راهرو اصلی طولانی است که در شکل 14 ب نشان داده شده است. نوع سوم دارای یک سالن در مرکز و چندین راهرو به صورت شعاعی است که در شکل 14 نشان داده شده است.ج ما آنها را با روش زیر تولید کردیم. برای نوع 1، ما 5 تا 8 قطعه تصادفی متصل به هم تراز محور با طول بین 9 متر تا 60 متر ایجاد کردیم، سپس یک عملیات بافر با 1.5 متر اعمال کردیم که یک راهروی طولانی به عرض 3 متر ایجاد می کند. برای نوع 2، ما 3 قطعه تصادفی متصل به هم تراز محور با طول بین 6 متر تا 60 متر تولید کردیم. سپس قطعاتی با طول از 6 متر تا 12 متر به عنوان شاخه های عمود بر قطعه اصلی ایجاد کردیم. سپس به همین ترتیب عملیات بافر را روی آنها اعمال کردیم. برای نوع 3، دایره ای به شعاع 6 متر ایجاد کردیم و آن را به بخش های خطی ساده کردیم. سپس شاخههایی با عرض 1 متر به طول بین 15 متر تا 30 متر ایجاد کردیم که از مرکز دایره به صورت شعاعی امتداد مییابد. ما برای هر نوع 100 نمونه تولید کردیم و آزمایشها را انجام دادیم تا بتوانیم با میانگینگیری از آنها، عملکرد را اندازهگیری کنیم. ما آنها را در قالب json ذخیره کردیم که به شرح زیر است:
{'راس': [[1.5،52.5]،[-40.2،52.5]،[-40.2،89.7]،[-6.6،89.7]، [-6.6،57.9]،
[19.2،57.9]، [19.2،60.9]، [-3.6،60.9]، [-3.6،92.7]، [-43.2،92.7]،
[-43.2،49.5]، [-1.5،49.5]، [-1.5،-1.5]، [1.5,-1.5]]،
«بخشها»: [[0،1]، [1،2]، [2،3]، [3،4]، [4،5]، [5،6]، [6،7]، [7، 8]، [8،9]، [10،11]،
[11،12]، [12،13]، [13،0]]،
"سوراخ":[]}
همه الگوریتم ها در پایتون 3 پیاده سازی شده اند. ما از بسته Shapely برای مدیریت هندسه مانند تولید داده های مصنوعی استفاده کردیم. ما از بسته مثلثی برای مثلث بندی دلونای محدود استفاده کردیم. ما از CBC (COIN-OR شاخه و Cut) به عنوان حلکننده برنامه خطی باینری ارائه شده توسط کتابخانه پالپ برای یافتن راهحل فرمول شرح داده شده در بخش 5 و بخش 6 استفاده کردیم.. هر یک از چهار مرحله به عنوان یک ماژول جداگانه پیاده سازی می شود و خروجی ماژول یک مرحله به عنوان ورودی ماژول مرحله بعدی آن مصرف می شود که شامل یک خط لوله از کل چارچوب است. هر ماژول آرگومان های خود را برای تنظیمات خاص می گیرد تا بتوانیم آنها را به صورت انعطاف پذیر با توجه به وظایف مورد نظر ترکیب کنیم. ما چندین آزمایش را بر روی تنظیمات مختلف در رابطه با مشکل قرار دادن دستگاه برای ارزیابی عملکرد وظیفه پوشش انجام دادیم. ما همچنین آزمایشی را در مورد مسئله برنامه ریزی مسیر به عنوان یک برنامه از کار پارتیشن بندی انجام دادیم.
7.2. نمونه برداری بذر
ما ابتدا آزمایشی را بر روی نمونه برداری از بذر انجام می دهیم که در بخش 4 مورد بحث قرار گرفت . از آنجایی که برای پوشاندن چند ضلعی ورودی نیازی به محاسبه حداکثر بسطها از بسیاری از وجوه بذر غیر ضروری نداریم، ممکن است یک استراتژی جایگزین انتخاب کنیم که بخشی از وجوه را به عنوان دانه انتخاب کند. آزمایش در این بخش نشان میدهد که چگونه عملکرد پوشش تحت تأثیر نسبت بخشهای بذر قرار میگیرد. ابتدا، کار حداقل پوشش را با تمام جنبهها به عنوان دانه انجام میدهیم تا حداقل تعداد k انبساط را برای پوشش راهحل ورودی با استفاده از چارچوب خود تعیین کنیم. ما انتخاب میکنیم ρnوجوه دانه که در آن 0<ρ≤1یک پارامتر و n تعداد تمام وجوه است و حداکثر بسط وجوه دانه انتخاب شده را محاسبه کنید. اگر فقط از بخشی از وجوه دانه (با حداکثر انبساط آنها) استفاده کنیم، تضمین نمی شود که تمام وجوه را حداقل بتوان با یکی از حداکثر انبساط وجوه دانه انتخابی پوشاند. اگرچه ممکن است از برخی اکتشافیها برای اجتناب از جنبههای کشف نشده استفاده کنیم، به عنوان مثال، استفاده از الگوریتمهای اکتشافی برای مسئله مجموعه ضربهای، ما از سادهترین استراتژی استفاده میکنیم که بهطور تصادفی وجوه اولیه را انتخاب میکند. در عوض، ما حداکثر وظیفه پوشش را با k روکش با وجوه دانه انتخاب شده انجام می دهیم. نتیجه نشان میدهد که در مقایسه با بهترین راهحلی که چارچوب میتواند ارائه دهد، چقدر میتواند چند ضلعی ورودی را با بخش کوچکی از وجههای دانه بپوشاند.
جدول 4 نتایج تجربی را نشان می دهد. مقادیر نسبت مساحت تحت پوشش با k را نشان می دهدبا دانه های نمونه برداری شده، مساحت کل چند ضلعی ورودی را پوشش می دهد. به عنوان مثال، زمانی که ما حداکثر پوشش را در مجموعه داده 1 با پوشش محدوده با استفاده از 10٪ از وجوه به عنوان دانه انجام می دهیم، می توانیم به طور متوسط 94.9٪ از چند ضلعی ورودی را پوشش دهیم. برای مواردی با محدودیت دید در مجموعه داده 3، میتوانیم پوششهای نسبتاً کمتری را مشاهده کنیم. در مجموعه داده 3، یک سالن بزرگ در مرکز وجود دارد. وجوه مثلثی در مرکز برای پوشاندن کل چند ضلعی مهم هستند زیرا یک وجه بذر در یک شاخه فقط از طریق آن شاخه قابل رویت است و نمی تواند به مرکز گسترش یابد. اگر برخی از وجوه در مرکز در انتخاب تصادفی وجوه دانه وجود نداشته باشد، در نتیجه پوشش را کاهش می دهد. با این وجود، میتوان مشاهده کرد که 90 درصد از چند ضلعیهای ورودی را میتوان تنها با 10 درصد از وجوهی که در تنظیمات دیگر بهعنوان دانه انتخاب میشوند، پوشانده است. یعنی می توانیم زمان محاسبه حداکثر بسط ها را کاهش دهیم. زمان حل برنامه خطی باینری را نیز می توان به دلیل کاهش تعداد پارامترهای فرمول برنامه کاهش داد. در حالی که ما فقط انتخاب تصادفی را بررسی کردیم، استراتژی بهتری برای انتخاب جنبه های دانه باید در کار آینده مورد توجه قرار گیرد.
7.3. مشکلات قرار دادن دستگاه
ما یک مشکل پوشش را با یک محدودیت شعاع مانند مسئله قرارگیری سنسور در نظر می گیریم. فضای هدف تقریباً به صورت خطی گسترش یافته است، بنابراین می توان انتظار داشت که تعداد تقریباً بهینه سنسورها با شعاع r فضا را پوشش دهند. ⌈ل/2r⌉که در آن l طول راهرو است، زیرا خط محور مرکزی چند ضلعی را با دایره هایی به شعاع r می پوشانیم . می توان با استفاده از محیط p چند ضلعی ورودی و عرض راهرو w تقریب زد : ل≈(پ-2w)/2. توجه داشته باشید که خط مبنا در واقع بهینه نیست زیرا ما فقط محور مرکزی چند ضلعی ورودی را در نظر می گیریم. در عوض، ما از این خط مبنا استفاده می کنیم تا به سادگی تعداد پوشش های مورد نیاز را تخمین بزنیم.
جدول 5 تعداد روکش های تولید شده با روش پیشنهادی را نشان می دهد. وقتی r کوچک است، به تعداد پوششهای بیشتری نسبت به خط پایه نیاز داریم. این به این دلیل است که یک راه حل واقعی باید نه تنها محور مرکزی بلکه کل ناحیه چند ضلعی را نیز پوشش دهد. وقتی r بزرگتر میشود، به تعداد پوششهای کمتری نیاز داریم، زیرا یک پوشش در گوشهای ممکن است بخش بزرگتری از محور مرکزی را در بر بگیرد. 2r.
همچنین میتوانیم محدودیت دید مانند مشکل گالری هنری را در نظر بگیریم. مشخص است که ⌊n/3⌋حفاظ ها در این مسئله کافی هستند [ 48 ]، اما تعداد بهینه محافظ ها همانطور که اشاره کردیم NP-Hard نشان داده شده است. با این حال، در این مجموعه داده، میتوان با قرار دادن یک محافظ در چندین گوشه به یک راهحل ساده فکر کرد تا هر محافظ بتواند دو بخش کوتاه را پوشش دهد. همانطور که می توان تعداد بخش ها را با استفاده از تعداد رئوس چند ضلعی ورودی محاسبه کرد (n-2)/2، تعداد نگهبانان خواهد بود (n-2)/4، که در آن n تعداد رئوس است. همانطور که در جدول 6 نشان داده شده است ، ما توانستیم تعداد بهینه حفاظ ها را برای پوشش چند ضلعی های ورودی نوع 1 بدست آوریم.
با مجموعه داده دوم که دارای تعدادی کریدور فرعی به همراه یک راهرو بلند اصلی است، حفاظ ها باید به درستی قرار داده شوند تا تمام راهروهای فرعی را پوشش دهند. اگر هیچ یک از دو راهرو فرعی از یکدیگر قابل مشاهده نباشند، به تعداد راهروهای فرعی به نگهبان نیاز داریم. همانطور که در جدول 6 نشان داده شده است ، مشاهده می کنیم که در مقایسه با خط پایه، به تعداد کمی محافظ کمتر نیاز است. این به این دلیل است که یک نگهبان می تواند در برخی موارد دو راهرو فرعی را پوشش دهد، به خصوص زمانی که آنها در گوشه ای قرار دارند.
برای مجموعه داده سوم که ساختاری ستاره ای شکل دارد، تنها به یک نگهبان در مرکز سالن نیاز داریم. با این حال، ما از مرکز وجه بذر برای بررسی محدودیتها در طول محاسبه انبساطهای حداکثر استفاده کردیم، که در واقع موقعیتهای محافظ ممکن را محدود میکند به طوری که ممکن است نتوانیم محافظ را به درستی قرار دهیم. این باعث می شود که در برخی موارد همانطور که از جدول 6 می بینیم فقط یک محافظ برای پوشش کل فضای ورودی کافی نیست . ما ممکن است استراتژی قرار دادن خود را به جای انتخاب مرکز وجه بذر بهبود دهیم، اما آن را به عنوان کار آینده رها می کنیم. ما میانگین پوشش را با توجه به افزایش تعداد نگهبان ها همانطور که در جدول 7 نشان داده شده است اندازه گیری کردیم. میتوانیم مشاهده کنیم که یک محافظ میتواند 89 درصد از چند ضلعی ورودی را پوشش دهد، حتی اگر به دلیل قرارگیری محدود محافظ در مرکز به محافظهای بیشتری نیاز داشته باشیم. با این حال، ما همچنین می توانیم مشاهده کنیم که یک محافظ اضافی می تواند به طور متوسط بیش از 99٪ از مساحت چند ضلعی های ورودی را پوشش دهد.
برای نشان دادن عملکرد در مقایسه با راهحل بهینه بیشتر، آزمایشهای مقایسهای اضافی را با یک کار موجود اخیر [ 25 ] که به مسئله گالری هنر اختصاص داده شده است، انجام دادیم. این رویکرد راه حل بهینه را ارائه می دهد و آنها چندین مجموعه داده تست را ارائه می دهند. ما از مجموعه دادههای چند ضلعی متعامد تصادفی و چندضلعیهای ساده تصادفی استفاده کردیم که هر کدام شامل 30 نمونه از چند ضلعیهای تصادفی با تعداد رئوس مختلف است. در جدول 8 ، ما راه حل بهینه (حداقل تعداد محافظ) به دست آمده توسط [ 25] را فهرست کرده ایم.کار ] و عملکرد پوشش نتیجه محاسبه شده توسط چارچوب ما بر حسب نسبت متوسط و اختلاف میانگین به جواب بهینه. برای چند ضلعی های متعامد با 100 راس، نتایج ما 8٪ محافظ بیشتر از نظر نسبت به جواب بهینه و 1.233 محافظ بیشتر از نظر تعداد مطلق حفاظ ها استفاده کرد. مشاهده می کنیم که چارچوب ما برای چند ضلعی های متعامد بهتر از چند ضلعی های ساده عمل می کند، که در واقع در بسیاری از فضاهای داخلی رایج است. برای چند ضلعی های ساده تصادفی، که برای موارد واقعی طبیعی نیستند، چارچوب ما از حدود 20٪ محافظ بیشتری برای پوشش کل چند ضلعی استفاده می کند. با این وجود، وقتی رگرسیون خطی را روی تعداد راس ها و تعداد گاردهای اضافی انجام می دهیم، از 0.0275 گارد اضافی نسبت به تعداد رئوس استفاده می کنیم که کاملاً قابل قبول است.
7.4. مشکل برنامه ریزی مسیر
در این بخش، اثربخشی روش برنامه ریزی مسیر پیشنهادی را نشان می دهیم. تاکید این آزمایش بر این واقعیت است که روش پیشنهادی میتواند اطلاعات شبکه را برای ناوبری داخلی به طور موثر و بدون کاهش کیفیت وظایف برنامهریزی مسیر ذخیره کند.
ما 1000 جفت نقطه تصادفی در هر یک از چند ضلعی های ورودی ایجاد کردیم و مسیر بین نقاط پرس و جو را جستجو کردیم. ما مسیر حاصل را با در نظر گرفتن دو معیار ارزیابی کردیم. طول مسیر یک معیار اساسی است زیرا در بسیاری از کاربردها مطلوب است که مسیر کوتاهترین باشد. در مسیریابی ربات، تعداد چرخش ها نیز یک معیار مهم است، زیرا چرخاندن یک ربات مستلزم عملیات اضافی است که زمان و انرژی مصرف می کند. ما همچنین تعداد گرهها و لبههای شبکه زیربنایی را که برای جستجوی مسیرها استفاده میشود، اندازهگیری کردیم. ما نتایج روش پیشنهادی را با شبکه مبتنی بر شبکه مقایسه کردیم، که به طور گسترده برای وظایف مسیریابی در ادبیات استفاده میشود [ 39 ، 44 ، 45] و همچنین کوتاه ترین مسیر در چند ضلعی های ورودی. برای شبکه مبتنی بر شبکه، گره ها را روی یک شبکه مستطیلی قرار دادیم و لبه ها را به 8 همسایه برای هر گره تعیین کردیم. ما از دو اندازه شبکه استفاده کردیم g=0.5متر و g=1.0متر
جدول 9 ارزیابی مقایسه ای مسیرهای حاصل را نشان می دهد. روش پیشنهادی با استفاده از پارتیشن محدب عملکرد بهتری نسبت به روش مبتنی بر شبکه از نظر طول مسیر و تعداد چرخش به دست آورد. میانگین طول مسیر پیشنهادی طولانیتر بود اما بیش از 4 درصد کوتاهترین مسیر بهینه نبود.
جدول 10 اندازه نمودار را برای هر روش نشان می دهد. همانطور که میتوان انتظار داشت، شبکه مبتنی بر شبکه فضای بسیار بزرگی را مصرف میکند، زیرا ما به گرهها و لبههای زیادی نیاز داریم. روش پیشنهادی تنها به یک پارتیشن محدب و اتصال آن نیاز دارد که از نظر اندازه نمودار کارآمدتر است.
8. بحث
چندین مشکل وجود دارد که می توان آنها را از نظر محاسباتی بهبود بخشید. اگرچه ما یک فرمول بهبودیافته را تحت یک شرایط خاص ارائه کردهایم، برنامهریزی خطی باینری ممکن است زمانی که حجم عظیمی از دادهها را مدیریت میکنیم پرهزینه باشد. برای مقیاس پذیری، ممکن است یک الگوریتم کارآمد برای مرحله پوشش و پارتیشن بندی ایجاد کنیم. نقطه محوری وجه بذر مورد استفاده در مرحله محاسبات بسط را می توان بهبود بخشید تا بتوانیم به عملکرد بهتری در وظایف پوشش و پارتیشن بندی دست یابیم. به عنوان مثال، ما ممکن است از یک نقطه دلخواه در وجه دانه به جای ثابت کردن در مرکز آن مانند این مطالعه استفاده کنیم. کار آینده همچنین باید شامل یک مطالعه جامع در مورد طراحی محدودیت های مناسب برای برنامه های کاربردی خاص در دنیای واقعی در مورد مشکلات پوشش و پارتیشن بندی باشد.
ما همچنین ممکن است معناشناسی را در نظر بگیریم، به ویژه در وظایف پارتیشن بندی. بسیاری از برنامه های کاربردی داخلی مبتنی بر خدماتی هستند که اطلاعات معنایی را ارائه می دهند. با توجه به این کاربردها، ما باید این معناشناسی را در نظر بگیریم نه اینکه چارچوب پارتیشن بندی خود را مستقیماً در کل فضا انجام دهیم. به عنوان مثال، اگر بتوانیم به صورت دستی فضا را به واحدهای معنایی تقسیم کنیم، می توانیم وظیفه پارتیشن بندی را برای فضاهای جداگانه با پارامترهای مختلف انجام دهیم. ما ممکن است وجوه مثلثی را به منظور نشان دادن برخی نقاط مهم (POI) برای کاربردهای خاص وزن کنیم. در مسئله برنامه ریزی مسیر، معناشناسی نقش مهمی در ناوبری ایفا می کند [ 49]. برای عابران پیاده انسانی، مقاصد احتمالاً مختصات دقیقی نیستند، اما برخی مکانها دارای معنای خاصی مانند فروشگاهها، دروازهها، سرویسهای بهداشتی یا آسانسور هستند. ما می توانیم این جنبه ها را در توسعه و ارزیابی چارچوب خود در آینده در نظر بگیریم.
9. نتیجه گیری
مشکلات پوشش و پارتیشن بندی در تحلیل و مدیریت فضاهای داخلی مهم است. در این مقاله، ما یک چارچوب انعطافپذیر ارائه کردهایم که میتواند به طور موثر برای این مشکلات اعمال شود. مشارکت های ما را می توان به شرح زیر خلاصه کرد:
-
ما چارچوبی را برای رسیدگی به مشکلات پوشش و پارتیشن بندی که به بسیاری از برنامه های داخلی مربوط می شود، پیشنهاد کرده ایم. این چارچوب از سه مرحله تشکیل شده است که عبارتند از مثلث بندی ریز دانه، محاسبه بسط، و پوشش/پارتیشن بندی.
-
در مرحله محاسبات بسط، میتوانیم از یک محدودیت مناسب طراحی شده برای برنامه هدف استفاده کنیم، که منظور ما از انعطافپذیر است زیرا روش پیشنهادی برای یک برنامه منفرد خیلی خاص نیست. ما چندین محدودیت را با یک روش محاسباتی کارآمد ارائه کردیم که می تواند برای بسیاری از برنامه های داخلی شناخته شده استفاده شود.
-
ما فرمول های برنامه ریزی خطی باینری را برای مرحله پوشش و پارتیشن بندی پیشنهاد کردیم. به خصوص، ما مفهوم بسط غیر چرخه ای را معرفی کردیم و یک فرمول برنامه ریزی خطی باینری ساده شده را برای مسئله پارتیشن بندی تحت این شرایط خاص ارائه کردیم.
-
به عنوان یک مورد استفاده از روش پارتیشن بندی، ما مسئله برنامه ریزی مسیر را با پارتیشن محدب ارائه کردیم. ما همچنین نحوه نمایش پارتیشن به دست آمده و اتصال آنها برای ناوبری را در قالب IndoorGML که یک استاندارد بین المللی برای نمایش فضاهای داخلی است، ارائه کردیم.
-
با نتایج تجربی، ما نشان دادیم که چارچوب ما می تواند به عنوان یک روش خارج از قفسه برای مسائل مختلف پوشش و پارتیشن بندی با نشان دادن اینکه راه حل های قابل قبولی را در مقایسه با روش های دیگر محاسبه می کند، حتی اگر تضمینی برای بهینه بودن آنها وجود ندارد، استفاده شود.
ما همچنین چندین موضوع را پیدا کردیم که میتوان آنها را بهبود بخشید، که در بخش قبلی در مورد آنها بحث کردیم. ما چارچوب را در این دیدگاه ها در کارهای آینده بهبود خواهیم داد.
بدون دیدگاه