2015, Volume 1, Issue 1
Engineering >> 2015, Volume 1, Issue 1 doi: 10.15302/J-ENG-2015009
Efficient Configuration Space Construction and Optimization for Motion Planning
1 Department of Computer Science, The University of Hong Kong, Hong Kong, China
2 Department of Computer Science, University of N. Carolina, Chapel Hill, NC 27599-3175, USA
Next Previous
Abstract
The configuration space is a fundamental concept that is widely used in algorithmic robotics. Many applications in robotics, computer-aided design, and related areas can be reduced to computational problems in terms of configuration spaces. In this paper, we survey some of our recent work on solving two important challenges related to configuration spaces: ① how to efficiently compute an approximate representation of high-dimensional configuration spaces; and ② how to efficiently perform geometric proximity and motion planning queries in high-dimensional configuration spaces. We present new configuration space construction algorithms based on machine learning and geometric approximation techniques. These algorithms perform collision queries on many configuration samples. The collision query results are used to compute an approximate representation for the configuration space, which quickly converges to the exact configuration space. We also present parallel GPU-based algorithms to accelerate the performance of optimization and search computations in configuration spaces. In particular, we design efficient GPU-based parallel k-nearest neighbor and parallel collision detection algorithms and use these algorithms to accelerate motion planning.
Keywords
configuration space ; motion planning ; GPU parallel algorithm
Figures
Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
References
[ 1 ] G. Litzenberger. Professional service robots: Continued increase. Statistical Department, International Federation of Robotics, Tech. Rep., 2012
[ 2 ] E. Guizzo, E. Ackerman. How Rethink Robotics built its new Baxter robot worker. IEEE Spectrum, http://spectrum.ieee.org/robotics/industrial-robots/rethink-robotics-baxter-robot-factory-worker, 2012
[ 3 ] K. Yamazaki, Home-assistant robot for an aging society. Proc. IEEE, 2012, 100(8): 2429–2441
[ 4 ] S. Cousins. Robots for humanity. http://www.willowgarage.com/blog/2011/07/13/robots-humanity, 2012
[ 5 ] S. Kajita, Cybernetic human hrp-4c: A humanoid robot with human-like proportions. In: C. Pradalier, R. Siegwart, G. Hirzinger, eds. Robotics Research, ser. Springer Tracts in Advanced Robotics, vol 70. Berlin: Springer, 2011, 70: 301–314
[ 6 ] M. Montemerlo, Junior: The Stanford entry in the urban challenge. J. Field Robot., 2008, 25(9): 569–597 link1
[ 7 ] M. Bonfe, Towards automated surgical robotics: A requirements engineering approach. In: Proceedings of IEEE RAS EMBS International Conference on Biomedical Robotics and Biomechatronics, 2012: 56–61
[ 8 ] E. Guizzo. Robots enter fukushima reactors, detect high radiation. IEEE Spectrum, 2011. http://spectrum.ieee.org/automaton/robotics/industrial-robots/robots-enter-fukushima-reactors-detect-high-radiation
[ 9 ] E. Ackerman. Latest alphadog robot prototypes get less noisy, more brainy, 2012. http://spectrum.ieee.org/automaton/robotics/military-robots/latest-ls3-alphadog-prototypes-get-less-noisy-more-brainy
[10] S. Thrun, W. Burgard, D. Fox. Probabilistic Robotics. Boston, MA: The MIT Press, 2005
[11] R. B. Rusu, N. Blodow, Z. C. Marton, M. Beetz. Close-range scene segmentation and reconstruction of 3D point cloud maps for mobile manipulation in domestic environments. In: Proceedings of International Conference on Intelligent Robots and Systems, 2009: 1–9
[12] T. Lozano-Pérez, J. L. Jones, E. Mazer, P. A. O’Donnell. Task-level planning of pick-and-place robot motions. Computer, 1989, 22(3): 21–29
[13] L. Kaelbling, T. Lozano-P’erez. Unifying perception, estimation and action for mobile manipulation via belief space planning. In: Proceedings of IEEE International Conference on Robotics and Automation, 2012: 2952–2959
[14] L. Kaelbling, T. Lozano-Perez. Hierarchical task and motion planning in the now. In: Proceedings of IEEE International Conference on Robotics and Automation, 2011: 1470–1477
[15] R. F. Stengel. Optimal Control and Estimation (Dover Books on Advanced Mathematics). New York: Dover Publications, 1994
[16] K. J. Astrom, B. Wittenmark. Adaptive Control. 2nd ed. Boston, MA: Addison-Wesley Longman Publishing Co., Inc., 1994
[17] V. Unhelkar, J. Perez, J. Boerkoel, J. Bix, S. Bartscher, J. Shah. Towards control and sensing for an autonomous mobile robotic assistant navigating assembly lines. In: IEEE International Conference on Robotics and Automation, 2014: 4161–4167
[18] L. P. Ellekilde, H. G. Petersen. Motion planning efficient trajectories for industrial bin-picking. Int. J. Robot. Res., 2013, 32(9¯10): 991–1004
[19] O. Khatib. Real-time obstacle avoidance for manipulators and mobile robot. Int. J. Robot. Res., 1986, 5(1): 90–98
[20] T. Lozano-Pérez, M. A. Wesley. An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM, 1979, 22(10): 560–570 link1
[21] T. Lozano-Pérez. Automatic planning of manipulator transfer movements. IEEE Trans. Syst. Man Cybern., 1981, 11(10): 681–698 link1
[22] T. Lozano-Pérez. Spatial planning: A configuration space approach. IEEE Trans. Comput., 1983, C-32(2): 108–120 link1
[23] B. Chazelle. Approximation and decomposition of shapes. In: J. T. Schwartz, C. K. Yap, eds. Algorithmic and Geometric Aspects of Robotics. Hillsdale: Lawrence Erlbaum Associates, 1987: 145–185
[24] J. F. Canny. Some algebraic and geometric computations in PSPACE. In: Proceedings of ACM symposium on Theory of Computing, 1988: 460–467
[25] J. F. Canny, J. Reif, B. Donald, P. Xavier. On the complexity of kinodynamic planning. In: Proceedings of Symposium on Foundations of Computer Science, 1988: 306–316
[26] L. Kavraki, P. Svestka, J. C. Latombe, M. Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom., 1996, 12(4): 566–580 link1
[27] J. J. Kuffner, S. LaValle. RRT-connect: An efficient approach to single-query path planning. In: Proceedings of IEEE International Conference on Robotics and Automation, 2000: 995–1001
[28] V. I. Arnold. Mathematical Methods of Classical Mechanics. New York: Springer-Verlag, 1989
[29] D. Halperin. Robust geometric computing in motion. Int. J. Robot. Res., 2002, 21(3): 219–232
[30] J. M. Lien. Covering Minkowski sum boundary using points with applications. Comput. Aided Geom. Des., 2008, 25(8): 652–666
[31] J. M. Lien, N. M. Amato. Approximate convex decomposition of polyhedral. In: Proceedings of the ACM Symposium on Solid and Physical Modeling, 2007: 121–131
[32] J. M. Lien. A simple method for computing Minkowski sum boundary in 3D using collision detection. In: Algorithmic Foundation of Robotics VIII, Springer Tracts in Advanced Robotics, vol 57. Berlin: Springer, 2009: 401–415
[33] G. Varadhan, Y. J. Kim, S. Krishnan, D. Manocha. Topology preserving approximation of free configuration space. In: Proceedings of International Conference on Robotics and Automation, 2006: 3041–3048
[34] L. Zhang, Y. J. Kim, D. Manocha. A hybrid approach for complete motion planning. In: Proceedings of International Conference on Intelligent Robots and Systems, 2007: 7–14
[35] N. M. Amato, O. B. Bayazit, L. K. Dale, C. Johns, D. Vallejo. OBPRM: An obstacle-based prm for 3D workspaces. In: Proceedings of Workshop on the Algorithmic Foundations of Robotics on Robotics, 1998: 155–168
[36] V. Boor, M. Overmars, A. van der Stappen. The Gaussian sampling strategy for probabilistic roadmap planners. In: Proceedings of IEEE International Conference on Robotics and Automation, 1999: 1018–1023
[37] D. Hsu, L. E. Kavraki, J. C. Latombe, R. Motwani, S. Sorkin. On finding narrow passages with probabilistic roadmap planners. In: Proceedings of Workshop on the Algorithmic Foundations of Robotics on Robotics, 1998: 141–153
[38] S. Rodriguez, X. Tang, J. M. Lien, N. M. Amato. An obstacle-based rapidly-exploring random tree. In: Proceedings of IEEE International Conference on Robotics and Automation, 2006: 895–900
[39] L. Zhang, D. Manocha. An efficient retraction-based RRT planner. In: Proceedings of IEEE International Conference on Robotics and Automation, 2008: 3743–3750
[40] Z. Sun, D. Hsu, T. Jiang, H. Kurniawati, J. H. Reif. Narrow passage sampling for probabilistic roadmap planners. IEEE Trans. Robot., 2005, 21(6): 1105–1115 link1
[41] J. Denny, N. M. Amato. Toggle PRM: Simultaneous mapping of C-free and C-obstacle–A study in 2D. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, 2011: 2632–2639
[42] L. Zhang, Y. J. Kim, G. Varadhan, D. Manocha. Generalized penetration depth computation. Comput. Aided Des., 2007, 39(8): 625–638
[43] L. Zhang, Y. J. Kim, D. Manocha. A fast and practical algorithm for generalized penetration depth computation. In: Proceedings of Robotics: Science and Systems, 2007
[44] C. Je, M. Tang, Y. Lee, M. Lee, Y. J. Kim. Polydepth: Realtime penetration depth computation using iterative contact-space projection. ACM Transactions on Graphics, 2012, 31(3): 5:1–5:14
[45] J. H. Reif. Complexity of the mover’s problem and generalizations. In: Proceedings of Annual Symposium on Foundations of Computer Science, 1979: 421–427
[46] P. Cheng, G. Pappas, V. Kumar. Decidability of motion planning with differential constraints. In: Proceedings of International Conference on Robotics and Automation, 2007: 1826–1831
[47] S. Karaman, E. Frazzoli. Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res., 2011, 30(7): 846–894
[48] D. Hsu, J. C. Latombe, H. Kurniawati. On the probabilistic foundations of probabilistic roadmap planning. Int. J. Robot. Res., 2006, 25(7): 627–643
[49] N. Ratliff, M. Zucker, J. A. D. Bagnell, S. Srinivasa. CHOMP: Gradient optimization techniques for efficient motion planning. In: Proceedings of International Conference on Robotics and Automation, 2009: 489–494
[50] J. Schulman, J. Ho, A. Lee, I. Awwal, H. Bradlow, P. Abbeel. Finding locally optimal, collision-free trajectories with sequential convex optimization. In: Proceedings of Robotics: Science and Systems, 2013
[51] M. Likhachev, D. Ferguson, G. Gordon, A. Stentz, S. Thrun. Anytime dynamic A*: An anytime, replanning algorithm. In: Proceedings of the International Conference on Automated Planning and Scheduling, 2005
[52] J. Pan, X. Zhang, D. Manocha. Efficient penetration depth approximation using active learning. ACM Transactions on Graphics, 2013, 32(6): 191:1–191:12
[53] J. Schulman, et al. Motion planning with sequential convex optimization and convex collision checking. Int. J. Robot. Res., 2014, 33(9): 1251–1270
[54] J. Pan, C. Lauterbach, D. Manocha. g-Planner: Real-time motion planning and global navigation using GPUs. In: Proceedings of AAAI Conference on Artificial Intelligence, 2010: 1245–1251
[55] N. M. Amato, L. Dale. Probabilistic roadmap methods are embarrassingly parallel. In: Proceedings of IEEE International Conference on Robotics and Automation, 1999: 688–694
[56] V. N. Vapnik. The Nature of Statistical Learning Theory. New York: Springer-Verlag, 1995
[57] S. J. Huang, R. Jin, Z. H. Zhou. Active learning by querying informative and representive examples. In: Proceedings of Advances in Neural Information Processing Systems, 2010: 892–900
[58] M. Karasuyama, I. Takeuchi. Multiple incremental decremental learning of support vector machines. IEEE Trans. Neural Netw., 2010, 21(7): 1048–1059 link1
[59] C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, D. Manocha. Fast BVH construction on GPUs. Comput. Graph. Forum, 2009, 28(2): 375–384 link1
[60] S. Tzeng, L. Y. Wei. Parallel white noise generation on a GPU via cryptographic hash. In: Proceedings of the Symposium on Interactive 3D Graphics and Games, 2008: 79–87
[61] J. Pan, C. Lauterbach, D. Manocha. Efficient nearest-neighbor computation for GPU-based motion planning. In: Proceedings of International Conference on Intelligent Robots and Systems, 2010: 2243–2248
[62] J. Pan, D. Manocha. Bi-level locality sensitive hashing for k-nearest neighbor computation. In: Proceedings of International Conference on Data Engineering, 2012: 378–389
[63] C. Lauterbach, Q. Mo, D. Manocha. gProximity: Hierarchical GPU-based operations for collision and distance queries. Comput. Graph. Forum, 2010, 29(2): 419–428 link1
京公网安备 11010502051620号
