روش های ابتدایی تعیین مسیر:

مطالبی که به آن خواهیم پرداخت پنهان سازی سر فصل ها

در پروژه های ساخت، منابع باید دائماً در کارگاه از نقطه ای به نقطه دیگر جابجا شوند تا ملزومات فعالیت های مختلف را تامین کنند. برنامه ریزی نحوه جابجایی منابع بخش مهمی از تدارکات کارگاهی بوده و برای برنامه ریزی تجهیز کارگاه و برنامه ریزی ایمنی ضروری می باشد. اما اثرگذاری مسیرهای حرکتی بر روش های مختلف هنوز به طور دقیق مشخص نشده است.

منابعی از قبیل نیروی کار، تجهیزات و مصالح در محوطه کارگاه جابجا می شوند تا فعالیت های مختلف را پشتیبانی نمایند . کاهش مسیر طی شده منجر به کاهش اتلاف زمان و هزینه های حمل و نقل می گردد و کارایی پروژه را بهبود می بخشد . کل مسیر طی شده در یک پروژه به دو صورت قابل کاهش می باشد. اولاً با برنامه ریزی تجهیز کارگاه برای جانمایی مناسب قسمت های مختلف به منظور بهینه سازی چیدمان کارگاهی و ثانیاً با تعیین کوتاهترین مسیر جابجایی در کارگاه برای اتصال نقاط مبدا و مقصد با توجه به موانع موجود. در هر دو مرحله این فعالیت ها، تعیین فاصله واقعی میان هر دو نقطه از کارگاه اهمیت بالایی دارد .

تاکنون سه روش عمده برای تعیین فاصله بین دو نقطه وجود داشته است: روش مسیر مستقیم، روش مبتنی بر مش بندی و روش مسیر قابل رویت. روش اول براساس خط مستقیم بین دو نقطه بوده و موانع موجود در کارگاه را در نظر نمی گیرد. در این روش، فاصله میان دو نقطه a و b با مختصات (Y_a،X_a) و (Y_b،X_b) بصورت زیر محاسبه می شود:

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

مرحله اول: مش بندی براساس شکل کارگاه و ابعاد مش صورت می پذیرد.

مرحله دوم: برای تمام موانع، نقاطی که در محدوده موانع قرار گیرند حذف می شوند.

مرحله سوم: نقاط مجاور با خط مستقیم به هم متصل می شوند.

مرحله چهارم: برای جابجایی از نقطه مبدا به مقصد، کوتاهترین مسیر جستجو می شود.

روش های حرفه ای تعیین مسیر:

روش مسیر قابل رویت، با فرض اینکه جابجایی در کارگاه از کنار موانع صورت می پذیرد، تعریف شده است. این روش برای مسیریابی در برنامه ریزی جابجایی رباتیک به کار گرفته می شود. در این روش نقطه مبدا و مقصد با مسیری که از نقاط گوشه موانع عبور می کند متصل شده و از میان حالت های بوجود آمده، کوتاهترین مسیر که از میان محدوده مانع نگذرد به عنوان مسیر حرکت درنظر گرفته می شود. در این روش، فاصله میان دو نقطه در چهار مرحله محاسبه می گردد :

مرحله اول: تمامی نقاط مسیر قابل رویت شامل نقاط مبدا، مقصد و گوشه های موانع تعیین می شوند.

مرحله دوم: هر دو نقطه به یکدیگر متصل می شوند تا تمامی حالت های ممکن شکل گیرند.

مرحله سوم: تمامی خطوطی که از محدوده موانع می گذرند حذف می شوند.

مرحله چهارم: برای جابجایی از نقطه مبدا به مقصد، کوتاهترین مسیر جستجو می شود.

نحوه عملکرد سه روش فوق برای جابجایی از نقطه A به نقطه B در تصویر زیر قابل مشاهده می باشد:

در مقالات بررسی شده، برای جستجوی کوتاهترین مسیر در روش مبتنی بر مش بندی عمدتاً از الگوریتم ژنتیک A* استفاده شده است که یکی از سریعترین روش های محاسباتی این مسئله بوده و سختی محاسبات آن، تابع درجه دومی از تعداد نقاط موجود در مش می باشد. در روش مسیر قابل رویت، نیز از الگوریتم ژنتیک A* استفاده میشود و سختی محاسبات، تابع درجه دومی از چهار برابر تعداد موانع (با فرض مستطیل شکل بودن موانع) می باشد. در محیط ۳ بعدی محاسبات مورد نیاز برای جستجوی کوتاهترین مسیر به مراتب پیچیده تر خواهد بود.