Distributed Planning for Self-Organizing Production Systems

Für automatisierte Produktionsanlagen gibt es einen fundamentalen Tradeoff
zwischen Effizienz und Flexibilität. In den meisten Fällen sind die Abläufe
nicht nur durch den physischen Aufbau der Produktionsanlage, sondern auch durch
die spezielle zugeschnittene Programmierung der Anlagensteuerung fest
vorgegeben. Änderungen müssen aufwändig in einer Vielzahl von Systemen
nachgezogen werden. Das macht die Herstellung kleiner Stückzahlen unrentabel.

In dieser Dissertation wird ein Ansatz entwickelt, um eine automatische
Anpassung des Verhaltens von Produktionsanlagen an wechselnde Aufträge und
... mehr
Rahmenbedingungen zu erreichen. Dabei kommt das Prinzip der Selbstorganisation
durch verteilte Planung zum Einsatz. Die aufeinander aufbauenden Ergebnisse der
Dissertation sind wie folgt:

1. Es wird ein Modell von Produktionsanlagen entwickelt, dass nahtlos von der
detaillierten Betrachtung physikalischer Produktionsprozesse bis hin zu
Lieferbeziehungen zwischen Unternehmen skaliert. Im Vergleich zu
existierenden Modellen von Produktionsanlagen werden weniger limitierende
Annahmen gestellt. In diesem Sinne ist der Modellierungsansatz ein Kandidat
für eine häufig geforderte "Theorie der Produktion".

2. Für die so modellierten Szenarien wird ein Algorithmus zur Optimierung der
nebenläufigen Abläufe entwickelt. Der Algorithmus verbindet Techniken für die
kombinatorische und die kontinuierliche Optimierung: Je nach Detailgrad und
Ausgestaltung des modellierten Szenarios kann der identische Algorithmus
kombinatorische Fertigungsfeinplanung (Scheduling) vornehmen, weltweite
Lieferbeziehungen unter Einbezug von Unsicherheiten und Risiko optimieren und
physikalische Prozesse prädiktiv regeln. Dafür werden Techniken der
Monte-Carlo Baumsuche (die auch bei Deepminds Alpha Go zum Einsatz kommen)
weiterentwickelt. Durch Ausnutzung zusätzlicher Struktur in den Modellen
skaliert der Ansatz auch auf große Szenarien.

3. Der Planungsalgorithmus wird auf die verteilte Optimierung durch unabhängige
Agenten übertragen. Dafür wird die sogenannte "Nutzen-Propagation" als
Koordinations-Mechanismus entwickelt. Diese ist von der Belief-Propagation
zur Inferenz in Probabilistischen Graphischen Modellen inspiriert. Jeder
teilnehmende Agent hat einen lokalen Handlungsraum, in dem er den
Systemzustand beobachten und handelnd eingreifen kann. Die Agenten sind an
der Maximierung der Gesamtwohlfahrt über alle Agenten hinweg interessiert.
Die dafür notwendige Kooperation entsteht über den Austausch von Nachrichten
zwischen benachbarten Agenten. Die Nachrichten beschreiben den erwarteten
Nutzen für ein angenommenes Verhalten im Handlungsraum beider Agenten.

4. Es wird eine Beschreibung der wiederverwendbaren Fähigkeiten von Maschinen
und Anlagen auf Basis formaler Beschreibungslogiken entwickelt. Ausgehend von
den beschriebenen Fähigkeiten, sowie der vorliegenden Aufträge mit ihren
notwendigen Produktionsschritten, werden ausführbare Aktionen abgeleitet. Die
ausführbaren Aktionen, mit wohldefinierten Vorbedingungen und Effekten,
kapseln benötigte Parametrierungen, programmierte Abläufe und die
Synchronisation von Maschinen zur Laufzeit.

Die Ergebnisse zusammenfassend werden Grundlagen für flexible automatisierte
Produktionssysteme geschaffen -- in einer Werkshalle, aber auch über Standorte
und Organisationen verteilt -- welche die ihnen innewohnenden Freiheitsgrade
durch Planung zur Laufzeit und agentenbasierte Koordination gezielt einsetzen
können. Der Bezug zur Praxis wird durch Anwendungsbeispiele hergestellt. Die
Machbarkeit des Ansatzes wurde mit realen Maschinen im Rahmen des EU-Projekts
SkillPro und in einer Simulationsumgebung mit weiteren Szenarien demonstriert.

There is a fundamental tradeoff between automation and flexibility in production
systems. Large lot sizes can be produced efficiently with automated production
systems. Many machines and equipment, like a 5-axis CNC mill, are in principle
capable of producing many different kinds of parts. Similarly, (intra-)
logistics systems exist for the automated transport and warehousing. Integrating
these flexible components to an overall production system that is equally
flexible has been prevented by the limits of automation technology in dealing
with the ensuing complexity. ... mehrMost production processes are rigid not only by way
of the physical layout of machines and their integration, but also by the custom
programming of the control logic for the integration of components to a
production systems. Changes are time- and resource-expensive. This makes the
production of small lot sizes of customized products economically challenging.

This thesis develops solutions for the automated adaptation of production
systems based on self-organisation and distributed planning. The main
results are the following:

1. A model of production systems that scales seamlessly from detailed
physical process dynamics up to more abstract descriptions of entire supply
chains. Compared to existing models of production systems, the proposed
approach requires less limiting assumptions and also includes a treatment of
concurrency---many productions on many machines in parallel and their
interaction. In the sense, the proposed model is a candidate for a
"theory of production".

2. Based on the model, an algorithm for the optimization of concurrent
production scenarios is proposed. The algorithm combines techniques for
combinatorial and continuous optimization. Depending on the level fidelity of
of the model, the same algorithm can solve combinatorial scheduling problems,
minimize risk in global supply-chains and control physical production
processes. For this, the technique of Monte-Carlo Tree Search is extended. By
exploiting algebraic structure in the models, the approach can be scaled to
large scenarios.

3. The algorithm is further extended to decentralized optimization by
independent agents. For the coordination between agents, the technique of
"utility propagation" is developed. Utility propagation is inspired by
belief propagation, a well-known technique for inference in probabilistic
graphical models. Every agent has a local scope of visibility where can
further influence the actions taking place. For the coordination, it is
expected that the scope of the different agents is overlapping. The agents are
further expected to cooperate, i.e.\ they are interested to maximize the
overall welfare that is generated. The coordination between agents is based on
the exchange of messages between neighboring agents. The messages describe the
expected generated welfare conditional to the actions that are in the scope of
both the sending and the receiving agent.

4. A formal description of reusable skills of production resources (machines
and tools) in production systems is developed. By combining the modeled skills
with a description of the production steps, executable actions are generated
that are described by preconditions and effects. Internally, the actions
encapsulate all required program logic for the automation and the
runtime-synchronization between different machines and tools that participate
in the action.

In summary, the results of this work enable future production systems that are
both efficient and adaptive. For this the components of the production system
are enabled to use the degrees of freedom that are available to them. By the use
of self-organization for the coordination, components of the overall system can
react to changes in the system topology and external conditions. The approach
was tested in application scenarios---in simulation and in physical production
systems. For example as part of the EU-project SkillPro.