Knowledge- and structure- driven motion planning
Yajia Zhang, Kris Hauser
Summary
Although configuration space paradigms lead to effective general-purpose motion planning algorithms for problems of moderate scale (dozens of dimensions), they work poorly on very large-scale problems that involve hundreds or thousands of dimensions, mixed continuous and discrete reasoning, or require near-optimal solutions. New planning paradigms are needed to handle these large problems. This project is investigating two complementary approaches: 1) knowledge-driven, in which good solutions exhibit of common patterns that can be learned automatically (e.g., a humanoid using similar stepping motions to navigate uneven terrain), and 2) structure-driven, in which the constraints and performance criteria possess inherent structure that can be exploited to compute better plans more quickly (e.g., the motions of distant objects are essentially decoupled). We are applying these techniques to humanoid robots, manipulation under clutter, and the motion of biological molecules.
- K. Hauser. Learning the Problem-Optimum Map: Analysis and
Application to Global Optimization in Robotics. In IEEE Transactions on Robotics, PP(99)1-12. Also in arXiv:1605.04636 [cs.RO], 2016
- K. Hauser. The Minimum Constraint Removal Problem with Three Robotics Applications. International Journal of Robotics Research, 33(1):5-17, January, 2014. doi: 10.1177/0278364913507795
- Y. Zhang, K. Hauser Unbiased, scalable sampling of protein loop conformations from probabilistic priors. To appear in BMC Structural Biology, 2014.
-
Y. Zhang, J. Luo, K. Hauser, R. Ellenberg, P. Oh, H.A. Park, M. Paldhe, and C.S.G. Lee. Motion Planning of Ladder Climbing for Humanoid Robots. In proceedings of IEEE Conf. on Technologies for Practical Robot Applications (TePRA), April 2013.
-
K. Hauser. Minimum Constraint Displacement Motion Planning. In proceedings of Robotics: Science and Systems (RSS), Berlin, Germany, June 2013.
- Y. Zhang, K. Hauser, and J. Luo. Unbiased, Scalable Sampling of Closed Kinematic Chains. To appear in IEEE Int'l Conference on Robotics and Automation (ICRA), Karlsruhe, Germany, May 2013.
- Y. Zhang, K. Hauser Unbiased, Scalable Sampling of Constrained Kinematic Loops. In BIBM Workshop on Computational Structural Bioinformatics, Philadelphia, PA, USA, 2012
-
K. Hauser. The Minimum Constraint Removal Problem with Three Robotics Applications. In Workshop on the Algorithmic Foundations of Robotics, Boston, June 2012.
Illustration of the Minimum Constraint Displacement algorithm on a problem with 100 circular obstacles. A roadmap is grown using sampling-based techniques, with increasing exploration limits, until a path is found to the goal. Local optimization improves path quality and displacement magnitudes. The process repeats until convergence.
- Implementation of MCR in the Lightweight Motion Planning Library
- Sub-Loop Inverse Kinematics Monte Carlo
NSF Robust Intelligence Grant #1218534
