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

Aufgabe:
  1. Entwerfen Sie eine Strategie, die Roy in möglichst vielen Fällen zum Ziel bringt.
  2. Erläutern Sie, in welchen Situationen Ihre Strategie Roy nicht zum Ziel führt.
  3. 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