PathGame: Crowdsourcing Time-Constrained Human Solutions for the Travelling Salesperson Problem

Area of Science:

• Cognitive Science
• Computer Science
• Human-Computer Interaction

Background:

• Human decision-making in complex problem-solving, like the Traveling Salesperson Problem (TSP), is of significant research interest.
• Automated solvers can benefit from understanding human strategies for TSP.
• Online games offer an efficient method for collecting large datasets of human solutions to TSP.

Purpose of the Study:

• To investigate human strategies for solving non-Euclidean, closed-form TSP using an online game.
• To collect a substantial dataset of human-generated TSP tours.
• To analyze instinctive decision-making processes under time constraints.

Main Methods:

• Development and deployment of the PathGame online platform.
• Collection of over 16,000 human-generated tours for TSP instances.
• Analysis of a dataset comprising over 22,000,000 destinations.

Main Results:

• Identification of novel insights into human approaches to solving TSP.
• Understanding the time dynamics of human TSP solvers facing high complexity.
• Characterization of decision-making patterns in a speed-focused TSP game.

Conclusions:

• PathGame effectively captures human decision-making for TSP.
• The collected data provides a valuable resource for TSP research.
• Insights gained can inform the development of more efficient automated TSP solvers.