حذف کم ترین تعداد موانع مربعی در برنامه ریزی حرکت ربات

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

کلیدواژه ها:

مسیریابی ربات ، الگوریتم ، گراف ، هندسه محاسباتی ، حذف موانع