Bewegung einer Strecke bei punktförmigen Hindernissen
Das Rush Hour Puzzle verallgemeinert
Das Finden des Ufers bei unbekannter Orientierung
Hinweise: Mathematische Idealisierung, Euklidische Ebene, Optimale Lösung,
Worst-Case Komplexität
Methoden:
(Teil-)Diskretisierung des Problems auf kleine Mengen von Positionen
Spiegelung des Ziels
Das Feuerwehrproblem
Bewegungsplanung mit Hindernissen
Idee:
Virtuelle Hindernisse werden durch die Minkowsi-Summe der Hindernisse mit dem negativen bewegten Objekt gebildet, die Anzahl der Ecken ist polynomiell.
Der kürzeste Weg zum Ziel knickt nur an Ecken von (virtuellen) Hindernissen ab und verläuft ansonsten gerade (Gummibandargument).
Fazit:
Der kürzesete Weg eines nicht drehbaren Objekts (Polygon) in einer Ebene mit Hindernissenen
(ebenfalls Polygone) ist effizient (d.h. in polynomieller Zeit) berechenbar.
Einfachster Fall eines drehbaren Objekts: Strecke der Länge l mit Drehpunkt an einem Ende.
Idee: Wir betrachten die folgende 3 Arten von Positionen für die Strecke, an der die Bewegung des Drehpunktes abknicken kann:
1. Schnittpunkte zweier Kreise mit Radius l um zwei Hindernispunkte.
2. Positionen bei denen sich das andere Ende der Strecke an einem Hindernispunkt befindet und ein weiterer Hindernispunkt die Strecke berührt (zwei Möglichkeiten welche Seite).
3. Positionen direkt bei einem Hindernispunkt, dabei sind maximal eine lineare Anzahl von Schwenkbereichen zu unterscheiden.
Es gibt O(n2) solche Konfigurationen.
[Hald 2014]: Der direkte Übergang für zwei solche Konfigurationen kann in polynomieller Zeit geprüft werden
Gleiches gilt für Übergänge mit einer Reflexion am Kreisbogen:
Fazit:
Der kürzesete Weg einer um einen Endpunkt drehbaren Strecke in der Ebene mit Punkt-Hindernissenen ist effizient berechenbar.
[Asano, Kirkpartik, Yap 2003]: NP-vollständig für Polygone als Hindernisse.
Problem offen für um einen inneren Punkt drehbare Strecke in der Ebene mit Punkt-Hindernissenen
Das Rushhour Puzzle:
Mathematische Idealisierung, Euklidische Ebene, Optimale Lösung,
Worst-Case Komplexität
Methoden:
(Teil-)Diskretisierung des Problems auf kleine Mengen von Positionen
Spiegelung des Ziels
Das Feuerwehrproblem
Bewegungsplanung mit Hindernissen
Idee:
Virtuelle Hindernisse werden durch die Minkowsi-Summe der Hindernisse mit dem negativen bewegten Objekt gebildet, die Anzahl der Ecken ist polynomiell.
Der kürzeste Weg zum Ziel knickt nur an Ecken von (virtuellen) Hindernissen ab und verläuft ansonsten gerade (Gummibandargument).
Fazit:
Der kürzesete Weg eines nicht drehbaren Objekts (Polygon) in einer Ebene mit Hindernissenen
(ebenfalls Polygone) ist effizient (d.h. in polynomieller Zeit) berechenbar.
Einfachster Fall eines drehbaren Objekts: Strecke der Länge l mit Drehpunkt an einem Ende.
Idee: Wir betrachten die folgende 3 Arten von Positionen für die Strecke, an der die Bewegung des Drehpunktes abknicken kann:
1. Schnittpunkte zweier Kreise mit Radius l um zwei Hindernispunkte.
2. Positionen bei denen sich das andere Ende der Strecke an einem Hindernispunkt befindet und ein weiterer Hindernispunkt die Strecke berührt (zwei Möglichkeiten welche Seite).
3. Positionen direkt bei einem Hindernispunkt, dabei sind maximal eine lineare Anzahl von Schwenkbereichen zu unterscheiden.
Es gibt O(n2) solche Konfigurationen.
[Hald 2014]: Der direkte Übergang für zwei solche Konfigurationen kann in polynomieller Zeit geprüft werden
Gleiches gilt für Übergänge mit einer Reflexion am Kreisbogen:
Fazit:
Der kürzesete Weg einer um einen Endpunkt drehbaren Strecke in der Ebene mit Punkt-Hindernissenen ist effizient berechenbar.
[Asano, Kirkpartik, Yap 2003]: NP-vollständig für Polygone als Hindernisse.
Problem offen für um einen inneren Punkt drehbare Strecke in der Ebene mit Punkt-Hindernissenen
Das Rushhour Puzzle:
(Teil-)Diskretisierung des Problems auf kleine Mengen von Positionen
Spiegelung des Ziels
Das Feuerwehrproblem
Bewegungsplanung mit Hindernissen
Idee:
Virtuelle Hindernisse werden durch die Minkowsi-Summe der Hindernisse mit dem negativen bewegten Objekt gebildet, die Anzahl der Ecken ist polynomiell.
Der kürzeste Weg zum Ziel knickt nur an Ecken von (virtuellen) Hindernissen ab und verläuft ansonsten gerade (Gummibandargument).
Fazit:
Der kürzesete Weg eines nicht drehbaren Objekts (Polygon) in einer Ebene mit Hindernissenen
(ebenfalls Polygone) ist effizient (d.h. in polynomieller Zeit) berechenbar.
Einfachster Fall eines drehbaren Objekts: Strecke der Länge l mit Drehpunkt an einem Ende.
Idee: Wir betrachten die folgende 3 Arten von Positionen für die Strecke, an der die Bewegung des Drehpunktes abknicken kann:
1. Schnittpunkte zweier Kreise mit Radius l um zwei Hindernispunkte.
2. Positionen bei denen sich das andere Ende der Strecke an einem Hindernispunkt befindet und ein weiterer Hindernispunkt die Strecke berührt (zwei Möglichkeiten welche Seite).
3. Positionen direkt bei einem Hindernispunkt, dabei sind maximal eine lineare Anzahl von Schwenkbereichen zu unterscheiden.
Es gibt O(n2) solche Konfigurationen.
[Hald 2014]: Der direkte Übergang für zwei solche Konfigurationen kann in polynomieller Zeit geprüft werden
Gleiches gilt für Übergänge mit einer Reflexion am Kreisbogen:
Fazit:
Der kürzesete Weg einer um einen Endpunkt drehbaren Strecke in der Ebene mit Punkt-Hindernissenen ist effizient berechenbar.
[Asano, Kirkpartik, Yap 2003]: NP-vollständig für Polygone als Hindernisse.
Problem offen für um einen inneren Punkt drehbare Strecke in der Ebene mit Punkt-Hindernissenen
Das Rushhour Puzzle:
Der kürzeste Weg zum Ziel knickt nur an Ecken von (virtuellen) Hindernissen ab und verläuft ansonsten gerade (Gummibandargument).
Fazit: Der kürzesete Weg eines nicht drehbaren Objekts (Polygon) in einer Ebene mit Hindernissenen (ebenfalls Polygone) ist effizient (d.h. in polynomieller Zeit) berechenbar.
Einfachster Fall eines drehbaren Objekts: Strecke der Länge l mit Drehpunkt an einem Ende.
1. Schnittpunkte zweier Kreise mit Radius l um zwei Hindernispunkte.
2. Positionen bei denen sich das andere Ende der Strecke an einem Hindernispunkt befindet und ein weiterer Hindernispunkt die Strecke berührt (zwei Möglichkeiten welche Seite).
3. Positionen direkt bei einem Hindernispunkt, dabei sind maximal eine lineare Anzahl von Schwenkbereichen zu unterscheiden.
Es gibt O(n2) solche Konfigurationen.
[Hald 2014]: Der direkte Übergang für zwei solche Konfigurationen kann in polynomieller Zeit geprüft werden
Gleiches gilt für Übergänge mit einer Reflexion am Kreisbogen:
Fazit: Der kürzesete Weg einer um einen Endpunkt drehbaren Strecke in der Ebene mit Punkt-Hindernissenen ist effizient berechenbar.
