Abstract
In this paper, we demonstrate an equivalence between a large class of discrete motion planning problems, and piano mover’s problems, which we refer to as ”continuous motion planning problems”. We first prove that under some assumptions, discrete motion planning in d dimensions can be transformed into continuous motion planning in 2d + 1 dimensions. Then we prove a more specific, similar equivalence for which the number of dimensions of the configuration space does not necessarily have to be increased.We study two simple cases where this theorem applies, and show that it can lead to original and efficient motion planning algorithms, which could probably be applied to a wide range of multi-contact planning problems.We apply this equivalence to a simulation of legged locomotion planning for a hexapod robot.
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
Alami, R., Laumond, J.-P., Siméon, T.: Two manipulation planning algorithms. In: 1st Workshop on the Algorithmic Foundations of Robotics, WAFR 1994 (1994)
Bouyarmane, K., Kheddar, A.: Multi-contact stances planning for multiple agents. In: IEEE Int. Conf. on Robotics and Automation (ICRA 2011), pp. 5246–5253 (2011)
Bullo, F., Leonard, N.E., Lewis, A.D.: Controllability and motion algorithms for underactuated lagrangian systems on lie groups. IEEE Transactions on Automatic Control 45(8), 1437–1454 (2000)
Chestnutt, J., Lau, M., Cheung, G., Kuffner, J.J., Hodgins, J., Kanade, T.: Footstep planning for the honda asimo humanoid. In: IEEE Int. Conf. on Robotics and Automation (ICRA 2005), pp. 631–636 (2005)
Dalibard, S., El Khoury, A., Lamiraux, F., Taix, M., Laumond, J.-P.: Small-space controllability of a walking humanoid robot. In: IEEE/RAS Int. Conf. on Humanoid Robots, Humanoids 2011 (2011)
Ferré, E., Laumond, J.-P.: An iterative diffusion algorithm for part disassembly. In: IEEE Int. Conf. on Robotics and Automation, ICRA 2004 (2004)
Geraerts, R., Overmars, M.H.: Creating high-quality paths for motion planning. I. J. Robotic Res. 26, 845–863 (2007)
Hauser, K., Bretl, T., Latombe, J.-C., Wilcox, B.: Motion Planning for a Six-Legged Lunar Robot. In: Akella, S., Amato, N.M., Huang, W.H., Mishra, B. (eds.) Algorithmic Foundations of Robotics VII. STAR, vol. 47, pp. 301–316. Springer, Heidelberg (2008)
Hauser, K., Latombe, J.-C.: Multi-modal motion planning in non-expansive spaces. I. J. Robotic Res. 29(7), 897–915 (2010)
Kalakrishnan, M., Buchli, J., Pastor, P., Mistry, M., Schaal, S.: Learning, planning, and control for quadruped locomotion over challenging terrain. I. J. Robotic Res. 30(2) (2011)
Kanoun, O., Yoshida, E., Laumond, J.-P.: An optimization formulation for footsteps planning. In: IEEE/RAS Int. Conf. on Humanoid Robots, Humanoids 2009 (2009)
Karaman, S., Frazzoli, E.: Incremental sampling-based algorithms for optimal motion planning. In: Robotics Science and Systems VI (2010)
Kavraki, L.E., Svestka, P., Latombe, J.-C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. on Robotics and Automation 12, 566–580 (1996)
Kuffner, J.J., Lavalle, S.M.: RRT-Connect: An efficient approach to single-query path planning. In: IEEE Int. Conf. on Robotics and Automation (ICRA 2000), pp. 995–1001 (2000)
Kuffner, J.J., Nishiwaki, K., Kagami, S., Inaba, M., Inoue, H.: Footstep planning among obstacles for biped robots. In: IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS 2001), pp. 500–505 (2001)
Lafferriere, G., Sussmann, H.J.: Motion planning for controllable systems without drift. In: IEEE Int. Conf. on Robotics and Automation (ICRA 1991), pp. 1148–1153 (1991)
LaValle, S.M., Kuffner, J.J.: Rapidly-exploring random trees: Progress and prospects. In: 4th Workshop on the Algorithmic Foundations of Robotics (WAFR 2000), pp. 293–308 (2000)
The Open Motion Planning Library (2010), http://ompl.kavrakilab.org
Pan, J., Lauterbach, C., Manocha, D.: g-Planner: Real-time motion planning and global navigation using GPUs. In: 24th AAAI Conf. on Artificial Intelligence (2010)
Pan, J., Liangjun, Z., Manocha, D.: Collision-free and curvature-continuous path smoothing in cluttered environments. In: Robotics: Science and Systems, RSS 2011 (2011)
Perrin, N., Stasse, O., Lamiraux, F., Kim, Y.J., Manocha, D.: Real-time footstep planning for humanoid robots among 3d obstacles using a hybrid bounding box. In: IEEE Int. Conf. on Robotics and Automation, ICRA 2012 (2012)
Perrin, N., Stasse, O., Lamiraux, F., Yoshida, E.: Weakly collision-free paths for continuous humanoid footstep planning. In: IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS 2011), pp. 4408–4413 (2011)
Serra, J.: Image Analysis and Mathematical Morphology. Academic Press, Inc. (1983)
Zucker, M., Andrew, J., Christopher, B., Atkeson, G., Kuffner, J.J.: An optimization approach to rough terrain locomotion. In: IEEE Int. Conf. on Robotics and Automation, ICRA 2010 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Perrin, N. (2013). From Discrete to Continuous Motion Planning. In: Frazzoli, E., Lozano-Perez, T., Roy, N., Rus, D. (eds) Algorithmic Foundations of Robotics X. Springer Tracts in Advanced Robotics, vol 86. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36279-8_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-36279-8_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36278-1
Online ISBN: 978-3-642-36279-8
eBook Packages: EngineeringEngineering (R0)