A comparison of human performance in figural and navigational versions of the traveling salesman problem

Performance on a typical pen-and-paper (figural) version of the Traveling Salesman Problem was compared to performance on a room-sized navigational version of the same task. Nine configurations were designed to examine the use of the nearest-neighbor (NN), cluster approach, and convex-hull strategies. Performance decreased with an increasing number of nodes internal to the hull, and improved when the NN strategy produced the optimal path. There was no overall difference in performance between figural and navigational task modalities. However, there was an interaction between modality and configuration, with evidence that participants relied more heavily on the NN strategy in the figural condition. Our results suggest that participants employed similar, but not identical, strategies when solving figural and navigational versions of the problem. Surprisingly, there was no evidence that participants favored global strategies in the figural version and local strategies in the navigational version.     

Human performance on the traveling salesman problem

Two experiments on performance on the traveling salesman problem (TSP) are reported. The TSP consists of finding the shortest path through a set of points, returning to the origin. It appears to be an intransigent mathematical problem, and heuristics have been developed to find approximate solutions. The first experiment used 10-point, the second, 20-point problems. The experiments tested the hypothesis that complexity of TSPs is a function of number of nonboundary points, not total number of points. Both experiments supported the hypothesis. The experiments provided information on the quality of subjects’ solutions. Their solutions clustered close to the best known solutions, were an order of magnitude better than solutions produced by three well-known heuristics, and on average fell beyond the 99.9th percentile in the distribution of random solutions. The solution process appeared to be perceptually based.     

The traveling salesman problem: A hierarchical model

Our review of prior literature on spatial information processing in perception, attention, and memory indicates that these cognitive functions involve similar mechanisms based on a hierarchical architecture. The present study extends the application of hierarchical models to the area of problem solving. First, we report results of an experiment in which human subjects were tested on a Euclidean traveling salesman problem (TSP) with 6 to 30 cities. The subject's solutions were either optimal or near-optimal in length and were produced in a time that was, on average, a linear function of the number of cities. Next, the performance of the subjects is compared with that of five representative artificial intelligence and operations research algorithms, that produce approximate solutions for Euclidean problems. None of these algorithms was found to be an adequate psychological model. Finally, we present a new algorithm for solving the TSP, which is based on a hierarchical pyramid architecture. The performance of this new algorithm is quite similar to the performance of the subjects.     

Cognitive maps not used by humans (Homo sapiens) during a dynamic navigational task

To account for the impressive navigational ability of animals, some researchers have suggested that animals might use a cognitive map. Two groups of human participants (Homo sapiens) were tested for cognitive mapping using procedures similar to those used by B. M. Gibson and A. C. Kamil (2001). Participants who had to acquire spatial information about a hidden goal from the experimental contingencies alone showed patterns of search most like nutcrackers in the companion study (B. M. Gibson & A. C. Kamil, 2001). Surprisingly, postexperimental questionnaires revealed that most participants used an alternative strategy of vector integration rather than cognitive mapping during search for the hidden goal. The current study and its companion indicate that some simpler mechanisms of navigation are flexible enough to account for what appears to be map-based behavior in human and nonhuman species.     

The importance of the convex hull for human performance on the traveling salesman problem: a comment on MacGregor and Ormerod (1996)

MacGregor and Ormerod (1996) have presented results purporting to show that human performance on visually presented traveling salesman problems, as indexed by a measure of response uncertainty, is strongly determined by the number of points in the stimulus array falling inside the convex hull, as distinct from the total number of points. It is argued that this conclusion is artifactually determined by their constrained procedure for stimulus construction, and, even if true, would be limited to arrays with fewer than around 50 points.     

Applications of combinatorial programming to data analysis: The traveling salesman and related problems

The Traveling Salesman and similar combinatorial programming tasks encountered in operations research are discussed as possible data analysis models in psychology, for example, in developmental scaling, Guttman scaling, profile smoothing, and data array clustering. In addition, a short overview of the various computational approaches from this area of combinatorial optimization is included.The research of the first author was supported by a research grant SOC-75-07860 from the National Science Foundation.     

Directional learning,but no spatial mapping by rats performing a navigational task in an inverted orientation

Previous studies have identified neurons throughout the rat limbic system that fire as a function of the animal’s head direction (HD). This HD signal is particularly robust when rats locomote in the horizontal and vertical planes, but is severely attenuated when locomoting upside-down (Calton & Taube, 2005). Given the hypothesis that the HD signal represents an animal’s sense of directional heading, we evaluated whether rats could accurately navigate in an inverted (upside-down) orientation. The task required the animals to find an escape hole while locomoting inverted on a circular platform suspended from the ceiling. In Experiment 1, Long-Evans rats were trained to navigate to the escape hole by locomoting from either one or four start points. Interestingly, no animals from the 4-start point group reached criterion, even after 29 days of training. Animals in the 1-start point group reached criterion after about six training sessions. In Experiment 2, probe tests revealed that animals navigating from either 1- or 2-start points utilized distal visual landmarks for accurate orientation. However, subsequent probe tests revealed that their performance was markedly attenuated when navigating to the escape hole from a novel start point. This absence of flexibility while navigating upside-down was confirmed in Experiment 3 where we show that the rats do not learn to reach a place, but instead learn separate trajectories to the target hole(s). Based on these results we argue that inverted navigation primarily involves a simple directional strategy based on visual landmarks.     

Never cross the path of a traveling salesman: The neural network generation of Halstead-Reitan trail making tests

The Halstead-Reitan Trail Making Test (TMT) is one of the most widely used neuropsychological instruments for the assessment of brain damage. Despite its usefulness, however, the TMT has two major disadvantages. It has not been constructed in a principled manner that would facilitate systematic investigation, and there is no established procedure for generating equivalent, but stochastically different, test forms. The reason is that the generation of self-avoiding TMT pathways resembles the finding of near-optimal solutions to the Euclidean Traveling Salesman Problem (TSP) and constitutes a computational problem that is NP-complete. This article describes a practical approach to the problem of generating stochastically different test forms. This approach employs anelastic net neural network to generate TMT forms based on self-avoiding, near-optimal paths, and closed circuits. The usefulness and limitations of this solution are discussed briefly in relation to alternative and complementary problems and procedures.     

Preference for familiar humans by rats

Many “higher” animals are commonly assumed to distinguish between individual humans. This belief is based largely on anecdotal reports; in reality, there is little empirical evidence to support human recognition in nonhuman species. We report that laboratory rats consistently chose a familiar human over an unfamiliar human following fourteen and five 10-min exposures and even following a single 10-min exposure. Furthermore, this preference was retained in the absence of additional contact for at least 5 months. These results confirm that laboratory rats can tell individual humans apart, a prerequisite for associating them with hedonic events. Such human-based conditioning, described by Pavlov and by Gantt, Newton, Royer, and Stephens (1966), may have important implications for animal research in a variety of settings.     

The verbalization of multiple strategies in a variant of the traveling salesperson problem

What kinds of strategies do humans employ when confronted with a complex spatial task, and how do they verbalize these strategies? Previous research concerned with the well-known traveling salesperson problem (TSP) typically aimed at the identification of a generally applicable heuristics that adequately represents human behavior in relation to the abstract task of combining points. This paper adopts a novel perspective in two respects. On the one hand, it addresses the strategies people employ when confronted with a more complex task, involving distractors and feature information rather than identical points. On the other hand, retrospective linguistic representations of the strategies used are analyzed in relation to the behavioral data, using discourse analytic methods. Results show that both the behavioral results and the verbalizations point to a range of strategies related to those proposed for solving abstract TSPs. However, in contrast to earlier accounts in the literature, the participants employ a repertory of multi-faceted strategies and planning processes, simplifying and structuring the problem space across subtasks and processes in flexible ways. These findings provide further insight into the nature of human strategies in spatial problem solving tasks and their retrospective verbalization, highlighting how procedures generally known in the literature may be adapted to more complex tasks, and how they may be verbalized spontaneously.     

For efficient navigational search, humans require full physical movement, but not a rich visual scene

During navigation, humans combine visual information from their surroundings with body-based information from the translational and rotational components of their movement. Theories of navigation focus on the role of visual and rotational body-based information, even though experimental evidence shows they are not sufficient for complex spatial tasks. To investigate the contribution of all three sources of information, we asked participants to search a computer-generated virtual room for targets. Participants were provided with only visual information or with visual information supplemented with body-based information for all movement (walk group) or rotational movement (rotate group). The walk group performed the task with near-perfect efficiency, irrespective of whether a rich or impoverished visual scene was provided. The visual-only and rotate groups were significantly less efficient and frequently searched parts of the room at least twice. These results suggest that full physical movement plays a critical role in navigational search, but only moderate visual detail is required.     

Bidirectional associations in humans and rats

In 1 experiment with humans and 3 experiments with rats, the authors sought evidence of temporal integration of independently acquired temporal relationships, including forward and backward temporal associations. The experiments were designed and analyzed in the framework of the temporal coding hypothesis (e.g., L. D. Matzel, F. P. Held, & R. R. Miller, 1988; H. I. Savastano & R. R. Miller, 1998) as a strategy toward illuminating the use of forward and backward temporal associations and assessing the directional nature of these temporal associations. The results obtained suggest that the temporal content of learning about paired events involves a single bidirectional association instead of 2 independent unidirectional, forward and backward, associations.     

Stimulus-outcome interactions during instrumental discrimination learning by rats and humans

The associative structure mediating goal-directed action was investigated using congruent and incongruent conditional discriminations. The stimulus was the same as the outcome in each component of the congruent discriminations, whereas the stimulus of one component of the incongruent discriminations was the same as the outcome of the other component. Humans, but not rats, learned the congruent discrimination more rapidly than the incongruent discrimination, a difference that the authors attribute to the fact that outcome-response associations caused response conflict in the incongruent discrimination. Moreover, responding was resistant to outcome devaluation following incongruent, but not congruent, training, suggesting that both humans and rats adopted a stimulus-response strategy to resolve the incongruent discrimination.     

Expectancy and stimulus frequency: a comparative analysis in rats and humans.

We examined whether expectancy, one of several factors influencing attention, is similarly affected in rats and humans by manipulation of relative stimulus frequency. A two-choice reaction time (RT) task was developed for rats, and an analogous task was used for humans. Errors, RTs, discriminability, and response bias were measured. Both rats and humans shifted their response bias to the more frequent stimulus, with no change in overall discriminability. As stimulus probability or stimulus repetition increased, RTs and errors decreased. These results illustrate the similarity of expectancy in rats and humans. This two-choice RT task for rats can be used in future studies to examine the neuronal mechanisms of expectancy and attention.     

A comparison of event-related potentials of humans and rats elicited by a serial feature-positive discrimination task

The purpose of this experiment was to compare components of the human and rat auditory event-related potential (ERP) in a serial feature-positive discrimination task. Subjects learned to respond to an auditory target stimulus when it followed a visual feature (X → A+), but to not respond when it was presented alone (A−). Upon solving the task, the N2 component, which has been suggested to reflect the activation of inhibitory processes, was temporarily more negative in response to the target on A− than on X → A+ trials in both species. However, whereas a P3 component was present in the human participants, this component was absent in the rats. In both species, the amplitude of several ERP components, including the N2, decreased in the course of training. These results are discussed in the framework of contemporary models of associative learning.     

Global perceptual processing in problem solving: The case of the traveling salesperson

The traveling salesperson problem (TSP) consists of finding the shortest tour around a set of locations and is an important task in computer science and operations research. In four experiments, the relationship between processes implicated in the recognition of good figures and the identification of TSP solutions was investigated. In Experiment 1, a linear relationship was found between participants’ judgments of good figure and the optimality of solutions to TSPs. In Experiment 2, identification performance was shown to be a function of solution optimality and problem orientation. Experiment 3 replicated these findings with a forced-pace method, suggesting that global processing, rather than a local processing strategy involving point-by-point analysis of TSP solutions, is the primary process involved in the derivation of best figures for the presented TSPs. In Experiment 4, the role of global precedence was confirmed using a priming method, in which it was found that short (100 msec) primes facilitated solution identification, relative to no prime or longer primes. Effects of problem type were found in all the experiments, suggesting that local features of some problems may disrupt global processing. The results are discussed in terms of Sanocki’s (1993) global-to-local contingency model. We argue that global perceptual processing may contribute more generally to problem solving and that human performance can complement computational TSP methods.