May 2008
Volume 8, Issue 6
Free
Vision Sciences Society Annual Meeting Abstract  |   May 2008
Non-Euclidean visual traveling salesman problem
Author Affiliations
  • Yll Haxhimusa
    Psychological Sciences, Purdue University
  • Zygmunt Pizlo
    Psychological Sciences, Purdue University
  • Joseph Catrambone
    Psychological Sciences, Purdue University
Journal of Vision May 2008, Vol.8, 941. doi:10.1167/8.6.941
  • Views
  • Share
  • Tools
    • Alerts
      ×
      This feature is available to authenticated users only.
      Sign In or Create an Account ×
    • Get Citation

      Yll Haxhimusa, Zygmunt Pizlo, Joseph Catrambone; Non-Euclidean visual traveling salesman problem. Journal of Vision 2008;8(6):941. doi: 10.1167/8.6.941.

      Download citation file:


      © ARVO (1962-2015); The Authors (2016-present)

      ×
  • Supplements
Abstract

Traveling Salesman Problem (TSP) is defined as the task of finding the shortest tour of N cities given intercity costs. Usually the intercity costs are 2D Euclidean distances. In the presence of obstacles or in the case of 3D surfaces, the intercity distances are in general not Euclidean. The TSP with obstacles and on 3D surfaces approximates our everyday visual navigation. There are three questions related to the mechanisms involved in solving TSP: (i) how do subjects find the intercity distances, (ii) how do they determine clusters of cities, and (ii) how do they produce the TSP tour. In our model, the non-Euclidean distances (geodesics) are found by using a non-linear Eikonal equation, i.e. the evolution of interfaces (Sethian, 1999). The geodesic distances are then used as intercity costs in an MST graph pyramid (Haxhimusa et. al., 2007). The original TSP problem is represented by a sequence of problems involving clusters of cities. The hierarchical clustering is performed by using a Boruvka's minimum spanning tree. Close to the top of the pyramid, the original TSP problem is represented at a very coarse level and involves very small number of “cities”. This coarse representation is solved optimally. Expanding this coarse tour in a top-down manner leads to a solution of the original TSP. The new model has an adaptive spatial structure and it simulates visual acuity and visual attention. The model solves the TSP problem sequentially, by moving its attention from city to city. The model's performance will be compared to the performance of human subjects.

Haxhimusa, Y. Pizlo, Z. Catrambone, J. (2008). Non-Euclidean visual traveling salesman problem [Abstract]. Journal of Vision, 8(6):941, 941a, http://journalofvision.org/8/6/941/, doi:10.1167/8.6.941. [CrossRef]
Footnotes
 AFOSR.
×
×

This PDF is available to Subscribers Only

Sign in or purchase a subscription to access this content. ×

You must be signed into an individual account to use this feature.

×