Destination prediction is an essential task in a variety of mobile applications. In this paper, we optimize the matrix operation and adapt a semi-lazy framework to improve the prediction accuracy and efficiency of a state-of-the-art approach. To this end, we employ efficient dynamic-programming by devising several data constructs including Efficient Transition Probability and Transition Probabilities with Detours that are capable of pinpointing the minimum amount of computation. We prove that our method achieves one order of cut in both time and space complexity. The experimental results on real-world and synthetic datasets have shown that our solution consistently outperforms its state-of-the-art counterparts in terms of both efficiency (approximately over 100 times faster) and accuracy (above 30 increase).
We describe a method called Predestination that uses a history of a driver's destinations, along with data about driving behaviors, to predict where a driver is going as a trip progresses. Driving behaviors include types of destinations, driving efficiency, and trip times. Beyond considering previously visited destinations, Predestination leverages an open-world modeling methodology that considers the likelihood of users visiting previously unobserved locations based on trends in the data and on the background properties of locations. This allows our algorithm to smoothly transition between “out of the box” with no training data to more fully trained with increasing numbers of observations. Multiple components of the analysis are fused via Bayesian inference to produce a probabilistic map of destinations. Our algorithm was trained and tested on hold-out data drawn from a database of GPS driving data gathered from 169 different subjects who drove 7,335 different trips. CrowdPlanner -- a novel crowd-based route recommendation system has been developed, which requests human workers to evaluate candidates routes recommended by different sources and methods, and determine the best route based on the feedbacks of these workers. Our system addresses two critical issues in its core components: a) task generation component generates a series of informative and concise questions with optimized ordering for a given candidate route set so that workers feel comfortable and easy to answer; and b) worker selection component utilizes a set of selection criteria and an efficient algorithm to find the most eligible workers to answer the questions with high accuracy. We present PROCAB, an efficient method for Probabilistically Reasoning from Observed Context-Aware Behavior. It models the context-dependent utilities and underlying reasons that people take different actions. The model generalizes to unseen situations and scales to incorporate rich contextual information. We train our model using the route preferences of 25 taxi drivers demonstrated in over 100,000 miles of collected data, and demonstrate the performance of our model by inferring: (1) decision at next intersection, (2) route to known destination, and (3) destination given partially traveled route. Human behavior is often complex and context-dependent. This paper presents a general technique to exploit this "multidimensional" contextual variable for human mobility prediction. We use an ensemble method, in which we extract different mobility patterns with multiple models and then combine these models under a probabilistic framework. The key idea lies in the assumption that human mobility can be explained by several mobility patterns that depend on a sub-set of the contextual variables and these can be learned by a simple model. We showed how this idea can be applied to two specific online prediction tasks: what is the next place a user will visit? and how long will he stay in the current place?. Using smartphone data collected from 153 users during 17 months, we show the potential of our method in predicting human mobility in real life. 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.