Human TSP Solvers and the Convex Hull Hypothesis

I released some changes for the Human TSP Solver application yesterday, and I thought I would spend today reading up on theories as to how humans are able to effortlessly find solutions to small TSP instances. These human-based heuristics are generally mixed up into the concerns of spatial cognition, which have been investigated over the last twelve years or so by Ormerod, MacGregor, and colleagues.

The fact that humans are good TSP solvers was established perhaps in the 1970's in a study by Krolak, et. al. and has been confirmed in studies since, both for the TSP and related NP-hard problems. Krolak, et al.'s study titled A man-machine approach toward solving the traveling salesman problem (1971) uses a man-machine heuristic where the computer clustered cities for the human operator to connect, then offered sub-tours to the user to connect until a complete and feasible solution emerged. I like the paper, because it refers to the training of users on solving the TSP, and suggests at the writing a training manual (seems funny).

Ormerod and MacGregor's work started in 1996 with the publication of Human performance on the traveling salesman problem. The study involved two experiments with samples of people on 10 and 20 node TSP instances, where participants were given a booklet of connect-the-dots to complete. The human-based results were assessed against three heuristics (nearest neighbour, largest interior angle, and convex hull), and found to be superior. Human results were produced quickly (low cognitive load) and consistently were of a high quality (within a few percent of optimal). The core of the study tested the hypothesis that the difficulty of a TSP is a function of the number of interior cities with regard to a convex polygon, rather than the total number of cities, which seemed to be supported.

Follow-up work by the pair involved elaborating on the finding, and considering the underlying heuristic employed by human subjects to explain the results. Global perceptual processing in problem solving: The case of the traveling salesperson in 1999 considered a top-down explanation where the subject firstly perceived the overall structure of the problem, then made local step-by-step decisions that aligned with the global perception. The paper suggested that the global properties involved the identification of the convex hull (polygon) in the perceived data points, which guided tour construction. The experiments considered the measurement of this perception as well as aspects that may effect such global perception such as rotation. Similar concerns were also investigated in another 1999 paper titled Spatial and contextual factors in human performance on the travelling salesperson problem, where a larger instance (48 cities) was considered under a variety of contexts.

The convex hull explanation was pursued in the 2000 paper A model of human performance on the traveling salesperson problem, where the heuristic model was elaborated and assessed. The Convex Hull Hypothesis for human TSP solving proposes that the boundary cities are connected based on adjacency in a single direction, from which internal cities are linked. The implementation of this cognitive model was demonstrated to locate high quality solutions to TSP instances in a range between 10 and 100 cities.

The model was defended against an alternative explanation involving tour crossing avoidance in Convex-Hull or Crossing-Avoidance? Solution Heuristics in the Traveling Salesperson Problem, 2004. Most recently, the model was compared to a set of standard heuristic methods and found to provide the best fit with human-based observations: A Comparison of Heuristic and Human Performance on Open Versions of the Traveling Salesperson Problem, 2006.

I cannot comment on this variation of the convex hull TSP heuristic as I have not read up on the base method, although the hypothesis that humans use some variation of this approach seems quite reasonable. I know from observing my own behaviour and of others during user testing that variations on a directional bounding-polygon approach is taken. Unfortunately, this granularity of information is not recorded by the application, so I cannot do my own assessment (yet).

With regard to the Human TSP Solver application, this body of work mearly confirms that harnessing human spatial intelligence is a good idea, and Krolak's early work suggests that effective integration will result in meaningful solutions (also confirmed by my early experiments). Further, knowing that the majority of contributions in the database were collected under the convex hull assumption, means that exploiting the information in aggregate may be doe in a meaningful way. I'm not sure how yet, but my gut tells me there is an opportunity for a hull-sub-tour-based integration algorithm.

Finally, the premise of Ormerod and MacGregor's work highlights to me that humans will see spatial patterns, even if none exist, such as in random TSP instances. This is interesting because these spatial patterns strongly influence local decision making, which in the context of this research positively affects holistic TSP tours.