Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung
Letzte Überarbeitung Beide Seiten der Revision
lehre:ss19:projektgruppe-computational-geometry [2019/04/05 14:59]
langetepe [Inhalt]
lehre:ss19:projektgruppe-computational-geometry [2019/04/05 15:04]
langetepe [Vorgestellte Themen im SS19]
Zeile 39: Zeile 39:
    
 4. Multiple Robot Routing mit Nebenbedingungen\\ 4. Multiple Robot Routing mit Nebenbedingungen\\
-  * Eine effiziente Bewegung modularer Angenten auf engstem Raum ist eine wichtige Aufgabe. In einer Gitterwelt sollen einzelne aus Gitterzellen bestehende Agenten von einer Startkonfiguration zu einer Endkonfiguration effizient kollisionsfrei bewegt werden. Dazu soll eine interaktive Applikation programmiert werden. Ausgangspunkt ist dabei eine Arbeit, bei der die Aufgabe für ein komplett gefülltes Grid mit einzelnen Agenten algorithmisch quasi optimal gelöst wird. Dieser Algorithmus besteht aus kleinen Bewegungsblöcken und soll zunächst in 2D umgesetzt und animiert dargestellt werden und dann ggf. mit Nebenbedingungen (z.B. Ruheplätze oder ausgedehnte Agenten) erweitert werden. Ein effiziemter ​2D-Algorithmus wird in folgender Arbeit beschrieben:​ https://​arxiv.org/​abs/​1801.10465+  * Eine effiziente Bewegung modularer Angenten auf engstem Raum ist eine wichtige Aufgabe. In einer Gitterwelt sollen einzelne aus Gitterzellen bestehende Agenten von einer Startkonfiguration zu einer Endkonfiguration effizient kollisionsfrei bewegt werden. Dazu soll eine interaktive Applikation programmiert werden. Ausgangspunkt ist dabei eine Arbeit, bei der die Aufgabe für ein komplett gefülltes Grid mit einzelnen Agenten algorithmisch quasi optimal gelöst wird. Dieser Algorithmus besteht aus kleinen Bewegungsblöcken und soll zunächst in 2D umgesetzt und animiert dargestellt werden und dann ggf. mit Nebenbedingungen (z.B. Ruheplätze oder ausgedehnte Agenten) erweitert werden. Ein effizienter ​2D-Algorithmus wird in folgender Arbeit beschrieben:​ https://​arxiv.org/​abs/​1801.10465
 5. Terrain Guarding in Dimension 1.5 (oder 2.5)\\ 5. Terrain Guarding in Dimension 1.5 (oder 2.5)\\
   * Die Platzierung von Wächtern zur Beobachtung eines Gebietes kommt in vielen Anwendungen vor. Gegeben ​ ist hier ein 1.5 dimensionales Terrain als Polygonzug und es soll eine minimale Anzahl an Agenten gefunden werden, die das ganze Gebiet //sehen//. Dieses Problem ist NP-schwer im allgemeinen,​ es gibt aber Algorithmen mit guten Laufzeiten für Spezialfälle und zur Approximation der Anzahl der minimal notwendigen Agenten. Hierfür soll eine interaktive Applikation programmiert werden, bei der das Terrain editiert werden kann und verschiedene Algorithmen animiert dargestellt werden. Als Ausgangspunkt und Anhalt dienen die u.a. Arbeiten. Bei erweitertem Interesse kann auch das //​Hochschießen//​ eines Satellitens in einem 2.5 dimensionalen Terrain betrachtet werden. Dabei soll ein Online-Algorithmus zur Kernsuche erweitert werden. Literatur dazu wird dann bei Interesse angefügt.  ​   * Die Platzierung von Wächtern zur Beobachtung eines Gebietes kommt in vielen Anwendungen vor. Gegeben ​ ist hier ein 1.5 dimensionales Terrain als Polygonzug und es soll eine minimale Anzahl an Agenten gefunden werden, die das ganze Gebiet //sehen//. Dieses Problem ist NP-schwer im allgemeinen,​ es gibt aber Algorithmen mit guten Laufzeiten für Spezialfälle und zur Approximation der Anzahl der minimal notwendigen Agenten. Hierfür soll eine interaktive Applikation programmiert werden, bei der das Terrain editiert werden kann und verschiedene Algorithmen animiert dargestellt werden. Als Ausgangspunkt und Anhalt dienen die u.a. Arbeiten. Bei erweitertem Interesse kann auch das //​Hochschießen//​ eines Satellitens in einem 2.5 dimensionalen Terrain betrachtet werden. Dabei soll ein Online-Algorithmus zur Kernsuche erweitert werden. Literatur dazu wird dann bei Interesse angefügt.  ​
lehre/ss19/projektgruppe-computational-geometry.txt · Zuletzt geändert: 2019/04/05 22:33 von hjhaverkort

Benutzer-Werkzeuge