کاربرد نظریه گراف در حل مسائل برنامه ریزی حرکت روبات: گراف های قابل حل مینیمال

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