Abstract
Motion planning is a major topic in robotics . Divergent paths have been taken by practical roboticists and theoretical motion planners. Our goal is to produce algorithms that are practical and have strong theoretical guarantees. Recently, we have proposed a subdivision approach based on soft predicates Wang, C., Chiang, Y.-J., Yap, C.: On soft predicates in subdivision motion planning. In: 29th ACM Symposium on Computational Geometry (SoCG’13), pp. 349–358 (2013). To appear CGTA, Special Issue for SoCG’13 [20], but with a new notion of correctness called resolution-exactness. Unlike mos ques for planar link robots . The technical contributions of this paper are the design of soft predicates for link robots, a novel “T/R splitting method” for subdivision, and feature-based search strategies. The T/R idea is to give primacy to the translational (T) components, and perform splitting of rotational components (R) only at the leaves of a subdivision tree. We implemented our algorithm for a 2-link robot with 4 degrees of freedom (DOFs). Our implementation achieves real-time performance on a variety of nontrivial scenarios. For comparison, our method outperforms sampling-based methods significantly. We extend our 2-link planner to thick link robots with little impact on performance. Note that there are no known exact algorithms for thick link robots.
This work is supported by NSF Grants CCF-0917093, IIS-096053, CNS-1205260, EFRI-1240459, and DOE Grant DE-SC0004874.
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.
- 2.
All constants of Physics have at most 8 digits of accuracy. The speed of light is an exception: it is exact, by definition.
- 3.
- 4.
- 5.
It is standard to identify \(C_{space}(R_0)\) with a subset \(X\subseteq {\mathbb R}^d\). The topology of \(C_{space}(R_0)\) is generally different from that of \(X\). In the case of \(k=2\), the correct topology is easy to simulate since \(S^1\) may be regarded as an interval with the endpoints identified.
- 6.
- 7.
Note that a random strategy is available, but it is never competitive.
References
Barraquand, J., Latombe, J.-C.: Robot motion planning: a distributed representation approach. Int. J. Robot. Res. 10(6), 628–649 (1991)
Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry, 2nd edn. Algorithms and Computation in Mathematics. Springer, Berlin (2006)
Boor, V., Overmars, M.H., van der Stappen., F.: The Gaussian sampling strategy for probabilistic roadmap planners. In: Proceedings of the IEEE Robotics and Automation, vol. 2, pp. 1018–1023. IEEE (1999)
Brooks, R.A., Lozano-Perez, T.: A subdivision algorithm in configuration space for findpath with rotation. In: Proceedings of the 8th International Joint Conference on Artificial intelligence, vol. 2, pp. 799–806. Morgan Kaufmann Publishers Inc., San Francisco (1983)
Choset, H., Lynch, K.M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L.E., Thrun, S.: Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, Boston (2005)
Halperin, D., Kavraki, V., Latombe, J.-C.: Robotics. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, Chapter 41, pp. 755–778. CRC Press LLC (1997)
Hsu, D., Latombe, J.-C., Kurniawati, H.: On the probabilistic foundations of probabilistic roadmap planning. Int. J. Robot. Res. 25(7), 627–643 (2006)
Kavraki, L., Švestka, P., Latombe, C., Overmars, M.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12(4), 566–580 (1996)
Kavraki, L.E.: Random Networks in Configuration Space for Fast Path Planning. PhD thesis, Stanford University (1995)
Kuffner, Jr. J.J., LaValle, S.M.: RRT-connect: an efficient approach to single-query path planning. In: Proceedings of the 2000 IEEE International Conference on Robotics and Automation ICRA’00, vol. 2, pp. 995–1001. IEEE (2000)
LaValle, S., Branicky, M., Lindemann, S.: On the relationship between classical grid search and probabilistic roadmaps. Int J. Robot. Res. 23(7/8), 673–692 (2004)
LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006)
Lumelsky, V., Sun, K.: A unified methodology for motion planning with uncertainty for 2d and 3d two-link robot arm manipulators. Int. J. Robot. Res. 9, 89–104 (1990)
Luo, Z.: Resolution-exact planner for a 2-link planar robot using soft predicates. Master thesis, New York University, Courant Institute, January 2014. Master Thesis Prize (2014)
Luo, Z., Chiang, Y.-J., Lien, J.-M., Yap, C.: Resolution exact algorithms for link robots, 2014. Full paper download with http://www.cs.nyu.edu/exact/doc/linkRobot2014.pdf or http://cse.poly.edu/chiang/wafr14-full.pdf
Sharir, M., Ariel-Sheffi, E.: On the piano movers’ problem: IV. Various decomposable two-dimensional motion planning problems. NYU Robotics Report 58, Courant Institute, New York University (1983)
Sharir, M., O’D’únlaing, C., Yap, C.: Generalized Voronoi diagrams for moving a ladder II: efficient computation of the diagram. Algorithmica 2, 27–59 (1987). Also: NYU-Courant Institute, Robotics Laboratory, No. 33, October (1984)
Şucan, l., Moll, M., Kavraki, L.: The open motion planning library. IEEE Robot. Autom. Mag. 19(4):72–82 (2012). http://ompl.kavrakilab.org
Thrun, S., Burgard, W., Fox, D.: Probabilistic Robotics. MIT Press, Cambridge (2005)
Wang, C., Chiang, Y.-J., Yap, C.: On soft predicates in subdivision motion planning. In: 29th ACM Symposium on Computational Geometry (SoCG’13), pp. 349–358 (2013). To appear CGTA, Special Issue for SoCG’13
Yap, C., Sharma, V., Lien, J.-M.: Towards exact numerical Voronoi diagrams. In: 9th Proceedings of the International Symposium of Voronoi Diagrams in Science and Engineering (ISVD), Invited Talk, , Rutgers University, NJ, pp. 2–16. IEEE 27–29 June 2012
Yap, C.K.: Soft subdivision search in motion planning. In: Proceedings, Robotics Challenge and Vision Workshop (RCV 2013). Best Paper Award, sponsored by Computing Community Consortium (CCC). Robotics Science and Systems Conference (RSS 2013), Berlin, Germany, 27 June 2013. In arXiv:1402.3213v1 [cs.RO]. Full paper from: http://cs.nyu.edu/exact/papers/
Zhang, L., Kim, Y.J., Manocha, D.: Efficient cell labeling and path non-existence computation using C-obstacle query. Int. J. Robot. Res. 27, 11–12 (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendices
Appendices
The full paper [15] has 2 appendices: Appendix I describes the experimental setup including screen shots of the obstacle sets in our experiments. Appendix II provides the basic theory of our Soft Subdivision Search (SSS) framework.
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Luo, Z., Chiang, YJ., Lien, JM., Yap, C. (2015). Resolution-Exact Algorithms for Link Robots. In: Akin, H., Amato, N., Isler, V., van der Stappen, A. (eds) Algorithmic Foundations of Robotics XI. Springer Tracts in Advanced Robotics, vol 107. Springer, Cham. https://doi.org/10.1007/978-3-319-16595-0_21
Download citation
DOI: https://doi.org/10.1007/978-3-319-16595-0_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16594-3
Online ISBN: 978-3-319-16595-0
eBook Packages: EngineeringEngineering (R0)