docEnglish - Universität Koblenz · Landau
download 
Denúncia Transcrição
English - Universität Koblenz · Landau
Seminar Sommersemester 2015: Automobile Systeme in der Automatisierung Prof. Dr. Dieter Zöbel, Universität Koblenz-Landau, FB Informatik Deadlocks bei fahrerlosen Transportsystemen Arne Reepen Eingereicht: 31.08.2015 / Fertiggestellt: 04.10.2015 Zusammenfassung Die vorliegende Arbeit vermittelt einen Einblick in den Bereich der Deadlocks bei fahrerlosen Transportsystemen. Dabei wird ein Überblick über die drei Herangehensweisen für die Behandlung von Deadlocks gegeben. Außerdem wird der modifizierte Bankier Algorithmus nach Kalinovcic im Detail vorgestellt. Abschließend werden Vor- und Nachteile der verschiedenen Herangehensweisen gegenübergestellt. Schlüsselwörter Deadlock, AGV, Banker Algorithmus 1 Einleitung Fahrerlose Transportsysteme (AGV-Systeme) werden in vielen Bereichen bereits eingesetzt, um effektiv und automatisiert Güter zu transportieren. Einige dieser Anwendungsgebiete sind zum Beispiel automatisierte Lagerhaltung, Anlieferung von Material in Produktions- oder Verpackungsanlagen oder der Transport von Containern in Güterhäfen. Neben den zahlreichen Vorteilen, die ein solches System mit sich bringt, werden auch viele neue Herausforderungen geschaffen. Ein fahrerloses Transportsystem kann nur dann effektiv arbeiten, wenn Routenplanung und Wegführung das Potenzial an Fahrzeugen und vorhandenem Platz ausschöpfen. Vor allem Deadlocks, die Verklemmung mehrerer Fahrzeuge beispielsweise an einer Kreuzung, kann die Auslastung eines Systems massiv einschränken oder gar vollständig zum Erliegen bringen. Daher ist es von großer Bedeutung, Deadlocks innerhalb des Systems entweder zu vermeiden oder frühzeitig zu erkennen und zu beheben. Dabei ist zu beachten, dass es im Vergleich zu Deadlocks im Bereich der Betriebssysteme einige Unterschiede gibt. Beispielsweise ist es einem AGV technisch möglich Rückwärts zu fahren um eine Deadlock Situation auf zu lösen. Dies führt, neben vielen Gemeinsamkeiten, zu einigen wichtigen Unterschieden im Vergleich zu der Behandlung von Deadlocks im Rahmen von Softwareprozessen. Diese Arbeit gliedert sich dabei wie folgt. Zunächst werden in Kapitel 2 die drei Herangehensweisen vorgestellt, in die man die Behandlung von Deadlocks grundlegend unterteilen kann. Anschließend wird in Kapitel 3 der modifizierte Bankier Algorithmus Universität Koblenz-Landau, Institut für Informatik [email protected] http://www.uni-koblenz-landau.de/koblenz/fb4/institute/IST/AGZoebel 2 A. Reepen nach Kalinovcic et al. [4] im Detail vorgestellt. Abschließend werden in Kapitel 4 die Vor- und Nachteile der unterschiedlichen Herangehensweisen gegenübergestellt. 2 Herangehensweisen Das Problem der Behandlung von Deadlocks stammt ursprünglich aus dem Bereich der Betriebssysteme und beschäftigt sich mit der Vergabe von exklusiven Ressourcen zwischen mehreren Prozessen. Um dies auf AGV-Systeme zu übertragen, betrachten wir Prozesse als Missionen, die von einem Fahrzeug ausgeführt werden. Eine Mission ist dabei eine Abfolge von Stationen, die für die Bearbeitung einer Transportmission angefahren werden müssen. Ressourcen entsprechen Wegabschnitten, die von den Fahrzeugen belegt werden, während sie eine Mission bearbeiten. Da sich nie zwei Fahrzeuge gleichzeitig an derselben Position aufhalten können, müssen Verfahren gefunden werden, um diese Ressourcen zu verwalten. Wollen zwei Fahrzeuge zur gleichen Zeit auf eine Kreuzung fahren, kann es ohne entsprechende Mechanismen zur Auflösung der Situation zu einer Verklemmung (Deadlock) des gesamten Systemablaufes kommen. Für den Umgang mit Deadlocks in gibt es drei unterschiedliche Herangehensweisen. 1. Verhinderung von Deadlocks 2. Vermeidung von Deadlocks 3. Erkennung und Behebung von Deadlocks Die grundlegenden Ideen dieser Herangehensweisen und ihre Eignung für den Einsatz in fahrerlosen Transportsystemen werden in den folgenden Kapiteln erläutert. Eine Gegenüberstellung der Vor- und Nachteile findet sich in Kapitel 4. 2.1 Verhinderung von Deadlocks Bei der ersten Herangehensweise, der Verhinderung von Deadlocks, wird das System nach ganz bestimmten Kriterien entworfen. Durch die Einhaltung dieser Kriterien wird effektiv verhindert, dass es zu einem Deadlock kommen kann. Nach [1] müssen für das Auftreten eines Deadlocks folgende vier Bedingungen gleichzeitig erfüllt sein: 1. Wechselseitiger Ausschluss (Mutual Exclusion): Aufgaben verlangen exklusiven Zugriff auf Ressourcen. 2. Besitzen und Warten (Hold and Wait): Aufgaben halten Ressourcen besetzt, während sie auf weitere Ressourcen warten. 3. Kein Ressourcenentzug (No Preemption): Ressourcen können nicht gewaltsam von einer Aufgabe entzogen werde. 4. Zyklisches Warten (Circular Wait): Eine Reihe von Aufgaben wartet auf Ressourcen, die der jeweils nächste belegt. Ein Transportsystem, das nach dem Verfahren der Verhinderung von Deadlocks entworfen ist, versucht das Eintreten mindestens einer dieser Bedingungen zu verhindern. Gelingt dies, so ist garantiert, dass in diesem System keine Deadlocks auftreten können. Bedingung 1 kann in den meisten Fällen nicht vermieden werden, da sich nur ein Fahrzeug zur gleichen Zeit an einem Ort aufhalten kann. Bedingung 2 kann vermieden werden, indem jede Aufgabe direkt zu Beginn alle Ressourcen anfragen muss, die sie jemals benötigen wird. Bedingung 3 kann in AGV-Systemen nicht im Deadlocks bei fahrerlosen Transportsystemen 3 Allgemeinen vermieden werden, da ein belegter Wegabschnitt nicht in jedem Fall freigegeben werden kann. Das Rückwärts fahren eines AGVs beispielsweise, bringt weitere Schwierigkeiten mit sich. Das Eintreten von Bedingung 4 kann durch eine lineare Ordnung der Missionen und dementsprechender Vergabe von Ressourcen verhindert werden. Dies führt allerdings zu starken Einschränkungen für das gesamte System. Um von einer tatsächlichen Verhinderung von Deadlocks sprechen zu können, muss außerdem das gesamte System inklusive aller zukünftigen Ereignisse bekannt sein. In einer realen Umgebung können äußere Einflüsse, die zu einem Deadlock führen können nie vollständig ausgeschlossen werden. 2.2 Vermeidung von Deadlocks Die zweite Herangehensweise zielt auf die Vermeidung von Deadlocks ab. Dabei wird nicht durch das Systemdesign garantiert, dass keine Deadlocks auftreten können, sondern das Auftreten wird zum Beispiel durch die geschickte Vergabe von Ressourcen vermieden. Anders als die Verhinderung von Deadlocks, die bereits mit dem Entwurf des Systems Deadlocks verhindert, ist die Deadlock-Vermeidung ein online Verfahren. Für jede neue Mission muss eine Route bestimmt werden, welche die Abarbeitung von Teilzielen ermöglicht, ohne dass es zu Verklemmungen mit anderen Fahrzeugen kommt. Hier gibt es unterschiedliche Strategien, wie etwa das Vorausplanen der vollständigen Route oder die schrittweise Überprüfung des nächsten Systemzustandes. Dies ermöglicht zwar eine flexiblere Auslastung ist jedoch auch mit mehr Verwaltungsaufwand verbunden. Die Aufteilung der Systemzustände in sichere und unsichere Zustände kommt dabei häufig zum Einsatz. Beispielsweise im Bankier Algorithmus nach Coffman[2], der sich in angepasster Form auch auf den Bereich der AGV Systeme anwenden lässt. Um einen sicheren Zustand handelt es sich hier, wenn es aus diesem Zustand eine Abfolge von Fahrzeugbewegungen gibt, die in einem erfolgreichen Endzustand enden. Ein unsicherer Zustand ist entsprechend dann gegeben, wenn die Gefahr eines Deadlocks besteht, da keine Bewegungsabfolge gefunden werden konnte, die in einem erfolgreichen Endzustand endet. Eine detaillierte Vorstellung einer Modifikation des Bankier Algorithmus findet sich in Kapitel 3. 2.3 Erkennen und Beheben von Deadlocks Die dritte Herangehensweise betrachtet den Aspekt der Erkennung und Behebung von Deadlocks. Anders als die bisherigen Verfahren, die versuchen, das Auftreten von Deadlocks zu verhindern, wird bei diesem Ansatz versucht Deadlocks, möglichst frühzeitig zu erkennen und den Zustand möglichst effizient aufzulösen. Im Idealfall tritt so der tatsächliche Deadlock nicht ein. Diese Herangehensweise ist die flexibelste, da sie mit wenigen Informationen über das System funktioniert. Im einfachsten Fall müssen nur die aktuellen Positionen und Fahrrichtungen der AGVs bekannt sein. Ohne Wissen über die zukünftigen Bewegungen der Fahrzeuge können Deadlocks jedoch nicht vorhergesagt und frühzeitig behoben werden. Auch können in einigen Situationen hohe Kosten, in Form von Wartezeit oder zusätzlich zurückgelegtem Weg, für das Auflösen eines Deadlocks entstehen. Daher bietet es sich an, das auftreten von Deadlocks möglichst gering zu halten, in dem beispielsweise die Strecken Auslastung nicht zu hoch wird. 4 A. Reepen Eine Umsetzung dieser Herangehensweise wird in [3] vorgestellt und kann in automatisierten Containerterminals eingesetzt werden. 3 Modifizierte Bankier Algorithmus Der hier vorgestellte modifizierte Bankier Algorithmus wurde 2011 von Kalinovcic et al. vorgestellt [4]. Ziel der Modifikationen ist es, die Auslastung der AGVs innerhalb eines Systems zu erhöhen. Dazu werden einige Zustände zugelassen, die im klassischen Bankier Algorithmus [2] als unsicher ausgeschlossen werden. Dabei sollen die Berechnung von geringer Komplexität sein und einfach in reelle Anlagen integriert werden können. 3.1 Systembeschreibung Die Struktur eines AGV-Systems lässt sich mithilfe eines ungerichteten Graphen H = (N, A) darstellen. Er besteht aus einer Menge von Knoten N = {n1 , n2 , ..., np } und einer Menge von Kanten A = {a1 , a2 , ..., aq }. Die Knotenpunkte können dabei in drei Typen unterschieden werden. Die Ladestationen Ii , Arbeitsstationen Wi sowie Kreuzungen Ci . Die Menge aller AGVs wird mit R bezeichnet. Es werden die folgenden Annahmen gemacht: 1. AGVs können sich nur auf Kanten aufhalten 2. auf jeder Kante kann sich maximal ein AGV zur gleichen Zeit aufhalten, breite Wege müssen durch mehrere Kanten modelliert werden 3. jedes AGV besitzt eine eigene Ladestation 4. AGVs dürfen weder Rückwärts fahren noch eine 180◦ Wendung machen, außer sie verlassen eine Arbeitsstation Der Ablauf einer Mission folgt immer dem Muster Ii → Wk → Wl → ... → Ii . Sie startet und endet in der Ladestation des jeweiligen AGVs und es können ein oder mehrere Arbeitsstationen angefahren werden. Eine Mission wird als mi = (σr , r) modelliert. Sie besteht aus dem Missionspfad σr und dem Fahrzeug r ∈ R, das die Mission bearbeitet. Ein Missionspfad σr = ap → aq → as → ... → ap hat die Länge |σr | und ist eine Sequenz von Kanten, welche die besuchten Knoten verbinden. σr (j) liefert die j-te Stelle in σr . Außerdem wird für jedes Fahrzeug ein Kantenindex k definiert, bei dem kr = i bedeutet, dass r die i-te Kante in σr belegt. Alle aktiven Pfade eines System, die gerade einer Mission zugewiesen sind, bilden Σ = {σ1 , σ2 , ..., σl }. Die Menge aller Kantenindizes bildet K = {k1 , k2 , ..., kl }. Daher wird der Zustand S = (Σ, K) des Systems vollständig beschrieben durch die aktiven Pfade sowie die belegten Kanten. Im initialen Zustand S0 = (Σ, K) gilt ∀kr ∈ K : kr = 1, das heißt alle Fahrzeuge befinden sich in ihrer Ladestation. Im finalen Zustand SF gilt ∀kr ∈ K : kr = |σr |, es haben alle Fahrzeuge das Ende ihres Pfades erreicht und befinden sich in ihrer Ladestation. Die folgenden Definitionen beschreiben die Zustände und Zustandsübergabe innerhalb des Systems. Deadlocks bei fahrerlosen Transportsystemen 5 Definition 1: zulässiger Zustand [4] Zustand S = (Σ, K) ist zulässig wenn: ∀p, q ∈ R, p 6= q : σp (kp ) 6= σq (kq ) Zustand S ist zulässig, wenn sich alle Fahrzeuge auf unterschiedlichen Kanten befinden. Start- und Endzustand sind nach Definition immer zulässig. Definition 2: Zustandsübergang durch Fahrzeugbewegung [4] Seien S = (Σ, K) und S 0 = (Σ, K 0 ) Zustände, dann gibt es ein r, sodass: ( 1≤r≤ |R|, ki0 ki , i 6= r = ki + 1, i = r Zustand S ändert sich zu Zustand S’ durch die Bewegung von Fahrzeug r. r Dies wird geschrieben als: S − → S0. Definition 3: Zustandsübergang durch Missionszuweisung [4] Seien S = (Σ, K) und S 0 = (Σ 0 , K 0 ) Zustände, dann gibt es ein r, sodass: ( 1 ≤ r ≤ |R|, kr = |σr |, ki0 = ki , i 6= r 1, i = r ∀i 6= r : σi0 = σi Ein Zustand S ändert sich zu Zustand S’ durch eine neue Missionszuweisung an Fahrzeug r. Dies wird geschrieben als: S − → S0. r Definition 4: Deadlock-Zustand [4] S = (Σ, K) ist ein Deadlock-Zustand, wenn es kein Fahrzeug r gibt, sodass r S− → S 0 und S 0 = (Σ, K 0 ) zulässig sind. Tritt ein Deadlock-Zustand ein, können keine erlaubten Fahrzeugbewegungen mehr durchgeführt werden, die das System zurück in einen sicheren Zustand bringen. Somit kann keine der Missionen abgeschlossen werden und der Endzustand kann nicht erreicht werden. Das System ist blockiert. Definition 5: Sicherer Zustand [4] Zustand S = (Σ, K) ist sicher, wenn es eine Sequenz von Fahrzeugbewegungen rM r1 r2 → SF gilt. r1 → r2 → ... → rM gibt, sodass S −→ S 0 −→ S 00 ... −− Ein Zustand ist sicher, wenn es mindestens eine Sequenz von Fahrzeugbewegungen gibt, sodass alle Missionen erfolgreich beendet werden können. Betrachten wir nun den Ablauf des Verfahrens. Zunächst muss einer Mission ein Pfad zugewiesen werden, über den das Fahrzeug die entsprechenden Arbeitsstationen erreichen kann. Dabei wird als Pfad einer Mission immer der kürzeste Pfad gewählt. Einflüsse, welche beispielsweise die mögliche Maximalgeschwindigkeit auf einem Wegabschnitt beeinflussen, werden ignoriert. Um in einen Deadlock-Zustand zu gelangen, muss der Zustand des Systems verändert werden. Dies ist nach den Definition 2 und 3 nur auf zwei Arten möglich. Wie von Kalinovcic et al. [4] bewiesen, kann die Vergabe einer Mission nie zu einem Deadlock führen. Damit bleibt nach Definition 2 nur noch die Bewegung eines Fahrzeuges, um den Zustand des System zu einem unsicheren Zustand zu verändern. Daher wird für die jeweils nächste Fahrzeugbewegung überprüft, ob sie in einem sicheren oder unsicheren Zustand endet. Dazu kann beispielsweise der klassische Bankier Algorithmus nach Dijkstra [2] angewendet werden, nach dem er auf fahrerlose Transportsysteme angepasst wurde. 6 A. Reepen Abb. 1 Graphdarstellung eines AGV Systems [4] Abb. 2 Wartegraph für Abbildung 1 [4] 3.2 Bankier Algorithmus für fahrerlose Transportsysteme Um den Bankier Algorithmus auf ein AGV-System anwenden zu können, müssen zunächst Ressourcen und Prozesse definiert werden. Wegabschnitte, beziehungsweise die Kanten des Graphen, sind die Ressourcen. Prozesse entsprechen den Missionen, die ein Fahrzeug abarbeiten soll. Für die jeweils nächste Bewegung, die ein Fahrzeug ausführen möchte wird getestet, ob diese Bewegung in einem sicheren Zustand endet. Verdeutlichung anhand eines Beispiels nach [4]. In Abbildung 1 sehen wir vier Fahrzeuge in einem AGV System. Fahrzeug V1 ,V3 und V4 kehren auf kürzestem Weg zu ihren Ladestationen zurück, während sich Fahrzeug V2 zu Arbeitsstelle W1 begibt. Es soll nun getestet werden, ob Fahrzeug V1 auf Kante 13 fahren darf. Dazu werden zunächst die bereits belegten Ressourcen benötigt. V1 belegt Kante 13, V2 belegt Kante 15, V3 belegt Kante 8 und V4 belegt Kante 17. Außerdem werden die Ressourcen benötigt, die eine Mission für ihre Vollendung benötigt. Für V1 sind das 1, 5, 15, V2 2, 5, 7, 15, V3 3, 6, 8, 14, 17 und V4 4, 6. Nach Ausführung des Bankier Algorithmus erhalten wir eine Sequenz, in der wir die Missionen ausführen müssen, um in einen Endzustand zu gelangen. Dabei wird jede Mission eines Fahrzeugs vollständig ausgeführt, bevor das nächste Fahrzeug fährt. Eine solche Sequenz wäre: m2 → m1 → m4 → m3 , es kann jedoch mehrere gültige Sequenzen geben. Für den Beweis, dass dieser Zustand nicht zu einem Deadlock führt, ist nur die Existenz einer solchen Abfolge wichtig. In einer realen Implementation würde eine solche Ausführungsabfolge zu sehr geringen Auslastungen führen. Deadlocks bei fahrerlosen Transportsystemen 7 Abb. 3 Grundlegender Algorithmus für den Test auf BA-Sicherheit[4] Die Bestimmung, ob ein Zustand im Bankier Algorithmus sicher(im folgenden BAsicher) ist, wird mit Hilfe von Wartegraphen nach [6] getestet. Ein solcher Wartegraph für das AGV System in Abbildung 1 is in Abbildung 2 zu sehen. Eine aus einem Knoten ausgehende Kante beschreibt darin eine Wartebeziehung gegenüber dem Zielknoten der Kante. Ist die Anzahl der ausgehenden Kanten eines Knoten outdegree = 0, so wird sein Missionspfad von keinem anderen Fahrzeug belegt. Theorem 1: Zustand S = (Σ, K) ist BA-sicher, genau dann wenn der Wartegraph G = (Ng , Ag ) azyklisch ist. [4] In Abbildung 3 ist der grundlegende Algorithmus für die Bestimmung von BASicherheit gezeigt. Dieser nimmt als Eingabe den Wartegraph für den aktuellen Systemzustand G = (Ng , Ag ). Es werden nach und nach Knoten mit einem outdegree = 0 entfernt. Wenn alle Knoten entfernt werden konnten ist der Zustand BA-sicher. Können nicht alle Knoten entfernt werden besteht eine zyklische Wartebeziehung zwischen zwei Knoten. Damit ist der Zustand nicht BA-sicher. Dies bedeutet jedoch nicht, dass es er in einem Deadlock-Zustand enden muss. Die Ausführung dieses Algorithmus hat für einen Graphen G mit n Knoten die Komplexität O(n2 ). 3.3 Modifikation zur Steigerung der Auslastung Die Annahmen des klassischen Bankier Algorithmus sind sehr streng, dadurch gibt es Zustände, die ebenfalls erfolgreich zu einem Endzustand führen, jedoch als nicht sicher erkannt werden. Das führt zu einer nicht optimalen Auslastung des Systems. Dies geschieht dadurch, dass der Fortschritt der Bewegungen anderer Fahrzeuge nicht berücksichtigt wird. Ein Fahrzeug, das den Pfad eines anderen kreuzt, belegt zwar kurzzeitig einen benötigten Wegabschnitt, hat diesen jedoch möglicherweise bereits freigegeben, wenn der Wegabschnitt tatsächlich benötigt wird. Diese Zustände werden modifiziert BA-sicher(im folgenden MBA-sicher) genannt und wie folgt formalisiert: Definition 6: MBA-sichere Sequenz [4] Sequenz r1 → r2 → ... → rM ist eine MBA Sequenz, wenn k, 1 ≤ k ≤ M existiert sodass: i)∀(i, j), 1 ≤ i ≤ j ≤ k : ri = rj und ii)∀(i, j), 1 ≤ i ≤ j ≤ M : ri = rj ⇒ ri = rj+1 = ... = rj 8 A. Reepen Abb. 4 Erweiterter Algorithmus für den Test auf MBA-Sicherheit[4] Definition 7: [4] Zustand S = (Σ, K) ist MBA-sicher, wenn es eine MBA-Sequenz r1 → r2 → ... → rM r1 r2 rM gibt, sodass: S −→ S 0 −→ S 00 ... −−→ SF Theorem 2: Zustand S = (Σ, K) und Fahrzeug r fragt an Kante a zu befahren. Das System ist nicht deadlockgefährdet, wenn die Belegung von a durch r zu einem Zustand S = (Σ, K 0 ) führt, welcher MBA-sicher ist. Dies bedeutet, dass Zustand S MBA-sicher ist, solange durch das Bewegen eines Fahrzeuges ein BA-sicherer Zustand erreicht werden kann, da man aus diesem immer einen Endzustand erreichen kann. Für die Bestimmung, ob ein Zustand MBA-sicher ist, werden ebenfalls Wartegraphen verwendet. Dabei wird für jedes Fahrzeug der Wert emax bestimmt. Dieser gibt an, wie viele Schritte das Fahrzeug auf seinem Pfad ausführen kann bevor es den Pfad eines anderen Fahrzeuges kreuzt. In Abbildung 4 ist der erweiterte Algorithmus zu sehen, der auf MBA-Sicherheit testet. Für alle Teilschritte 1 ≤ j ≤ emax wird mit Hilfe von Algorithmus 1 getestet, ob der Zustand BA-sicher ist. Kann ein solcher Zustand gefunden werden, ist der Weg bis zu diesem Punkt MBA-sicher und kann befahren werden. 3.4 Simulationsergebnisse Der vorgestellte modifizierte Bankier Algorithmus wurde in einer Simulationsumgebung getestet und mit dem klassischen Bankier Algorithmus sowie dem Ansatz von Revelio- Deadlocks bei fahrerlosen Transportsystemen 9 Abb. 5 Simulationsergebnisse für BA, MBA und RBA[4] tis [7](im folgenden RBA) verglichen. Reveliotis wählt eine andere Herangehensweise, in der Fahrzeugpfade dynamisch bestimmt werden, statt bei der Missionsvergabe festgelegt zu werden. Für die Simulation wurde ein reale Lager und Verpackungsanlage gewählt, die mit vier Fahrzeugen, acht Arbeitsstationen und 34 Pfaden arbeitet. In Abbildung 5 sind die Ergebnisse dieser Simulation zu sehen. Aus den Ergebnissen wird deutlich, dass BA und MBA immer die gleiche Strecke zurücklegen, da sie beide den kürzesten Pfad für eine Mission wählen. RBA legt längere Strecken zurück, da dieses Verfahren die Route anpasst, wenn die kürzeste Route blockiert ist. MBA erzielt im Durchschnitt kürzere Laufzeiten pro Mission als BA und RBA. Auch die Wartezeiten können mit MBA gegenüber BA reduziert werden, jedoch ist die dynamische Routenplanung von RBA hier deutlich überlegen. Wie in den Simulationsergebnissen zu sehen ist, erreicht der modifizierte Bankier Algorithmus die angestrebten Ziele. Er erzielt eine höhere Auslastung der Fahrzeuge durch kürzere Ausführungszeiten pro Mission und verkürzte Wartezeiten. Dennoch gibt es einige Aspekte, die bei der Umsetzung zu beachten sind. Vor allem sind die Simulationen mit nur vier Fahrzeugen durchgeführt worden. Diese sehr kleine Anzahl lässt wenig Rückschlüsse auf die Performanz in großen Systemen zu. Auch die Anzahl der betrachteten Wegstrecken ist, verglichen mit beispielsweise einem Containerterminal, sehr gering. Diese zwei Aspekte lassen die verwendeten Graphen sehr groß werden, was möglicherweise zu Problemen führen könnte. Vor allem in großem Systemen können auch die vollständig vorberechneten Missionspfade zu Problemen führen, da durch mehr Fahrzeuge sehr viele Kreuzungen von Missionspfaden auftreten können. Im klassischen Bankier Algorithmus würden diese bereits zu unsicheren Zuständen führen. Dies wird durch die schrittweise Überprüfung der MBA-Sicherheit bis emax zwar teilweise abgefangen, jedoch leider nicht für eine größere Anzahl von Fahrzeugen simuliert. 4 Zusammenfassung In dieser Arbeit wurden die drei grundlegenden Herangehensweisen für die Behandlung von Deadlocks in fahrerlosen Transportsystemen prinzipiell betrachtet. Im Detail wurde der modifizierte Bankier Algorithmus nach Kalinovcic[4] betrachtet. Der Ansatz der Deadlock-Verhinderung bringt durch strikte Vorgaben für das Systemdesign deutliche Einschränkungen mit sich und ist damit am wenigsten flexibel. Mit Verfahren, wie dem vorgestellten modifizierten Bankier Algorithmus, wird die 10 A. Reepen Herangehensweise der Deadlock Vermeidung verfolgt. Über die Bewertung von Systemzuständen als sicher bzw. unsicher, können die Ressourcen effizienter vergeben werden und es müssen weniger pessimistische Annahmen getroffen werden, als es bei Verhinderungsstrategien geschieht. Die Herangehensweise der Deadlock-Erkennung und -Behebung kann am flexibelsten auf neue Ereignisse reagieren, benötigt dafür allerdings den höchsten Verwaltungsaufwand [3]. Die in Kapitel 3.4 gezeigten Simulationsergebnisse zeigen, dass die von Kalinovcic et al. gemachten Modifikationen zu kürzeren Bearbeitungs- und Wartezeiten führen. Damit kann das angestrebte Ziel der Erhöhung der Auslastung, gegenüber dem klassischen Bankier Algorithmus, als erreicht angesehen werden. Das Verfahren macht allerdings einige Annahmen, welche die Fähigkeiten eines AGVs, zu Gunsten der einfacheren Planung, einschränken. Als Kritik ist außerdem die sehr geringe Anzahl der simulierten Fahrzeuge anzuführen. Insgesamt zeigt sich, dass die Wahl des richtigen Verfahrens stark vom Einsatzgebiet, Anzahl der Fahrzeuge und gegeben Vorgaben abhängt. Literatur 1. Coffman, E. G., Elphick, M., & Shoshani, A. (1971): System deadlocks. ACM Computing Surveys (CSUR), 3(2), 67-78. 2. Dijkstra, E. W. (1982): The mathematics behind the Banker?s algorithm. In Selected Writings on Computing: A Personal Perspective (pp. 308-312). Springer New York. 3. Lehmann, M., Grunow, M., & Günther, H. O. (2006): Deadlock handling for real-time control of AGVs at automated container terminals. OR Spectrum, 28(4), 631-657. 4. Kalinovcic, L., Petrovic, T., Bogdan, S., & Bobanac, V. (2011, August): Modified Banker’s algorithm for scheduling in multi-AGV systems. In Automation Science and Engineering (CASE), 2011 IEEE Conference on (pp. 351-356). IEEE. 5. Fanti, M. P., & Turchiano, B. (2001): Deadlock avoidance in automated guided vehicle systems. In Advanced Intelligent Mechatronics, 2001. Proceedings. 2001 IEEE/ASME International Conference on (Vol. 2, pp. 1017-1022). IEEE. 6. Silberschatz, A., Galvin, P. B., Gagne, G., & Silberschatz, A. (1998): Operating system concepts (Vol. 4). Reading: Addison-Wesley. 7. Reveliotis, S. A. (2000): Conflict resolution in AGV systems. IIE Transactions, 32(7), 647659.
