@article { author = {خشخاشی مقدم, شکرانه and مسیحی, الیپس}, title = {Navigation among Movable Obstacles}, journal = {Supply Chain Management}, volume = {16}, number = {46}, pages = {14-23}, year = {2015}, publisher = {Imam Hussein University}, issn = {2008-9198}, eissn = {2717-1647}, doi = {}, abstract = {The problem of navigation among movable obstacles (NAMO) is to find a collision free path for a robot while the robot is able to manipulate and transfer some objects (if possible or needed) to clear its path toward the goal. NAMO is a NP-complete problem and is in a class of motion planning problems that have dynamic environments. In this domain, an optimal plan for the robot can be defined with respect to many different criteria such as length of the transit and transfer paths, number of manipulated obstacles, total number of displacements of all the objects and time. In this article, we have tried to design an algorithm capable of solving a wide variety of NAMO problems, using concepts like, visibility graph and penetration depth. Using the recursive function to solve some existing problems in the literature shows significant reduction in number of transferred movable obstacles as well as total number of displacements of all the objects.}, keywords = {Robot Navigation,Movable Obstacles,Visibility Graph,Penetration Depth,Minkowski Sum}, title_fa = {مسیریابی از میان موانع جابه جاشونده}, abstract_fa = {مسئله برنامه­ریزی حرکت با موانع جابه‌جاشونده، (NAMO)3، عبارت از یافتن مسیرهایی بدون تصادم برای روبات است؛ این در حالی است که روبات برای یافتن یک مسیر، می­تواند برخی موانع را جابه­جا کند. NAMOیکمسئله NP-Complete و در زمره مسائلی از مسیریابی حرکت روبات قرار می­گیرد که دارای محیط­های متغیر هستند. در این حوزه یک برنامه بهینه برای روبات می­تواند با توجه به فاکتورهای مختلف هم­چون طول مسیرهای انتقال و جابه­جایی، تعداد اجسام جابه‌جاشونده، تعداد دفعات جابه­جایی اجسام و زمان تعیین شود. در این مقاله با استفاده از مفاهیمی هم­چون گراف دید نگار4،و عمق نفوذ5، الگوریتم بازگشتی ارائه شده قادر است مسائل مختلف NAMO را در زمان معقولی حل کند. هم‏چنین به‌کارگیری الگوریتم پیشنهادی برای حل برخی مسائل موجود در ادبیات، موجب کاهش چشمگیر تعداد اجسام جابه­جا شده و تعداد دفعات جابه­جایی اجسام جابه‌جاشونده شده است.}, keywords_fa = {مسیریابی حرکت روبات,موانع جابه‌جاشونده,گراف دیدنگار,عمق نفوذ,جمع مینکوفسکی}, url = {https://scmj.ihu.ac.ir/article_203544.html}, eprint = {https://scmj.ihu.ac.ir/article_203544_b08320c043772055afb251e90e5a9513.pdf} }