Abstract
In this paper, we present an approach towards approximating configuration spaces of 2D and 3D rigid objects. The approximation can be used to identify caging configurations and establish path non-existence between given pairs of configurations. We prove correctness and analyse completeness of our approach. Using dual diagrams of unions of balls and uniform grids on SO(3), we provide a way to approximate a 6D configuration space of a rigid object. Depending on the desired level of guaranteed approximation accuracy, the experiments with our single core implementation show runtime between 5–21 s and 463–1558 s. Finally, we establish a connection between robotic caging and molecular caging from organic chemistry, and demonstrate that our approach is applicable to 3D molecular models. The supplementary material for this paper can be found at https://anvarava.github.io/publications/wafr-2018-supplementary-material.pdf.
A. Varava and J. Frederico Carvalho—These two authors contributed equally.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Throughout the paper \(n \in \{2, 3\}\).
- 2.
A theoretical analysis of different ways to define the free space can be found in [20].
- 3.
By distance here we mean Euclidean distance in \(\mathbb {R}^n\).
- 4.
This is a cover by closed sets, but given \(q' > q\) satisfying \(D(R_{q}) < \varepsilon \) we can use instead \(U(\phi _i,\varepsilon ) = (\phi _i - q', \phi _i + q')\) which results on the same graph.
- 5.
Since the KDTree T uses the Euclidean distance in \(\mathbb {R}^4\) we employ the formula \(\Vert p - q \Vert = 2 \sin (\frac{\rho (p,q)}{2}) \).
References
Barraquand, J., Kavraki, L., Latombe, J.-C., Motwani, R., Li, T.-Y., Raghavan, P.: A random sampling scheme for path planning. IJRR 16(6), 759–774 (1997)
Basch, J., Guibas, L.J., Hsu, D., Nguyen, A.T.: Disconnection proofs for motion planning. In: IEEE ICRA, pp. 1765–1772 (2001)
Behar, E., Lien, J.-M.: Mapping the configuration space of polygons using reduced convolution. In: IEEE/RSJ Intelligent Robots and Systems, pp. 1242–1248 (2013)
Edelsbrunner, H.: Deformable smooth surface design. Discrete Comput. Geom. 21(1), 87–115 (1999)
Kuperberg, W.: Problems on polytopes and convex sets. In: DIMACS Workshop on Polytopes, pp. 584–589 (1990)
Latombe, J.-C.: Robot Motion Planning. Kluwer Academic Publishers, Norwell (1991)
Lozano-Perez, T.: Spatial planning: a configuration space approach. IEEE Trans. Comput. 2, 108–120 (1983)
Mahler, J., Pokorny, F.T., McCarthy, Z., van der Stappen, A.F., Goldberg, K.: Energy-bounded caging: formal definition and 2-D energy lower bound algorithm based on weighted alpha shapes. IEEE RA-L 1(1), 508–515 (2016)
Makita, S., Maeda, Y.: 3D multifingered caging: basic formulation and planning. In: IEEE IROS, pp. 2697–2702 (2008)
Makita, S., Okita, K., Maeda, Y.: 3D two-fingered caging for two types of objects: sufficient conditions and planning. Int. J. Mechatron. Autom. 3(4), 263–277 (2013)
Makita, S., Wan, W.: A survey of robotic caging and its applications. Adv. Robot. 31(19–20), 1071–1085 (2017)
Makapunyo, T., Phoka, T., Pipattanasomporn, P., Niparnan, N., Sudsang, A.: Measurement framework of partial cage quality based on probabilistic motion planning. In: IEEE ICRA, pp. 1574–1579 (2013)
McCarthy, Z., Bretl, T., Hutchinson, S.: Proving path non-existence using sampling and alpha shapes. In: IEEE ICRA, pp. 2563–2569 (2012)
Mitra, T., Jelfs, K.E., Schmidtmann, M., Ahmed, A., Chong, S.Y., Adams, D.J., Cooper, A.I.: Molecular shape sorting using molecular organic cages. Nat. Chem. 5, 276 (2013)
Milenkovic, V., Sacks, E., Trac, S.: Robust complete path planning in the plane. In: Frazzoli, E., Lozano-Perez, T., Roy, N., Rus, D. (eds.) Algorithmic Foundations of Robotics X, pp. 37–52. Springer, Heidelberg (2013)
Pipattanasomporn, P., Sudsang, A.: Two-finger caging of concave polygon. In: IEEE ICRA, pp. 2137–2142 (2006)
Pipattanasomporn, P., Sudsang, A.: Two-finger caging of nonconvex polytopes. IEEE T-RO 27(2), 324–333 (2011)
Pokorny, F.T., Stork, J.A., Kragic, D.: Grasping objects with holes: a topological approach. In: IEEE ICRA, pp. 1100–1107 (2013)
Rimon, E., Blake, A.: Caging planar bodies by one-parameter two-fingered gripping systems. IJRR 18(3), 299–318 (1999)
Rodriguez, A., Mason, M.T.: Path connectivity of the free space. IEEE T-RO 28(5), 1177–1180 (2012)
Rodriguez, A., Mason, M.T., Ferry, S.: From caging to grasping. IJRR 31(7), 886–900 (2012)
Rother, M., Nussbaumer, M.G., Rengglic, K., Bruns, N.: Protein cages and synthetic polymers: a fruitful symbiosis for drug delivery applications, bionanotechnology and materials science. Chem. Soc. Rev. 45, 6213 (2016)
Stork, J.A., Pokorny, F.T., Kragic, D.: Integrated motion and clasp planning with virtual linking. In: IEEE/RSJ IROS, pp. 3007–3014 (2013)
Stork, J.A., Pokorny, F.T., Kragic, D.: A topology-based object representation for clasping, latching and hooking. In: IEEE-RAS International Conference on Humanoid Robots, pp. 138–145 (2013)
Pereira, G.A.S., Campos, M.F.M., Kumar, V.: Decentralized algorithms for multi-robot manipulation via caging. IJRR 23(7–8), 783–795 (2004)
Varava, A., Kragic, D., Pokorny, F.T.: Caging grasps of rigid and partially deformable 3-d objects with double fork and neck features. IEEE T-RO 32(6), 1479–1497 (2016)
Varava, A., Carvalho, J.F., Pokorny, F.T., Kragic, D.: Caging and path non-existence: a deterministic sampling-based verification algorithm. In: ISRR (2017). Preprint: https://www.csc.kth.se/~jfpbdc/path_non_ex.pdf
Vahedi, M., van der Stappen, A.F.: Caging polygons with two and three fingers. IJRR 27(11–12), 1308–1324 (2008)
Wang, Z., Kumar, V.: Object closure and manipulation by multiple cooperating mobile robots. In: IEEE ICRA, pp. 394–399 (2002)
Wise, K., Bowyer, A.: A survey of global configuration-space mapping techniques for a single robot in a static environment. IJRR 19(8), 762–779 (2000)
Zhang, L., Young, J.K., Manocha, D.: Efficient cell labelling and path non-existence computation using C-obstacle query. IJRR 27(11–12), 1246–1257 (2008)
Zhu, D., Latombe, J.: New heuristic algorithms for efficient hierarchical path planning. IEEE T-RO 7(1), 9–20 (1991)
Yershova, A., Jain, S., LaValle, S.M., Mitchell, J.C.: Generating uniform incremental grids on SO(3) using the Hopf fibration. IJRR 29, 801–812 (2009)
Zomorodian, A., Edelsbrunner, H.: Fast software for box intersections. In: Proceedings of the 16th Annual Symposium on Computational Geometry, pp. 129–138 (2000)
Liu, J., Xin, S., Gao, Z., Xu, K., Tu, C., Chen, B.: Caging loops in shape embedding space: theory and computation. In: ICRA (2018)
Acknowledgements
The authors are grateful to D. Devaurs, L. Kavraki, and O. Kravchenko for their insights into molecular caging. This work has been supported by the Knut and Alice Wallenberg Foundation and Swedish Research Council.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Varava, A., Carvalho, J.F., Pokorny, F.T., Kragic, D. (2020). Free Space of Rigid Objects: Caging, Path Non-existence, and Narrow Passage Detection. In: Morales, M., Tapia, L., Sánchez-Ante, G., Hutchinson, S. (eds) Algorithmic Foundations of Robotics XIII. WAFR 2018. Springer Proceedings in Advanced Robotics, vol 14. Springer, Cham. https://doi.org/10.1007/978-3-030-44051-0_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-44051-0_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-44050-3
Online ISBN: 978-3-030-44051-0
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)