Purchase this article with an account.
Flip Phillips, Oliver Layton; The traveling salesman problem in the natural environment. Journal of Vision 2009;9(8):1145. doi: https://doi.org/10.1167/9.8.1145.
Download citation file:
© ARVO (1962-2015); The Authors (2016-present)
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.
This PDF is available to Subscribers Only