Unbounded Orchestrations of Transducers for Manufacturing

Natasha Alechina, Tomás Brázdil, Giuseppe De Giacomo, Paolo Felli, Brian Logan, Moshe Y. VardiAAAI 2019 · DOI

Abstract

This paper investigates the "unbounded orchestration problem" in automated manufacturing, which asks whether a product recipe can be realized given an unlimited supply of specific machine types. By modeling machines and recipes as transducers, the authors establish a sharp complexity boundary. For uni-transducers (single input/output), the problem is decidable in 2EXPTIME via reduction to multi-dimensional energy games, allowing for the computation of Pareto optimal resource sets. Conversely, for multi-transducers with multiple ports, the problem is shown to be undecidable, as such systems can simulate universal computation.

Introduction

In the era of "cloud manufacturing" and highly customized small-batch production, factories must transition from rigid setups to flexible, on-demand configurations. Traditional automated process planning typically addresses the bounded orchestration problem: determining if a specific product can be manufactured using a fixed, pre-existing inventory of machines.

However, as manufacturing moves toward service-oriented models, a more pertinent question arises: resource provisioning. Instead of asking if a fixed set of robots is sufficient, manufacturers need to know: "Given the types of robots available on the market, how many of each must be acquired to fulfill a specific product recipe?" This is the unbounded orchestration problem. It shifts the focus from managing constraints to determining the minimum necessary infrastructure to realize a goal.

Modeling with Transducers

The researchers employ formal methods to model the manufacturing environment. Both manufacturing resources (the machines) and process recipes (the product blueprints) are represented as transducers—finite-state automata that produce output in response to input.

Transducer models representing a recipe (T) and available machine types (T1, T2).

In this framework, a recipe $T$ defines a sequence of required operations, while machine types $T_1, T_2, \dots$ define the capabilities of available hardware. The orchestration task is to find a combination of machine instances that can collectively simulate the behavior required by the recipe.

The Uni-Transducer Setting and Energy Games

For "uni-transducers"—machines that process a single input to produce a single output—the authors reduce the orchestration problem to multi-dimensional energy games. In these games, the "energy" levels correspond to the number of available machine instances of each type.

A recipe is considered realizable if a controller can navigate the state space such that the "energy" (machine count) never drops below zero. This abstraction allows the application of established game-theoretic algorithms to find the Pareto frontier: the set of minimal machine combinations required to complete the recipe.

Example of mapping an input sequence to resource requirements, illustrating the tracking of machine counts.

Results and Complexity

The study reveals a significant "complexity cliff" based on the architecture of the transducers:

  1. Uni-Transducers: The unbounded orchestration problem is decidable with a complexity of 2EXPTIME. While computationally intensive, it is solvable, and the authors provide an algorithm to compute the entire frontier of optimal resource combinations.
  2. Multi-Transducers: For machines with multiple input/output ports (e.g., a robot joining two parts), the problem becomes undecidable. By reducing the problem from the Turing Machine Halting Problem, the authors prove that no general-purpose algorithm can determine realizability for multi-port machines in the unbounded case. The ability to "wire" multiple ports allows these systems to simulate universal computation, leading to inherent unpredictability.

Conclusion

The distinction between bounded and unbounded orchestration is critical for modern manufacturing logistics. While bounded orchestration is always decidable, the unbounded version is only solvable for simpler machine models. Future research must focus on identifying "decidable fragments"—specific constraints or configurations of multi-port machines that remain computationally tractable—to bridge the gap between theoretical undecidability and practical industrial needs. Additionally, incorporating factors such as time-to-completion and energy consumption into the optimality models remains an open challenge.

Summary updated

BibTeX
@inproceedings{alechina2019unbounded,
  author = {Natasha Alechina and Tomás Brázdil and Giuseppe De Giacomo and Paolo Felli and Brian Logan and Moshe Y. Vardi},
  title = {{Unbounded Orchestrations of Transducers for Manufacturing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012646},
}
Figure