Inferring Waypoints in the Absence of Knowledge of Driving Style

Abstract

We present an algorithm for predicting intervals which contain waypoints from a GPS trace of a multi-part trip without having access to historical data about the driver or any other aggregated data sets. We assume the driver's driving style is not known, but that it can be approximated by one of a set of cost preferences. The method uses a set of repeated forward and backward searches along the trace, where each of the searches represents one of the driving costs. We evaluate the algorithm empirically on multi-part trips on real route maps. The algorithm selects the results of the search with the fewest number of intervals and we achieve over 95% recall on estimating waypoints while the intervals cover less than 9% of the trace.

Introduction

Recreating intent from activity traces is an important aspect of security, missing persons search, assisted living, and retail analysis. In the retail analysis case the inference would require the analysis of large sets of activity traces from many people, while in assisted living there will be many traces from one person. In the security and missing persons case the inferences may have to be determined from a single trace for an individual. In such cases the activity traces may be trajectories through space with intermediate waypoints intepreted as intent.

In previous work [ 1 ] we showed it was possible to predict intervals which contain up to 97% of waypoints from a driver's GPS trace when a driver's route choice is based on shortest paths. We now we relax this assumption and consider the case where the driver's route choice may be based on di erent criteria. We assume that we have a model which is an abstraction of road network, which contains details of travel times and distances, tolls and road types but no other information. We present an algorithm which compares the results of a series of repeated forward and backward searches for shortest paths based on di erent cost functions which approximate di erent route choices. We evaluate the algorithm empirically using randomly generated locations from which multi-trip routes are generated by an online route planner. We demonstrate that the algorithm generates intervals in the traces which cover over 95% of the waypoints, and where the intervals cover less than 9% of the trace.

The remainder of the paper is organised as follows: Section 2 discusses related work. Our proposed approach to the problem is introduced in section 3. Section 4 describes the form of the experiments. The results of the experiments are reported in section 5 and section 6 concludes the paper. 2

Related Work

Wardrop [ 2 ] proposed that the minimization of travel time was the most important criterion in route selection and his rst principle of route choice states \the journey times on all routes actually used are equal, and less than those which would be experienced by a single vehicle on any unused route". Studies by Du el and Kalombatis [ 3 ] and Huchingson et al. [ 4 ] also found that travel time was considered to be the most important factor when deciding on which route to take. However in a more recent review of multiple studies Chen et al. [ 5 ] showed that route choice was based on more than travel time, with the driver's preferences, familiarity with the areas being travelled and other judgements also accounting for how routes were chosen. Zhu and Levinson [ 6 ] also carried out an empirical test of Wardrops's rst principle and found that the majority of people did not choose the shortest path by time.

Currently the majority of research based on prediction or inference using GPS traces revolves around destination prediction and establishing if patterns exist such as popular or heavily travelled routes in the traces being examined. These require the use of a number of di erent types of machine learning methods such as pattern recognition [ 7 ] and Hidden Markov Models [ 8 ] among others. All of these methods require the use of large amounts of historical data to build up their models and do not use a graph of the geographical area being studied. Where the inference of waypoints via creating sub-traces from the trace is used, the ultimate aim is still to predict the destination [ 9 ]. The most similar problem to the one we are tackling here is one studied by Kafsi et al [ 10 ], where the aim is to infer a set of waypoints from a GPS trace. They ignore the time component when segmenting the trace but use historical data to estimate the waypoints computing the entropy of conditional Markov trajectories. To the best of our knowledge, we are the rst to present a method for inferring waypoints where historical data is not required and we only assume that the driver is consistent in their driving style for the whole trip.

There exist a multitude of trip planners both on-line and o -line such as Google maps [ 11 ], and those built using openstreetmap data(OSM)[ 12 ] data [ 13,14 ]. Openrouteservice [ 15 ] is an open source route planner in which it is possible to create multi-point trips with di erent travel pro les or cost functions and download the trace data for the trip.

In previous work [ 1 ], we demonstrated a method for inferring waypoints using only a GPS trace and no other historical or aggregated data, where the assumption was made that the creator of the trace used shortest paths by time. The method is based on repeated forward and backwards searches using Dijkstra's algorithm [ 16 ]. The method is discussed in section 3.

Approach

Our hypotheses are { Given a multipart trajectory constructed from point-to-point trips, in an unknown driving style, the individual destinations (waypoints) can be inferred from the results of multiple simulations of di erent driving styles. { The simulated driving style which produces the fewest waypoint estimates generates a reliable estimate of the true waypoints.

Let G = (V; E; t; d; c; H; h) be a strongly connected, multi-weighted, directed graph embedded in a two-dimensional (2D) space. V is the set of vertices where each vertex is a location in the space. E is the set of directed edges (vi; vj ) where vi; vj 2 V and so each edge represents a road segment. t is a function t : E ! N+ representing the cost of traversing an edge in seconds. d is a function d : E ! N+ representing the cost of traversing an edge in miles. c is a function c : E ! N+ representing the cost of using a toll in US dollars. h is a function h : E ! H representing the type of road of the edge. H is set of di erent road types.

A trip s is a sequence of vertices and s is the last vertex in s. A multitrip M is a sequence of trips hs1; s2; :::; sj i such that si is the rst vertex in si+1. A attened multitrip is a sequence of vertices created by attening the multitrip. A trace T = hv1; v2; :::; vki is a sequence of vertices sampled in order from the attened multitrip. Given a trace our aim is to reconstruct the individual trips i.e. the endpoints hs1; s2; :::; sj 1i from the multitrip. We allow a relaxation in which our aim is to output a list of intervals h[a1; b1]; [a2; b2]; :::; [aj ; bj ]i where si is contained within [ai; bi].

For this work we de ne a driving style to be a route choice preference function using an appropriate cost function . A shortest -path is the path with the smallest cost. If is based on travel time then the least cost path will be the path that takes the least time. To accommodate inaccuracies in travel costs in our abstraction of the road network and the driver's bounded knowledge of the route taken we introduce an "-shortest -path.

De nition 1. "-shortest -path: Path P from A to B is an "-shortest -path from A to B if there is no other A, B path Q with (Q) (P) - ". De nition 2. "-shortest -path(percentage): Path P from A to B is an "-shortest -path from A to B if there is no other A, B path Q with (Q) ( 101000 " ) (P), where " is a percentage.

In our previous work [ 1 ] we presented an algorithm and demonstrated its success at inferring intervals containing waypoints when the driver was following the shortest path by time. In the current work we do not know the driving style. Instead we simulate di erent driving styles (approximated by di erent cost functions ) and infer the intervals which contain waypoints from the results of the computations. The new algorithm modi ed for a speci c cost function is // will hold the calculated sub-traces shown in Algorithm 1. The algorithm infers waypoints using two methods which are carried out sequentially. In the rst method (lines 4-15) we identify abrupt reversals of direction which would be caused by driving in to an area and leaving by the reverse route and add these to the intervals. As each point is a location in 2D space, each successive pair of points in trace T has a direction between them. Therefore we de ne a -heading change as follows De nition 3. -heading change: Di erence between heading of travel from ti 1 to ti and heading of travel from ti to ti+1 is 180 .

We then split the trace into subtraces, separated by the intervals for abrupt reversals, where each subtrace is made up of contiguous points of the trace. The second method (lines 16-24) for inferring waypoints involves searching forward through a subtrace until we nd a point B which is the rst point not on a "-shortest -path, then search backwards from B until we nd point A which is the rst point not on a "-shortest -path from B. Interval [A,B] is added to the list of intervals, and the forward search resumes from point B. When we have reached the end of the subtraces we return the list of intervals found.

Based on the results of [ 1 ] a search that uses the correct cost function should produce approximately the correct number of intervals (or fewer if one waypoint is on the shortest path between its predecessor and successor waypoints). A simulation using an incorrect cost function should introduce extra intervals to account for deviations from its shortest -path, although it is possible that it could miss a waypoint between the intervals for the same reason as above. Therefore we suspect that the cost function that returns the fewest intervals is a good estimate for the true driving style. If more than one function produces the fewest intervals we need a tiebreaker. Given a list of intervals, we assume each interval will need to be examined for places of interest, therefore we could choose wide intervals where we are more likely to nd waypoints, which we call maximum spread, or we could choose narrow intervals where the search time would be smaller at the cost of missing a waypoint, which we call minimum spread, where spread is de ned as total width of the intervals in seconds. We de ne the spread in terms of seconds since the GPS points are timestamped and we cannot compute distance travelled between GPS points. The results from both of these options will be compared in section 5. If there is still more than one function remaining then random choice will be used to select one. Other options such as selecting by the maximum spread or minimum spread initially and then using the number of estimates as a tiebreaker were implemented but gave poor results and so are not discussed further.

The pseudocode for the Waypoint Estimation Assuming No Driving Style Information is shown in Algorithm 2. The inputs are the trace T , ", , and a set of cost functions representing di erent driving styles. Initialize two lists, AK which will hold the list of each the intervals returned from each of the waypoint estimation algorithms we are interested in and K to hold the intervals which will be returned(lines 1-2). A counter C to keep track of the minimum number of intervals returned by any cost function is initialized to 1 (line 3). For each of the cost functions we return a list L of intervals (line 5). If the number of intervals is equal to C then L is added to AK (lines 6-8). If the number of intervals is less than C then AK is cleared, L added to the now empty list and C set to the number of intervals in L (lines 9-13). If AK contains only one list of intervals then set K equal to this list of intervals (line 16). If AK contains more than one list, we select the one with minimum or maximum spread. If there are still ties, we randomly select a list with minimum or maximum spread (lines 17-24). Return the list K of the intervals found (line 25).

List S = Select From AK based on either the minimum or maximum spread of the intervals in each list if size of S = 1 then

K the only list of intervals in S

list of intervals selected randomly from S

Experiments

To evaluate the algorithms we simulate routes in the city of New York. The algorithms were implemented in Java 1.8 and run on a machine using Windows 10, an i7 CPU at 2.1 GHz and 7GB of RAM dedicated to the JVM. The graph of the road network was created from OSM data. The only modi cations made were that extra nodes were added to ensure that nodes were not separated by more than 20m, and insuring that all toll information was correctly captured. The cost of each toll was obtained from the MTA [ 17 ] and the value used was the undiscounted cost for a car.

(a) Quickest route

(b) Shortest route with no tolls (c) Shortest route (d) Shortest route with no highways Fig. 1: Di erent routes for the same multi-trip depending upon the driving style 104 test trips were created, each of which contained between 0 and 10 waypoints, with an average of 4.413 waypoints per trip. The waypoints were randomly selected from the original graph data. Openrouteservice was chosen to create the test routes because of its ability to create routes with di erent combinations of route choice including avoiding tolls, avoiding highways or no restrictions along with minimizing the travel time or travel distance, and because the latitude, longitude and timestamp of points along the route could be exported via the api. The routes range in length from 2.8 to 172.9 miles with an average of 59.8 miles and had a duration ranging from 269 to 18505 seconds, with an average of 5984 seconds. These routes were then sampled so that the points occurred at a regular interval of 15 seconds so as to simulate a GPS trace. A byproduct of the sampling was that except for a few cases the actual waypoint would not appear on the trace. Figure 1 shows a map of New York with the di erent routes taken for a multi-trip beginning at the location marked A and ending at B travelling via the waypoints 1 to 6 for each of 4 di erent driving styles. Table 1 details the cost functions used to generate the test routes.

The parameters for Algorithms 1 and 2 were set as follows: the heading tolerance was set to 5 , while the allowable tolerance " was set to 5 seconds n 2% where the driving style algorithm incorporates shortest route by time and set to 0.03 miles n 2% where the driving style algorithm incorporates shortest route by distance. These values were chosen based on the rectangular street layout in the majority of New York and the approximate size of a city block. The cost functions were instantiated as follows: The penalties for passing through a toll booth when the driving style indicates that the driver avoids tolls is 10 minutes n 3 miles for each dollar of the toll cost, and the penalty for traversing an edge tagged as highway is the cost of traversing the edge multiplied by 30 regardless of cost measure. It should be noted that these are not the same as the functions used by openroutesource. For example our cost functions allow, but penalise, the use of tolls and highways while openrouteservice avoid tolls and highways. The corresponding approximate functions are shown in Table 1.

openrouteservice Cost Function Q S QNH SNH QNT SNT

Results

Q S leQNH y t S g n i v i r D e u r TSNH QNT SNT First we measure the performance of each driving style cost function in estimating waypoints for each of the true driving styles by running Algorithm 1 on each combination of driving style algorithm and true driving styles. The results are shown in Table 2. From this table it can be seen that the driving style algorithm that most closely resembles the true driving style consistently produces the smallest number of intervals as a percentage of the number of actual waypoints and that it produced the fewest (or equal fewest) intervals in at least 85% of cases. The vagueness measure is de ned as the average width of the intervals returned in seconds. We note that in some some cases a di erent driving style returns a lower value for vagueness but this is outweighed by the number of intervals returned. Other measures of performance are the precision, accuracy and recall of each driving style algorithm against the true driving style of the route. A trace contains n waypoints. A search returns m explicit intervals as predicted waypoints which gives m + 1 additional implicit intervals which predict no waypoint. We measure the number of waypoints we correctly estimate (tp), the number of waypoints we falsely estimate (f p) and the number of waypoints we miss (f n). The standard measure of accuracy does not work because the algorithm output is an arbitrary number of intervals, therefore we calculate accuracy as the number of explicit and implicit intervals which are correct (i.e. explicit intervals that contain a true waypoint, and implicit intervals that do not contain a true waypoint). The formula for precision, accuracy and recall are as follows.

P recision = tp m Accuracy = 2m + 1 f p 2m + 1

f n Recall = tp n

It can be seen that the precision, accuracy and recall are at their highest when the driving style algorithm most closely resembles the true driving style.

We now consider Algorithm 2 which considers all simulated driving styles and returns the predictions from the style that produced fewest intervals, with the results shown in Tables 3 and 4. Minimum spread shows an average reduction of 9% in vagueness for a loss of less than 1% in precision, accuracy and recall when compared to maximum spread. The average cover of minimum spread intervals represent less than 9% of the actual trace. Therefore minimum spread is the better option. Examining the results in Table 4 show that when we do not know the driving style, we can still achieve a precision greater than 93% on average and a recall greater than 95%. Thus our method can infer intermediate waypoints in a single multi-trace without knowledge of true driving style. 6

Conclusion

In this paper we have identi ed a method to infer intervals which contain waypoints from a multi-trip GPS trace without knowing the driving style of the person creating the trace, using only a graph of the area. We show the simulated driving style which is closest to the true driving style produces the highest precision, accuracy and recall for each of the true driving styles. Our algorithm is based on multiple searches, using one for each possible driving style. It then selects which to return, selecting the list with the fewest estimated intervals and breaking ties by selecting the list with the minimum spread. In empirical testing the algorithm had a recall of over 95% with a precision of over 93% on average, while the intervals on average cover less than 9% of the trace.

Future work will involve investigating an approach for inferring waypoints on a GPS trace where the driver does not follow a single driving style, but may use a combination of driving styles over the duration of their trip, and also to investigate the possibility of integrating the algorithm into data analytic methods for improving destination prediction.

Acknowledgement. This project has been funded by Science Foundation Ireland under Grant Number SFI/12/RC/2289.

References

1. D. A. Desmond , K. N. Brown. : Inferring Waypoints Using Shortest Paths . In: Proc. of the 24th Irish Conference on Arti cial Intelligence and Cognitive Science (AICS 2016 ): 45 - 56 ( 2016 )

2. J. G. Wardrop.: Some theoretical aspects of road tra c research . In: Proceedings of Institute of Civil Engineers , Part II : 325 - 378 ( 1952 )

3. J. R. Du el, A. Kalombatis.: Empirical studies of car driver route choice in Herfordshire . In: Tra c Engineering and Control 29 ( 7 /8), 398 - 408 ( 1988 )

4. R. Huchingson , R. McNees , C. Dudek .: Survey of motorist route-selection criteria . In: Transportation Research Record 643 , 45 - 48 ( 1977 )

5. Chen , T.Y. , Chang , H.L. and Tzeng , G.H. : Using a weight-assessing model to identify route choice criteria and information e ects . In: Transportation Research Part A: Policy and Practice , 35 ( 3 ): 197 - 224 . ( 2001 )

6. S. Zhu , D. Levinson .: Do People Use the Shortest Path? An Empirical Test of Wardrop's First Principle . In: Proc. of the 91st Annual Meeting of the Transportation Research Board , Washington, DC. ( 2012 )

7. Tanaka , K. , Kishino , Y. , Terada , T. , Nishio , S.: A destination prediction method using driving contexts and trajectory for car navigation systems . In: Proceedings of ACM Symposium on Applied Computing ( 2009 )

8. Alvarez-Garcia , J.A. , Ortega , J.A. , Gonzalez-Abril , L. , Velasco , F. : Trip destination prediction based on past GPS log using a hidden markov model . In: Expert Systems with Applications: An International Journal , vol. 37 ( 2010 )

9. Xue , A.Y. , Zhang , R., Zheng , Y. , Xie , X. , Huang , J. , Xu , Z. : Destination prediction by sub-trajectory synthesis and privacy protection against such prediction In: Proceedings of the 2013 IEEE International Conference on Data Engineering (ICDE 2013 ) ( 2013 )

10. Kafsi , M. , Grossglauser , M. , Thiran , P. : Traveling Salesman in Reverse: Conditional Markov Entropy for Trajectory Segmentation In: ICDM 2015 : 201 - 210 ( 2015 )

11. https://www.google.com/maps/

12. https://www.openstreetmap.org/

13. http://map.project-osrm.org/

14. https://graphhopper.com/maps/

15. https://go.openrouteservice.org/

16. Dijkstra , E.W.: A note on two problems in connexion with Graphs . In: Numerische Mathematic , 1 : 269 - 271 ( 1959 )

17. http://web.mta.info/bandt/tra c/btmain.html/