TY - GEN
T1 - Resolution-exact algorithms for link robots
AU - Luo, Zhongdi
AU - Chiang, Yi Jen
AU - Lien, Jyh Ming
AU - Yap, Chee
N1 - Funding Information:
This work is supported by NSF Grants CCF-0917093, IIS-096053, CNS-1205260, EFRI-1240459, and DOE Grant DE-SC0004874.
Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
KW - Exact algorithms
KW - Link robots
KW - Motion planning
KW - Resolution-exact algorithms
KW - Soft predicates
KW - Subdivision algorithms
UR - http://www.scopus.com/inward/record.url?scp=84946012027&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84946012027&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-16595-0_21
DO - 10.1007/978-3-319-16595-0_21
M3 - Conference contribution
AN - SCOPUS:84946012027
SN - 9783319165943
T3 - Springer Tracts in Advanced Robotics
SP - 353
EP - 370
BT - Algorithmic Foundations of Robotics - Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014
A2 - van der Stappen, A. Frank
A2 - Levent Akin, H.
A2 - Amato, Nancy M.
A2 - Isler, Volkan
PB - Springer Verlag
T2 - 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014
Y2 - 3 August 2014 through 5 August 2014
ER -