Das Traveling Salesperson Problem (TSP) ist ein NP-vollständiges Problem. Trotzdem können Menschen derartige Probleme erstaunlich gut lösen. Deshalb untersuchen wir einerseits menschliche Lösungsstrategien, andererseits versuchen wir Modelle und Algorithmen zu finden, die diese Lösungsstrategien nachbilden.

In vorangegangenen Abschlussarbeiten wurde das Foveating Pyramid Model zum Lösen von TSPs untersucht. Dieses Modell ist die beste bekannte Vorhersage für menschliche Lösungsstrategien, ist allerdings vollständig auf eine graphische Repräsentation des Problems ausgelegt. Reale Probleme wie das Planen einer Urlaubstour beinhalten zwar eine graphische Repräsentation, aber darüber hinaus noch weitere Aspekte wie landschaftliche Schönheit, die Art der Fortbewegung oder die Bekanntheit von Sehenswürdigkeiten. Ein vorhandener heuristischer Ansatz kombiniert verschiedene Wissensaspekte und kann die Brücke schlagen zwischen der rein graphischen Herangehensweise des Foveating Pyramid Models und der vorhandenen heuristischen Lösung, die keine graphischen Informationen enthält.

Die Aufgabe besteht darin, den Foveating Pyramid Algorithmus in eine Menge von Heuristiken umzuschreiben und mit dem heuristischen Lösungsansatz zu verbinden.

Ein vorhandener Ansatz zur "menschenähnlichen" Lösung von TSPs soll erweitert werden: Einerseits um eine Backtracking-Funktionalität, die es erlaubt zu bestimmten Entscheidungspunkten zurückzukehren oder beim Wiederholten Lösen desselben Problems an diesem Punkt eine andere Entscheidung zu treffen. Andererseits spezifische Heuristiken zur Wahl des Startpunktes und der "Laufrichtung" der Lösung.

TSP Instanzen sind für Menschen unterschiedlich schwierig und verschiedene Situationen beim Finden der Lösung erfordern verschiedene Lösungsstrategien. In dem Spiel Perlentaucher werden verschiedene Hilfsmittel für das Lösen von TSPs angeboten. Bei diesem Projekt sollen die Daten aus Perlentaucher dahingehend untersucht werden, bei welchen Aufgaben und in welchen Situationen die Hilfsmittel eingesetzt wurden. Damit sollen beispielsweise folgende Fragen beantwortet werden: Wird die Lösung durch die Hilfsmittel tatsächlich besser? Welche sonstigen Gründe könnten Spieler dazu bewegen ein Hilfsmittel zu verwenden? Aus welchen Gründen verwenden Spieler die Hilfsmittel nicht?

Anhand eines bestehenden heuristischen Ansatzes zum Lösen von TSPs sollen Voting-Verfahren aus der Literatur recherchiert, implementiert und verglichen werden. In dem vorhandenen Ansatz stimmen mehrere Heuristiken über die nächste Aktion an. Dabei spielt die Gewichtung und Art der Kombination der einzelnen Stimmen eine Rolle. Kognitiv plausibler wären einfachere Methoden wie Umsortierung oder Verwerfen von Alternativen. Hier besteht die Herausforderung in der Kombination der einzelnen Stimmen und der Integration mit klassischem Abstimmen.