Navigation among Movable Obstacles

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

References

[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.

Files

History

  • Receive Date: 15 November 2014
  • Revise Date: 22 December 2014
  • Accept Date: 29 December 2014
  • Publish Date: 20 February 2015

Share

How to cite

Statistics