Knowledge- and structure- driven motion planning

Yajia Zhang, Kris Hauser


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 link pdf link software
  • 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 pdf pdf software
  • Y. Zhang, K. Hauser Unbiased, scalable sampling of protein loop conformations from probabilistic priors. To appear in BMC Structural Biology, 2014. pdf
  • 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. pdf
  • K. Hauser. Minimum Constraint Displacement Motion Planning. In proceedings of Robotics: Science and Systems (RSS), Berlin, Germany, June 2013. pdf
  • 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. pdf
  • Y. Zhang, K. Hauser Unbiased, Scalable Sampling of Constrained Kinematic Loops. In BIBM Workshop on Computational Structural Bioinformatics, Philadelphia, PA, USA, 2012 pdf
  • K. Hauser. The Minimum Constraint Removal Problem with Three Robotics Applications. In Workshop on the Algorithmic Foundations of Robotics, Boston, June 2012. pdf software

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.