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

工程(英文) ›› 2015, Vol. 1 ›› Issue (1) : 46-57.

PDF(2919 KB)
PDF(2919 KB)
工程(英文) ›› 2015, Vol. 1 ›› Issue (1) : 46-57. DOI: 10.15302/J-ENG-2015009
研究论文
Research

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

作者信息 +

Efficient Configuration Space Construction and Optimization for Motion Planning

Author information +
History +

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

引用本文

导出引用
. . Engineering. 2015, 1(1): 46-57 https://doi.org/10.15302/J-ENG-2015009

参考文献

[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
[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/in<?Pub Caret?>dustrial-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 
[21]
T. Lozano-Pérez. Automatic planning of manipulator transfer movements. IEEE Trans. Syst. Man Cybern., 1981, 11(10): 681–698 
[22]
T. Lozano-Pérez. Spatial planning: A configuration space approach. IEEE Trans. Comput., 1983, C-32(2): 108–120
[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
[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
[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 
[59]
C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, D. Manocha. Fast BVH construction on GPUs. Comput. Graph. Forum, 2009, 28(2): 375–384
[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

Acknowledgements

This research was partially supported by the Army Research Office, the National Science Foundation, Willow Garage, and the Seed Funding Programme for Basic Research at the University of Hong Kong.
Compliance with ethics guidelines
Jia Pan and Dinesh Manocha declare that they have no conflict of interest or financial conflicts to disclose.
基金
该研究得到了美国陆军研究办公室、美国国家科学基金会、Willow Garage公司香港大学基础研究基金项目的部分支持。()
PDF(2919 KB)

Accesses

Citation

Detail

段落导航
相关文章

/