Yannan_iRun_screenShot_maded
?
0 likes?148 views
Yannan Zheng developed an app called iRun to recommend running routes between set locations with customizable distances. The app builds a graph of roads and paths in Cambridge and Boston, then uses algorithms like Dijkstra's and Monte Carlo to find optimal routes matching desired distances while minimizing turns, loops, repetitive segments, and difference from the target distance. The system is intended to allow runners to vary their routes on different runs for different mileages.
Yannan_iRun_screenShot_maded
- 2. Here is the problem
- 3. Here is the problem Sometimes, I want to take a run from Lab to Home
- 4. Here is the problem Sometimes, I want to take a run from Lab to Home But I want to run different miles on different days
- 5. Here is the problem Sometimes, I want to take a run from Lab to Home But I want to run different miles on different days I want to run different routes on different days
- 6. Here is the problem Sometimes, I want to take a run from Lab to Home But I want to run different miles on different days I want to run different routes on different days How to find routes with targeted distances?
- 7. Building a graph of Cambridge and Boston
- 8. Data Clean Up 0: Original Map
- 9. Data Clean Up I: Remove un-runnable area
- 10. Data Clean Up II: Remove isolated islands
- 11. Data Clean Up III: Remove spikes
- 12. Data Clean Up IV: Combine parallel roads
- 13. Data Clean Up IV: remove redundant nodes
- 14. After Data Clean Up 103,365 Nodes, 225,766 edges 17,480 Nodes, 49,354 edges 5min 30s for path search ~5 fold reduction
- 15. Starting Address: My Lab Ending Address: My Home Desired Distance: 3km Path Finding Algorithm: My LabMy Home
- 16. Path Finding Algorithm: Dijkstra¡¯s Algorithm finding shortest path Shortest Path Length 1131m My LabMy Home
- 17. Score ? Penalize difference between desired distance and actual distance ? Penalize turns / loops / zigzags ? Penalize repetitive route
- 18. Path Finding Algorithm: Monte Carlo Heuristic perturbation of route penalty score = 4.99 path length = 1131m My LabMy Home
- 19. Path Finding Algorithm: Monte Carlo accept improvements penalty score = 2.95 path length = 1875m My LabMy Home
- 20. Path Finding Algorithm: Monte Carlo only accept deterioration with low probability penalty score = 39.32 path length = 8064m My LabMy Home
- 21. Path Finding Algorithm: Monte Carlo best route after 1000 iterations penalty score = 0.495 path length = 2985m My LabMy Home
- 22. Path Finding Algorithm: Monte Carlo best route after another 1000 iterations penalty score = 0.251 path length = 3202m My LabMy Home
- 25. Summary ? Build a route recommendation system for runners ? Recommend different routes for given running distances ? Customized running score ? Can be easily generalized for other purposes
- 29. Thank You!