Solving problems in general, and solving combinatorial optimization problems in particular, is a goal-directed activity. By its very nature, goal-directed, purposive action is impossible without an explicit representation (model) of the goal, and of the environment in which the problem is solved. The role of representation was emphasized by the Gestalt Psychologist who pointed out that solving an “insight problem” is impossible unless one finds a good representation of the problem. Unfortunately, the role of problem representation was minimized when the AI community started formulating theories for solving “search problems”, such as the Traveling Salesman Problem (TSP).

In this talk, Pizlo will describe results showing that humans produce near-optimal TSP tours in linear time. Pizlo will also describe a computational model that emulates human performance. This model uses a multiresolution/multiscale pyramid representation of the problem, a representation that is known to operate in the human visual cortex. The TSP tour is produced by the model in a sequence of coarse-to-fine approximations. This process eliminates the need for a global search; the search is always local, but the meaning of “local” gradually changes as one traverses up or down the pyramid. Specifically, local search on the coarse representation uses spatially-global operations. Pizlo will also discuss a number of other NP-hard combinatorial optimization problems that the human visual system solves very well, such as the Figure-Ground Organization problem, which is equivalent to finding the correct partition of the retinal or camera image. Pizlo will illustrate this set of problems by describing the task of integrating a closed fragmented contour in a 2D image. This problem is solved in the human visual system by using a complex-logarithm representation of the retinal image in the area V1 of the visual cortex. The talk will conclude with a discussion of the role of this complex-logarithm representation in solving the TSP.

 

 

© UC Irvine School of Social Sciences - 3151 Social Sciences Plaza, Irvine, CA 92697-5100 - 949.824.2766