Please wait a minute...
Submit  |   Chinese  | 
Advanced Search
   Home  |  Online Now  |  Current Issue  |  Focus  |  Archive  |  For Authors  |  Journal Information   Open Access  
Submit  |   Chinese  | 
Engineering    2015, Vol. 1 Issue (1) : 46 -57
Research |
Efficient Configuration Space Construction and Optimization for Motion Planning
Jia Pan1,(),Dinesh Manocha2
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

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     
Corresponding Authors: Jia Pan   
Just Accepted Date: 31 March 2015   Issue Date: 02 July 2015
E-mail this article
E-mail Alert
Articles by authors
Jia Pan
Dinesh Manocha
Cite this article:   
Jia Pan,Dinesh Manocha. Efficient Configuration Space Construction and Optimization for Motion Planning[J]. Engineering, 2015, 1(1): 46 -57 .
URL:     OR
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,, 2012
3   K. Yamazaki,  Home-assistant robot for an aging society. Proc. IEEE, 2012, 100(8): 2429–2441 
4   S. Cousins. Robots for 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.<?Pub Caret?>dustrial-robots/robots-enter-fukushima-reactors-detect-high-radiation
9   E. Ackerman. Latest alphadog robot prototypes get less noisy, more brainy, 2012.
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
[1] Holger Krueger. Standardization for Additive Manufacturing in Aerospace[J]. Engineering, 2017, 3(5): 585 .
[2] Joe A. Sestak Jr.. High School Students from 157 Countries Convene to Address One of the 14 Grand Challenges for Engineering: Access to Clean Water[J]. Engineering, 2017, 3(5): 583 -584 .
[3] Lance A. Davis. Climate Agreement—Revisited[J]. Engineering, 2017, 3(5): 578 -579 .
[4] Ben A. Wender, M. Granger Morgan, K. John Holmes. Enhancing the Resilience of Electricity Systems[J]. Engineering, 2017, 3(5): 580 -582 .
[5] Jin-Xun Liu, Peng Wang, Wayne Xu, Emiel J. M. Hensen. Particle Size and Crystal Phase Effects in Fischer-Tropsch Catalysts[J]. Engineering, 2017, 3(4): 467 -476 .
[6] Luis Ribeiro e Sousa, Tiago Miranda, Rita Leal e Sousa, Joaquim Tinoco. The Use of Data Mining Techniques in Rockburst Risk Assessment[J]. Engineering, 2017, 3(4): 552 -558 .
[7] Maggie Bartolomeo. Third Global Grand Challenges Summit for Engineering[J]. Engineering, 2017, 3(4): 434 -435 .
[8] Michael Powalla, Stefan Paetel, Dimitrios Hariskos, Roland Wuerz, Friedrich Kessler, Peter Lechner, Wiltraud Wischmann, Theresa Magorian Friedlmeier. Advances in Cost-Efficient Thin-Film Photovoltaics Based on Cu(In,Ga)Se2[J]. Engineering, 2017, 3(4): 445 -451 .
[9] Raffaella Ocone. Reconciling “Micro” and “Macro” through Meso-Science[J]. Engineering, 2017, 3(3): 281 -282 .
[10] Baoning Zong, Bin Sun, Shibiao Cheng, Xuhong Mu, Keyong Yang, Junqi Zhao, Xiaoxin Zhang, Wei Wu. Green Production Technology of the Monomer of Nylon-6: Caprolactam[J]. Engineering, 2017, 3(3): 379 -384 .
[11] Pengcheng Xu, Yong Jin, Yi Cheng. Thermodynamic Analysis of the Gasification of Municipal Solid Waste[J]. Engineering, 2017, 3(3): 416 -422 .
[12] Lei Xu, Jinhui Peng, Hailong Bai, C. Srinivasakannan, Libo Zhang, Qingtian Wu, Zhaohui Han, Shenghui Guo, Shaohua Ju, Li Yang. Application of Microwave Melting for the Recovery of Tin Powder[J]. Engineering, 2017, 3(3): 423 -427 .
[13] Ee Teng Kho, Salina Jantarang, Zhaoke Zheng, Jason Scott, Rose Amal. Harnessing the Beneficial Attributes of Ceria and Titania in a Mixed-Oxide Support for Nickel-Catalyzed Photothermal CO2 Methanation[J]. Engineering, 2017, 3(3): 393 -401 .
[14] Ke Dang, Tuo Wang, Chengcheng Li, Jijie Zhang, Shanshan Liu, Jinlong Gong. Improved Oxygen Evolution Kinetics and Surface States Passivation of Ni-Bi Co-Catalyst for a Hematite Photoanode[J]. Engineering, 2017, 3(3): 285 -289 .
[15] Mu Xiao, Songcan Wang, Supphasin Thaweesak, Bin Luo, Lianzhou Wang. Tantalum (Oxy)Nitride: Narrow Bandgap Photocatalysts for Solar Hydrogen Generation[J]. Engineering, 2017, 3(3): 365 -378 .
Copyright © 2015 Higher Education Press & Engineering Sciences Press, All Rights Reserved.