August 2009
Volume 9, Issue 8
Vision Sciences Society Annual Meeting Abstract  |   August 2009
The traveling salesman problem in the natural environment
Author Affiliations
  • Flip Phillips
    Skidmore College, Vision Laboratory
  • Oliver Layton
    Skidmore College, Vision Laboratory
Journal of Vision August 2009, Vol.9, 1145. doi:
  • Views
  • Share
  • Tools
    • Alerts
      This feature is available to authenticated users only.
      Sign In or Create an Account ×
    • Get Citation

      Flip Phillips, Oliver Layton; The traveling salesman problem in the natural environment. Journal of Vision 2009;9(8):1145.

      Download citation file:

      © ARVO (1962-2015); The Authors (2016-present)

  • Supplements

Is it possible for humans to navigate in the natural environment wherein the path taken between various destinations is ‘optimal’ in some way? This problem is traditionally framed as the “Traveling Salesman Problem” (TSP) — Given N cities to visit, what is the shortest path that connects them such that each city is visited only once? It has been shown that, when presented with an overhead, map-like presentation of the cities, subjects are exceptionally good at solving this optimization (error 2–3% longer than the optimum), even with very large Ns. (see e.g. Dry (2006) and MacGregor (2000)) In these experiments we evaluate human navigation performance when solving the TSP in the natural environment. Based on manipulations in these experiments we further investigate the effect of effort and its environmental affordance on navigation decisions. Two outdoor settings were used: A flat, open, 1/4 football field sized area and similar sized area with a variable terrain and obstacles. Fifteen locations in each area were marked with flags. From a random starting location subjects were instructed to walk to each location using the constraints of the TSP. Using a simple linear path-based metric, average performance in the flat-field condition was good (5% error) but was significantly worse in the variable-terrain condition (16% error). This suggests that subjects were not using a global representation of configurations to pre-plan their route, especially in the variable-terrain case. Because of this we hypothesize that subjects took a more ‘local’ approach. Based on the fact that the variable-terrain condition required a bit of ‘hiking’ and obstacle avoidance when compared to the flat condition we further hypothesize that the subjects took effort into account when planning their traversal. Lastly, we present a model that takes these local, ordinal decisions into account along with effort.

Phillips, F. Layton, O. (2009). The traveling salesman problem in the natural environment [Abstract]. Journal of Vision, 9(8):1145, 1145a,, doi:10.1167/9.8.1145. [CrossRef]

This PDF is available to Subscribers Only

Sign in or purchase a subscription to access this content. ×

You must be signed into an individual account to use this feature.