Motion Planning Templates: A Motion Planning Framework for Robots with Low-power CPUs
Pages 612 - 618
Abstract
Motion Planning Templates (MPT) is a C++ template-based library that uses compile-time polymorphism to generate robot-specific motion planning code and is geared towards eking out as much performance as possible when running on the low-power CPU of a battery-powered small robot. To use MPT, developers of robot software write or leverage code specific to their robot platform and motion planning problem, and then have MPT generate a robot-specific motion planner and its associated data-structures. The resulting motion planner implementation is faster and uses less memory than general motion planning implementations based upon runtime polymorphism. While MPT loses runtime flexibility, it gains advantages associated with compile-time polymorphism— including the ability to change scalar precision, generate tightly-packed data structures, and store robot-specific data in the motion planning graph. MPT also uses compile-time algorithms to resolve the algorithm implementation, and select the best nearest neighbor algorithm to integrate into it. We demonstrate MPT’s performance, lower memory footprint, and ability to adapt to varying robots in motion planning scenarios on a small humanoid robot and on 3D rigid-body motions.
References
[1]
J. H. Reif, “Complexity of the mover’s problem and generalizations,” in 20th Annual IEEE Symp. on Foundations of Computer Science, Oct. 1979, pp. 421–427.
[2]
H. Choset, K. M. Lynch, S. A. Hutchinson, G. A. Kantor, W. Burgard, L. E. Kavraki, and S. Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, 2005.
[3]
T. L. Veldhuizen, “C++ templates are turing complete,” Indiana University, Tech. Rep., 2003.
[4]
J. Ichnowski and R. Alterovitz, “Concurrent nearest-neighbor searching for parallel sampling-based motion planning in SO(3), SE(3), and Euclidean topologies,” in Algorthmic Foundations of Robotics (Proc. WAFR 2018). Springer, 2018 (to appear).
[5]
M. Herlihy and N. Shavit, The Art of Multiprocessor Programming. Morgan Kaufmann, 2011.
[6]
I. A. Sucan and L. E. Kavraki, “Kinodynamic motion planning by interior-exterior cell exploration,” in Algorithmic Foundation of Robotics VIII. Springer, 2009, pp. 449–464.
[7]
A. Yershova and S. M. LaValle, “Improving motion-planning algorithms by efficient nearest-neighbor searching,” IEEE Trans. Robotics, vol. 23, no. 1, pp. 151–157, 2007.
[8]
J. Ichnowski and R. Alterovitz, “Fast nearest neighbor search in for sampling-based motion planning,” in Algorithmic Foundations of Robotics XI. Springer, 15, pp. 197–214.
[9]
ISO/IEC, “ISO international standard ISO/IEC 14882:2017(E)—programming languages—C++,” International Organization for Standards (ISO), Geneva, Switzerland, Standard, Dec 2017.
[10]
I. A. Scucan, M. Moll, and L. E. Kavraki, “The open motion planning library,” IEEE Robotics and Automation Magazine, vol. 19, no. 4, pp. 72–82, Dec. 2012. [Online]. Available: http://ompl.kavrakilab.org
[11]
M. Otte and N. Correll, “C-FOREST: Parallel shortest path planning with superlinear speedup,” IEEE Trans. Robotics, vol. 29, no. 3, pp. 798–806, 2013.
[12]
R. Diankov and J. Kuffner, “OpenRAVE: A planning architecture for autonomous robotics,” Robotics Institute, Pittsburgh, PA, Tech. Rep. CMU-RI-TR-08-34, vol. 79, 2008.
[13]
M. Rickert and A. Gaschler, “Robotics library: An object-oriented approach to robot applications,” in Intelligent Robots and Systems (IROS), 2017 IEEE/RSJ International Conference on. IEEE, 2017, pp. 733–740.
[14]
S. M. LaValle and J. J. Kuffner, “Randomized kinodynamic planning,” Int. J. Robotics Research, vol. 20, no. 5, pp. 378–400, May 2001.
[15]
L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. Overmars, “Probabilistic roadmaps for path planning in high dimensional configuration spaces,” IEEE Trans. Robotics and Automation, vol. 12, no. 4, pp. 566–580, 1996.
[16]
I. A. Scucanand S. Chitta, “Moveit!” http://moveit.ros.org, 2013.
[17]
D. Coleman, I. Sucan, S. Chitta, and N. Correll, “Reducing the barrier to entry of complex robotic software: a moveit! case study,” Journal of Software Engineering for Robotics, 2014.
[18]
ROS.org, “Robot Operating System (ROS),” http://ros.org, 2012.
[19]
S. Murray, W. Floyd-Jones, Y. Qi, D. J. Sorin, and G. Konidaris, “Robot motion planning on a chip.” in Robotics: Science and Systems, 2016.
[20]
B. Stroustrup, The C++ programming language. Pearson Education, 2013.
[21]
K. Ishizaki, M. Kawahito, T. Yasue, H. Komatsu, and T. Nakatani, “A study of devirtualization techniques for a Java just-in-time compiler,” in ACM SIGPLAN Notices, vol. 35, no. 10. ACM, 2000, pp. 294–310.
[22]
B. Jacob, G. Guennebaud, et al. (2018) Eigen. [Online]. Available: http://eigen.tuxfamily.org
[23]
M. Kleinbort, O. Salzman, and D. Halperin, “Collision detection or nearest-neighbor search? on the computational bottleneck in sampling-based motion planning,” in Algorthmic Foundations of Robotics (Proc. WAFR 2016). Springer, 2016.
[24]
J. L. Bentley and J. B. Saxe, “Decomposable searching problems I. static-to-dynamic transformation,” J. Algorithms, vol. 1, no. 4, pp. 301–358, 1980.
[25]
S. Brin, “Near neighbor search in large metric spaces,” in Proc. 21st Conf. on Very Large Databases (VLDB), Zurich, Switzerland, 1995, pp. 574–584.
[26]
J. Ichnowski and R. Alterovitz, “Scalable multicore motion planning using lock-free concurrency,” IEEE Transactions on Robotics, vol. 30, no. 5, pp. 1123–1136, 2014.
[27]
S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” Int. J. Robotics Research, vol. 30, no. 7, pp. 846–894, June 2011.
[28]
J. D. Marble and K. E. Bekris, “Asymptotically near optimal planning with probabilistic roadmap spanners,” IEEE Transactions on Robotics, vol. 29, no. 2, pp. 432–444, 2013.
[29]
Raspberry Pi Foundation. (2018) Raspberry Pi 3 model B. [Online]. Available: https://www.raspberrypi.org/products/raspberry-pi-3-model-b/
[30]
Snapsort, Inc. (2018) Intel Atom Z530 vs N270. [Online]. Available: http://cpuboss.com/cpus/Intel-Atom-Z530-vs-Intel-Atom-N270
Information & Contributors
Information
Published In
May 2019
7095 pages
Copyright © 2019.
Publisher
IEEE Press
Publication History
Published: 20 May 2019
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 26 Jan 2025