Synthesizing Switching Logic to Minimize Long-Run Cost

Susmit Jha, Sanjit A. Seshia, Ashish TiwariarXiv 2011 · arXiv

Abstract

This paper introduces an automated framework for synthesizing optimal "switching logic"—the rules governing mode transitions in multi-modal systems—to minimize long-term operational costs. By reducing infinite-horizon trajectories to finite repetitive behaviors and combining numerical optimization with inductive learning, the authors provide a method for designing controllers that are both efficient and provably near-optimal.

Introduction

Many physical systems, from thermostats to industrial oil pumps, are multi-modal: they operate in discrete modes, each with its own continuous dynamics. A central challenge in engineering these systems is designing the switching logic (or "guards")—the conditions under which the system transitions from one mode to another. Historically, these guards have been designed manually, often focusing on safety. However, designing for long-run optimality—minimizing fuel consumption, reducing wear-and-tear, or maximizing comfort—is significantly harder because the search space is effectively infinite. Existing tools often struggle with these long-run costs as they are typically optimized for finite time horizons.

Methodology

The authors propose a two-stage approach to automate the design of optimal switching logic:

  1. Numerical Optimization for Single States: The authors define the "long-run cost" as a ratio of accumulated penalties to accumulated rewards (e.g., total discomfort divided by total time). Observing that optimal long-term behavior eventually becomes repetitive (cyclic or asymptotic), they reduce the infinite-length optimization problem into a finite one: finding optimal switching times for a single "representative" cycle using derivative-free numerical engines like the Nelder-Mead simplex algorithm.
  2. Inductive Learning for Generalization: To create a general rule for any state, the authors treat synthesis as a machine learning problem. Assuming guards are linear inequalities (halfspaces), they use a Probably Approximately Correct (PAC) learning algorithm. By labeling optimal switching points as positive and sub-optimal states as negative, the algorithm learns a linear boundary that serves as the synthesized switching logic.

Evaluation and Results

The method was evaluated on three classic control benchmarks: a thermostat controller, an industrial oil pump, and a DC-DC buck-boost converter.

Thermostat Controller

In the thermostat benchmark, the goal was to balance temperature stability against fuel cost and heater wear. The system successfully synthesized guards that adapted to user priorities; for example, when the discomfort penalty was weighted higher, the logic kept the temperature closer to the target.

Table showing numerical switching times (t) and corresponding temperature values (temp) for the thermostat benchmark.

Industrial Oil Pump and Power Electronics

For the industrial oil pump, the tool discovered switching logic that satisfied safety constraints while minimizing average oil volume, matching or outperforming manual designs. In the DC-DC buck-boost converter case, the synthesized logic maintained stable output voltage despite varying electrical loads, demonstrating a robust control strategy.

Key Insights and Discussion

A powerful insight of this work is that the long-run cost of an infinite trajectory is dominated by its limit behavior. By optimizing a single cycle of steady-state behavior, the infinite horizon is effectively addressed. Furthermore, the framework naturally handles "Zeno behavior"—where a system tries to switch infinitely fast to cheat the cost function—by penalizing the number of switches per unit of time.

While the current approach relies on numerical optimization (which can hit local minima) and assumes linear guards, it provides a rigorous foundation for automated synthesis. Future work may involve more complex geometric shapes, such as kernels or neural networks, to represent optimal switching logic for highly non-linear systems.

Summary updated

Abstract

Given a multi-modal dynamical system, optimal switching logic synthesis involves generating the conditions for switching between the system modes such that the resulting hybrid system satisfies a quantitative specification. We formalize and solve the problem of optimal switching logic synthesis for quantitative specifications over long run behavior. Each trajectory of the system, and each state of the system, is associated with a cost. Our goal is to synthesize a system that minimizes this cost from each initial state. Our paper generalizes earlier work on synthesis for safety as safety specifications can be encoded as quantitative specifications. We present an approach for specifying quantitative measures using reward and penalty functions, and illustrate its effectiveness using several examples. We present an automated technique to synthesize switching logic for such quantitative measures. Our algorithm is based on reducing the synthesis problem to an unconstrained numerical optimization problem which can be solved by any off-the-shelf numerical optimization engines. We demonstrate the effectiveness of this approach with experimental results.
BibTeX
@misc{jha2011synthesizing,
  author = {Susmit Jha and Sanjit A. Seshia and Ashish Tiwari},
  title = {{Synthesizing Switching Logic to Minimize Long-Run Cost}},
  year = {2011},
  eprint = {1103.0800},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1103.0800},
}
Figure