Modular Robot Control and Continuous Constraint Satisfaction

Abstract

Continuous constraint satisfaction is at the core of many real-world applications. One example is in the control of modular, hyper-redundant robots, which are robots with many more degrees of free-dom than required for typical tasks. Casting the control problem as a constraint problem is a promising approach for robustly handling a variety of non-standard constraints found in such robots. However, before we can scale to the many degrees of freedom and nonlinearities of this system and deploy constraint solvers for embedded, real-time control, we need to better understand the complex-ity issues arising in these problems. In this paper, we first present a parametric model for robotic con-trol. We then study the complexity of related but simpler problems by analyzing two classes of ar-tificial constraint satisfaction problems inspired by (discrete) 3-SAT problems, which have a strong re-lation between structure and search cost. With this, we also propose a generic benchmarking model for continuous constraint satisfaction problems. 1