Abstract
This paper presents 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 implementation for the domain of navigation among movable obstacles.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Stilman, M., Kuffner, J.J.: Navigation among movable obstacles: Real-time reasoning in complex environments. In: IEEE/RAS Int. Conf. on Humanoid Robotics, pp. 322–341. IEEE, Los Alamitos (2004), http://www.golems.org/NAMO
Wilfong, G.: Motion panning in the presence of movable obstacles. In: ACM Symp. Computat. Geometry, pp. 279–288. ACM Press, New York (1988)
Demaine, E., Demaine, M., O’Rourke, J.: Pushpush and push-1 are np-hard in 2d. In: 12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, Canada, August 16-19, pp. 211–219 (2000)
Reif, J.H., Sharir, M.: Motion planning in the presence of moving obstacles. In: Proc. 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, pp. 144–154. IEEE Computer Society Press, Los Alamitos (1985)
Hsu, D., Kindel, R., Latombe, J.C., Rock, S.: Randomized kinodynamic motion planning with moving obstacles. The Int. J. of Robotics Research 21(3), 233–255 (2002)
Brock, O., Khatib, O.: Elastic strips: Real-time path modification for mobile manipulation. In: International Symposium of Robotics Research, Hayama, Japan, pp. 117–122. Springer, Heidelberg (1997)
Fortune, S., Wilfong, G., Yap, C.: Coordinated motion of two robot arms. In: IEEE Int. Conf. on Robotics and Automation, pp. 1216–1223 (April 1986)
Erdmann, M., Lozano-Perez, T.: On multiple moving objects. In: IEEE Int. Conf. on Robotics and Automation, April 7-10, pp. 1419–1424 (1986)
Schwartz, J., Sharir, M.: On the piano movers’ problem. iii: Coordinating the motion of several independent bodies. the special case of circular bodies moving amidst polygonal barriers. Int. J. Robotics Research 2(3), 46–74 (1983)
Goldwasser, M.H., Motwani, R.: Complexity measures for assembly sequences. The International Journal of Computational Geometry and Applications 9(4 & 5), 371–418 (1999)
Randall, H.: Wilson. On Geometric Assembly Planning. PhD thesis, Department of Computer Science, Stanford University, Stanford, CA, USA, UMI Order Number: UMI Order No. GAX92-21686 (1992)
Alami, R., Laumond, J.P., Sim’eon, T.: Two manipulation planning algorithms. In: Goldberg, K., Halperin, D., Latombe, J., Wilson, R. (eds.) Workshop on the Algorithmic Foundations of Robotics, San Francisco, California, United States, pp. 109–125. A. K. Peters, Ltd., Natick (1994)
Ben-Shahar, O., Rivlin, E.: Practical pushing planning for rearrangement tasks. IEEE Trans. on Robotics and Automation 14(4), 549–565 (1998)
Ota, J.: Rearrangement of multiple movable objects. In: IEEE Int. Conf. Robotics and Automation (ICRA), New Orleans, LA, vol. 2, pp. 1962–1967. IEEE, Los Alamitos (2004)
Chen, P.C., Hwang, Y.K.: Pracitcal path planning among movable obstacles. In: IEEE Int. Conf. Robotics and Automation (ICRA), Sacramento, CA, pp. 444–449. IEEE, Los Alamitos (1991)
Okada, K., Haneda, A., Nakai, H., Inaba, M., Inoue, H.: Environment manipulation planner for humaonid robots using task graph that generates action sequence. In: IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS 2004), Sendai, Japan, pp. 1174–1179. IEEE, Los Alamitos (2004)
Chadzelek, T., Eckstein, J., Schömer, E.: Heuristic motion planning with movable obstacles. In: 8th Canadian Conference on Computational Geometry, Ottawa, Canada, August 12-15, pp. 131–136. Carleton University Press (1996)
Lozano-Perez, T.: Spatial planning: A configuration space approach. IEEE Trans. Comput. 32(2), 108–120 (1983)
Ganter, M.A.: Dynamic Collision Det. using Kinematics and Solid Modeling Techniques(Mechanical Engineering). PhD thesis, University of Wisconsin (1985)
Foisy, A., Hayward, V.: A safe swept-volume approach to collision detection. In: Robotics Research, Sixth International Symposium (1994)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Stilman, M., Kuffner, J.J. (2008). Planning Among Movable Obstacles with Artificial Constraints. In: Akella, S., Amato, N.M., Huang, W.H., Mishra, B. (eds) Algorithmic Foundation of Robotics VII. Springer Tracts in Advanced Robotics, vol 47. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68405-3_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-68405-3_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68404-6
Online ISBN: 978-3-540-68405-3
eBook Packages: EngineeringEngineering (R0)