Control of Timed Discrete Event Systems with Ticked Linear Temporal Logic Constraints

Takuma Kinugawa, Kazumune Hashimoto, Toshimitsu Ushio

TL;DR

This paper introduces ticked $LTL_f$, a novel temporal logic that incorporates discrete timing constraints by counting "tick" events within finite system executions. By encoding these logical and timing requirements into an Integer Linear Programming (ILP) framework, the authors provide an automated method for synthesizing valid control paths for complex, time-sensitive robotic tasks.

What Problem Does This Paper Address?

In the design of high-level controllers for robotics and manufacturing, we often need to satisfy two types of requirements: logical sequencing (e.g., "visit the warehouse, then the loading dock") and timing constraints (e.g., "complete the delivery within 10 minutes").

Standard Linear Temporal Logic (LTL) is excellent at describing sequences but lacks a native way to handle clock time. While Metric Temporal Logic (MTL) exists to handle time, it is often mathematically dense and designed for infinite trajectories. However, many real-world engineering problems—like path planning—have a clear beginning and end (a finite horizon).

The authors identify a gap: there is a need for a formal, computationally efficient way to specify and solve control problems that involve both logical order and discrete time steps over finite execution fragments.

Methods

The researchers propose a two-step solution:

  1. Ticked $LTL_f$ Logic: They extend $LTL_f$ (LTL for finite traces) by introducing a "tick" event. In their model, time doesn't just flow; it is represented by a specific event called tick that occurs in the system's transition graph. They define new temporal operators, such as $U_{[m,n]}$ (Until), where the bounds $[m,n]$ refer specifically to the number of tick events that must occur.
  2. ILP Encoding: To solve the control problem, they translate the system's dynamics and the ticked $LTL_f$ specifications into a set of linear constraints.
  3. Trajectory Encoding: They use adjacency matrices and binary vectors to represent state transitions.
  4. Logic Encoding: They recursively transform logical operators (AND, OR, NOT, Until) into linear inequalities using binary variables. For example, the "Until" operator is satisfied if there exists a future time step $j$ where the goal is met and the timing count (number of ticks) falls within the specified range $[m, n]$.

This transformation allows the use of powerful, off-the-shelf ILP solvers (like Gurobi or Z3) to find a valid sequence of states and events that satisfies the entire specification.

Datasets

The paper does not use a standard external dataset. Instead, it evaluates the method using a synthesized Timed Discrete Event System (TDES) representing a mobile agent (robot) moving between four locations ($p_1$ to $p_4$). The transitions between these locations are assigned specific time intervals (minimum and maximum ticks required to travel), creating a benchmark for testing the solver's ability to handle conflicting timing and logical constraints.

Key Insights and Ideas

  • Time as an Event: By treating time as a discrete tick event rather than a continuous variable, the authors simplify the state space while still capturing essential real-time behavior.
  • Finite Horizon Focus: Shifting from infinite-time logic to $LTL_f$ makes the problem much more applicable to "task-oriented" robotics, where a robot has a specific mission to complete and then stop.
  • ILP as a Bridge: The "aha moment" is the realization that the recursive satisfaction rules of temporal logic can be mapped directly to the constraints of an Integer Linear Programmer. This bypasses the need for complex automata-theoretic constructions often used in model checking.

Key Results

The effectiveness of the approach was demonstrated through a path-planning simulation:

  • Complex Specification Handling: The solver successfully found a path for a robot required to reach two different locations ($p_2$ and $p_4$) within a specific window of 1 to 5 total ticks.
  • Constraint Awareness: When the robot was tasked to reach $p_3$ while avoiding $p_2$ within a 3-to-5 tick window, the ILP solver correctly identified a trajectory that satisfied both the avoidance logic and the timing window.
  • Feasibility: The method proved capable of determining if a specification was impossible. For instance, if a certain sequence of moves required 6 ticks but the logic demanded completion in 5, the solver would correctly seek an alternative route or report no solution.

Limitations and Future Work

  • Feasibility vs. Optimality: The current framework finds a valid path (feasibility) but does not necessarily find the best path (e.g., the one with the fewest ticks or lowest energy consumption). The authors suggest that future work will involve incorporating cost functions to turn this into an optimization problem.
  • Scalability: As the time horizon ($H$) or the number of system states increases, the number of variables in the ILP grows. The authors mention that moving toward MAX-SAT solvers might be a more efficient way to handle larger, more complex environments.
  • Discrete vs. Continuous: Because the model relies on discrete tick events, it may not be suitable for systems requiring extremely high-precision, continuous-time synchronization.

Summary updated

Abstract

This paper presents a novel method of synthesizing a controller of a timed discrete event system(TDES), introducing a novel linear temporal logic(LTL), called ticked LTLf. The ticked LTLf is given as an extension to LTLf, where the semantics is defined over a finite execution sequence. Differently from the standard LTLf, the formula is defined as a variant of metric temporal logic formula, where the temporal properties are described by counting the number of tick in the execution sequence of the TDES. Moreover, we provide a scheme that encodes the problem into a suitable one that can be solved by an integer linear programming (ILP). The effectiveness of the proposed approach is illustrated through a numerical example of a path planning.
BibTeX
@inproceedings{kinugawa2020control,
  author = {Takuma Kinugawa and Kazumune Hashimoto and Toshimitsu Ushio},
  title = {{Control of Timed Discrete Event Systems with Ticked Linear Temporal Logic Constraints}},
  booktitle = {IFAC-PapersOnLine},
  year = {2020},
  doi = {10.1016/j.ifacol.2020.12.2539},
}
Figure