In this paper we present artificial constraints as a method for guiding heuristic search in the computationally challenging domain of motion planning among movable obstacles. The robot is permitted to manipulate unspecified obstacles in order to create space for a path. A plan is an ordered sequence of paths for robot motion and object manipulation. We show that under monotone assumptions, anticipating future manipulation paths results in constraints on both the choice of objects and their placements at earlier stages in the plan. We present an algorithm that uses this observation to incrementally reduce the search space and quickly find solutions to previously unsolved classes of movable obstacle problems. Our planner is developed for arbitrary robot geometry and kinematics. It is presented with an implementa tion for the domain of navigation among movable obstacles.
Alami, R., Laumond, J. and Simeon, T. (1994). Two manipulation planning algorithms. Proceedings of the Workshop on the Algorithmic Foundations of Robotics, Goldberg, K., Halperin, D., Latombe, J. and Wilson, R. (eds). Natick, MA, A.K. Peters, pp. 109-125.
2.
Ben-Shahar, O. and Rivlin, E. (1998). Practical pushing planning for rearrangement tasks . IEEE Transactions on Robotics and Automation, 14(4): 549-565.
3.
Brock, O. and Khatib, O. (1997). Elastic strips: real-time path modification for mobile manipulation. Proceedings of the International Symposium of Robotics Research. Berlin, Springer, pp. 117-122.
4.
Chadzelek, T., Eckstein, J. and Schemer, E. (1996). Heuristic motion planning with movable obstacles . Proceedings of the 8th Canadian Conference on Computational Geometry. Ottawa, Carleton University Press, pp. 131-136.
5.
Chen, P.C. and Hwang, Y.K. (1991). Pracitcal path planning among movable obstacles . Proceedings IEEE International Conference on Robotics and Automation (ICRA), pp. 444-449.
6.
Demaine, E., Demaine, M. and O'Rourke, J. (2000). Pushpush and push-1 are NP-hard in 2D. Proceedings of the 12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, Canada, pp. 211-219.
7.
Erdmann, M. and Lozano-Perez, T. (1986). On multiple moving objects . Proceedings IEEE International Conference on Robotics and Automation, pp. 1419-1424.
8.
Foisy, A. and Hayward, V. (1994). A safe swept-volume approach to collision detection . Proceedings of the 6th International Symposium on Robotics Research.
9.
Fortune, S., Wilfong, G., and Yap, C. (1986). Coordinated motion of two robot arms. Proceedings IEEE International Conference on Robotics and Automation , pp. 1216-1223.
10.
Ganter, M.A. (1985). Dynamic collision detection using kinematics and solid modeling techniques. Ph.D. Thesis, University of Wisconsin.
11.
Goldwasser, M.H. and Motwani, R. (1999). Complexity measures for assembly sequences. The International Journal of Computational Geometry and Applications , 9(4-5): 371-418.
12.
Hsu, D., Kindel, R., Latombe, J.C. and Rock, S. (2002). Randomized kinodynamic motion planning with moving obstacles. The International Journal of Robotics Research , 21(3): 233-255.
13.
Lozano-Perez, T. (1983). Spatial planning: a configuration space approach . IEEE Transactions on Computers, 32(2): 108-120.
14.
Lynch, K.M. and Mason, M.T. (1996). Stable pushing: Mechanics, controllability, and planning. The International Journal of Robotics Research, 15(6): 533-556.
15.
Miller, A.T. (2001). GraspIt ! : a versatile simulator for robotic grasping. Ph.D. Thesis, Department of Computer Science, Columbia University.
16.
Nieuwenhuisen, D. and van der Stappen, F.M.O. (2006). An effective framework for path planning amidst movable obstacles. Proceedings of the Workshop on the Algorithmic Foundations of Robotics.
17.
Okada, K., Haneda, A., Nakai, H., Inaba, M. and Inoue, H. (2004). Environment manipulation planner for humaonid robots using task graph that generates action sequence. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'04), Sendai, Japan, pp.1174-1179.
18.
Ota, J. (2004). Rearrangement of multiple movable objects. Proceedings IEEE International Conference Robotics and Automation (ICRA), Vol. 2, New Orleans, LA, pp. 1962-1967.
19.
Reif, J.H. and Sharir, M. (1985). Motion planning in the presence of moving obstacles . Proceedings of the 26th Annual Symposium on Foundations of Computer Science, Portland, OR, pp. 144-154.
20.
Schwartz, J. and Sharir, M. (1983a). On the piano movers' problem: III. Coordinating the motion of several independent bodies. The special case of circular bodies moving amidst polygonal barriers. The International Journal of Robotics Research, 2(3): 46-74.
21.
Schwartz, J. and Sharir, M. (1983b). On the piano movers' problem: I. The case of a rigid polygonal body moving amidst polygonal barriers. Comments on Pure and Applied Mathematics, 36: 345-398.
22.
Stilman, M. (2007). Navigation among movable obstacles. Technical Report CMU-RI-TR-07-37, Carnegie Mellon University, Pittsburgh, PA, http://www.golems.org/NAMO/stilman-thesis.pdf .
23.
Stilman, M. and Kuffner, J. (2004). Navigation among movable obstacles: real-time reasoning in complex environments. Proceedings of the IEEE/RAS International Conference on Humanoid Robotics, pp. 322-341. http://www.golems.org/NAMO.
24.
Stilman, M. and Kuffner, J. (2006). Planning among movable obstacles with artificial constraints. Proceedings of the Workshop on the Algorithmic Foundations of Robotics.
25.
Stilman, M., Nishiwaki, K., Kagami, S. and Kuffner, J. (2007a). Planning and executing navigation among movable obstacles. Advanced Robotics, 21(14): 1617-1634.
26.
Stilman, M., Shamburek, J., Kuffner, J. and Asfour, T. (2007b). Manipulation planning among movable obstacles . Proceedings IEEE International Conference on Robotics and Automation.
27.
Wilfong, G. (1988). Motion panning in the presence of movable obstacles . Proceedings of the ACM Symposium on Computational Geometry. New York, ACM Press, pp. 279-288.
28.
Wilson, R.H. (1992). On geometric assembly planning. Ph.D. Thesis (UMI Order No. GAX92-21686), Department of Computer Science, Stanford University, Stanford, CA.
