Aufgabe 16.2.2: Roboterweg
In einer rechteckigen Montagehalle ist Roy Blackbox, der Roboter, beschäftigt.
Roy muß immer wieder Gegenstände von seinem derzeitigen Standort
zu einem anderen Ort in der Halle transportieren. Dabei muß er die
Objekte, die in der Halle stehen, umfahren.
Roy stellt sich den Hallenplan wie ein quadratisches Raster mit Punktabstand
1 m vor (siehe Skizze). Roy selbst hat einen Durchmesser von 1,5 m und
bewegt sich auf den Koordinaten des Rasters. Eine Bewegung von Roy, auch
als Schritt bezeichnet, besteht dar in, daß er sich von einem Rasterpunkt
zum nächsten Rasterpunkt in Richtung Norden, Süden, Osten oder
Westen begibt.
Pro Transport stehen Roy höchstens n Schritte zur Verfügung.
Außerdem kennt Roy zu jedem Zeitpunkt nur
-
die Koordinaten seines jeweiligen Standortes,
-
die Koordinaten des Zielortes,
-
die maximale Zahl n von Schritten, die er vom Start zum Zielort
benötigen darf,
-
die Anzahl der während des aktuellen Transports bereits ausgeführten
Schritte,
-
die Hallengröße, gegeben durch die Koordinaten der Süd-West-
und der Nord-Ost-Ecke und
-
einen Ausschnitt des Hallenplans, der alle Rasterpunkte enthält, die
für Roy ohne Hindernisse maximal 10 Schritte entfernt wären (siehe
Skizze).
Aufgabe:
-
Entwerfen Sie eine Strategie, die Roy in möglichst vielen Fällen
zum Ziel bringt.
-
Erläutern Sie, in welchen Situationen Ihre Strategie Roy nicht zum
Ziel führt.
-
Implementieren Sie Ihre Strategie und senden Sie uns mindestens fünf
Protokolle von Transportversuchen in verschiedenen Hallen, darunter folgendes:
Roy soll in der abgedruckten Beispielhalle vom Startpunkt S zum Zielpunkt
Z fahren und darf dazu höchstens 200 Schritte benötigen.
Beachten Sie, daß Roy jeweils nur den aktuellen Hallenausschnitt
kennt und sich weder bereits gesehene Ausschnitte noch die Richtung, aus
der er gekommen ist, merken kann.
Hinweis:
Wie bereits erwähnt muß Roy die Hindernisse umfahren. Dabei
kann er aber davon ausgehen, daß die Hindernisse nicht über
den ihm frei erscheinenden Hallenboden hinausragen. Mit anderen Worten:
Wenn er an einem Hindernis vorbeifährt, kann er sich nicht unvermittelt
den Kopf (oder das Roboteräquivalent eines solchen) stoßen.
Außerdem ist die Halle so aufgeräumt, daß sich die
Ränder aller Hindernisse genau auf Rasterpunkten befinden.
Skizze und
Beispiel zu Aufgabe 16.2.2: Roboterweg
Weiter (Aufgabe 3: Übersetzungen)
Zurück (Aufgabe 1: Netz des Vertrauens)
Übersicht 2. Runde
BWINF Homepage