Sampling-Based Polytopic Trees for Approximate Optimal Control of Piecewise Affine Systems

Sadra Sadraddini, Russ TedrakeICRA 2018 · OpenReview

Abstract

Piecewise affine (PWA) systems are widely used to model highly nonlinear behaviors such as contact dynamics in robot locomotion and manipulation. Existing control techniques for PWA systems have computational drawbacks, both in offline design and online implementation. In this paper, we introduce a method to obtain feedback control policies and a corresponding set of admissible initial conditions for discrete-time PWA systems such that all the closed-loop trajectories reach a goal polytope, while a cost function is optimized. The idea is conceptually similar to LQR-trees, which consists of three steps: (1) open-loop trajectory optimization, (2) feedback control for computation of "funnels" of states around trajectories, and (3) repeating (1) and (2) in a way that the funnels are grown backward from the goal in a tree fashion and fill the state-space as much as possible. We show PWA dynamics can be exploited to combine steps (1) and (2) into a single step that is tackled using mixed-integer convex programming (MICP), which makes the method suitable for dealing with hard constraints. Illustrative examples on contact-based dynamics are presented.

Introduction

Robotic tasks involving impacts and contacts—such as walking, running, or dexterous manipulation—are inherently difficult to control. These systems are typically modeled as Piecewise Affine (PWA) systems, a class of hybrid systems where the dynamics change abruptly depending on the state and control inputs (e.g., whether a robotic foot is in the air or touching the ground).

The challenge in controlling PWA systems lies in the dual nature of the decision-making process: the controller must determine both the continuous control forces and the discrete sequence of contact modes. While Mixed-Integer Convex Programming (MICP) can solve these problems optimally, the computational cost is prohibitive for real-time applications. Conversely, sampling-based methods like LQR-trees, which work well for smooth nonlinear systems, struggle with the non-smoothness and hard constraints characteristic of contact dynamics.

The Polytopic Tree Method

This paper introduces Polytopic Trees, a sampling-based approach that builds a library of control laws offline to enable high-speed online execution. The method centers on growing a tree of stabilizing "funnels" backward from a goal region.

1. Polytopic Parameterization

Instead of searching for a single trajectory, the algorithm identifies a sequence of polytopes—specifically paralleltopes. These polytopes act as "funnels": any state starting within a polytope is guaranteed to transition into the next polytope in the sequence, eventually reaching the goal. This provides a robust region of attraction rather than a single path.

2. Unified Optimization via MICP

A key contribution of this work is the realization that for PWA systems, trajectory optimization and funnel computation can be fused into a single MICP problem. By using the "big-M" method to handle the switching logic of the PWA dynamics, the algorithm simultaneously finds an open-loop path and the largest possible stabilizing funnel around it. This "one-shot" approach is significantly more efficient than the iterative methods required for general nonlinear systems.

3. Backward Tree Growth

Inspired by Rapidly-exploring Random Trees (RRT), the algorithm samples the state space. If a sampled point is not already covered by an existing funnel, the system solves an MICP to "grow" a new branch from that sample back to the existing tree. Over time, the union of these polytopes covers the reachable state space.

Online Control and Real-Time Performance

The primary advantage of the Polytopic Tree is its online efficiency. Once the tree is constructed offline, the online controller performs a simple lookup:

  1. Identify which polytope currently contains the robot's state.
  2. Apply the pre-computed linear feedback law associated with that polytope.

This reduces the control problem from a complex optimization task to basic matrix multiplication and logical checks. Because the algorithm uses paralleltopes, the "point-in-polytope" check is a computationally inexpensive linear algebra operation.

Experimental Results

The authors evaluated the method on three benchmarks designed to test contact dynamics:

  • Inverted Pendulum with a Wall: The method successfully mapped regions of the state space that standard Hybrid Model Predictive Control (MPC) could not reach due to limited look-ahead horizons.
  • Bouncing Ball: The tree achieved 86% coverage of the reachable state space within 100 iterations, utilizing 1,049 polytopes to guarantee stability.
  • Planar Pushing: In a complex 6-DOF task involving sticking and sliding friction, the Polytopic Tree controller operated at 20-50Hz. In contrast, an online hybrid MPC solver managed only 0.5-1.2Hz, demonstrating a 40x speedup in decision-making.

Conclusion and Future Work

Polytopic Trees offer a powerful framework for the feedback control of hybrid systems with contact constraints. By shifting the heavy computational burden of mixed-integer optimization to an offline sampling phase, the method enables real-time, robust control of complex robotic behaviors.

Future work aims to address the "curse of dimensionality" as the number of contact modes increases and to bridge the gap between discrete-time guarantees and continuous-time execution. Additionally, incorporating biased sampling techniques could further improve the efficiency of tree growth for high-dimensional systems like humanoids.

Summary updated

Abstract

Piecewise affine (PWA) systems are widely used to model highly nonlinear behaviors such as contact dynamics in robot locomotion and manipulation. Existing control techniques for PWA systems have computational drawbacks, both in offline design and online implementation. In this paper, we introduce a method to obtain feedback control policies and a corresponding set of admissible initial conditions for discrete-time PWA systems such that all the closed-loop trajectories reach a goal polytope, while a cost function is optimized. The idea is conceptually similar to LQR-trees [1], which consists of 3 steps: (1) open-loop trajectory optimization, (2) feedback control for computation of “funnels” of states around trajectories, and (3) repeating (1) and (2) in a way that the funnels are grown backward from the goal in a tree fashion and fill the state-space as much as possible. We show PWA dynamics can be exploited to combine step (1) and (2) into a single step that is tackled using mixed-integer convex programming, which makes the method suitable for dealing with hard constraints. Illustrative examples on contact-based dynamics are presented.
BibTeX
@inproceedings{sadraddini2018sampling,
  author = {Sadra Sadraddini and Russ Tedrake},
  title = {{Sampling-Based Polytopic Trees for Approximate Optimal Control of Piecewise Affine Systems}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2018},
  url = {https://openreview.net/forum?id=LKWpRLcOo6},
}
Figure