期刊首页 优先出版 当期阅读 过刊浏览 作者中心 关于期刊 English

《工程(英文)》 >> 2015年 第1卷 第1期 doi: 10.15302/J-ENG-2015009

运动规划的高效配置空间构建与优化

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

收稿日期: 2015-03-12 修回日期: 2015-03-20 录用日期: 2015-03-25 发布日期: 2015-03-31

下一篇 上一篇

摘要

配置空间是算法机器人学领域使用较为广泛的一种基本概念。机器人学、计算机辅助设计与相关领域的诸多应用都可归类为配置空间方面的计算问题。本文将对近期与配置空间相关的两项重大挑战的解决方案成果进行探讨:①如何高效计算高维配置空间的近似表达;②如何在高维配置空间内高效执行几何学接近度与运动规划查询。基于机器学习与几何学近似技术,笔者在此提出几种新型配置空间构建算法。上述算法对多个配置样本进行碰撞查询。得出的碰撞查询结果将用来计算配置空间的近似表达,可快速聚合至准确的配置空间;同时还提出了基于并行图形处理器(GPU)的算法,以便加速配置空间优化与搜索计算的性能情况。笔者特别设计出了基于GPU的并行k最近邻算法与并行碰撞检测算法,并使用这些算法来加快运动规划。

图片

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

参考文献

[ 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 链接1

[ 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 链接1

[21] T. Lozano-Pérez. Automatic planning of manipulator transfer movements. IEEE Trans. Syst. Man Cybern., 1981, 11(10): 681–698 链接1

[22] T. Lozano-Pérez. Spatial planning: A configuration space approach. IEEE Trans. Comput., 1983, C-32(2): 108–120 链接1

[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 链接1

[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 链接1

[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 链接1

[59] C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, D. Manocha. Fast BVH construction on GPUs. Comput. Graph. Forum, 2009, 28(2): 375–384 链接1

[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 链接1

相关研究