Eric Horvitz
John Krumm
ABSTRACT
We investigate opportunistic routing, centering on the recommendation of ideal diversions on trips to a primary destination when an unplanned waypoint, such as a rest stop or a refueling station, is desired. In the general case, an automated routing assistant may not know the driver's final destination and may need to consider probabilities over destinations in identifying the ideal waypoint along with the revised route that includes the waypoint. We consider general principles of opportunistic routing and present the results of several studies with a corpus of real-world trips. Then, we describe how we can compute the expected value of asking a user about the primary destination so as to remove uncertainly about the goal and show how this measure can guide an automated system's engagements with users when making recommendations for navigation and analogous settings in ubiquitous computing.
- Krumm, J., Where Will They Turn: Predicting Turn Proportions At Intersections. Personal and Ubiquitous Computing, 2010. 14(7): p. 591--599. Google Scholar
Digital Library
- Horvitz, E., P. Koch, and M. Subramani, Mobile Opportunistic Planning: Methods and Models, in 11th international conference on User Modeling (UM 2007). 2007. p. 228--237. Google ScholarDigital Library
- Kamar, E., E. Horvitz, and C. Meek, Mobile Opportunistic Commerce: Mechanisms, Architecture, and Application, in International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008). 2008: Estoril, Portugal. Google ScholarDigital Library
- Marmasse, N. and C. Schmandt, A User-Centered Location Model. Personal and Ubiquitous Computing, 2002(6): p. 318--321. Google ScholarDigital Library
- Ashbrook, D. and T. Starner, Using GPS to Learn Significant Locations and Predict Movement across Multiple Users. Personal and Ubiquitous Computing, 2003. 7(5): p. 275--286. Google ScholarDigital Library
- Hariharan, R. and K. Toyama. Project Lachesis: Parsing and Modeling Location Histories. in Geographic Information Science: Third International Conference, GIScience 2004. 2004. Adelphi, MD, USA: Springer-Verlag GmbH.Google Scholar
- Liao, L., D. Fox, and H. Kautz. Learning and Inferring Transportation Routines. in Proceedings of the 19th National Conference on Artificial Intelligence (AAAI 2004). 2004. San Jose, CA, USA. Google ScholarDigital Library
- Patterson, D. J., et al., Inferring High-Level Behavior from Low-Level Sensors, in UbiComp 2003: Ubiquitous Computing. 2003: Seattle, WA USA. p. 73--89.Google Scholar
- Krumm, J. and E. Horvitz, Predestination: Inferring Destinations from Partial Trajectories, in UbiComp 2006: Ubiquitous Computing. 2006: Orange County, CA USA. p. 243--260. Google ScholarDigital Library
- Ziebart, B. D., et al., Navigate Like a Cabbie: Probabilistic Reasoning from Observed Context-Aware Behavior, in Tenth International Conference on Ubiquitous Computing (UbiComp 2008). 2008: Seoul, South Korea. p. 322--331. Google ScholarDigital Library
- Scellato, S., et al., NextPlace: A Spatio-temporal Prediction Framework for Pervasive Systems, in 9th International Conference on Pervasive Computing (Pervasive 2011). 2011: San Francisco, CA USA. Google ScholarDigital Library
- Filev, D., et al., Contextual On-Board Learning and Prediction of Vehicle Destinations, in 2011 IEEE Symposium on Computational Intelligence in Vehicles and Transportation Systems (CIVTS). 2011: Paris, France. p. 87--91.Google Scholar
- Yuan, J., et al., T-Drive: Driving Directions Based on Taxi Trajectories, in 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS). 2010, ACM: San Jose, CA USA. Google ScholarDigital Library
- Yuan, J., et al., Where to Find My Next Passenger?, in 13th International Conference on Ubiquitous Computing (UbiComp 2011). 2011, ACM: Beijing, China. Google ScholarDigital Library
- Zheng, Y. and X. Xie, Learning Travel Recommendations from User-Generated GPS Traces. ACM Transactions on Intelligent Systems and Technology (TIST) 2011. 2(1). Google ScholarDigital Library
- Zhang, K., et al., Adaptive Learning of Semantic Locations and Routes, in 3rd International Symposium in Location- and Context-Awareness (LoCA). 2007, Springer: Oberpfaffenhofen, Germany. p. 193--210. Google ScholarDigital Library
- Krumm, J., Real Time Destination Prediction Based on Efficient Routes, in Society of Automotive Engineers (SAE) 2006 World Congress. 2006: Detroit, Michigan, USA.Google Scholar
- Newson, P. and J. Krumm, Hidden Markov Map Matching Through Noise and Spaseness, in 17th ACM SIGSPATIAL Conference on Advances in Geographic Information Systems (GIS '09). 2009: Seattle, WA USA. p. 336--343. Google ScholarDigital Library
- Delling, D., A. V. Goldberg, and R. F. Werneck, Faster Batched Shortest Paths in Road Networks, in 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'11). 2011: Saarbruecken, Germany.Google Scholar
- Krumm, J., How People Use Their Vehicles: Statistics from the 2009 National Household Travel Survey, in Society of Automotive Engineers (SAE) 2012 World Congress. 2012: Detroit, MI USA.Google Scholar
- Delling, D., et al., PHAST: Hardware-accelerated shortest path trees Journal of Parallel and Distributed Computing, 2012.Google Scholar
- Horvitz, E., Principles of Mixed-Initiative User Interfaces, in SIGCHI Conference on Human Factors in Computing Systems (CHI 1999). 1999, ACM: Pittsburgh, Pennsylvania, USA. Google ScholarDigital Library
- Iqbal, S., Y.-C. Ju, and E. Horvitz, Cars, Calls and Cognition: Investigating Driving and Divided Attention, in 2010 ACM Conference on Human Factors in Computing Systems (CHI 2010). 2010: Atlanta, Georgia, USA. Google ScholarDigital Library
- Horvitz, E., J. Apacible, and M. Subramani, Balancing Awareness and Interruption: Investigation of Notification Deferral Policies, in Tenth Conference on User Modeling (UM 2005). 2005: Edinburgh, Scotland. Google ScholarDigital Library
Index Terms
- Some help on the way: opportunistic routing under uncertainty
Recommendations
Opportunistic Routing in Presence of Selfish Nodes for MANET
Opportunistic Routing protocols use broadcast nature of wireless communication to improve packet delivery from source to destination in mobile ad hoc network (MANET). In traditional routing protocols for MANET, each node uses the best neighbor for ...
Mobility-based opportunistic routing for mobile ad-hoc networks
PE-WASUN '14: Proceedings of the 11th ACM symposium on Performance evaluation of wireless ad hoc, sensor, & ubiquitous networksOpportunistic Routing (OR) is an effective and enhanced routing scheme for wireless multihop environment. OR is an approach which selects a certain number of best forwarders (candidates) at each hop by taking the advantage of the broadcast nature of the ...
Opportunistic media access control and routing for delay-tolerant mobile ad hoc networks
In delay-tolerant mobile ad hoc networks, motion of network nodes, network sparsity and sporadic density can cause a lack of guaranteed connectivity. These networks experience significant link delay and their routing protocols must take a store-and-...
Comments