اخبار و اعلانات

 آمار

تعداد نشریات38
تعداد شماره‌ها1,260
تعداد مقالات9,130
تعداد مشاهده مقاله8,464,339
تعداد دریافت فایل اصل مقاله5,164,835
خشخاشی مقدم, شکرانه, مسیحی, الیپس. (1393). مسیریابی از میان موانع جابه جاشونده. پدافند الکترونیکی و سایبری, 16(46), 14-23.
شکرانه خشخاشی مقدم; الیپس مسیحی. "مسیریابی از میان موانع جابه جاشونده". پدافند الکترونیکی و سایبری, 16, 46, 1393, 14-23.
خشخاشی مقدم, شکرانه, مسیحی, الیپس. (1393). 'مسیریابی از میان موانع جابه جاشونده', پدافند الکترونیکی و سایبری, 16(46), pp. 14-23.
خشخاشی مقدم, شکرانه, مسیحی, الیپس. مسیریابی از میان موانع جابه جاشونده. پدافند الکترونیکی و سایبری, 1393; 16(46): 14-23.

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

مدیریت زنجیره تأمین
مقاله 2، دوره 16، شماره 46، اسفند 1393، صفحه 14-23    اصل مقاله (423.68 K)
نویسندگان
شکرانه خشخاشی مقدم* ؛ الیپس مسیحی
دانشگاه تربیت مدرس
تاریخ دریافت: 24 آبان 1393،  تاریخ بازنگری: 01 دی 1393،  تاریخ پذیرش: 08 دی 1393 
چکیده
مسئله برنامه­ریزی حرکت با موانع جابه‌جاشونده، (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.

آمار
تعداد مشاهده مقاله: 585
تعداد دریافت فایل اصل مقاله: 196