Research Assistant: S. Graham
The geometry of visual space, and its effect on our perception has been the subject of some interest to the vision community. In this work we examine the interesting question of whether this influences the human ability to solve visual versions of some difficult (NP Complete) problems. We conjecture that NI (Natural Intelligence) algorithms, unlike their AI counterparts, are based on heuristics that develop only one path from the start to the goal and this path is almost always optimal. Our analysis involves formulating new properties of the A* algorithm under the assumption that the arcs in the search graph satisfy metric axioms. We also formulate certain properties of the problem in a metric space that can be used in obtaining efficient local-global solution techniques. We perform psychophysical experiments in which human subjects are asked to solve visual versions of various "hard" problems. We have performed some experiments with the Traveling Salesman Problem (TSP) in two cases: when distances between cities were Euclidean and thus satisfied the metric axioms, and when they didn't. Results show that in the metric case the solutions are almost always optimal and the time needed to find the solution is very short and proportional to the number of cities. This was not the case for the non-metric case. We conjecture that solving the visual version of TSP is characterized by developing the (close to) optimal path, without any sidetracking. We are working on characterizing the solution space of problems using Multidimensional Scaling (MDS) techniques. We are also working on the computational aspects of the visual phenomenon involved using solution techniques based on exponential pyramids.