مسیریابی از میان موانع جابه جاشونده

خشخاشی مقدم, شکرانه; مسیحی, الیپس

مسیریابی از میان موانع جابه جاشونده

نویسندگان

دانشگاه تربیت مدرس

چکیده

مسئله برنامهریزی حرکت با موانع جابه‌جاشونده، (NAMO)3، عبارت از یافتن مسیرهایی بدون تصادم برای روبات است؛ این در حالی است که روبات برای یافتن یک مسیر، میتواند برخی موانع را جابهجا کند. NAMOیکمسئله NP-Complete و در زمره مسائلی از مسیریابی حرکت روبات قرار میگیرد که دارای محیطهای متغیر هستند. در این حوزه یک برنامه بهینه برای روبات میتواند با توجه به فاکتورهای مختلف همچون طول مسیرهای انتقال و جابهجایی، تعداد اجسام جابه‌جاشونده، تعداد دفعات جابهجایی اجسام و زمان تعیین شود. در این مقاله با استفاده از مفاهیمی همچون گراف دید نگار4،و عمق نفوذ5، الگوریتم بازگشتی ارائه شده قادر است مسائل مختلف NAMO را در زمان معقولی حل کند. هم‏چنین به‌کارگیری الگوریتم پیشنهادی برای حل برخی مسائل موجود در ادبیات، موجب کاهش چشمگیر تعداد اجسام جابهجا شده و تعداد دفعات جابهجایی اجسام جابه‌جاشونده شده است.

کلیدواژه‌ها

عنوان مقاله [English]

Navigation among Movable Obstacles

چکیده [English]

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.

کلیدواژه‌ها [English]

Robot Navigation
Movable Obstacles
Visibility Graph
Penetration Depth
Minkowski Sum

مراجع

[1] Wilfong, G., “Motion Planning In The Presence Of Movable Obstacles”. Annals of Mathematics and Artificial Intelligence,, 1991. 3: p. 131-150

[2] Demaine, E.D., M.L. Demaine, and J. O’Rourke, “pushpush and push1 are hard in 2d”. in In Proceedings of the 12th Canadian Conference on Computational Geometry,, 2000: p. 211-219

[3] Chen, P.C. and Y.K. Hwang, “Practical Path Planning among movable obstacles”. Proceedings of the IEEE International Conference on Robotics and Automation, 1991: p. 444-449.

[4] Okada, K., et al., “Environment manipulation planner for humanoid robots using task graph that generates action sequence” Proceedings of 2004 1EEElRS.J International Conference on Intelligent Robots and Systems, 2004.

[5] Stilman, M. and J.J. Kuffner, “Navigation Among Movable Obstacles: Real-Time Reasoning In Complex Environments”. International Journal of Humanoid Robotics, 2005.2(4): p. 479-504.

[6] Stilman, M., et al., “Planning and Executing Navigation Among Movable Obstacles”. in IEEE/RSJ Int. Conf. On IntelligentRobots and Systems (IROS 06), 2006: p. 820-826.

[7] Stilman, M. and J.J. Kuffner, “Planning Among Movable Obstacles with Artificial Constraints”. In Proc. 6th Int. Workshop on the Algorithmic Foundations of Robotics, 2006: p. 1-20.

[8] Nieuwenhuisen, D., A.F. van der Stappen, and M. H. Overmars, “An Effective Framework for Path Planning amidst Movable Obstacles”. Algorithmic Foundation of Robotics 2008.VII: p. 87-102.

[9] Berg, J.v.d., et al., “Path Planning among Movable Obstacles: a Probabilistically Complete Approach”. Workshop on Algorithmic Foundation of Robotics (WAFR VIII), 2008: p. 599-614.

[10] Wu, H.N., M. Levihn, and M. Stilman, “Navigation Among Movable Obstacles in Unknown Environments”. in IEEE/RSJ Int. Conf. On Intelligent Robots and Systems (IROS 2010).

[11] Levihn, M., “Navigation among Movable Obstacles in Unknown Envrionments”, 2011, Georgia Institute of Technology. p. 87

[12] Choset, H., et al., “Principles of Robot Motion-Theory, Algorithms, and Implementation”, 2005, Cambridge, Massachusetts: The MIT Press.

[13] Dobkin, D., et al., “Computing the intersection-depth of polyhedra”. Algorithmica, 1993.9: p. 518-533.

[14] Zhang, L., et al., “Generalized penetration depth computation”. Computer-Aided Design, 2007.39(8): p. 625–638.