The skeleton in the cognitive map: a computational and empirical exploration (2003)
Benjamin Kuipers, Dan Tecuci and Brian Stankiewicz
Experts seem to find routes in a complex environment by finding a connection from the starting place to a subset of major paths --- the ``skeleton'' --- then moving within the skeleton to the neighborhood of the destination, making a final connection to the destination. We present a computational hypothesis to account for the skeleton as an emergent phenomenon, arising from the interaction of three factors. (1) The topological map is represented as a bipartite graph of places and paths, where a path is an extended one-dimensional description of an ordered set of places. (2) Travel through the environment allows the traveler to incrementally accumulate topological relationships, including the relation of a place to a path serving as a dividing boundary separating two regions. (3) A bounding path is often a natural subgoal during way-finding search, meaning that paths rich in boundary relations are likely to appear in routes, which means they are likely to acquire more boundary relations. This positive-feedback loop leads to an oligarchy of paths rich in boundary relations: the skeleton. We present preliminary computational and empirical methods for testing this hypothesis, and provide initial results.
Environment and Behavior, Vol. 35, 1 (2003), pp. 80--106.

Benjamin Kuipers Formerly affiliated Faculty kuipers [at] cs utexas edu
Dan Tecuci Ph.D. Alumni tecuci [at] cs utexas edu