عین الله پیرا - دانشکده مهندسی کامپیوتر، دانشگاه صنعتی شریف
محمد قدسی - دانشکده مهندسی کامپیوتر، دانشگاه صنعتی شریف

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

برنامه ریزی حرکت ، تحلیل تقریبی ، الگوریتم بر خط ، مسیربهینه