Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
METHOD, MACHINE CONTROL AND COMPUTER-PROGRAM PRODUCT FOR DETERMINING A PATH FOR AUTONAVIGATION
Document Type and Number:
WIPO Patent Application WO/2023/031320
Kind Code:
A1
Abstract:
In a method for determining at least part of a path (12) for connecting at least one starting point (14) to at least one finishing point (16) in a space (R) for at least one autonavigation of at least one movable component through the space on a machine (100), at least one model of the movable component and the machine is provided, information on the geometry is gathered, current positions are determined and these are brought into relation with one another to create a graph (10). An algorithm is used to calculate the path (12), collision-free autonavigation along the path (12) being carried out after a collision check has been performed. This assists the operator in adapting the machine cycle, while likewise bringing about an improvement in terms of the travel path, cycle time, reliability of the process, energy and wear.

Inventors:
FAULHABER WERNER (DE)
PETERS JÜRGEN (DE)
Application Number:
PCT/EP2022/074294
Publication Date:
March 09, 2023
Filing Date:
September 01, 2022
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
ARBURG GMBH CO KG (DE)
International Classes:
B25J9/16; B29C45/80; B29C45/42; G05B19/4061; G05B19/4069
Domestic Patent References:
WO2020158320A12020-08-06
WO2009080296A12009-07-02
WO2009024783A12009-02-26
Foreign References:
US20110153080A12011-06-23
EP2853354A12015-04-01
US20040232866A12004-11-25
DE102021122606A2021-09-01
DE102012103830A12012-11-08
DE69027634T21996-11-21
EP1672449A12006-06-21
US20170090454A12017-03-30
DE102004027944A12005-12-29
Other References:
KUNZ T ET AL: "Real-time path planning for a robot arm in changing environments", INTELLIGENT ROBOTS AND SYSTEMS (IROS), 2010 IEEE/RSJ INTERNATIONAL CONFERENCE ON, IEEE, PISCATAWAY, NJ, USA, 18 October 2010 (2010-10-18), pages 5906 - 5911, XP031920895, ISBN: 978-1-4244-6674-0, DOI: 10.1109/IROS.2010.5653275
Attorney, Agent or Firm:
RPK PATENTANWÄLTE REINHARDT, POHLMANN UND KAUFMANN PARTNERSCHAFT MBB (DE)
Download PDF:
Claims:
- 26 -

Patentansprüche

1 . Verfahren zur Bestimmung wenigstens eines Teils eines Pfades (12) zur Verbindung wenigstens eines Startpunkts (14) mit wenigstens einem Zielpunkt (16) in einem Raum für wenigstens eine Autonavigation wenigstens einer bewegbaren Komponente durch den Raum (R) an einer Maschine (100), insbesondere einer Spritzgießmaschine zur Verarbeitung von Kunststoffen und anderer plastifizierbarer Massen oder einer 3D-Druckma- schine, umfassend die Schritte: a) Bereitstellen wenigstens eines Modells der wenigstens einen bewegbaren Komponente und der Maschine (100), b) Erfassen von Geometrieinformationen des Raums (R) und der wenigstens einen bewegbaren Komponente und der Maschine (100), c) Bestimmen einer aktuellen Lage der wenigstens einen bewegbaren Komponente und der Maschine (100) im Raum (R), d) in Beziehung setzen der Geometrieinformationen und der aktuellen Lage der wenigstens einen bewegbaren Komponente sowie der Maschine (100) im Raum (R) zueinander zur Erzeugung wenigstens eines Graphen (10) des Raums (R), e) Berechnen des Pfades (12) unter Anwendung wenigstens eines Algorithmus auf den Graphen (10), wobei für das Berechnen des Pfades (12) zusätzlich wenigstens eine Optimierung durchgeführt wird, f) Durchführen wenigstens einer Kollisionsprüfung entlang des Pfades (12) zwischen der wenigstens einen bewegbaren Komponente einerseits und der Maschine (100) andererseits, g) kollisionsfreies Autonavigieren der wenigstens einen bewegbaren Komponente entlang des Pfades (12), wobei sich die wenigstens eine bewegbare Komponente relativ zu der Maschine bewegt und der Algorithmus unter dynamischer Änderung des Graphen (10) infolge von Bewegungen der wenigstens einen bewegbaren Komponente und/oder der Maschine (100) angewandt wird und wobei das Verfahren bei einer Änderung im Produktionsablauf in Echtzeit simuliert wird und/oder der Algorithmus auf veränderte Positionen und/oder Geschwindigkeiten der wenigstens einen bewegbaren Komponente und/oder der Maschine (100) reagiert, indem wenigstens eine weitere Kollisionsprüfung durchgeführt und/oder wenigstens ein neuer Pfad (12) berechnet wird.

2. Verfahren nach Anspruch 1 , gekennzeichnet durch das Bereitstellen jeweils wenigstens eines Kontaktpunkts von der wenigstens einen bewegbaren Komponente und der Maschine (100) in Bezug auf eine Lage des wenigstens eines Kontaktpunkts im Raum (R), wobei die Kontaktpunkte miteinander für das Bereitstellen des Modells der wenigstens einen bewegbaren Komponente und der Maschine logisch gekoppelt werden. Verfahren nach Anspruch 2, dadurch gekennzeichnet, dass dem wenigstens einen Kontaktpunkt wenigstens eine Liste zugeordnet wird, anhand derer ankoppelbare Modelle beschrieben und/oder aufgelistet werden. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass der Raum (R) in ein Raster aus Würfeln (18) unterteilt wird, welches für die Erzeugung des wenigstens einen Graphen (10) verwendet wird. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass als Algorithmus wenigstens ein Greedy-Search-, ein Dijkstra- und/oder ein A*-Algorithmus mit wenigstens einer offenen Liste verwendet wird. Verfahren nach Anspruch 5, dadurch gekennzeichnet, dass als Optimierung wenigstens eine Sprungpunkt-Suche und/oder eine Verwaltung der offenen Liste verwendet wird. Verfahren nach Anspruch 6, dadurch gekennzeichnet, dass die Verwaltung der offenen Liste mit einem Binärheap (20) erfolgt. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass das Verfahren vorab simuliert wird und/oder dass wenigstens zwei verschiedene Varianten des Verfahrens simuliert werden und in Bezug auf unterschiedliche Kriterien miteinander verglichen werden. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass der Graph und/oder das Modell der wenigstens einen bewegbaren Komponente und/oder der Maschine (100) grafisch dargestellt wird. Maschinensteuerung für eine Maschine (100), insbesondere für eine Spritzgießmaschine zur Verarbeitung von Kunststoffen und anderer plastifizierbarer Massen, dadurch gekennzeichnet, dass die Maschinensteuerung eingerichtet, ausgeführt und/oder konstruiert ist, um das Verfahren nach einem der Ansprüche 1 bis 9 auszuführen. Computerprogrammprodukt mit einem Programmcode, der auf einem Computer lesbaren Medium gespeichert ist, zur Durchführung eines Verfahrens nach einem der Ansprüche 1 bis 9.

Description:
Verfahren, Maschinensteuerung und Computerprogrammprodukt zur Bestimmung eines Pfades für eine Autonavigation

Beschreibung

Bezug zu verwandten Anmeldungen

Die vorliegende Anmeldung bezieht sich auf und beansprucht die Priorität der deutschen Patentanmeldung 10 2021 122 606.6, hinterlegt am 01 . September 2021 , deren Offenbarungsgehalt hiermit ausdrücklich auch in seiner Gesamtheit zum Gegenstand der vorliegenden Anmeldung gemacht wird.

Gebiet der Erfindung

Die Erfindung betrifft ein Verfahren zur Bestimmung wenigstens eines Teils eines Pfads zur Verbindung wenigstens eines Startpunkts mit wenigstens einem Zielpunkt in einem Raum für wenigstens eine Autonavigation vom Start- zum Zielpunkt, beispielsweise zur Entnahme, Umsetzung und/oder Ablage eines Formteils, wenigstens einer bewegbaren Komponente durch den Raum an einer Maschine, insbesondere einer Spritzgießmaschine zur Verarbeitung von Kunststoffen und anderer plastifizierbarer Massen oder einer 3D-Druckmaschine nach dem Oberbegriff des Anspruchs 1 , eine Maschinensteuerung nach dem Oberbegriff des Anspruchs 10 sowie ein Computerprogrammprodukt nach dem Oberbegriff des Anspruchs 11.

Für die Erläuterung der Erfindung werden zunächst einige Begriffe wie folgt definiert.

Unter einer „Achse“ werden im Rahmen dieser Anmeldung bewegbare Teile z.B. von Maschinen, Anlagen, Anlagenteilen und/oder Peripheriegeräten verstanden, welche sich beispielsweise über einen Antrieb z.B. einen Motor ansteuern lassen. Für das Beispiel einer Spritzgießmaschine wäre eine Achse z.B. die Spindel eines Spindelsystems.

Unter einer „Maschine“ werden im Rahmen dieser Anmeldung zumindest all die Teile verstanden, die strukturell zum Betrieb einer Maschine erforderlich sind, wie z.B. an einer Spritzgießmaschine die Formschließeinheit mit darin aufgenommener Spritzgießform, die Spritzgießeinheit, der Maschinenfuß sowie die zugehörigen Antriebe. Relevant für die Autonavigation ist zumindest der Bereich des Raums, in dem die Maschine oder deren Teile mit einer bewegbaren Komponente z.B. eines Peripheriegeräts kollidieren können. Ein konkreter Fall ist dabei z.B. ein Roboterarm mit Greifer, der sich im Formspannraum zwischen den geöffneten Formträgern der Formschließeinheit bewegt. Der Roboterarm und/oder der Greifer können verschiedene Bewegungen ausführen, wie z.B. Kipp-, Schwenk-, Drehbewegungen. Durch diese Bewegungen kann der Vektor des Roboterarms und/oder des Greifers geändert werden. Die Maschine kann wenigstens ein Maschinenteil aufweisen, wie z.B. ein Werkzeug, ein Formnest, ein Formteil, einen Anguss, eine bewegliche Platte, eine stationäre Platte und/oder eine Einspritzeinheit. Weiter kann die Maschine noch weitere Maschinenteile und/oder Komponenten aufweisen. Auch diese Maschinenteile können sich bewegen und können bevorzugt ebenfalls mit dem vorgestellten Verfahren im Raum autonavigiert werden. Das Maschinenteil wird dann bevorzugt entlang eines Pfades autonavigiert, welcher mittels des Algorithmus berechnet wurde, sodass es zu keiner Kollision mit anderen Maschinenteilen, bewegbaren Komponenten und/oder der Maschine kommt.

Wenn im Folgenden von der Maschine gesprochen wird sind immer die Maschine sowie gegebenenfalls die Maschinenteile der Maschine gemeint.

Unter einer „bewegbaren Komponente“ wird im Rahmen dieser Anmeldung ein relativ zur Maschine bewegbares Element wie z.B. ein Peripheriegerät verstanden. Dabei kann es sich um einen Roboterarm, Greifer, Roboter, Auswerfer oder auch andere bewegbare Komponenten eines Peripheriegeräts als auch der Maschine handeln, die sich im Raum bewegen, so dass eine Kollision mit der Maschine zu vermeiden ist, insbesondere wenn sich auch die Maschine und/oder Maschinenteile bewegen.

Stand der Technik

In einem Spritzgießprozess laufen heutzutage viele bzw. alle Vorgänge automatisiert ab. Nicht nur erfolgt meist die komplette Steuerung einer Spritzgießmaschine vollständig automatisiert, wie beispielsweise das Schließen der Werkzeugplatten, die Beaufschlagung des Druckes und das Öffnen der Werkzeugplatten, sondern auch das Entnehmen, das Umsetzen und/oder das Ablegen eines Formteils beispielsweise mittels eines Roboters. Oft befinden sich im Maschinen- und/oder Werkzeugraum mehrere Achsen, z.B. Tauchachsen, beispielsweise von Peripheriegeräten, z.B. eines Roboters oder eines Robotergreifers, sodass eine Beeinträchtigung oder Kollision der Achsen während des Spritzgießprozesses, z.B. bei der Entnahme des Formteils untereinander stattfinden kann. Für eine vorteilhaft effiziente Produktivität ist eine möglichst kurze Zykluszeit wünschenswert, welche z.B. auch durch die Entnahmegeschwindigkeit des Formteils beispielsweise durch das Peripheriegerät bedingt ist. Bekannt sind Systeme in kunststoffverarbeitenden Maschinen und Anlagen, bei denen z.B. Roboterabläufe interaktiv erstellt werden können. Beispielsweise können durch sogenannte Teachfunktionen Ablaufpositionen, z.B. Punkte einer Bahn eingegeben bzw. „geteacht“ und somit automatisch beispielsweise einer Roboter-Ablaufsteuerung eingegeben werden (siehe z.B. WO 2009/080296 A1).

Ebenfalls bekannt sind Systeme, bei denen im Ablauf Hüllkörper-Geometrieinformationen von Roboter und Werkzeug dazu verwendet werden, quasi statische Kollisionsprüfungen (zum Beispiel des Roboterarms bzw. Robotergreifers) mit der Maschine an den End- und Teach- punkten durchzuführen.

Aus der DE 10 2012 103 830 A1 ist ein Verfahren zur Verhinderung von gegenseitiger Blockierung eines Paares von Robotern offenbart, welche einen gemeinsamen Arbeitsbereich besitzen. Jeder Roboter wird durch ein zugeordnetes Programm gesteuert. Die Roboter besetzen während gleichzeitiger Ausführung der Programme einen Abschnitt eines gemeinsamen Arbeitsplatzbereichs. Es wird ein Störbereich gekennzeichnet, in dem sich die Abschnitte des gemeinsamen Arbeitsbereichs überdecken. Der Störbereich wird analysiert und es wird gekennzeichnet, wo eine gegenseitige Blockierung der Roboter auftreten kann. Zur Vermeidung der Blockierung wird eine Anweisung ausgeführt, welche zumindest eine Bedingung der gegenseitigen Blockierung während einer Ausführung der Programme vermeidet.

In der DE 690 27 634 T2 ist ein Kollisionserkennungsverfahren für eine Mehrroboteranordnung mit mindestens zwei Elementen offenbart. Für die Kollisionserkennung wird das Antikollisionsproblem in eine Kollisionserkennungsphase und eine Behebungs-(Ausweichmanöver- )Phase aufgespalten. Durch weiteres Zerteilen des 3D-Kollisionserkennungsproblems in eine 2D-XY-Erkennung und einen 1 D-Höhenvergleich kann das Problem weiter vereinfacht werden.

Zur Bestimmung von zeitgünstigen kollisionsfreien Wegen wird in der EP 1 672 449 A1 einer Maschinensteuerung ein Datensatz zur Verfügung gestellt, der in jedem diskretisierten Koordinatenpunkt sowie für jede Kombination der diskretisierten Werkzeugmodelle und Werkstückmodelle einen Kollisionsparameter 0 oder 1 aufweist. Der Kollisionsparameter zeigt an, ob die dem entsprechenden Koordinatenpunkt zugeordnete Konstellation, das heißt Relativposition von Werkstück und Werkzeug, eine Kollision oder räumliche Überschneidung des Werkzeugs und des Werkstücks zur Folge hat oder nicht. Dabei bildet der Datensatz eine Look-Up-Ta- belle, die zur Überprüfung von gegebenen Pfaden oder zum Strecken oder schrittweisen Aufbau von Pfaden genutzt werden kann. In der WO 2009/024783 A1 ist ein computerimplementiertes Verfahren offenbart um eine Bewegung zwischen einem Bauteil und einem Gerät, welches mit dem Bauteil interagiert, zu bestimmen. Es werden geometrische Daten bezüglich des Bauteils und des Geräts empfangen und aus den geometrischen Daten wird bestimmt, wie das Gerät und das Bauteil relativ zueinander bewegt werden können, wobei Optimierungskriterien verwendet werden. In einem Ausführungsbeispiel wird ein Modell eines Gegenstands, eines Turbinenblatts geladen und es wird eine Oberfläche des Gegenstands ausgewählt, auf der mehrere Punkte generiert werden. Die Punkte werden dann vom Messgerät wegoptimiert angefahren.

In der US 2017/0090454 A1 ist ein Verfahren zur Generierung von Positionsfahrtdaten für eine CNC-Maschine offenbart. Optimierte Positionswege werden auf der Grundlage der Maschinenkinematik, der Verfahrensgrenzen der Maschinenachsen, der Geschwindigkeits- und Beschleunigungsgrenzen der Maschinenachsen und der Positionier-Methoden der Maschine erstellt, wobei eine Vielzahl möglicher Pfade zum Neupositionieren eines Werkzeugs von einer ersten zu einer zweiten Konfiguration bestimmt wird.

Die DE 10 2004 027 944 A1 offenbart ein Verfahren zum Schützen von mindestens zwei Robotern gegen Kollisionen, bei denen Bewegungen eines Roboters automatisch auf mögliche Kollisionen geprüft werden und automatisch Verriegelungen in den Bewegungsablauf eingefügt werden.

Die beschriebenen Funktionen erleichtern heute bereits das Programmieren von Roboterabläufen und helfen, Fehler zu vermeiden. Alle zuvor beschriebenen, einzelnen unterstützenden Systeme haben jedoch das Problem, dass diese unvollständig und in gewissen Grenzen ungenau sind. Daher ist beim Programmieren immer noch die Interaktion mit dem Bediener notwendig. Das bedeutet zudem, dass Schäden durch Kollisionen nicht vollständig verhindert werden können.

Es soll nun nicht einfach durch Kombination der verschiedenen beschriebenen Einzelfunktionen eine Verbesserung der Roboterabläufe erreicht werden, sondern durch eine völlig neue Betrachtung die Voraussetzung zu einer dynamischen, kollisionsfreien Autonavigation geschaffen werden.

Zusammenfassung der Erfindung Ausgehend von diesem Stand der Technik liegt der vorliegenden Erfindung die Aufgabe zugrunde, ein Verfahren zur Bestimmung wenigstens eines Teils eines Pfads für wenigstens eine Autonavigation bereitzustellen, welches den Bediener bei Anpassungen des Maschinenzyklus unterstützt und in Bezug auf Fahrweg, Zykluszeit, Prozesssicherheit, Energie sowie Verschleiß optimiert ist.

Diese Aufgabe wird durch ein Verfahren zur Bestimmung wenigstens eines Teils eines Pfades für wenigstens eine Autonavigation mit den Merkmalen des Anspruches 1 , eine Maschinensteuerung mit den Merkmalen des Anspruches 10 sowie durch ein Computerprogrammprodukt mit den Merkmalen des Anspruches 11 gelöst.

Vorteilhafte Weiterbildungen sind Gegenstand der abhängigen Patentansprüche. Die in den Patentansprüchen einzeln aufgeführten Merkmale sind in technologisch sinnvoller Weise miteinander kombinierbar und können durch erläuternde Sachverhalte aus der Beschreibung und durch Details aus den Figuren ergänzt werden, wobei weitere Ausführungsvarianten der Erfindung aufgezeigt werden.

Das Verfahren zur Bestimmung wenigstens eines Teils eines Pfades zur Verbindung wenigstens eines Startpunkts mit wenigstens einem Zielpunkt in einem Raum für wenigstens eine Autonavigation wenigstens einer bewegbaren Komponente z.B. eines Peripheriegeräts, beispielsweise eines Roboters oder eines Robotergreifers, durch den Raum an einer Maschine, insbesondere einer Spritzgießmaschine zur Verarbeitung von Kunststoffen und anderer plastifizierbarer Massen oder einer 3D-Druckmaschine umfasst die folgenden Schritte.

Die Maschine, wie eingangs definiert kann wenigstens ein Maschinenteil aufweisen, wie z.B. ein Werkzeug, ein Formnest, ein Formteil, einen Anguss, eine bewegliche Platte, eine stationäre Platte, und/oder eine Einspritzeinheit. Weiter kann die Maschine noch weitere Maschinenteile und/oder Komponenten beispielsweise von einer Spritzgießmaschine oder einer 3D- Druckmaschine aufweisen. Die Maschinenteile können sich bewegen und können bevorzugt ebenfalls mit dem vorgestellten Verfahren im Raum autonavigiert werden. Das Maschinenteil wird dann bevorzugt entlang des Pfades autonavigiert, welche mittels des Algorithmus berechnet wurde, sodass es zu keiner Kollision mit anderen Maschinenteilen, Peripheriegeräten und/oder der Maschine kommt.

Wenn im Folgenden von der Maschine gesprochen wird sind immer die Maschine sowie gegebenenfalls die Maschinenteile der Maschine gemeint. Bei einer „bewegbaren Komponente“ handelt es sich um ein relativ zur Maschine bewegbares Element wie z.B. ein Peripheriegerät. Dabei kann es sich z.B. um Greifer, Roboter, Auswerfer oder auch andere bewegbare Komponenten z.B. eines Peripheriegeräts als auch der Maschine handeln, die sich im Raum bewegen, so dass eine Kollision mit der Maschine zu vermeiden ist, insbesondere wenn sich auch die Maschine bewegt.

Zunächst wird wenigstens ein Modell, z.B. ein digitales Modell der wenigstens einen bewegbaren Komponente, z.B. eines Peripheriegeräts, und der Maschine bereitgestellt. Je nachdem, ob die Maschine Maschinenteile aufweist, können auch bevorzugt für die Maschinenteile entsprechende Modelle bereitgestellt werden. Beispielsweise kann das Modell als Datei einem Computer, einem Programm oder einer Steuerung bereitgestellt werden. Es ist auch möglich, dass das Modell über ein Netzwerk bereitgestellt wird oder bereits auf der Maschine vorhanden ist. Das Modell kann Informationen über die Geometrie der bewegbaren Komponente und/oder der Maschine aufweisen. Die Geometrie des Modells kann mittels Geometriemodellen, wie beispielsweise Collada beschrieben werden.

In einem weiteren Schritt werden Geometrieinformationen des Raums und der wenigstens einen bewegbaren Komponente und der Maschine erfasst. Je nachdem, ob die Maschine Maschinenteile aufweist, können bevorzugt auch für die Maschinenteile entsprechende Geometrieinformationen erfasst werden. Die Geometrieinformationen können z.B. aus dem Modell entnommen werden bzw. sind im Modell enthalten. Auch kann z.B. die Position der beweglichen Platte anhand eines der Maschinensteuerung bekannten Istwertes der Plattenlage zu jedem Zeitpunkt eindeutig bestimmt werden. So ergeben sich beispielsweise die geometrischen Abmessungen in Länge, Breite und Höhe der einzelnen bewegbaren Komponenten, der Maschine und gegebenenfalls der Maschinenteile. Ferner ist es bevorzugt denkbar, die Geometrieinformationen anhand von Sensoren zu erfassen.

In einem nächsten Schritt wird eine aktuelle Lage der wenigstens einen bewegbaren Komponente und der Maschine im Raum bestimmt. Je nachdem, ob die Maschine Maschinenteile aufweist, kann bevorzugt auch eine aktuelle Lage der Maschinenteile im Raum bestimmt werden. Mit der Lage sind beispielsweise die Position und/oder die Ausrichtung gemeint. Beispielsweise kann mit einem Winkel bezüglich der Nulllage die Lage einer Achse im Raum, z.B. in einem kartesischen Koordinatensystem eindeutig bestimmt werden. Es ist somit auch möglich, beispielsweise eine Orientierung einer Achse beispielsweise von einem Roboter im Raum zu erfassen. Auch hier kann die aktuelle Lage bevorzugt anhand von Sensoren erfasst werden. Die Geometrieinformationen und die aktuelle Lage der wenigstens einen bewegbaren Komponente und der Maschine im Raum werden beispielsweise mit einem Computer oder einer Maschinensteuerung zueinander in Beziehung gesetzt zur Erzeugung wenigstens eines Graphen des Raums. Je nachdem, ob die Maschine Maschinenteile aufweist, können bevorzugt auch die Geometrieinformationen und die aktuelle Lage der Maschinenteile mit den Geometrieinformationen und der aktuellen Lage der wenigstens einen bewegbaren Komponente und der Maschine zur Erzeugung eines Graphen im Raum in Beziehung gesetzt werden. Mit den Geometrieinformationen und der aktuellen Lage ist die Anordnung von bewegbaren Komponenten wie z.B. Peripheriegeräten und der Maschine sowie gegebenenfalls der Maschinenteile im Raum bestimmt, sodass eine „Karte des Raums“ als Graph erzeugt werden kann. Die bewegbaren Komponenten, die Maschine und gegebenenfalls die Maschinenteile können im Graph beispielsweise als ein Hindernis dargestellt werden.

In einem weiteren Schritt erfolgt das Berechnen des Pfades unter Anwendung wenigstens eines Algorithmus auf den Graphen, wobei für das Berechnen des Pfades zusätzlich wenigstens eine Optimierung durchgeführt wird.

In einem weiteren Schritt wird wenigstens eine Kollisionsprüfung entlang des Pfades durchgeführt zwischen der wenigstens einen bewegbaren Komponente einerseits und der Maschine andererseits. Je nachdem, ob die Maschine Maschinenteile aufweist, können bevorzugt auch die Maschinenteile bei der Kollisionsprüfung berücksichtigt werden. Beispielsweise kann während der Entnahme des Formteils eine Kollision zwischen einem Peripheriegerät und der Maschine bzw. Maschinenteilen auftreten. Die Kollisionsprüfung erfolgt z.B. entlang des Pfades, indem überprüft wird, ob entlang des Pfades ein Hindernis liegt.

Bevorzugt erfolgt die Kollisionsprüfung in Echtzeit. Ergibt die Kollisionsprüfung, dass sich ein Hindernis entlang des Pfades befindet, wird beispielsweise nach einer Bewegungsanweisung an die bewegbare Komponente, an die Maschine und/oder gegebenenfalls an das Maschinenteil eine neue Berechnung des Pfades durchgeführt. Ergibt die Kollisionsprüfung, dass entlang des Pfades kein Hindernis vorliegt, wird in einem weiteren Schritt entlang des Pfades die wenigstens eine bewegbare Komponente autonavigiert, wobei sich die wenigstens eine bewegbare Komponente relativ zu der Maschine bewegt.

Während eines Spritzgießprozesses bewegen sich in aller Regel die bewegbaren Komponenten wie Peripheriegeräte, die Maschine und/oder gegebenenfalls die Maschinenteile wie z.B. Teile einer Spritzgießform relativ zueinander, sodass der Pfad für die Autonavigation angepasst werden muss. Für eine vorteilhaft erhöhte Sicherheit und Bedienerfreundlichkeit wird der Algorithmus unter dynamischer Änderung des Graphen infolge von Bewegungen der wenigstens einen bewegbaren Komponente und/oder der Maschine angewandt. Je nachdem, ob die Maschine Maschinenteile aufweist, kann bevorzugt der Algorithmus unter dynamischer Änderung der Maschinenteile angewandt werden. Bewegen sich z.B. die bewegbare Komponente, die Maschine und/oder gegebenenfalls das Maschinenteil so, dass sich der Graph so verändert, dass entlang des aktuellen Pfads ein Hindernis liegt, wird die Bewegung der bewegbaren Komponente, der Maschine und/oder gegebenenfalls des Maschinenteils auf dem aktuellen Pfad mit Hindernis gestoppt und auf einem neuen berechneten Pfad fortgesetzt. Mit jeder Bewegung kann sich also der Pfad auf der „Karte“ ändern, die durch die anderen vorhandenen Elemente beschrieben wird und auf der die bewegbare Komponente bewegbar ist. Gleiches gilt auch für die bei einem 3D-Druckprozess verwendeten Elemente wie z.B. Materialzuführeinheit, Austragskopf, Faserzuführeinheit, Bauträger, herzustellendes Objekt.

Da während eines Produktionsprozesses unvorhergesehene Ereignisse eintreten können, wird das Verfahren bei einer Änderung im Produktionsablauf in Echtzeit simuliert und/oder der Algorithmus reagiert auf veränderte Positionen und/oder Geschwindigkeiten der wenigstens einen bewegbaren Komponente wie z.B. eines Peripheriegeräts und/oder der Maschine, indem wenigstens eine weitere Kollisionsprüfung durchgeführt und/oder wenigstens ein neuer Pfad berechnet wird. Je nachdem, ob die Maschine Maschinenteile aufweist, kann bevorzugt der Algorithmus auch auf veränderte Positionen und/oder Geschwindigkeiten der Maschinenteile reagieren, indem wenigstens eine weitere Kollisionsprüfung durchgeführt und/oder wenigstens ein neuer Pfad berechnet wird.

Vorteilhaft wird so der Bediener bei Anpassung des Maschinenzyklus unterstützt, wobei sich ebenfalls eine Verbesserung in Bezug auf Fahrweg, Zykluszeit, Prozesssicherheit, Energie und Verschleiß ergibt. Ebenfalls wird mit möglichst geringer Rechenzeit und Speicherbedarf der kürzeste/schnellste Fahrweg ermittelt. Weiter vorteilhaft erfolgt so ein kollisionsfreier Fahrweg, für den eine manuelle Programmierung und Parametrierung mittels der Maschinen- und/oder Robotersteuerung durch den Einrichter nicht nötig ist oder weitestgehend automatisiert abläuft.

Vorteilhaft kann so wie bei einer Autonavigation im Straßenverkehr auf Veränderungen reagiert werden mit dem Unterschied, dass sich im Gegensatz zum Straßenverkehr hier der Graph, d.h. übertragen die Karte, ändert. Der hinterlegte Algorithmus ist z.B. in der Lage, auf veränderte Lageistwerte und Achsgeschwindigkeiten zu reagieren. Der Bediener muss z.B. bei Anpassungen des Maschinenzyklus keinerlei Rücksicht mehr auf das Robotersystem nehmen. Dessen Abläufe werden automatisch und dynamisch angepasst. Dies kann im laufenden Zyklus geschehen, denn aufgrund der hohen Performance des Verfahrens kann die aktuelle Istposition als neuer Startwert und das geänderte Hindernis (z.B. bewegte Werkzeughälfte) zur Ermittlung des optimalen Pfades zum Zielpunkt erneut angepasst werden.

So kann bei einer für die Autonavigation relevanten Parameteränderung im laufenden Zyklus der Pfad angepasst werden. Beispielsweise registriert das Verfahren, ob während der Autonavigation eine Änderung des Graphen beispielsweise eine Änderung der Hindernisse vorliegt. Befindet sich aufgrund der Änderung ein Hindernis auf dem Pfad, wird ausgehend von der aktuellen Position der Algorithmus erneut angewandt und ein neuer Pfad berechnet. Beeinträchtigt das Hindernis den aktuellen Pfad nicht, erfolgt keine neue Berechnung.

Bevorzugt erfolgt die Berechnung, die Kollisionsprüfung und/oder das Autonavigieren vorausschauend. D.h., bei einer Bewegung kann es z.B. sein, dass zwar während einer bestimmten Zeitspanne ein Hindernis entlang des Pfades liegt, jedoch dieses Hindernis aufgrund von Bewegungen der bewegbaren Komponente, der Maschine, des Formteils und/oder gegebenenfalls des Maschinenteils wieder vom Pfad verschwindet, bevor die bewegbare Komponente, die Maschine, das Formteil und/oder gegebenenfalls das Maschinenteil auf das Hindernis stoßen bzw. mit diesem kollidieren. Vorteilhaft muss so nicht die Richtung gewechselt werden, wodurch beispielsweise Erschütterungen aufgrund von Richtungsänderungen vermieden werden.

Für eine vorteilhaft genaue und präzise Navigation wird bevorzugt jeweils wenigstens ein Kontaktpunkt von wenigstens einer bewegbaren Komponente und der Maschine in Bezug auf dessen Lage im Raum bereitgestellt, wobei die Kontaktpunkte miteinander für das Bereitstellen des Modells der wenigstens einen bewegbaren Komponente und der Maschine logisch gekoppelt werden. Je nachdem, ob die Maschine Maschinenteile aufweist, kann bevorzugt jeweils wenigstens ein Kontaktpunkt der Maschinenteile bereitgestellt und mit anderen Kontaktpunkten gekoppelt werden. Beispielsweise kann das Spritzgießwerkzeug an der Anbaufläche zur Form durch mindestens einen Kontaktpunkt in Bezug auf Position und Lage im Raum, ergänzt durch einen Winkel der Nulllage, eindeutig beschrieben werden, an den z.B. das nächste Maschinenteil und/oder ein Peripheriegerät automatisch ankoppeln kann. Dieser Punkt ist logisch mit dem aktuellen Istwert zum Beispiel der beweglichen Platte gekoppelt und wird automatisch nachgeführt. Dieser Kontaktpunkt kann in Analogie zur Elektrotechnik beispielsweise als „socket“ bezeichnet werden. Ebenfalls kann z.B. die feste Platte über wenigstens einen Punkt in Bezug auf Position und Lage und Winkel im Raum verfügen, welcher im Fall der festen Platte statisch ist. Auch kann beispielsweise ein Roboter als bewegbare Komponente in seiner Geometrie als Modell und dessen Lage zur Maschine bekannt sein. Im einfachsten Fall ist der Roboter mit seinem Sockel oder Fuß über die vorher beschriebene Funktion „plug“ und „socket“ z.B. mit der festen Werkzeugplatte der Maschine geometrisch und/oder logisch gekoppelt. Die Tauchachse des Roboters verfügt z.B. über eine Flanschplatte, an welcher ein formteilspezifischer Greifer angekoppelt wird. Die Flanschplatte kann über zusätzliche Kipp-, Schwenk- und/oder Drehachsen verfügen. Das bedeutet, der logische Ankoppelpunkt, „socket“, zum Ankoppeln des Greifers folgt der Fahr-, Kipp-, Schwenk- und/oder Drehbewegung der Flanschplatte. Der formteilspezifische Greifer kann beispielsweise über dessen Modell und über einen definierten Ankoppelpunkt, „plug“, logisch mit dem Greiferflansch verbunden werden und kann über eventuelle Fahr-, Kipp- und/oder Drehbewegungen geometrisch mitgeführt werden. Der Greifer hat wiederum mindestens einen Ankoppelpunkt (z.B. Mittelpunkt der Saugerfläche), welcher als logischer „socket“ wiederum das Formteil aufnehmen kann. Relevant ist die Lage des Greifers auch in Bezug auf den aktuellen Pfad. In bestimmten Ausrichtungen kann es bei starken Beschleunigungen zum Verrutschen des Formteils am Sauger des Greifers kommen, im Extremfall verliert der Greifer das Formteil. Je nach Greiferausrichtung kann bevorzugt die Beschleunigung entsprechend begrenzt werden. In einem Spritzgießprozess wird nach dem Ende der Formteilbildung die Form geöffnet. Die Zielposition des Greifers kann zur Entnahme des Formteils bevorzugt geometrisch bestimmt werden, wobei alle potenziellen Kollisionskanten und Störgeometrien als Hindernisse bekannt sind.

Um vorteilhaft eine schnelle und sichere Überprüfung hinsichtlich ankoppelbarer Modelle zu erhalten, wird dem wenigstens einen Kontaktpunkt bevorzugt wenigstens eine Liste zugeordnet, anhand derer ankoppelbare Modelle beschrieben und/oder aufgelistet werden. Beispielsweise wird an die bewegliche Platte der bewegliche Teil einer Spritzgießform angekoppelt. Die Spritzgießform ist ebenfalls als Modell bekannt und z.B. in der Maschine digital vorhanden. Dieser Teil des digitalen Modells der Spritzgießform (bewegliche Werkzeughälfte) verfügt nun über einen definierten Ankoppelpunkt, der in Position und Lage im Raum, im Modell genau definiert ist. Dieser Punkt kann beispielweise entsprechend „plug“ genannt werden. Die bewegliche Werkzeughälfte mit ihrem Kontaktpunkt „plug“ ist in der Ankoppelliste am „socket“ z.B. der beweglichen Werkzeugplatte gelistet. Bevorzugt kann so durch die Verwendung eines „plug“ bzw. eines „socket“ beispielsweise über die Bewegung eines Peripheriegerätes und/oder eines Maschinenteils auch die Bewegung des daran gekoppelten Peripheriegerätes und/oder Maschinenteils nachvollzogen werden.

Für eine vorteilhaft präzise Berechnung des Pfades wird der Raum bevorzugt in ein Raster aus Würfeln unterteilt, welches für die Erzeugung des wenigstens einen Graphen verwendet wird. Bevorzugt wird der gesamte Raum in ein Raster aus Würfeln unterteilt, welches für die Erzeugung des wenigstens einen Graphen verwendet wird. Der Raum kann dabei wenigstens teilweise die wenigstens eine bewegbare Komponente und/oder die Maschine aufweisen. Je nachdem, ob die Maschine Maschinenteile aufweist, kann bevorzugt der Raum wenigstens teilweise auch die Maschinenteile aufweisen. Im Graph werden dann z.B. die bewegbare Komponente, die Maschine und/oder gegebenenfalls die Maschinenteile als ein Hindernis dargestellt. Die anderen Teile des Raumes ohne Hindernisse können bevorzugt als Fahrbereiche grafisch unterschiedlich, z.B. mit unterschiedlichen Farben dargestellt werden.

Weiter bevorzugt ist es möglich, dass unabhängig von der Rastergröße des Raums, welcher z.B. aus Würfeln unterteilt ist ein diagonaler Weg beschrieben werden kann. Beispielsweise kann über eine Bahnbewegung mit z.B. zwei Achsen und mit einer definierten gemeinsamen Bahngeschwindigkeit eine Diagonale abfahren werden. In dem Fall werden vorteilhaft nicht mehrere Einzelbewegungen ausgeführt, sondern bevorzugt eine Bewegung vom Startpunkt bis zum Zielpunkt, wobei sich die Achsen synchron zueinander bewegen.

Bevorzugt wird als Algorithmus wenigstens ein Greedy-Search, ein Dijkstra- und/oder ein A*- Algorithmus mit wenigstens einer offenen Liste verwendet. Vorteilhaft ergibt sich so je nach Graph der kürzeste Pfad von einem Startpunkt zu einem Zielpunkt.

Für eine vorteilhaft schnelle Berechnung des Pfades wird als Optimierung bevorzugt wenigstens eine Sprungpunkt-Suche und/oder eine Verwaltung der offenen Liste verwendet.

Für eine vorteilhaft optimierte Verwaltung der offenen Liste erfolgt bevorzugt die Verwaltung der offenen Liste mit einem Binärheap.

Für eine vorteilhafte Übersicht und eine verbesserte Sicherheit wird das Verfahren bevorzugt vorab simuliert. Es kann beispielsweise so eine Vorabsimulation der Abläufe und Pfaderstellung an einem Computermodell stattfinden, welche weiter vorteilhaft noch visualisiert werden kann.

Um vorteilhaft eine Verbesserung hinsichtlich Rechenzeit und Geschwindigkeit des Verfahrens zu gewährleisten, werden bevorzugt wenigstens zwei verschiedene Varianten des Verfahrens simuliert und in Bezug auf unterschiedliche Kriterien miteinander verglichen. Der Ablauf kann so, bezogen auf den aktuellen Werkzeug-Datensatz erstellt werden. Hierbei ist es möglich, verschiedene Varianten zu simulieren und in Bezug auf verschiedene Kriterien, z.B. Energie, Verschleiß, Fahrweg, und/oder Zykluszeit zu vergleichen.

Um den Produktionsprozess vorteilhaft auch aus der Entfernung überwachen zu können, wird bevorzugt der Graph und/oder das Modell der wenigstens einen bewegbaren Komponente und/oder der Maschine grafisch dargestellt. Je nachdem, ob die Maschine Maschinenteile aufweist, können bevorzugt die Maschinenteile grafisch dargestellt werden.

Das beschriebene Verfahren lässt sich beispielsweise mit mehreren Werkzeugen beispielsweise an einer Spritzgießmaschine an einem Mehrkavitäten-Werkzeug und/oder einem Mehr- komponenten-Werkzeug durchführen, welches nicht direkt auf der beweglichen Platte montiert wird, sondern z.B. auf einer Dreheinheit, die wiederum als Modell hinterlegt ist, deren Lage über „plug“ und „socket“ genau definiert ist. Ebenfalls kann ein Mehrkomponentenwerkzeug verwendet werden, bei welchem ein Vorspritzling über ein Robotersystem umgesetzt wird. Auch möglich sind Einlegeteile, die über das Robotersystem mittels Greifer eingelegt werden. Ebenso kann ein Würfelwerkzeug („Cube“) verwendet werden, welches noch über mindestens eine Drehachse verfügt und mehrere Einlege- bzw. Entnahme-Flächen besitzt sowie dessen Sonderform („Reverse Cube“), bei welchem der Würfel nochmals geteilt ist und gegenläufig dreht. Hier wird jede Würfelhälfte separat beschrieben.

Die Aufgabe wird zudem durch eine Maschinensteuerung für eine Maschine, insbesondere für eine Spritzgießmaschine zur Verarbeitung von Kunststoffen und anderer plastifizierbarer Massen oder einer 3D-Druckmaschine gelöst. Für eine vorteilhafte Anpassung des Maschinenzyklus durch den Bediener sowie für Verbesserungen in Bezug auf Fahrweg, Zykluszeit, Prozesssicherheit, Energie und Verschleiß ist die Maschinensteuerung eingerichtet, ausgeführt und/oder konstruiert um das vorher beschriebene Verfahren auszuführen.

Ebenfalls wird die Aufgabe durch ein Computerprogrammprodukt gelöst. Für Vorteile hinsichtlich einer Berechnung des Pfades bezüglich Fahrweg, Zykluszeit, Prozesssicherheit, Energie und Verschleiß ist das Computerprogrammprodukt mit einem Programmpunkt auf einem Computer lesbaren Medium gespeichert zur Durchführung des oben beschriebenen Verfahrens.

Weitere Vorteile ergeben sich aus den Unteransprüchen und der nachfolgenden Beschreibung eines bevorzugten Ausführungsbeispiels. Die in den Patentansprüchen einzeln aufgeführten Merkmale sind in technologisch sinnvoller Weise miteinander kombinierbar und können durch erläuternde Sachverhalte aus der Beschreibung und durch Details aus den Figuren ergänzt werden, wobei weitere Ausführungsvarianten der Erfindung aufgezeigt werden. Kurzbeschreibung der Figuren

Im Folgenden wird die Erfindung anhand eines in den beigefügten Figuren dargestellten Ausführungsbeispiels näher erläutert. Es zeigen:

Fig. 1 eine Maschine mit bewegbarer Komponente,

Fig. 2 eine Maschine mit bewegbarer Komponente,

Fig. 3 ein Graph nach Durchlauf eines Greedy-Search-Suchverfahren,

Fig. 4 ein Graph nach Durchlauf eines Dijkstra-Algorithmus,

Fig. 5 ein Flussdiagramm des A*-Algorithmus,

Fig. 6 ein Graph nach Durchlauf eines A*-Algorithmus,

Fig. 7a, 7b ein Vergleich von symmetrischen Pfaden gegenüber einer Sprungpunkt-Suche,

Fig. 8a-8c ein Vergleich zur Reduzierung der Nachbarzahl,

Fig. 9 ein Graph nach Durchlauf der Sprungpunkt-Suche,

Fig. 10 eine Darstellung eines Binärheaps in einem Array,

Fig. 11 ein Graph mit einer Bahnbewegung.

Beschreibung bevorzugter Ausführungsbeispiele

Die Erfindung wird jetzt beispielhaft unter Bezug auf die beigefügten Zeichnungen näher erläutert. Allerdings handelt es sich bei den Ausführungsbeispielen nur um Beispiele, die nicht das erfinderische Konzept auf eine bestimmte Anordnung beschränken sollen. Bevor die Erfindung im Detail beschrieben wird, ist darauf hinzuweisen, dass sie nicht auf die jeweiligen Bauteile der Vorrichtung sowie die jeweiligen Verfahrensschritte beschränkt ist, da diese Bauteile und Verfahren variieren können. Die hier verwendeten Begriffe sind lediglich dafür bestimmt, besondere Ausführungsformen zu beschreiben und werden nicht einschränkend verwendet. Wenn zudem in der Beschreibung oder in den Ansprüchen die Einzahl oder unbestimmte Artikel verwendet werden, bezieht sich dies auch auf die Mehrzahl dieser Elemente, solange nicht der Gesamtzusammenhang eindeutig etwas Anderes deutlich macht.

In einem Ausführungsbeispiel wird bei einem Verfahren zur Bestimmung wenigstens eines Teils eines Pfades 12 zur Verbindung wenigstens eines Startpunktes 14 mit wenigstens einem Zielpunkt 16 in einem Raum R für wenigstens eine Autonavigation wenigstens einer bewegbaren Komponente wie z.B. eines Peripheriegerätes durch den Raum an einer Maschine 100, insbesondere einer Spritzgießmaschine zur Verarbeitung von Kunststoffen und anderer plasti- fizierbarer Massen oder einer 3D-Druckmaschine, in einem ersten Schritt wenigstens ein Modell der wenigstens einen bewegbaren Komponente und der Maschine bereitgestellt. Das Modell kann beispielsweise als digitales Modell bereitgestellt werden.

Die Maschine 100 kann wenigstens ein Maschinenteil aufweisen, wie z.B. ein Formwerkzeug, ein Formnest, ein Formteil, einen Anguss, eine bewegliche Platte 110, eine stationäre Platte 112, und/oder eine Einspritzeinheit. Weiter kann die Maschine noch weitere Maschinenteile und/oder Komponenten beispielsweise von einer Spritzgießmaschine oder einer 3D-Druckma- schine aufweisen. Die Maschinenteile können sich auch bewegen, wie z.B. die bewegliche Platte 110.

Je nachdem, ob die Maschine Maschinenteile aufweist, kann bevorzugt ein Modell des Maschinenteils bereitgestellt werden.

Als „bewegbaren Komponente“ wird ein relativ zur Maschine bewegbares Element wie z.B. ein Peripheriegerät verstanden. Dabei kann es sich um Greifer, Roboter, Auswerfer oder auch andere bewegbare Komponenten eines Peripheriegeräts als auch der Maschine handeln, die sich im Raum R bewegen, so dass eine Kollision mit der Maschine zu vermeiden ist, insbesondere wenn sich auch die Maschine bewegt. Die Fig. 1 , 2 zeigen als Beispiel für eine bewegbare Komponente eine Tauchachse 102.

In einem weiteren Schritt werden Geometrieinformationen des Raums R und der wenigstens einen bewegbaren Komponente und der Maschine 100 erfasst. Die Geometrieinformationen können dabei wenigstens teilweise aus dem Modell bzw. aus den Modellen abgeleitet werden. Beispielsweise können die Geometrieinformationen auch über Sensoren erfasst werden.

Je nachdem, ob die Maschine 100 Maschinenteile aufweist, können bevorzugt Geometrieinformationen des Maschinenteils erfasst werden.

Weiterhin wird in einem weiteren Schritt eine aktuelle Lage der wenigstens einen bewegbaren Komponente und der Maschine 100 im Raum R bestimmt. Die aktuelle Lage kann beispielsweise über Sensoren oder über Positionsistwerte der wenigstens einen bewegbaren Komponente und/oder der Maschine erfasst werden.

Je nachdem, ob die Maschine 100 Maschinenteile aufweist kann bevorzugt eine aktuelle Lage des Maschinenteils bzw. der Maschinenteile bestimmt werden. In einem weiteren Schritt werden die Geometrieinformationen und die aktuelle Lage der wenigstens einen bewegbaren Komponente sowie der 100 Maschine im Raum R zueinander zur Erzeugung wenigstens eines Graphen 10 des Raums R in Beziehung gesetzt.

Je nachdem, ob die Maschine Maschinenteile aufweist, können bevorzugt die Geometrie Informationen und die aktuelle Lage des Maschinenteils ebenso zur Erzeugung des Graphen 10 in Beziehung gesetzt werden. Beispielsweise ergibt sich somit ein Graph 10 gemäß Fig. 3, in dem beispielsweise die Maschine 100, bewegbare Komponenten und vorhandene Maschinenteile als Hindernisse 24 dargestellt sind. Der Einfachheit halber ist der Graph 10 in Fig. 3 lediglich als zweidimensionaler Graph dargestellt. Prinzipiell kann der Graph aber für andere und/oder mehrere Dimensionen dargestellt werden, z.B. als ein eindimensionaler oder dreidimensionaler Graph.

Die Berechnung des Pfades 12 unter Anwendung wenigstens eines Algorithmus auf den Graphen 10 erfolgt in einem weiteren Schritt, wobei für das Berechnen des Pfades 12 zusätzlich wenigstens eine Optimierung durchgeführt wird.

In einem weiteren Schritt wird wenigstens eine Kollisionsprüfung entlang des Pfades 12 durchgeführt. Bevorzugt erfolgt die Kollisionsprüfung in Echtzeit.

Dann erfolgt in einem weiteren Schritt die Autonavigation der wenigstens einen bewegbaren Komponente entlang des Pfades 12.

Bevorzugt kann eine Berechnung eines Pfades und eine Autonavigation entlang des Pfades auch für Maschinenteile der Maschine 100 erfolgen. So kann beispielsweise zusätzlich zur Autonavigation der bewegbaren Komponente z.B. des Peripheriegeräts eine Autonavigation eines oder auch mehrerer Maschinenteile erfolgen.

In einem bevorzugten Ausführungsbeispiel wird der Algorithmus unter dynamischer Änderung des Graphen 10 infolge von Bewegungen der wenigstens einen bewegbaren Komponente und/oder der Maschine 100 angewandt. Je nachdem, ob die Maschine Maschinenteile aufweist, kann bevorzugt der Algorithmus unter dynamischer Änderung des Graphen 10 infolge von Bewegungen des wenigstens einen Maschinenteils angewandt werden. Beispielsweise kann es während der Autonavigation zu einer Bewegung anderer Maschinenteile, bewegbaren Komponenten und/oder der Maschine auch relativ zueinander kommen. Aufgrund dieser Bewegung kann es vorkommen, dass der Graph 10, d.h. die „Karte“, sich ändert und somit ein Hindernis 118 auf dem bereits berechneten Pfad 12 auftaucht. Der Algorithmus erkennt diese Änderung des Graphen 10 bevorzugt automatisch und registriert, ob ein Hindernis auf dem Pfad 12 liegt. Ist dies der Fall, wird der Algorithmus erneut angewandt, wobei als Startpunkt 14 nun die aktuelle Istposition verwendet wird. So kann bei einer für die Autonavigation relevanten Parameteränderung im laufenden Zyklus der Pfad 12 angepasst werden.

Im Ausführungsbeispiel der Fig. 1 ist eine Maschine 100 mit einer bewegbaren Komponente, z.B. einer Tauchachse 102 als bewegbare Komponente dargestellt, welche gerade ein Formteil 122 entnimmt. Die Tauchachse 102 soll das Formteil 122 kollisionsfrei, autonavigiert entnehmen und kann in verschiedene Richtungen 106, 108, im Ausführungsbeispiel gemäß Fig. 1 nach links, rechts, oben und unten bewegt werden. Prinzipiell ist es denkbar, dass die Tauchachse 102 bevorzugt zusätzlich auch eine Kipp-, Schwenk- und Drehbewegung ausführen kann und somit beliebige Positionen im Raum einnehmen kann. Dadurch ergeben sich beliebige Vektoren, welche die Tauchachse 102 aufweisen kann.

Die Maschine 100 weist weiter eine Schließeinheit mit einer beweglichen Platte 110 und einer stationären Platte 112 auf, die zwischen sich einen Formspannraum zur Aufnahme von Formwerkzeugen mit zwei Werkzeughälften 114, 116 aufspannen. Die bewegliche Platte 110 kann in einer Richtung 104, im Ausführungsbeispiel gemäß Fig. 1 nach links und rechts, bewegt werden. Prinzipiell denkbar ist auch, dass die stationäre Platte 112 in einer Richtung, z.B. in der Richtung 104 bewegt werden kann. Durch die Bewegung der beweglichen Platte 110 bewegt sich auch die Werkzeughälfte 116. Der Raum R, in dem ich die Maschine 100 befindet, weist somit Hindernisse 118 und Fahrbereiche 120 auf, in denen ein kollisionsfreies Autonavigieren nicht bzw. möglich ist.

In Fig. 2 ist eine Bewegung der Tauchachse 102 als bewegbare Komponente und der beweglichen Werkzeugplatte 110 dargestellt. Die Tauchachse 102 wurde dort mit dem Formteil 122 nach oben entlang der Richtung 106 bewegt. Die bewegliche Platte 110 wurde entlang der Richtung 104 nach rechts bewegt. Durch die Bewegungen entstehen entsprechend neue Hindernisse 118 und Fahrbereiche 120 für die Autonavigation.

In einem weiteren bevorzugten Ausführungsbeispiel erfolgt die Berechnung, die Kollisionsprüfung und/oder das Autonavigieren vorausschauend. Beispielsweise taucht entlang des Pfades nur während einer bestimmten Zeitspanne ein Hindernis 118 auf, welches jedoch bereits dann wieder vom Pfad verschwunden ist, bevor die bewegbare Komponente, die Maschine 100, das Formteil und/oder gegebenenfalls das Maschinenteil damit kollidieren würde. Vorteilhaft muss so nicht die Richtung gewechselt werden, wodurch beispielsweise Erschütterungen aufgrund von Richtungsänderungen vermieden werden. In einem weiteren bevorzugten Ausführungsbeispiel wird jeweils wenigstens ein Kontaktpunkt von der wenigstens eine bewegbare Komponente und der Maschine 100 in Bezug auf eine Lage des wenigstens eines Kontaktpunktes im Raum R bereitgestellt, wobei die Kontaktpunkte miteinander für das Bereitstellen des Modells der wenigstens einer bewegbaren Komponente und der Maschine logisch gekoppelt werden. Je nachdem, ob die Maschine Maschinenteile aufweist, kann bevorzugt jeweils ein Kontaktpunkt des Maschinenteils bzw. der Maschinenteile bereitgestellt werden, welche logisch mit anderen Kontaktpunkten gekoppelt werden können. Beispielsweise kann an die bewegliche Platte 110 der bewegliche Teil einer Spritzgießform angekoppelt werden. Die Spritzgießform ist ebenfalls als Modell bekannt und vorhanden. Z.B. verfügt der bewegliche Teil des Modells der Spritzgießform (bewegliche Werkzeughälfte 116) über einen definierten Kontaktpunkt, der in Position und Lage im Raum R, im Modell genau definiert ist. Dieser Punkt kann als „plug“ bezeichnet werden.

In einem weiteren bevorzugten Ausführungsbeispiel wird dem wenigstens einen Kontaktpunkt wenigstens eine Liste zugeordnet, anhand derer ankoppelbare Modelle beschrieben und/oder aufgelistet werden. Um beim obigen Beispiel mit der beweglichen Werkzeughälfte 116 zu bleiben, ist diese mit ihrem Kontaktpunkt „plug“ in der Liste am „socket“ der beweglichen Platte 110 gelistet.

In einem weiteren bevorzugten Ausführungsbeispiel gemäß Fig. 3 wird der Raum R in ein Raster aus Würfeln 18 unterteilt, welches für die Erzeugung des wenigstens einen Graphen 10 verwendet wird. Der Raum R kann wenigstens teilweise die wenigstens eine bewegbare Komponente und/oder die Maschine 100 aufweisen. Je nachdem, ob die Maschine Maschinenteile aufweist, kann der Raum bevorzugt wenigstens teilweise ein Maschinenteil aufweisen, welches z.B. im Graph 10 gemäß Fig. 3 als ein Hindernis 24 dargestellt ist. In Fig. 3 ist der Einfachheit halber lediglich eine Ebene des Raums mit Hindernissen 24 als Graph 10 dargestellt. Der Graph kann jedoch grundsätzlich dreidimensional sein.

In einem weiteren bevorzugten Ausführungsbeispiel wird als Algorithmus wenigstens ein Greedy-Search-, ein Dijkstra- und/oder ein A*-Algorithmus mit wenigstens einer offenen Liste verwendet.

Im Folgenden wird vorgestellt, wie Pfade 12 zwischen zwei beliebigen Punkten 14, 16 in einem Graphen 10 berechnet werden. Kürzeste-Wege-Probleme sind häufig im Bereich der künstlichen Intelligenz zu finden und sind mit dem Ziel, einen möglichsten guten Pfad 12 durch einen Graphen 10 zu finden, meist mit einer recht hohen Komplexität verbunden. Die Wegfindung befasst sich mit dem Problem, einen Pfad 12 in einem Graphen 10 von einem Startpunkt 14 zu einem Zielpunkt 16 zu finden. Der Graph 10 muss für die vorgestellten Ansätze die Eigenschaft erfüllen, dass alle Kanten des Graphen 10 positiv gewichtet sind. Dafür wird der Maschinenraum in ein Raster aus Würfeln 18 unterteilt, welche auch Knoten 18 genannt werden. Basierend auf dem rasterförmigen Modell des Raumes R, welches als Graph 10 verwendet wird, ist ein möglichst kurzer Pfad 12 vom Startpunkt 14 zum Zielpunkt 16 gesucht. Dazu kommt, dass der Suchgraph 10 nur implizit vorliegt. Es muss also für jeden Knoten 18 beim Betreten überprüft werden, ob dieser Knoten 18 eine gültige Position des Robot-Systems ist oder ein Hindernis 24 darstellt.

Der Greedy-Search-Algorithmus (gierige Suche) ist ein informiertes Suchverfahren und benötigt eine Schätzfunktion (Heuristik). Diese schätzt die Entfernung von einem beliebigen Knoten 18 zum Zielpunkt 16. Beispielsweise ist es denkbar, dass z.B. ein Roboter eine Achse nach der anderen Achse bewegen soll. Deshalb kann als Heuristikfunktion z.B. die Manhattan-Distanz verwendet werden. Der Roboter kann sich jedoch nicht nur linear in X-, Y- oder Z-Rich- tung bewegen oder nur eine Achse nach der anderen bewegen. Unabhängig von der Rastergröße, kann z.B. mit Würfeln auch ein diagonaler Weg beschrieben werden. Prinzipiell ist es in einem weiteren bevorzugten Ausführungsbeispiel auch möglich, dass der Roboter über eine Bahnbewegung 130 mit z.B. zwei Achsen 132, 134 (z.B. Y und Z), mit einer definierten gemeinsamen Bahngeschwindigkeit eine Diagonale abfährt (Fig. 11). In dem Fall in Fig. 11 führt der Roboter z.B. nicht 14 Einzelbewegungen aus, sondern eine Bewegung vom Startpunkt 14 bis zum Zielpunkt 16, wobei sich beide Achsen synchron zueinander bewegen.

Die Suche beginnt beim Startpunkt 14, dieser wird expandiert. Beim Expandieren werden alle vom Startpunkt 14 erreichbaren Knoten 18 über die Heuristik auf ihre geschätzte Entfernung zum Zielpunkt 16 hin untersucht. Außerdem wird in jedem besuchten Knoten 22 eine Referenz auf den Knoten 18 gespeichert, der gerade expandiert wird (siehe Pfeile 26 in Fig. 3). Somit kennt jeder besuchte Knoten 22 seinen Vorgänger. Der Knoten mit der besten Heuristik wird als nächstes expandiert. Iterativ wird so lange der günstigste Knoten expandiert, bis der Zielpunkt 16 gefunden ist. Als Folgeknoten wird also immer derjenige Knoten 18 gewählt, welcher zum Zeitpunkt der Wahl das beste Ergebnis verspricht. Einmal getroffene Entscheidungen werden nicht aus globaler Sicht analysiert oder revidiert.

Wenn der Zielpunkt 16 gefunden wurde, kann der Pfad 12 vom Zielpunkt 16 zum Startpunkt 14 einfach über die gespeicherten Vorgänger der Knoten 18 zurückverfolgt werden. Dieser Pfad 12 ist in umgekehrter Reihenfolge der gesuchte Pfad 12 vom Startpunkt 14 zum Zielpunkt 16. Ein Vorteil des Greedy-Search-Algorithmus ist, dass er einfach zu entwerfen und effizient zu implementieren ist. Er löst Probleme schnell, jedoch nicht immer optimal. In Fig. 3 ist ein Beispiel dargestellt, dass der gefundene Pfad 12 nicht immer der kürzeste ist. Aus diesem Grund ist der Greedy-Search-Algorithmus nicht immer geeignet, den kürzesten Pfad 12 zu finden.

Der Dijkstra-Algorithmus gemäß Fig. 4 löst im Gegensatz zum Greedy-Search-Algorithmus das Problem des kürzesten Pfades. Statt eine schätzende Heuristik zu verwenden, geht Dijkstra den umgekehrten Weg. Der Dijkstra-Algorithmus speichert die Kosten des Pfades von den besuchten Knoten 18 zum Startpunkt 14. Außerdem merkt sich ebenfalls jeder besuchte Knoten 18 seinen Vorgängerknoten. Beginnend beim Startpunkt 14 wird iterativ der Knoten 18, der die bisher geringsten zurückgelegten Pfadkosten hat, expandiert. Beim Expandieren werden für alle direkten Nachbarn des aktuellen Knoten 18 die Kosten zum Startpunkt 14 ermittelt. Das ist in diesem Fall denkbar einfach. Da alle Knoten 18 in dem Raster gleich groß sind, kann für das Betreten eines Knotens immer „1“ als Kosten veranschlagt werden. Die Kosten ergeben sich also aus der Anzahl der besuchten Knoten 22 zwischen dem Startpunkt 14 und der untersuchten Position. Aus diesem Grund wird das gesamte Gebiet um den Startpunkt 14 gleichmäßig erforscht. Dadurch, dass jeder Knoten 18 seinen Vorgänger kennt, ist von jedem Knoten 18 der kürzeste Weg zum Startpunkt 14 bekannt. Wenn der Zielpunkt 16 durch das gleichmäßige Expandieren gefunden wird, terminiert der Algorithmus, da der gefundene Pfad 12 bereits der günstigste ist. Der Pfad 12 muss auch hier in umgekehrter Reihenfolge abgearbeitet werden. Nachvollziehen kann man das, indem man sich in Fig. 4 einen beliebigen besuchten Knoten 22 aussucht und die Pfeile 26 bis zum Startpunkt 14 verfolgt.

Fig. 4 zeigt deutlich, dass der Dijkstra-Algorithmus im Vergleich zum Greedy-Search-Algorithmus (Fig. 3) zwar den kürzesten Pfad 12 findet, jedoch deutlich mehr Knoten 18 dafür untersuchen muss. Das liegt daran, dass dieser die Information, an welcher Stelle der Zielpunkt 16 sich im Graphen 10 befindet, nicht bei der Auswahl der zu expandierenden Knoten 18 nutzen kann. Stärken kann der Algorithmus vor allem in Szenarien zeigen, in denen die Position des Zielpunkts 16 unbekannt ist. Bei bekannter Position des Zielpunkts 16 werden aber in den meisten Fällen unnötig viele Knoten 18 expandiert. Das geht sehr zu Lasten der Laufzeit und des Speicherverbrauches.

Auf dem Gebiet der künstlichen Intelligenz ist der A*-Algorithmus ein bewährter Ansatz, um in einem gerichteten Graphen 10 den besten Pfad 12 zwischen dem Startpunkt 14 und dem Zielpunkt 16 zu berechnen. Der A*-Algorithmus kombiniert die Vorteile des Dijkstra-Algorithmus und des Greedy-Search-Algorithmus und eliminiert weitestgehend die Nachteile. Wenn ein Pfad 12 gefunden wird, ist dieser immer optimal. Die Anzahl der besuchten Knoten 22 ist in den meisten Fällen deutlich geringer als beim Durchlauf von Dijkstras-Algorithmus (Fig. 6). Im schlechtesten Fall jedoch gleich groß. Für jeden besuchten Knoten Ki aus dem Pfad 12 werden die geschätzten Pfadkosten F für den gesamten Pfad 12 vom Startpunkt 14 zum Zielpunkt 16 berechnet.

Um die Pfadkosten F zu ermitteln, gilt die Formel: F = G + H. G sind die Kosten für den bereits zurückgelegten Pfad 12 vom Startpunkt 14 zum Knoten Ki. Um G zu bestimmen, werden auf das G des Vorgängers die Kosten für das Besuchen von einem Knoten 18 addiert. H steht für Heuristik, also die geschätzten Kosten die von Knoten Ki zum Zielpunkt 16 anfallen werden. Dafür wird wie bei dem Greedy-Search-Algorithmus eine Heuristikfunktion verwendet. Diese muss immer an die spezifische Problemstellung angepasst werden. Die Garantie auf den günstigsten Pfad 12 ist nur gegeben, wenn die Heuristikfunktion unterschätzend ist. Sie darf also niemals höhere Kosten schätzen, als tatsächlich anfallen. Je genauer die Schätzfunktion ist, desto schneller läuft der A*-Algorithmus ab. Auch hier ist es beispielsweise denkbar, dass z.B. ein Roboter eine Achse nach der anderen Achse bewegen soll. Beispielsweise kann dann wie beim Greedy-Search-Algorithmus die Manhattan-Distanz als Heuristikfunktion verwendet werden. Prinzipiell kann der Roboter sich jedoch nicht nur linear in X-, Y- oder Z-Richtung oder nur eine Achse nach der anderen Achse bewegen. Unabhängig von der Rastergröße, kann z.B. mit Würfeln auch ein diagonaler Weg beschrieben werden. Prinzipiell ist es in einem weiteren bevorzugten Ausführungsbeispiel auch möglich, dass der Roboter über eine Bahnbewegung 130 mit z.B. zwei Achsen 132, 134 (z.B. Y und Z), mit einer definierten gemeinsamen Bahngeschwindigkeit eine Diagonale abfährt (Fig. 11). In dem Fall in Fig. 11 führt der Roboter nicht 14 Einzelbewegungen aus, sondern eine Bewegung vom Startpunkt 14 bis zum Zielpunkt 16, wobei sich beide Achsen synchron zueinander bewegen. Weiter werden beim A*- Algorithmus eine offene und eine geschlossene Liste verwendet. In die offene Liste werden die besuchten, in die geschlossene alle vollständig untersuchten Knoten 18 gelegt.

In Fig. 5 ist anhand eines Flussdiagramms der Ablauf des A*-Algorithmus erklärt. Zum Start 30 wird der Startpunkt 14 bzw. der Startknoten in Schritt 32 in die offene Liste gelegt, dann wird in Schritt 34 in einer Schleife 36 immer der Knoten 18 mit dem günstigsten F-Wert aus der offenen Liste geholt und bearbeitet. Wenn die offene Liste leer ist, bedeutet das, dass der Algorithmus keine Lösung gefunden hat. Da z.B. der Roboter seine Geometrie mithilfe von Rotationsachsen ändern kann, muss die Suche hier noch nicht aufgegeben werden. In einer weiteren Schleife 38 wird überprüft, ob es z.B. Rotationsachsen gibt, die noch nicht betätigt wurden. Können diese in einem Schritt 40 bewegt werden, beginnt die Suche in einem weiteren Schritt 42 von neuem. Ansonsten hat der Algorithmus ein Ende 44. Erfolgreich terminiert die Suche, wenn der Zielpunkt 16 in einer Schleife 39 gefunden ist. Wenn ein Knoten 18 in Schritt 46 bearbeitet werden soll, wird in Schritt 48 in den Schleifen 50, 52 für jeden seiner direkten Nachbarn geprüft, ob diese Hindernisse 24 darstellen oder bereits in der geschlossenen Liste sind. Falls ja, wird der Nachbar in einem Schritt 54 ignoriert. Andernfalls werden in einem Schritt 56 für den Nachbarn die G- und H-Werte bestimmt und in einem Schritt 58 der aktuelle Knoten als Vorgänger gespeichert. Abschließend wird in einem Schritt 60 der Nachbar in die offene Liste eingefügt. Sind alle Nachbarn eines Knotens untersucht, kommt dieser in einem Schritt 62 in die geschlossene Liste.

Sobald ein Knoten 18 in die geschlossene Liste eingefügt wurde, ist der günstigste Weg von diesem Knoten 18 bekannt. Im schlechtesten Fall, muss der A*-Algorithmus alle Knoten 18 besuchen. Hindernisse 24 auf der Ideallinie verschlechtern die Laufzeit immens, da die Kosten entlang des Hindernisses 24 wachsen und daher zuerst viele Knoten 18 in der falschen Richtung untersucht werden müssen.

In einem weiteren bevorzugten Ausführungsbeispiel wird als Optimierung wenigstens eine Sprungpunkt-Suche und/oder eine Verwaltung der offenen Liste verwendet.

Bei genauerer Betrachtung des Suchgraphen nach dem Durchlauf des A*-Algorithmus in Fig. 7a fällt auf, dass es eine Vielzahl von Pfaden 12 mit den gleichen Kosten gibt. Dieses Phänomen tritt in rasterförmig angeordneten Graphen 10 auf, die nur horizontale oder vertikale Bewegungen erlauben. Diese Pfade 12 werden symmetrisch genannt, da sie sich nur in der Reihenfolge der Bewegungen unterscheiden. Für den Graphen 10 in Fig. 7a und Fig. 7b bedeutet das, dass z.B. der Roboter insgesamt sechs Knoten 18 nach rechts und drei Knoten 18 nach oben fährt. Die Reihenfolge der Aktionen spielt keine Rolle. Durch Berücksichtigung dieser Eigenschaft, kann die Anzahl der besuchten Knoten 18 erheblich reduziert werden.

Um ein Ergebnis wie in Fig. 7b erreichen zu können, muss die Symmetrie der Pfade 12 berücksichtigt werden. Der Weg zum Erfolg führt über das Reduzieren der Nachbarn (Neighbour Pruning). Im Gegensatz zum A*-Algorithmus werden beim Expandieren eines Knotens 18 nicht immer alle Nachbarknoten untersucht, sondern in den meisten Fällen nur einer (anstatt vier im zweidimensionalen und sechs im dreidimensionalen Raum). Die wichtigsten drei Regeln dafür lassen sich aus Fig. 8a - 8c ableiten. 1. Regel:

Alle Nachbarn, die sich nicht genau in Bewegungsrichtung befinden, werden nicht beachtet. Im Beispiel in Fig. 8a ist der Knoten Nummer 6 der einzige Knoten, der in die offene Liste gelegt wird. Die Knoten mit der Nummer 2, 4 und 8 werden nicht untersucht.

2. Regel:

Wenn der aktuelle Knoten 18 an ein Hindernis 24 grenzt, werden wie beim A*-Algorithmus alle befahrbaren Nachbarn untersucht (Fig. 8b). Das ist nötig, um Hindernisse 24 ideal zu umfahren und den kürzesten Pfad 12 zu finden.

3. Regel:

Wenn der in Regel 1 ausgewählte Nachbar einen schlechteren F-Wert als der aktuelle Knoten 18 bekommt, werden alle befahrbaren Nachbarn untersucht (Fig. 8c). So wird verhindert, dass der Pfad 12 in einer Dimension am Ziel vorbei geht (Fig. 9).

Während Regel 1 das Weglassen der Nachbarn beschreibt, sorgen die Regeln 2 und 3 dafür, dass die Suche weiterhin ein optimales Ergebnis abliefert. Diese finden die so genannten Sprungpunkte 64 (Jump-Points), die der Sprungpunkt-Suche ihren Namen gibt. Diese Punkte heißen Sprungpunkte 64, weil zwischen ihnen sehr schnell und nur gerade aus navigiert wird. Sprungpunkte 64 erkennt man daran, dass sie mehr als einen Nachbarn untersuchen. In Fig. 9 ist zum Beispiel der Knoten 18, in dem der Pfad 12 seine Richtung nach rechts ändert, ein Sprungpunkt 64.

Als Vorteile der Sprungpunkt-Suche ergeben sich folgende Punkte:

1. Sie ist optimal (findet den günstigsten Pfad 12).

2. Vorberechnungen werden nicht benötigt.

3. Es wird kein Mehrverbrauch von Speicher verursacht.

4. Beschleunigt den einfachen A*-Algorithmus erheblich. Dabei gilt: je länger der Pfad 12, desto größer ist die Verbesserung.

Im direkten Vergleich mit Hindernissen 24 zwischen dem einfachen A*-Algorithmus (Fig. 6) und dem optimierten A*-Algorithmus mit einer Sprungpunkt-Suche (Fig. 9) ist nochmals deutlich zu sehen, wie viele Knotenuntersuchungen mit der Optimierung eingespart werden können.

Ein großer Teil der Rechenzeit beim A*-Algorithmus entfällt auf das Durchsuchen der offenen Liste nach dem Element mit dem geringsten F-Wert. Je größer Graph 10, desto höher ist der Laufzeitanteil, der zur Verwaltung der offenen Liste benötigt wird. Da der Graph 10 z.B. des Maschinenraumes sehr groß ist, lohnt es sich, die Verwaltung der offenen Liste zu optimieren. Im einfachsten Fall werden alle Elemente der offenen Liste in einer Array-Liste gehalten. Das ermöglicht ein schnelles Einfügen (Komplexität: 0(1)) in die Liste, aber das verlangsamt das vorstellbare Entfernen eines Elements, da jedes Element durchsucht werden muss, um das kleinste F zu finden (Komplexität: O(n)). Bei einer langen offenen Liste kann das schnell problematisch werden. Eine Möglichkeit, das Entfernen von Elementen einfach zu beschleunigen, ist die offene Liste sortiert zu halten. Die beim Einfügen entstehenden Kosten sind gerade bei größeren Listen nur ein Bruchteil von dem, was ansonsten beim Entfernen benötigt würde. Wird ein Sortieralgorithmus zum Einfügen mit einer Komplexität < O(n) gewählt, hat sich der Aufwand gelohnt. Die Komplexität der Entfernen-Operation beträgt in einer sortierten Liste 0(1).

In einem weiteren bevorzugten Ausführungsbeispiel erfolgt die Verwaltung der offenen Liste mit einem Binärheap 20. Sehr effektiv können Daten strukturiert in einem Binärheap 20 (Binary Heap) gehalten werden. Dieser kann z.B. in einem einfachen Array gespeichert werden. Einfüge-, Lösch- und Suchoperationen können mit einer Worst-Case-Laufzeit von O(log n) erledigt werden, die Suche nach dem kleinsten Element 66 (diese wird beim A*-Algorithmus verwendet) sogar mit 0(1). Allerdings muss nach dem Zugriff auf das kleinste Element dieses auch gelöscht werden. Anders als in einer sortierten Liste, ist ein Binärheap 20 nicht streng absteigend oder aufsteigend sortiert. Es handelt sich um einen Binärbaum 70, der zwei zusätzliche Bedingungen erfüllt:

1 . Der Binärbaum 70 ist linksbündig balanciert.

2. Für jeden Knoten 18 gilt: Der eigene Schlüssel ist kleiner als der Schlüssel der Kindknoten.

Damit steht an erster Stelle des Binärbaumes 70 immer das kleinste Element 66. Fig. 10 zeigt exemplarisch einen Binärheap 20. Es fällt auf, dass im Array 28 kein Element 66 an der nullten Stelle steht. Berechnungen der Indizes von Kind- oder Vaterknoten werden dadurch vereinfacht.

In einem weiteren bevorzugten Ausführungsbeispiel wird das Verfahren bei einer Änderung im Produktionsablauf in Echtzeit simuliert und/oder der Algorithmus reagiert auf veränderte Positionen und/oder Geschwindigkeiten der wenigstens einen bewegbaren Komponente und/oder der Maschine 100, indem wenigstens eine weitere Kollisionsprüfung durchgeführt und/oder wenigstens ein neuer Pfad 12 berechnet wird. Je nachdem, ob die Maschine Maschinenteile aufweist, kann bevorzugt der Algorithmus auf veränderte Positionen und/oder Geschwindigkeiten wenigstens eines Maschinenteils reagieren.

In einem weiteren bevorzugten Ausführungsbeispiel wird das Verfahren vorab simuliert. Beispielsweise ist eine Vorabsimulation der Abläufe und Pfaderstellung an einem Computermodell möglich.

In einem weiteren Ausführungsbeispiel werden wenigstens zwei verschiedene Varianten des Verfahrens simuliert und in Bezug auf unterschiedliche Kriterien miteinander verglichen. Beispielsweise können so verschiedene Kriterien des Verfahrens in Bezug auf z.B. Energie, Verschleiß, Fahrweg und/oder Zykluszeit verglichen und das gewünschte günstige Verfahren ausgewählt werden. Beispielsweise ist bei bestimmten Prozessen die Zykluszeit zweitrangig, während es jedoch stark auf den Verschleiß ankommt bzw. darauf geachtet werden muss, da z.B. das Werkzeug stark beansprucht wird.

Zur besseren Übersichtlichkeit wird in einem weiteren Ausführungsbeispiel der Graph und/oder das Modell der wenigstens einen bewegbaren Komponente und/oder der Maschine 100 grafisch dargestellt. Je nachdem, ob die Maschine Maschinenteile aufweist, kann bevorzugt auch das Maschinenteil grafisch dargestellt werden. Beispielsweise kann die Darstellung auf einer Maschinensteuerung, einem Bildschirm oder einem Computer erfolgen.

In einem Ausführungsbeispiel ist eine Maschinensteuerung für eine Maschine 100, insbesondere für eine Spritzgießmaschine zur Verarbeitung von Kunststoffen und anderer plastifizierbarer Massen oder einer 3D-Druckmaschine offenbart, welche eingerichtet, ausgeführt und/oder konstruiert ist, um wenigstens eines der vorher beschriebenen Verfahren unter Erreichung der genannten Vorteile auszuführen.

Ein weiteres Ausführungsbeispiel bildet ein Computerprogrammprodukt mit einem Programmcode, der auf einem Computer lesbaren Medium gespeichert ist, zur Durchführung wenigstens eines der zuvor beschriebenen Verfahren unter Erreichung der genannten Vorteile.

Es versteht sich von selbst, dass diese Beschreibung verschiedensten Modifikationen, Änderungen und Anpassungen unterworfen werden kann, die sich im Bereich von Äquivalenten zu den anhängenden Ansprüchen bewegen. Bezugszeichenliste

10 Graph 100 Maschine

12 Pfad 102 Tauchachse

14 Startpunkt 104 Richtung

16 Zielpunkt 106 Richtung

18 Würfel, Knoten 108 Richtung

20 Binärheap 110 bewegliche Platte

22 besuchter Knoten 112 stationäre Platte

24 Hindernis 114 Werkzeughälfte

26 Pfeil 116 Werkzeughälfte

28 Array 118 Hindernis

30 Start 120 Fahrbereich

32 Schritt 122 Formteil

34 Schritt 130 Bahnbewegung

36 Schleife 132 Achse

38 Schleife 134 Achse

39 Schleife R Raum

40 Schritt

42 Schritt

44 Ende

46 Schritt

48 Schritt

50 Schleife

52 Schleife

54 Schritt

56 Schritt

58 Schritt

60 Schritt

62 Schritt

64 Sprungpunkt

66 Element

68 Index

70 Binärbaum