University Library
  • Login
A gateway to Melbourne's research publications
Minerva Access is the University's Institutional Repository. It aims to collect, preserve, and showcase the intellectual output of staff and students of the University of Melbourne for a global audience.
View Item 
  • Minerva Access
  • Engineering and Information Technology
  • Infrastructure Engineering
  • Infrastructure Engineering - Research Publications
  • View Item
  • Minerva Access
  • Engineering and Information Technology
  • Infrastructure Engineering
  • Infrastructure Engineering - Research Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

    "Simplest" paths: automated route selection for navigation

    Thumbnail
    Citations
    Altmetric
    Author
    DUCKHAM, MATT; KULIK, LARS
    Date
    2003
    Source Title
    Lecture Notes in Computer Science 2825
    Publisher
    Springer
    University of Melbourne Author/s
    Kulik, Lars; Duckham, Matt
    Affiliation
    Engineering: Department of Geomatics
    Metadata
    Show full item record
    Document Type
    Book Chapter
    Citations
    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 repository
    URI
    http://hdl.handle.net/11343/33600
    Description

    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; instructioncomplexity

    Export 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


    Collections
    • Infrastructure Engineering - Research Publications [1256]
    Minerva AccessDepositing Your Work (for University of Melbourne Staff and Students)NewsFAQs

    BrowseCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects
    My AccountLoginRegister
    StatisticsMost Popular ItemsStatistics by CountryMost Popular Authors