Abstract
In many real-world route planning and search tasks, humans must solve a combinatorial optimization problem that holds many similarities to the Euclidean Traveling Salesman Problem (TSP). The problem spaces used in real-world tasks differ most starkly from traditional TSP in terms of optimization criteria – Whereas the traditional TSP asks participants to connect all of the nodes to produce the solution that minimizes overall path length, real-world search tasks are often conducted with the goal of minimizing the duration of time required to find the target (i.e., the average distance between nodes). Traditional modeling approaches to TSP assume that humans solve these problems using intrinsic characteristics of the brain and perceptual system (e.g., hierarchical structure in the visual system). A consequence of these approaches is that they are not robust to strategic changes in the aforementioned optimization criteria during path planning. To investigate performance in these tasks, 28 participants solved 18 randomly-presented computer-based combinatorial optimization problems with two sets of task instructions, one designed to encourage shortest-path solutions and the other to encourage solutions that minimized the estimated time to find a target hidden among the nodes (i.e., locations). The node distributions were designed to discriminate between these two strategies. In nearly every case, participants were capable of strategically adapting optimization criteria based on instruction alone. These results indicate the importance of modeling cognition in behaviors that are traditionally thought to be driven automatically by perceptual processes. In addition, we discuss computational models that we have developed to produce optimization criteria-specific solutions to these combinatorial optimization problems using a strategic optimization parameter to guide solutions using a single underlying mechanism. Such models have applications in approximating human behavior in real-world tasks.
Meeting abstract presented at VSS 2015