"Simplest" paths: automated route selection for navigation
Citations
Altmetric
Author
DUCKHAM, MATT; KULIK, LARSDate
2003Source Title
Lecture Notes in Computer Science 2825Publisher
SpringerAffiliation
Engineering: Department of GeomaticsMetadata
Show full item recordDocument Type
Book ChapterCitations
Duckham, M. & Kulik, L. (2003). "Simplest" paths: automated route selection for navigation. In W. Kuhn, M. Worboys & S. Timpf (Eds.), Lecture Notes in Computer Science 2825 (pp. 169-185). Springer.Access Status
This item is currently not available from this repositoryDescription
Publisher's version is restricted access in accordance with the publisher's policy. The original publication is available at http://www.springerlink.com
Abstract
Numerous cognitive studies have indicated that the form andcomplexity of route instructions may be as important to human navigatorsas the overall length of route. Most automated navigation systemsrely on computing the solution to the shortest path problem, and not theproblem of finding the “simplest” path. This paper addresses the issueof finding the “simplest” paths through a network, in terms of the instructioncomplexity. We propose a “simplest” paths algorithm that hasquadratic computation time for a planar graph. An empirical study ofthe algorithm’s performance, based on an established cognitive model ofnavigation instruction complexity, revealed that the length of a simplestpath was on average only 16% longer than the length of the correspondingshortest path. In return for marginally longer routes, the simplest pathalgorithm seems to offer considerable advantages over shortest paths interms of their ease of description and execution. The conclusions indicateseveral areas for future research: in particular cognitive studies areneeded to verify these initial computational results. Potentially, the simplestpaths algorithm could be used to replace shortest paths algorithmsin any automated system for generating human navigation instructions,including in-car navigation systems, Internet driving direction servers,and other location-based services.
Keywords
navigation; wayfinding; route selection; shortest path; instructioncomplexityExport Reference in RIS Format
Endnote
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
Refworks
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References