DART: A Particle-Based Method for Generating Easy-To-Follow Directions

摘要

Despite evidence that human wayfinders consider directions involving landmarks or topological descriptions easier to follow, the majority of commerical direction-planning services and GPS navigation units plan routes based on metrically or temporally shortest paths, ignoring this potentially valuable information. We propose a method for generating directions that maximizes the probability of a human arriving at the correct destination, taking into account a model of their ability to follow topological, metrical, and landmark-based directions. We discuss optimization techniques for employing these models and present a method, DART, for extracting model-improved sets of directions in a tractable amount of time. DART employs particle simulation techniques to maximize the probability that the modeled wayfinder will successfully reach their destination. Our synthetic evaluation shows that DART produces improvements in arrival rates over existing methods and illustrates how DART's directions reflect properties of the wayfinder model.