Malte Helmert

Über die Komplexität von Transportdomänen

Das Zeitverhalten von Planungssystemen wird in der Regel anhand empirischer Ergebnisse beurteilt. Bestimmten Domänen, etwa den aus den Wettbewerben der AIPS 98 und AIPS 2000 bekannten, wird dabei eine besondere Aufmerksamkeit beigemessen. Bislang erschöpfen sich die Untersuchungen im Wesentlichen in Vergleichen von Planungssystemen untereinander. Interessant wäre es jedoch auch, diese Ergebnisse in Relation zum theoretischen Optimum setzen zu können. Dies setzt eine komplexitätstheoretische Betrachtung des Planens in den interessierenden Domänen voraus.

Als erster Schritt in dieser Richtung wird in diesem Vortrag die Komplexität von Transportdomänen beleuchtet. Es wird eine natürliche Hierarchie von Transportdomänen eingeführt und zu den sechs Transportdomänen aus den AIPS-Wettbewerben in Beziehung gesetzt. Weiterhin wird für diese Domänen die Komplexität der relevanten Entscheidungs- und Optimierungsprobleme besprochen. Dabei soll insbesondere deutlich werden, dass die Forderung nach optimalen (kürzestmöglichen) Plänen die Komplexität deutlich erhöht.