Human performance on visually presented Traveling Salesman problems

Vaximap: route optimisation for housebound vaccination

During the United Kingdom's Covid-19 vaccination campaign, general practitioners (GPs) have held responsibility for vaccinating housebound patients. This presented them with a large, complex and unfamiliar logistical challenge, namely determining the most time-efficient route to visit multiple patients at their home address. In response to a lack of existing solutions tailored specifically to vaccination, and in light of overwhelming demand, Vaximap ( https://www.vaximap.org ) was created in January 2021 to automate the process of route planning. It is free of charge for all users and has been used to-date to plan vaccinations for over 470,000 patients. This article analyses usage data to estimate the time savings (3 work years) and financial savings (£110,000) the service has yielded for GP surgeries, thus demonstrating that it helped to accelerate the UK's Covid-19 vaccination campaign at critical moments.

Contribution of the hippocampus to performance on the traveling salesperson problem in rats

The Traveling Salesman Problem (TSP) is an optimization problem in which the subject attempts to find the shortest possible route that passes through a set of fixed locations exactly once. The TSP is used in cognitive and behavioral research to study problem solving and spatial navigation. While the TSP has been studied in some depth from this perspective, the biological mechanisms underlying the behavior have not yet been explored. The hippocampus is a structure in the brain that is known to be involved in tasks that require spatial memory. Because the TSP requires spatial problem solving, we designed the current study to determine whether the hippocampus is required to find efficient solutions to the TSP, and if so, what role the hippocampus serves. Rats were pretrained on the TSP, which involved learning to retrieve bait from targets in a variety of spatial configurations. Matched for performance, rats were then divided into two groups, receiving either a hippocampal lesion or a control sham surgery. After recovering from surgery, the rats were tested on eight new configurations. A variety of behavioral measures were recorded, including distance travelled, number of revisits, memory span, and latency. The results showed that the sham group outperformed the lesion group on most of these measures. Based on the behavioral data and histological tissue analysis of each group, we determined that the hippocampus is involved in successful performance in the TSP, particularly regarding memory for which targets have already been visited.

Decision-making in sensorimotor control

Skilled sensorimotor interactions with the world result from a series of decision-making processes that determine, on the basis of information extracted during the unfolding sequence of events, which movements to make and when and how to make them. Despite this inherent link between decision-making and sensorimotor control, research into each of these two areas has largely evolved in isolation, and it is only fairly recently that researchers have begun investigating how they interact and, together, influence behaviour. Here, we review recent behavioural, neurophysiological and computational research that highlights the role of decision-making processes in the selection, planning and control of goal-directed movements in humans and nonhuman primates.

GUIRO: User-Guided Matrix Reordering

Matrix representations are one of the main established and empirically proven to be effective visualization techniques for relational (or network) data. However, matrices-similar to node-link diagrams-are most effective if their layout reveals the underlying data topology. Given the many developed algorithms, a practical problem arises: "Which matrix reordering algorithm should I choose for my dataset at hand?" To make matters worse, different reordering algorithms applied to the same dataset may let significantly different visual matrix patterns emerge. This leads to the question of trustworthiness and explainability of these fully automated, often heuristic, black-box processes. We present GUIRO, a Visual Analytics system that helps novices, network analysts, and algorithm designers to open the black-box. Users can investigate the usefulness and expressiveness of 70 accessible matrix reordering algorithms. For network analysts, we introduce a novel model space representation and two interaction techniques for a user-guided reordering of rows or columns, and especially groups thereof (submatrix reordering). These novel techniques contribute to the understanding of the global and local dataset topology. We support algorithm designers by giving them access to 16 reordering quality metrics and visual exploration means for comparing reordering implementations on a row/column permutation level. We evaluated GUIRO in a guided explorative user study with 12 subjects, a case study demonstrating its usefulness in a real-world scenario, and through an expert study gathering feedback on our design decisions. We found that our proposed methods help even inexperienced users to understand matrix patterns and allow a user-guided steering of reordering algorithms. GUIRO helps to increase the transparency of matrix reordering algorithms, thus helping a broad range of users to get a better insight into the complex reordering process, in turn supporting data and reordering algorithm insights.

Sense of direction and conscientiousness as predictors of performance in the Euclidean travelling salesman problem

A salesperson wishes to visit a number of cities before returning home using the shortest possible route, whilst only visiting each city once. This optimization problem, called the Travelling Salesman Problem, is difficult to solve using exhaustive algorithms due to the exponential growth in the number of possible solutions. Interestingly, when presented in Euclidean space (ETSP), humans quickly find good solutions. Past studies, however, are in disagreement whether human solutions are impacted by the participant’s ability to process figural effects in the graph geometry. In this study, we used principal component analysis to combine two correlated [r = 0.37, p < 0.01] self-assessed personality measures, i.e., a participant’s sense of direction and a participant’s level of conscientiousness, onto a single impulsiveness/cautiousness dimension. We then showed, using simple linear regression, that this new dimension is a significant predictor [R² = 0.12, p < 0.01] of the number of edge crossings that occur in human ETSP solutions, a key metric of graph optimality. Our study provides evidence to suggest that human solutions to the ETSP are significantly affected by individual differences, including personality and cognitive traits.

Rapid target foraging with reach or gaze: The hand looks further ahead than the eye

Real-world tasks typically consist of a series of target-directed actions and often require choices about which targets to act on and in what order. Such choice behavior can be assessed from an optimal foraging perspective whereby target selection is shaped by a balance between rewards and costs. Here we evaluated such decision-making in a rapid movement foraging task. On a given trial, participants were presented with 15 targets of varying size and value and were instructed to harvest as much reward as possible by either moving a handle to the targets (hand task) or by briefly fixating them (eye task). The short trial duration enabled participants to harvest about half the targets, ensuring that total reward was due to choice behavior. We developed a probabilistic model to predict target-by-target harvesting choices that considered the rewards and movement-related costs (i.e., target distance and size) associated with the current target as well as future targets. In the hand task, in comparison to the eye task, target choice was more strongly influenced by movement-related costs and took into account a greater number of future targets, consistent with the greater costs associated with arm movement. In both tasks, participants exhibited near-optimal behaviour and in a constrained version of the hand task in which choices could only be based on target positions, participants consistently chose among the shortest movement paths. Our results demonstrate that people can rapidly and effectively integrate values and movement-related costs associated with current and future targets when sequentially harvesting targets.

Many natural tasks involve a series of decisions about which target to acquire next, either with our gaze or hand. We examined the factors influencing such decisions using a task in which targets of varying value and size are sequentially acquired by eye or hand movements. By developing a probabilistic model of decision-making behavior we show that eye movement decisions are made in isolation, independent of potential future targets, and are primarily determined by target value. In contrast, hand movement decisions consider multiple future targets and are strongly shaped by movement-related costs. By examining decision-making in sequential actions, our results and model represent a significant advance over previous work that has focused primarily on decisions about single actions.

Effects of cluster location and cluster distribution on performance on the traveling salesman problem

Research on human performance in solving traveling salesman problems typically uses point sets as stimuli, and most models have proposed a processing stage at which stimulus dots are clustered. However, few empirical studies have investigated the effects of clustering on performance. In one recent study, researchers compared the effects of clustered, random, and regular stimuli, and concluded that clustering facilitates performance (Dry, Preiss, & Wagemans, 2012). Another study suggested that these results may have been influenced by the location rather than the degree of clustering (MacGregor, 2013). Two experiments are reported that mark an attempt to disentangle these factors. The first experiment tested several combinations of degree of clustering and cluster location, and revealed mixed evidence that clustering influences performance. In a second experiment, both factors were varied independently, showing that they interact. The results are discussed in terms of the importance of clustering effects, in particular, and perceptual factors, in general, during performance of the traveling salesman problem.

Performance of young children on ''traveling salesperson'' navigation tasks presented on a touch screen

Background

The traveling salesperson problem (TSP) refers to a task in which one finds the shortest path when traveling through multiple spatially distributed points. Little is known about the developmental course of the strategies used to solve TSPs. The present study examined young children's performance and route selection strategies in one-way TSPs using a city-block metric. A touch screen-based navigation task was applied.

Methodology/Principal Findings

Children (39–70 months) and adults (21–35 years) made serial responses on a touch screen to move a picture of a dog (the target) to two or three identical pictures of a bone (the goals). For all the versions of the tasks, significant improvement in measures of performance was observed from younger to older participants. In TSPs in which a specific route selection strategy such as the nearest-neighbor strategy minimized the total traveling distance, older participants used that strategy more frequently than younger ones. By contrast, in TSPs in which multiple strategies equally led to the minimal traveling distance, children tended to use strategies different from those used by adults, such as traveling straight to the farthest goal first.

Conclusions/Significance

The results primarily suggest development of efficient route selection strategies that can optimize total numbers of movements and/or solution time. Unlike adults, children sometimes prioritized other strategies such as traveling straight ahead until being forced to change directions. This may reflect the fact that children were either less attentive to the task or less efficient at perceiving the overall shape of the problem and/or the relative distance from the starting location to each goal.

Dose-related effects of alcohol on cognitive functioning

We assessed the suitability of six applied tests of cognitive functioning to provide a single marker for dose-related alcohol intoxication. Numerous studies have demonstrated that alcohol has a deleterious effect on specific areas of cognitive processing but few have compared the effects of alcohol across a wide range of different cognitive processes. Adult participants (N = 56, 32 males, 24 females aged 18–45 years) were randomized to control or alcohol treatments within a mixed design experiment involving multiple-dosages at approximately one hour intervals (attained mean blood alcohol concentrations (BACs) of 0.00, 0.048, 0.082 and 0.10%), employing a battery of six psychometric tests; the Useful Field of View test (UFOV; processing speed together with directed attention); the Self-Ordered Pointing Task (SOPT; working memory); Inspection Time (IT; speed of processing independent from motor responding); the Traveling Salesperson Problem (TSP; strategic optimization); the Sustained Attention to Response Task (SART; vigilance, response inhibition and psychomotor function); and the Trail-Making Test (TMT; cognitive flexibility and psychomotor function). Results demonstrated that impairment is not uniform across different domains of cognitive processing and that both the size of the alcohol effect and the magnitude of effect change across different dose levels are quantitatively different for different cognitive processes. Only IT met the criteria for a marker for wide-spread application: reliable dose-related decline in a basic process as a function of rising BAC level and easy to use non-invasive task properties.

The wisdom of the crowd in combinatorial problems

The "wisdom of the crowd" phenomenon refers to the finding that the aggregate of a set of proposed solutions from a group of individuals performs better than the majority of individual solutions. Most often, wisdom of the crowd effects have been investigated for problems that require single numerical estimates. We investigate whether the effect can also be observed for problems where the answer requires the coordination of multiple pieces of information. We focus on combinatorial problems such as the planar Euclidean traveling salesperson problem, minimum spanning tree problem, and a spanning tree memory task. We develop aggregation methods that combine common solution fragments into a global solution and demonstrate that these aggregate solutions outperform the majority of individual solutions. These case studies suggest that the wisdom of the crowd phenomenon might be broadly applicable to problem-solving and decision-making situations that go beyond the estimation of single numbers.

It looks easy! Heuristics for combinatorial optimization problems

Human performance on instances of computationally intractable optimization problems, such as the travelling salesperson problem (TSP), can be excellent. We have proposed a boundary-following heuristic to account for this finding. We report three experiments with TSPs where the capacity to employ this heuristic was varied. In Experiment 1, participants free to use the heuristic produced solutions significantly closer to optimal than did those prevented from doing so. Experiments 2 and 3 together replicated this finding in larger problems and demonstrated that a potential confound had no effect. In all three experiments, performance was closely matched by a boundary-following model. The results implicate global rather than purely local processes. Humans may have access to simple, perceptually based, heuristics that are suited to some combinatorial optimization tasks.

The aesthetic appeal of minimal structures: Judging the attractiveness of solutions to traveling salesperson problems

Ormerod and Chronicle (1999) reported that optimal solutions to traveling salesperson problems were judged to be aesthetically more pleasing than poorer solutions and that solutions with more convex hull nodes were rated as better figures. To test these conclusions, solution regularity and the number of potential intersections were held constant, whereas solution optimality, the number of internal nodes, and the number of nearest neighbors in each solution were varied factorially. The results did not support the view that the convex hull is an important determinant of figural attractiveness. Also, in contrast to the findings of Ormerod and Chronicle, there were consistent individual differences. Participants appeared to be divided as to whether the most attractive figure enclosed a given area within a perimeter of minimum or maximum length. It is concluded that future research in this area cannot afford to focus exclusively on group performance measures.

Convex hull or crossing avoidance? Solution heuristics in the traveling salesperson problem

Untrained adults appear to have access to cognitive processes that allow them to perform well in the Euclidean version of the traveling salesperson problem (E-TSP). They do so despite the famous computational intractability of the problem, which stems from its combinatorial complexity. A current hypothesis is the humans' good performance is based on following a strategy of connecting boundary points in order (the convex hull hypothesis). Recently, an alternative has been proposed, that performance is governed by a strategy of avoiding crossings. We examined the crossing avoidance hypothesis from the perspectives of its capacity to explain existing data, its theoretical adequacy, and its ability to explain the results of three new experiments. In Experiment 1, effects on the solution quality of number of points versus number of interior points were compared. In Experiment 2, the distributions of observed paths were compared with those predicted from the two hypotheses. In Experiment 3, figural effects were varied to induce crossings. The results of the experiments were more consistent with the convex hull than with the crossing avoidance hypothesis. Despite its simplicity and intuitive appeal, crossing avoidance does not provide a complete alternative to the convex hull hypothesis. Further elucidation of human strategies and heuristics for optimization problems such as the E-TSP will aid our understanding of how cognitive processes have adapted to the demands of combinatorial difficulty.

The perception of minimal structures: performance on open and closed versions of visually presented Euclidean travelling salesperson problems

The planar Euclidean version of the travelling salesperson problem (TSP) requires finding a tour of minimal length through a two-dimensional set of nodes. Despite the computational intractability of the TSP, people can produce rapid, near-optimal solutions to visually presented versions of such problems. To explain this, MacGregor et al (1999, Perception 28 1417-1428) have suggested that people use a global-to-local process, based on a perceptual tendency to organise stimuli into convex figures. We review the evidence for this idea and propose an alternative, local-to-global hypothesis, based on the detection of least distances between the nodes in an array. We present the results of an experiment in which we examined the relationships between three objective measures and performance measures of optimality and response uncertainty in tasks requiring participants to construct a closed tour or an open path. The data are not well accounted for by a process based on the convex hull. In contrast, results are generally consistent with a locally focused process based initially on the detection of nearest-neighbour clusters. Individual differences are interpreted in terms of a hierarchical process of constructing solutions, and the findings are related to a more general analysis of the role of nearest neighbours in the perception of structure and motion.

The roles of the convex hull and the number of potential intersections in performance on visually presented traveling salesperson problems

The planar Euclidean version of the traveling salesperson problem requires finding the shortest tour through a two-dimensional array of points. MacGregor and Ormerod (1996) have suggested that people solve such problems by using a global-to-local perceptual organizing process based on the convex hull of the array. We review evidence for and against this idea, before considering an alternative, local-to-global perceptual process, based on the rapid automatic identification of nearest neighbors. We compare these approaches in an experiment in which the effects of number of convex hull points and number of potential intersections on solution performance are measured. Performance worsened with more points on the convex hull and with fewer potential intersections. A measure of response uncertainty was unaffected by the number of convex hull points but increased with fewer potential intersections. We discuss a possible interpretation of these results in terms of a hierarchical solution process based on linking nearest neighbor clusters.

Convex hull and tour crossings in the Euclidean traveling salesperson problem: implications for human performance studies

Recently there has been growing interest among psychologists in human performance on the Euclidean traveling salesperson problem (E-TSP). A debate has been initiated on what strategy people use in solving visually presented E-TSP instances. The most prominent hypothesis is the convex-hull hypothesis, originally proposed by MacGregor and Ormerod (1996). We argue that, in the literature so far, there is no evidence for this hypothesis. Alternatively we propose and motivate the hypothesis that people aim at avoiding crossings.