Chapter 4 - The Exponential Pyramid Representation that Compensates for Exponentially Large Problem Spaces

Summary

This chapter begins with a discussion of classes of problem complexity. It then focuses on hierarchical pyramids that have been accepted for the last three decades as computational models of the visual system of primates, including humans. Anatomical and behavioral results that support this claim are reviewed. First, the speed-accuracy tradeoff results in visual perception are reviewed. Second, mental size transformation is described and it is shown that they can be explained by a pyramid model. With these results related to visual perception in hand, it is shown how the pyramid model can be applied to the TSP. Pyramid models are characterized by self-similarity across space and scale. This self-similarity is a form of invariance, also known as symmetry. A pyramid model produces near-optimal TSP tours by using a global-to-local (coarse-to-fine) sequence of computational steps. Good performance of pyramid models on TSP comes with a price when the geometry of a TSP problem is perturbed by inserting obstacles. Finally, subjects are tested in a real-life application of the TSP, where they collect tennis balls on a tennis court. The fact that humans are capable of producing near-optimal TSP tours in almost “no time” suggests that they solve the task of minimizing a tour's length without ever measuring the length of the tour. Instead, they infer the concept of direction in the search space, and use the direction, rather than the distance, when they navigate within the problem spaces.