An Anytime, Scalable and Complete Algorithm for Embedding a Manufacturing Procedure in a Smart Factory

Christopher Leet, Aidan Sciortino, Sven Koenig

Introduction

In the rapidly evolving landscape of Industry 4.0, "smart factories" leverage a grid of heterogeneous manufacturing units—such as 3D printers, CNC machines, and assembly stations—interconnected by a fleet of mobile robots. To maximize the potential of such flexible systems, one must solve the Smart Factory Embedding (SFE) problem. This complex task requires the simultaneous optimization of process assignment (mapping manufacturing tasks to specific machines) and transport planning (routing robots to move parts between stations without collisions or bottlenecks).

Historically, solving these two components jointly has been a significant computational challenge. Previous state-of-the-art solvers, such as ACES, relied on Mixed Integer Linear Programming (MILP) modeled at the level of individual grid cells and discrete timesteps. While effective for small-scale operations, this approach creates a massive number of binary variables, rendering it intractable for factories with more than a few dozen machines.

Problem Formulation and Abstraction

The SFE problem is defined by a manufacturing procedure (a set of tasks and part dependencies) and a factory layout. To overcome the limitations of cell-based modeling, the authors introduce a hierarchical abstraction that simplifies the search space.

The SFE problem components: (a) manufacturing tokens and processes, (b) the physical grid layout with machines, and (c) the abstracted traffic system of roads and junctions.

As illustrated above, the factory environment is abstracted into a Traffic System. Instead of considering every grid cell, the algorithm groups cells into "roads" and "junctions." This spatial reduction is complemented by a temporal abstraction into "epochs," where one epoch is the time required for a robot to traverse a single road. This two-layer abstraction drastically reduces the number of variables in the underlying optimization problem, enabling the solver to handle much larger environments.

The TS-ACES Algorithm

The proposed solution, TS-ACES (Traffic System based Anytime Cyclic Embedding Solver), utilizes this abstraction to provide a scalable and complete algorithm.

The TS-ACES algorithmic pipeline, from the initial embedding problem to the final cell-based robot instructions.

The algorithm operates through a multi-stage pipeline:

  1. TS-MILP: A novel MILP formulation that operates on the abstracted traffic system. It ensures "buffer conservation" (parts are correctly handled) and "traffic conservation" (robot flow is consistent).
  2. Anytime Hyperparameter Search: TS-ACES is an "anytime" algorithm; it quickly finds a valid initial solution and then continuously searches for higher-throughput configurations by adjusting the number and length of temporal epochs.
  3. Cell-Based Generator ($G_{TS}$): A low-level controller translates the high-level cyclic plan back into specific, collision-free cell-by-cell instructions for the robots in real-time.

A key theoretical contribution is the proof of completeness: if a valid embedding exists for a given traffic system layout, TS-ACES is guaranteed to find it.

Evaluation and Results

TS-ACES was evaluated on six scenarios derived from real-world industrial cases in the pharmaceutical and food sectors, ranging from 8 to 108 machines.

  • Massive Scalability: TS-ACES demonstrated a significant leap in performance, successfully solving instances with 108 machines. Previous state-of-the-art methods failed to find any solution for these large-scale scenarios within standard time limits.
  • Throughput Gains: In the "Contact Lens Large" scenario, TS-ACES achieved a throughput of 4.71 units/time, more than double the 2.14 achieved by the previous cell-based method.
  • Efficiency: The low-level transport generator ($G_{TS}$) proved to be extremely fast, taking only 0.01 to 0.02 seconds to run, confirming its suitability for real-time robot coordination.

Conclusion

By abstracting factory layouts into traffic systems and utilizing a cyclic MILP formulation, TS-ACES provides a scalable solution to the Smart Factory Embedding problem. While current implementations rely on manual layout design for the traffic system, the algorithm's ability to handle over 100 machines marks a major milestone in automated factory management. Future work will explore the automatic generation of optimal road networks and the inclusion of more dynamic traffic rules.

Summary updated

BibTeX
@inproceedings{leet2025anytime,
  author = {Christopher Leet and Aidan Sciortino and Sven Koenig},
  title = {{An Anytime, Scalable and Complete Algorithm for Embedding a Manufacturing Procedure in a Smart Factory}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2025},
  doi = {10.1109/iros60139.2025.11247734},
}

Loading related content...

Figure