Optimization for control and planning of multi-contact dynamic motion

The fundamental promise of robotics centers on the ability to productively interact with a complex and changing world. Yet, current robots are largely limited to basic tasks in structured environments and act slowly and cautiously, afraid of incidental contact. In this thesis, we consider a class of control and planning problems for robots dynamically interacting with their environment. We address challenges that arise from non-smooth motions induced by contact, where discontinuities result from impact events and frictional forces. First, we examine the problem of trajectory optimization in contact-rich environments, and present two algorithms for synthesizing motions which make and break contact. The novel contact-implicit trajectory optimization algorithm lifts the problem and reasons over the set of possible contacts forces. In doing so, we eliminate the requirement for an a priori sequencing of the active contacts, and avoid explicit combinatorial complexity. We also introduce a direct collocation algorithm for optimizing high-accuracy trajectories, given an arbitrary contact schedule. This approach eliminates drift in the numerical integration of contact constraints, even when constraints result in closed kinematic chains and require non-minimal coordinates. Second, this thesis concerns questions of control synthesis and provable stability verification of a robot making and breaking contact. To verify stability, we introduce an algorithm for discovering polynomial Lyapunov functions, where the system dynamics include impacts and friction. We leverage the measure differential inclusion representation of non-smooth contact mechanics to efficiently optimize over Lyapunov functions in multi-contact settings. Since avoiding hazardous falls is a primary necessity for bipedal walking robots, we use similar tools to characterize the capabilities of multiple simple models used for balancing and push recovery. Using the notions of barrier functions and occupation measures, we explicitly bound the set of disturbances from which a robot can recover by balancing or stepping. The primary contributions of this thesis are computational in nature, and we heavily leverage modern approaches to both general nonlinear programming and convex optimization. Sums-of-squares, an approach to polynomial optimization utilizing semidefinite programming, plays a central role in our methods for formal stability analysis.