Multi-Area Coverage Path Planning

Die Aufgabe, einen Überdeckungspfad für einen Robotermanipulator zu berechnen, um eine gegebene Oberfläche zu bearbeiten, wird üblicherweise Coverage Path Planning Problem (CPP) genannt. Die Lösung für dieses Problem ist ein Pfad, so dass jeder Punkt auf der Oberfläche vom Footprint eines Werkzeugs abgedeckt wird. Optimierungsziele für CPP in der Robotik sind vor allem die Länge des Werkzeugweges, die Fertigstellungszeit sowie die Länge des Weges im Gelenkraum des Roboters.
Die Komplexität des CPP Problems steigt extrem, wenn die zu überdeckenden Bereiche nicht miteinander verbunden sind. Zum Beispiel beim Lackieren einer Oberfläche, ist es üblich, dass größere Objekte von mehreren Seiten gesprüht werden müssen, während andere Teile der Oberfläche gar nicht bearbeitet werden. Aus algorithmischer Sicht ist das Ziel jedoch nicht die Bearbeitungszeit für jeden einzelnen Bereich, sondern für die gesamte Fläche zu minimieren. Außerdem enthalten viele Anwendungen eine Menge (oft implizit definierter) Freiheitsgrade (z. B. mehrere Lösungen der inversen Kinematik, Symmetrien des Werkzeugs etc.). Diese Freiheitsgrade bieten ein enormes Optimierungspotenzial, machen aber das Finden von optimalen Lösungen noch schwieriger.
 
Im Gegensatz zum klassischen CPP wurde die Multi-Area CPP Problem mit einem Robotermanipulator nicht genügend untersucht. Die meisten verwandten Ansätze konzentrieren sich entweder auf die Abdeckung von Pfaden für die gegebenen Gebiete oder auf das Verbinden von Pfaden zwischen ihnen. Darüber hinaus berücksichtigen die meisten State-of-the-Art-Ansätze keine Wiederverwendung von existierenden Teillösungen oder nutzen die vorhandenen Freiheitsgrade, welche großes Optimierungspotential enthalten, nicht aus.
 
Ziel dieses Vorhabens ist es, effiziente Algorithmen zur automatischen und optimierten Lösung eines Multi-Area CPP Problems zu entwickeln. Das Kernidee ist es, zwei Ansätze zu kombinieren: (1) eine Anpassung von Techniken für optimale Abarbeitung von Aufgabensequenzen (wobei die Freiheit der Ausführungsreihenfolge ausgenutzt werden kann) auf das Multi-Area CPP Problem sowie (2) Verwenden von zuvor berechneten Teillösungen für dieses Problem. Solche Kombination würde zur zeiteffizienten Pfadberechnung führen sowie eine optimierte Neu- bzw. Umplanung ermöglichen.