View
1.194
Download
2
Category
Preview:
DESCRIPTION
Vortrag von Tilo Dietrich, Institut für Wirtschaftsinformatik an der Universität Leiptig auf dem 14. Interuniversitären Doktorandenseminar Wirtschaftsinformatik am 14.07.2011 auf der Augustusburg bei Chemnitz.
Citation preview
Wirtschaftswisschenschaftliche Fakultät
Institut für Wirtschaftsinformatik
Optimale Anordnung beliebig geformter Objekte im Raum
14. Interuniversitäres Doktorandenseminar
Dipl.-Inf. Tilo Dietrich
14.07.2011
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
Einordnung: Packungsproblem
Quelle
: fla
sh-scr
een.c
om
14. Interuniversitäres Doktorandenseminar am 14.07.2011 2
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
Szenario: Rapid Prototyping
• Herstellung dreidimensionaler Objekte durch „drucken“
• betrachtete Verfahren: 3D-Druck und selektives Lasersintern
14. Interuniversitäres Doktorandenseminar am 14.07.2011 3
Quelle
: Realit
yserv
ice G
mbH
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
Definition des Problems
• Eingabedaten
• Ausgabedaten
• Randbedingungen
• Zielstellung und Optimalitätskriterium
14. Interuniversitäres Doktorandenseminar am 14.07.2011 4
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
Eingabedaten
3D-Modelle der Körper CAD
begrenzt durch Polygonflächen
verschiedene Datenformate
Form und Größe des Bauraums bei heutigen kommerziellen
Druckmaschinen quaderförmig
14. Interuniversitäres Doktorandenseminar am 14.07.2011 5
Quelle
: Realit
yserv
ice G
mbH
Quelle
: pre
ssebox.
de
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
Ausgabedaten
• Auswahl, welche Körper gedruckt werden und welche nicht
• Positionen und Orientierungen der Körper in Bauraum
14. Interuniversitäres Doktorandenseminar am 14.07.2011 6
Quelle
: M
ate
rialis
e N
V
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
Randbedingungen
• keine Einschränkung der Geometrie der Körper insbesondere auch konkave Körper zugelassen
keine Einschränkung der Form relativ zueinander (können alle verschieden sein)
keine Einschränkung der absoluten Größe (solange das Teil überhaupt in den Bauraum passt…) und relativer Größe zueinander
• Bauraum ist ein Quader
• keine Einschränkung der Verschiebungsdistanzen und -achsen, keine Einschränkung der Rotationswinkel und -achsen
14. Interuniversitäres Doktorandenseminar am 14.07.2011 7
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
Randbedingungen (2)
• nach Anordnungsvorgang alle Körper vollständig innerhalb der räumlichen Grenzen des Bauraums
• nach Anordnungsvorgang keine Überschneidungen der Körper
• Vermeidung von Interlocks Interlock = zwei Körper können nicht
zerstörungsfrei voneinander getrennt werden
14. Interuniversitäres Doktorandenseminar am 14.07.2011 8
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
Zielstellung und Optimalitätskriterium
• Maximierung der Ausnutzung des Bauraums möglichst dichte Packung
Auswahlproblem: Welche Körper werden gedruckt?
zur Lösung des Auswahlproblems muss Anordnungsproblem gelöst werden
• möglichst flache Anordnung flache Anordnung weniger Schichten zu drucken Druckvorgang
früher beendet
falls alle Körper in den Bauraum passen
14. Interuniversitäres Doktorandenseminar am 14.07.2011 9
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
Lösung durch Heuristik
• keine optimale Lösung, aber möglichst „nah dran“
• Problem: Wie „nah“ ist „nah“?
• Augenmaß: die optimale Lösung ist nicht bekannt, damit die Güte der gefunden Lösung nicht absolut bewertbar
• bewertbar relativ zu anderen Lösungen
14. Interuniversitäres Doktorandenseminar am 14.07.2011 10
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
Stand der Wissenschaft
• Anordnung von beliebig geformten Körpern in 3D ist stark unterrepräsentiert
• insbesondere Vermeidung von Interlocks wird praktisch nicht thematisiert in 2D sind Interlocks erstrebenswert Erhöhen die Raumausnutzung
in 3D zwar auch, aber dann kann man mit dem Erzeugnis nichts mehr anfangen…
14. Interuniversitäres Doktorandenseminar am 14.07.2011 11
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
1. Methode: mit Überschneidungen
• Körper zufällig anordnen und dann auseinandertreiben
• Überschneidungen werden im Verlauf „wegoptimiert“
• häufigstes Verfahren: Simulated Annealing
sehr anfällig für Interlocks
14. Interuniversitäres Doktorandenseminar am 14.07.2011 12
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
2. Methode: ohne Überschneidungen
• Hybride Algorithmen: Layout-Algorithmus zur Anordnung der Körper (Anordnung erfolgt iterativ)
kombiniert mit Metaheuristik zur Optimierung der Reihenfolge
• häufigste Metaheuristik: Genetischer Algorithmus
• einfacher Layout- Algorithmus: Bottom-Left
14. Interuniversitäres Doktorandenseminar am 14.07.2011 13
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
2. Methode: ohne Überschneidungen (2)
• Anordnung abhängig von Reihenfolge des Hinzufügens
• keine Interlocks
14. Interuniversitäres Doktorandenseminar am 14.07.2011 14
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
Aktueller Stand und nächste Schritt
1. Vereinfachung der Eingabedaten Approximation der Körper durch eine Kugelmenge
bereits gut erforscht wird als gegeben angesehen
2. Entwicklung eines Layout-Algorithmus
3. Suchen nach einer geeigneten Metaheuristik vermutlich genetischer Algorithmus
14. Interuniversitäres Doktorandenseminar am 14.07.2011 15
Wirtschaftswissenschaftliche Fakultät
Institut für Wirtschaftsinformatik
Danke für die
Aufmerksamkeit
Fragen?
14. Interuniversitäres Doktorandenseminar am 14.07.2011 16
Quelle
: A
ndy
Klu
the (dejita
rudavi
s.dev
ianta
rt.c
om
)
Recommended