STyLuS*: A Temporal Logic Optimal Control Synthesis Algorithm for Large-Scale Multi-Robot Systems

Yiannis Kantaros, Michael M. Zavlanos

Abstract

This paper proposes a new highly scalable and asymptotically optimal control synthesis algorithm from linear temporal logic specifications, called $\text{STyLuS}^{*}$ for large-Scale optimal Temporal Logic Synthesis, that is designed to solve complex temporal planning problems in large-scale multi-robot systems. Existing planning approaches with temporal logic specifications rely on graph search techniques applied to a product automaton constructed among the robots. In our previous work, we have proposed a more tractable sampling-based algorithm that builds incrementally trees that approximate the state-space and transitions of the synchronous product automaton and does not require sophisticated graph search techniques. Here, we extend our previous work by introducing bias in the sampling process which is guided by transitions in the B$\ddot{\text{u}}$chi automaton that belong to the shortest path to the accepting states. This allows us to synthesize optimal motion plans from product automata with hundreds of orders of magnitude more states than those that existing optimal control synthesis methods or off-the-shelf model checkers can manipulate. We show that $\text{STyLuS}^{*}$ is probabilistically complete and asymptotically optimal and has exponential convergence rate. This is the first time that convergence rate results are provided for sampling-based optimal control synthesis methods. We provide simulation results that show that $\text{STyLuS}^{*}$ can synthesize optimal motion plans for very large multi-robot systems which is impossible using state-of-the-art methods.

Introduction

Multi-robot path planning often requires satisfying complex logical constraints beyond simple point-to-point navigation. For instance, in a warehouse setting, a fleet of robots might need to follow rules such as "Robot 1 must visit Room A and B infinitely often, but only if Robot 2 has already dropped off a package at Room C." Such tasks are formally described using Linear Temporal Logic (LTL).

The traditional approach involves constructing a Product Buchi Automaton (PBA), which combines the physical state space of all robots with the logical states of the task. However, this leads to a "state-space explosion." As the number of robots or the complexity of rules increases, the PBA size grows exponentially, often exceeding the memory capacity of modern supercomputers.

Methodology

STyLuS* (large-Scale optimal Temporal Logic Synthesis) addresses this challenge by moving from exhaustive graph search to incremental sampling. The algorithm relies on a discrete abstraction of the environment, typically represented as a Weighted Transition System (WTS).

Mapping an indoor environment to a weighted transition system.

The core innovations of STyLuS* include:

  1. Tree-Based Exploration: Instead of building the full PBA, STyLuS* constructs a directed tree, storing only explored paths to save memory.
  2. NBA Pruning: The algorithm prunes transitions in the Nondeterministic Buchi Automaton (NBA) that are physically impossible, such as a single robot occupying two disjoint locations simultaneously.
  3. Biased Sampling: Unlike standard sampling-based planners that explore uniformly, STyLuS* uses a bias guided by the task's structure. It calculates a metric based on the shortest path to "accepting" (goal) states in the logic automaton, sampling new states that are more likely to progress the mission.
  4. Asymptotic Optimality: By incorporating "rewiring" techniques similar to RRT*, the algorithm ensures that the synthesized plan converges to the mathematical optimum over time.
Illustration of the biased sampling process in the product state space.

Results and Discussion

The algorithm was evaluated in simulated indoor environments with up to 200 robots. Key findings include:

  • Unprecedented Scalability: STyLuS* successfully synthesized plans for systems with state spaces as large as $10^{800}$. In comparison, standard model checkers like NuSMV typically fail beyond $10^{40}$ states.
  • Efficiency: For a 10-robot system ($10^{21}$ states), STyLuS* found feasible plans in under a second, outperforming traditional model checkers.
  • Convergence: The paper provides the first proof of an exponential convergence rate for sampling-based optimal LTL synthesis, demonstrating that the algorithm finds high-quality solutions rapidly.

Conclusion

STyLuS* represents a significant leap in multi-robot planning, enabling the synthesis of optimal controls for massive systems that were previously computationally intractable. Future work includes extending the framework to dynamic environments with moving obstacles and developing distributed implementations to further enhance performance.

Summary updated

Abstract

This paper proposes a new highly scalable and asymptotically optimal control synthesis algorithm from linear temporal logic specifications, called $\text{STyLuS}^{*}$ for large-Scale optimal Temporal Logic Synthesis, that is designed to solve complex temporal planning problems in large-scale multi-robot systems. Existing planning approaches with temporal logic specifications rely on graph search techniques applied to a product automaton constructed among the robots. In our previous work, we have proposed a more tractable sampling-based algorithm that builds incrementally trees that approximate the state-space and transitions of the synchronous product automaton and does not require sophisticated graph search techniques. Here, we extend our previous work by introducing bias in the sampling process which is guided by transitions in the B$\ddot{\text{u}}$chi automaton that belong to the shortest path to the accepting states. This allows us to synthesize optimal motion plans from product automata with hundreds of orders of magnitude more states than those that existing optimal control synthesis methods or off-the-shelf model checkers can manipulate. We show that $\text{STyLuS}^{*}$ is probabilistically complete and asymptotically optimal and has exponential convergence rate. This is the first time that convergence rate results are provided for sampling-based optimal control synthesis methods. We provide simulation results that show that $\text{STyLuS}^{*}$ can synthesize optimal motion plans for very large multi-robot systems which is impossible using state-of-the-art methods.
BibTeX
@article{kantaros2020stylus,
  author = {Yiannis Kantaros and Michael M. Zavlanos},
  title = {{STyLuS*: A Temporal Logic Optimal Control Synthesis Algorithm for Large-Scale Multi-Robot Systems}},
  journal = {Int. J. Robotics Res.},
  year = {2020},
  doi = {10.1177/0278364920913922},
}
Figure