Perceived optimality of competing solutions to the Euclidean travelling salesperson problem

Markos Kyritsis*, Stephen R. Gulliver, Eva Feredoes, Vasilios Stouraitis

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

The Travelling Salesperson Problem (TSP) is a nondeterministic-polynomial hard (NP-hard) combinatorial problem that occurs in a wide range of industrial domains, including logistics, route finding, and computer wiring. Interestingly, despite the problem’s inherent computational difficulty, when presented in Euclidean space (ETSP), human participants can produce close-to-optimal solutions in near-linear time. However, when asked to compare and select the most optimum solution from a set of pre-defined competing solution options, participants can struggle. In this study we investigate this paradox by asking participants to compare four closed-loop Euclidean TSP solutions, in order to determine which solution they perceived to have the most optimal tour cost. We hypothesise that the extracted geometric properties have an effect on stimulus selection in a discrimination task (selection or no selection). Accordingly, we extracted four geometric properties from competing stimuli in order to create a perceptual activation function. Predictive analytics demonstrated that a classification model could identify the most optimal solution 97% of the time using the perceptual activation scores alone, yet human participants only correctly determined the most optimal solution 47% of the time. Mixed-effects models suggest that ‘likelihood of stimulus selection’ can be modelled as a function of the weighted coefficients of competing perceptual activation scores within each trial; however only a small amount of the variance is explained by these perceptual activation scores. Finally, a drift-diffusion model was used to create a theoretical framework of how likelihood of stimulus selection is influenced by competing perceptual activators. Our study highlights a novel way of extracting and analysing the importance of geometric properties that influence ETSP discrimination tasks, and links this analysis to human behaviour when discriminating between competing ETSP solutions.
Original languageEnglish
Pages (from-to)1-17
Number of pages17
JournalCognitive Systems Research
Volume74
Early online date26 Feb 2022
DOIs
Publication statusPublished - Aug 2022

Keywords

  • Travelling Salesperson Problem, choice discrimination task, Monte Carlo methods, perceptual activation, geometric properties
  • Choice discrimination task
  • Geometric properties
  • Monte Carlo methods
  • Travelling salesperson problem
  • Perceptual activation

ASJC Scopus subject areas

  • Experimental and Cognitive Psychology
  • Artificial Intelligence
  • Cognitive Neuroscience

Fingerprint

Dive into the research topics of 'Perceived optimality of competing solutions to the Euclidean travelling salesperson problem'. Together they form a unique fingerprint.

Cite this