Synthesizing communication plans for reachability and safety specifications

Kazumune Hashimoto, Dimos V. Dimarogonas

Abstract

We propose control and communication strategies for nonlinear networked control systems subject to state and input constraints. The objective is to steer the state of the system towards a prescribed target set in finite time (reachability), while at the same time remaining inside a safety set for all time (safety). By leveraging the notion of $\delta$-ISS control Lyapunov function, we derive a sufficient condition to generate a communication scheduling, such that the resulting state trajectory guarantees reachability and safety. Moreover, in order to alleviate computational burden we present a way to find a suitable communication scheduling by implementing abstraction schemes and standard graph search methodologies. Simulation examples validate the effectiveness of the proposed approach.

Introduction

In modern Networked Control Systems (NCS), the exchange of data between sensors, actuators, and controllers occurs over shared communication networks. While these systems offer flexibility and scalability, they are often constrained by limited bandwidth and battery life. Traditional control strategies often assume continuous or periodic communication, which can lead to unnecessary network congestion and energy depletion. To address this, researchers have developed event-triggered and self-triggered control methods. However, most existing work focuses on simple stabilization tasks. This paper introduces a novel framework for managing communication in nonlinear NCS to ensure a system reaches a target destination while remaining within a safe operating region (reach-avoid specifications).

The Challenge: Reach-Avoid Specifications in NCS

The core difficulty in reach-avoid problems lies in managing the trade-off between communication frequency and system safety. In a nonlinear system, the state trajectory can deviate significantly from a desired path due to disturbances or lack of updates. Ensuring that the system remains within a non-convex safe space while navigating toward a target requires precise timing of communication events.

Finding the optimal communication schedule—the exact moments when the controller should receive state updates—is a computationally daunting task. For a mission spanning $L$ time steps, a naive approach that considers whether to communicate at each step results in a search space that grows exponentially.

Addressing the Complexity Bottleneck

A brute-force search for the optimal communication plan involves exploring a binary tree where each node represents a state update decision (0 for no communication, 1 for communication). As the number of time steps increases, the number of possible schedules becomes $2^L$. For a typical mission of 169 steps, this results in approximately $1.7 \times 10^{50}$ nodes, making the problem mathematically intractable for standard computing hardware.

Figure 2: Naive binary search tree for communication scheduling, illustrating exponential growth ($2^L$ nodes).

To overcome this "exponential explosion," the authors propose a framework that decouples path planning from communication scheduling. The process begins with offline path planning to generate a nominal reference trajectory using tools like Rapidly-exploring Random Trees (RRT). The key innovation lies in how the error—the deviation from this trajectory—is managed:

  1. Error Modeling: By utilizing a $\delta$-ISS (incremental Input-to-State Stability) control Lyapunov function, the authors quantify how the error grows during periods of silence and shrinks upon receiving a state update.
  2. Symbolic Abstraction: The continuous error space is partitioned into a finite set of discrete symbols. This transforms the complex nonlinear dynamics into a Symbolic Error System, effectively a finite state machine.
  3. Optimal Scheduling: With the system represented as a finite graph, standard graph search methodologies like Dijkstra’s algorithm can be employed to find the plan requiring the minimum number of transmissions. This reduces the scheduling complexity from exponential to linear relative to the number of time steps.
Figure 3: Symbolic Error System modeled as a finite state machine to reduce scheduling complexity.

Experimental Validation

The proposed approach was evaluated using two primary benchmarks. In a linear vehicle motion planning scenario, the framework successfully navigated a 4D model through a 2D workspace with obstacles. The symbolic abstraction allowed the optimal schedule to be found in less than 2 seconds. Notably, while a fixed offline plan required 36 transmissions, an online self-triggered refinement—which re-calculates the next communication time based on real-time state data—reduced the transmissions to just 21.

In a nonlinear inverted pendulum simulation, the system demonstrated robustness by successfully traversing between target regions under disturbance. The communication frequency naturally adapted to the environment, increasing when the system entered "narrow" safe passages where the margin for error was minimal.

Conclusion and Future Work

This research provides a scalable solution for synthesizing communication plans in nonlinear NCS with complex safety requirements. By combining Lyapunov-based error modeling with symbolic abstractions, the authors achieve significant reductions in network traffic without compromising performance. Future work aims to extend this framework to mobile networks with stochastic connectivity and to incorporate more complex mission logic, such as Linear Temporal Logic (LTL) specifications.

Summary updated

Abstract

We propose control and communication strategies for nonlinear networked control systems subject to state and input constraints. The objective is to steer the state of the system towards a prescribed target set in finite time (\textit{reachability}), while at the same time remaining inside a safety set for all time (\textit{safety}). By leveraging the notion of $δ$-ISS control Lyapunov function, we derive a sufficient condition to generate a communication scheduling, such that the resulting state trajectory guarantees reachability and safety. Moreover, in order to alleviate computational burden we present a way to find a suitable communication scheduling by implementing abstraction schemes and standard graph search methodologies. Simulation examples validate the effectiveness of the proposed approach.
BibTeX
@article{hashimoto2020synthesizing,
  author = {Kazumune Hashimoto and Dimos V. Dimarogonas},
  title = {{Synthesizing communication plans for reachability and safety specifications}},
  journal = {IEEE Trans. Automatic Control},
  year = {2020},
  url = {https://openreview.net/forum?id=KWIsnSfxkz},
}
Figure