¿Where do we go? OnTheWay: A prediction system for spatial locations

¿Where do we go? OnTheWay: A prediction system for spatial locations Juan Antonio Álvarez1, Juan Antonio Ortega1, Luis González2, Francisco Velasco2, Francisco Javier Cuberos3 1 Dept. Lenguajes y Sistemas Informáticos, Univ. Sevilla. Av. Reina Mercedes s/n. 41012 Sevilla, Spain {alvarez,ortega}@lsi.us.es 2 Dept. Economía Aplicada I, University of Seville. Ramón y Cajal 1. 41018 Sevilla, Spain. {luisgon,velasco}@us.es 3 Dept. Planificación. Radio Televisión de Andalucía. José Gálvez s/n. 41092 Sevilla, Spain [email protected] Abstract. In ubiquitous computing we need to know the present context in order to interact properly with the nearby smart elements. When we are moving outdoors, mobile devices take a very important role because they provide us with a link between the world outside and ourselves through means of intelligent interfaces. There are a lot of situations in which it would be very useful to know or foresee the future context, i.e. as a geographic environment, in which we could find ourselves in a near future, and at the same time being able to use that information from our devices. Therefore we must preview this location with enough precision and time and be able to use this information from our mobile device. In our “OnTheWay” system, we used GPS technology and databases made of past paths taken by a person, in order to predict the next location, once we had begun a new course, comparing the new one with those ones stored. The results were amazing: from the data collected about paths travelled during a month and five days, we got the actual destination in 98% of cases, when we have only made a 30,35% of the total path. Therefore, including statistic and semantic information will allow us to upgrade our results, due to the sedentary human behaviour, the small number of frequently visited locations and the fact that the paths used to arrive to these locations are usually the same. 1. Introduction The information provided by indoor or outdoors positioning systems is very valuable; however it is not fully exploited. The most spread applications only provide accurate positioning in time and space of the object or person we would like to locate on earth. Some programs offer geocoded services that allow looking for buildings, roads or even taxis. Nowadays, research works are oriented towards technical aspects, like the improvement of features of performance (i.e. acquisition times, positioning accuracy) or the reduction of energy consumed by receptors. The Federal Communication Committee and the European recommendation E112 have made these researches to grow a lot allowing the wireless providers to locate accurately within a dozens of meters, users who make emergency calls E911/E112. However the applications using this information are in an early stage of development. Obtaining semantic information from wild life is being used incipiently with new applications, as in some works about tracking animals’ lives, but there are several problems, like privacy or intimacy when research is focused on human life. However, these difficulties should be a technical challenge and not a handicap. Novel ideas must be planned and the use of positioning should become an instrument, not a problem. This article explains our efforts to predict the future location of people. The work is based on their routine activities. We can realise that the principle of locality or locality of reference in computer science is valid for the human behaviour. In the most developed societies, life is lived in a sedentary and comfort ambient with moves that follow a pattern. Displacements are usually done to known places like our house, work office, the house of our family, favourite cinema or the fashionable shopping centre. These facts are repeated periodically and to get to our final destination we use different means of transport. The autonomous recognition of the destinies we go to, without the interaction of people, will open our minds to new applications with which we will know the present context and the future context. The known places and the ritual behaviour will be considered facts and our work will focus on frequently taken paths. The OnTheWay system will obtain an accurate and will foretell or foresee the place where we are going, knowing several points frequently visited and using the history of the paths taken by a person. Current work about localisation and obtaining semantic information is explained in the next section. In the development point we will describe the methodology used, called OnTheWay, the problems reported and the solutions created to avoid them. Once analysed the features of the system and the obtained results, we will illustrate the future context with some scenarios. Finally, conclusions and future work will be explained. 2. Related work Research about enhanced localisation is until now focused to identify frequently visited places. In [2], [3], [4] and [5] authors describe methods based in different technologies (GPS, GSM, WiFi) to obtain algorithms that recognise a reached place during the second and successive arrivals. The object of these works is to make easy the use of context in ubiquitous computing. If we know where we are and what smart devices surround us, we could interact with the environment. Concretely ComMotion [5] uses this information to make a spatial to-do-list associating a task-reminder to a particular location, i.e. at home, the housework to-do-list. The accuracy of the said systems is measured by the percentage of success or the correct identification of the reached place during the second and successive visits. Although results of algorithm proposed by Ashbrook and Starner’s (A&S) [2] are not so amazing as BeaconPrint’s [3], basically due to the variety of technologies used to obtain signals (first one just use GPS but the second one utilizes and tracks GPS, WiFi and GSM), the work of A&S accomplish an interesting study of future places where we could go after reach one place frequently visited. They have built a Markov model to foretell where the tracked person will go. This idea is resumed in this paper, but the prediction of possible destinations is not made when the person reaches a specific place but when he begins a new journey. Moreover the possibility to foretell in advance and accurately the places he goes are in-depth approached. In our research we have assumed the work of detecting the frequently visited places labelling them in a map through its coordinates and a textual representation of the place like we know it, i.e. we are familiar with the term “home”, but we don’t know that it corresponds to the coordinates 37°22'55.98"N, 5°58'14.20"W. On the other hand, when tracking wild animal life projects like [1], [6], [7] and [10] positioning technology to store the journeys and extract information about animal behaviour is used. Concretely in ZebraNet [6] project, unknown information until now has been obtained. Biologists know now that zebras explore more wooded areas and gullies at night. Although it is not intended to track human life, it is obvious that their way of moving allow the creation of interesting and useful applications which could manage future situations obtained from predicted contexts. 3. Development Firstly, scope and used terms will be defined; next the used methodology there will be described. 3.1. Scope of the problem OnTheWay proposal is based on the similarity of journeys to foretell the place where we are going when we begin a new path. This problem depends on the spatial dimension of the course so temporal dimension will be put away because it will increase the difficulty of our problem (e.g. a journey by car compared temporally to the same path by bicycle will be temporally very different). Elected option for avoid this, was a sampling used to acquire the spatial data with a temporal frequency of one second. On this way, graphical representation will be simplified too from three to two dimensions (longitude and latitude). 3.2. Terms definition Concepts will be simplified on defining the next terms: Point: Tuple composed by their geographical values of longitude and latitude. p=(long, lat) Place: Tuple composed by a point and a radius. Both define a circumference centred on the origin of the place. The third element is a label representing the semantic information about this place (“home”, “work”, etc.) L=(p, radius, label) Current path or current journey: Set of points obtained sampling the geographic coordinates using the positioning system. In our case was GPS (Global Positioning System). These points are validated by this system, satisfying the correct number of satellites that allow obtain an accurate position. The points of the current path are separated by not less than 30 meters to avoid redundant information. X={ p0, p1, …, pn } Class: Given a place origin A and another destination B. A class will be defined as the pair A-B or B-A. Although the path from A to B will probably different, we will suppose the same class to reduce the number of journeys needed to train the system. Labelled path: Given a finished path, it will be labelled with it class. XA-B=X|A=(P,radius1,origin) ^ B=(Q,radius2,destination) Distance between points: Although in the cities the distances are considered using the Manhattan distance, OnTheWay system uses the great-circle distance based on the spherical geometry and very important for finding the shortest distance between points on the surface of the Earth. To express it between two points it will be notated: dist(pi,qj). Scope of a path: Given a labelled path XA-B ={ p0, p1, …, pn} and a point q, this point will belongs to the scope of the path if there exists some point of the path which distance to q is less than a given value of δ: q ∈ scope(XA-B), if ∃ j | dist(pi,q)≤ δ. On our work we have determined that δ =85 meters is an acceptable distance to consider. A point will be on the scope of a path if it belongs to the region generated on the image. Image 1: Generating the scope of a path Canonical path or representative: Given a set of labelled paths with the same class, we will choose one of more paths from this set to represent in an accurate manner the others. The reliability will be given by the percentage of points that belongs to the scope of this path. The more paths from the class are enclosed by a canonical path, the better representative is it. Because there could be different paths used to do a journey from A to B, more than one canonical will be accepted to represent each class. Similarity of paths: A path matches with other if it has a percentage of points from their total that belong to the scope of the second one. Similarity level will be expressed on the next manner: Given XA-B ={ p0, p1, …, pn } ^ YC-D ={ q0, q1, …, qm} Similarity(XA-B YC-D)=100*(Number of qi ∈ scope(XA-B))/m) Hence, given XA-B ={ p0, p1, …, pn } ^ Y ={ q0, q1, …, qm} Y will be identical to XA-B if ∀ i, qi ∈ scope(XA-B) and Y is labelled with the class A-B so it is a labelled path: YA-B Because number of points of two paths is not the same, the features are not commutative. Given X={ p0, p1, …, pn } ^ Y={ q0, q1, …, qm } similarity(X,Y)= similarity(Y,X) only if n=m. Image 2 shows an example of four journeys on Seville, X1A-B, X2A-B (both on the left of image), X3B-A and X4A-B (both on the right). Image 2: Four paths from A to B All of the paths are from the class A-B. Although the places origin and destination of all are the same, for a correct tagged, OnTheWay should take two canonical paths, the first one for represent two on the right and the other for represent the two on the left. Section called selection of canonical will describe the manner to take the canonical paths. 3.3. Methodology The image 3 describes the used methodology to obtain our objective, identify the probable destinations where we will go when we begin a path. Image 3: Methodology 3.3.1. Data retrieval Data retrieval was done by a member of the group during the period from December 10th, 2005 and January 14th, 2006. The journeys were tracked in the cities of Sevilla (31 days), Almeria (3 days) and Granada (1 day). Data obtained from Granada was insufficient to any prediction but the tracked paths on Sevilla and Almeria were very useful. 103 tracked paths were obtained. To achieve this set of routes, a Royaltek Bluetooth GPS was used. Due to the impossibility of storing these tracked paths on the device, a Dell Axim X30 PDA was used to store the routes on NMEA format. The vehicles used were only bicycles and cars. 3.3.2. Labelled When the destination was reached, the NMEA file was renamed including the date and time of the journey, the origin and the destination. Moreover, the file was transformed to KML format, used by the GoogleEarth software to obtain an easy and fast representation. On the conversion, unreliable or erroneous points were filtered. 3.3.3. Data cleaning and bizarre paths Two kinds of problems were distinguished on the Data retrieval process: some derived from the GPS technology and others derived from the real experience. On-line results Canonical Non canonical Data retrieval Labelled Learning set Current path Data cleaning Canonical paths selection Off-line results GPS technology: • First valid GPS point: The validation system of GPS takes some time to obtain the first correct point. If the receiver is still, the duration is about 1 minute. If the receiver is in movement the duration could be much more. On the collection of data, the first valid point sometimes was very far on space and time from the real origin of the journey. Despite this, the path was tagged with the real origin (not the first validated) and destination. These paths would not be a canonical path because the canonical ones must represent with fidelity the real path. So we need a rule to select it checking that initial and finals points are close to the real places of origin and destination. • “Urban canyon” effect: The global positioning satellite signal cannot be received by the receiver if it is surrounded by tall buildings or hills. It causes interruptions of validated positions during a variable time. So it reduces the number of correct points on the track file. Although the cities where the Data retrieval did not have skyscrapers or lots of tunnels, the effect was observed on narrow roads. Because of this, we add a new rule to discriminate canonical paths from non canonical ones: Each couple of points composed by one point and the next one, have to be near. If the distance between them is more than the advanced in a car the points will not be close. Data sampling interval is 1 second in our Royaltek GPS and it was considered the possibility of having one point not validated between two NMEA validated, so due to the speed limit is 120 k.p.h. in most countries, the distance considered was 66,7 meters. Real experience: In Data retrieval and the labelling process, problematic situations that could alter the selection of canonical paths were found. The main problem occurred when it was difficult to find a place to park the car during a journey.. That caused the driver to become stressed-out and the increase of points collected on the surroundings of the destination place. The selection of this kind of journeys and their associated paths as canonical paths would be an error because another path would not be similar to this one even if their origins and destinations were the same. So we add another rule that specifies that if there are two paths that satisfy the last two rules, we will take the one that has fewer points. After having verified the tagged paths, 7 were discarded because their results were totally erroneous or nonsense. So it rested 96 with checked information including the ones that had the features explained. 3.3.4. Canonical paths selection Given a set of labelled paths from the place origin=(o, r1,A) to the place destination=(d,r2,B), X0 A-B X1 A-B ... Xn A-B the selection of a canonical path Xc A-B ={ p0, p1, …, pm} | 0 ≤ c ≤ n will be done following the next rules: 1. Nearby to origin and destination ∀ i ∈ [0,k], dist(pi, o) ≤ r1 ^ ∀ i ∈ [m-k,m], dist(pi, d) ≤ r2 2. Uniform distribution: ∀ i ∈ [0,n) dist(pi, pi+1) ≤ 66,7 meters. If there is more than one candidate path to be canonical and their points don’t satisfy this rule, it will be taken the one with less points that not fulfil the rule. 3. Distinguish rules for some canonical paths. a. Less number of points: If XiA-B XjA-B satisfy the rules 1 and 2 and similarity(Xi A-B Xj A-B)>80, then it would be selected the one with less points. b. If XcA-B is a canonical path and we found another path Xi A-B | similarity(Xc A-B Xi A-B)<80, then we will consider XiA-B also as a representative. c. If there did not exist any canonical path for an origin and a destination, the first path with this origin and destination will be considered as a canonical. After applying this rules to the learning set of paths, we obtained 44 canonical paths and 52 non canonical. 3.3.5. Off-line results Once the set of canonical paths were obtained, legitimacy of the methodology was checked comparing the sets of representative and non-canonical paths. The goal was to predict the destination where the non-canonical path went to. So for a noncanonical path, his similarity index was obtained for all the canonicals, and the one that produces the greater index was selected. We compare the destination from the selected canonical path with the real destination of the non-canonical path. The results were correct in 51 of 52 cases. The incorrect case was because a canonical path was not selected when it should. These results showed us the strength of the methodology and the importance of the selection of the canonical paths. Due to the good results obtained in the off-line mode, we faced the task of obtaining the point where the correct prediction begins. 3.3.6. On-line results. Having checked the similarity index with all the canonicals over all the points of the non-canonical path, the predicted destination in each point was obtained. The point when the real destination was predicted not being altered until the end of the path, was called detection point. Results were coherent with common sense: Until the itinerary did not enter in a not common area with other paths, it was impossible to distinguish where we go. Nonetheless, we also observed that although there were overstrike paths, frequently small changes taken on the paths allowed the OnTheWay system to distinguish the correct destination. The results were very hopeful because the remaining distance to the destination measured in a straight line, on average was the 69,65% of the total path and the remaining time to reach the destination was more than the 70% of the total (when the journey finally stops). Destination detection 0 5 10 15 20 25 (1,10] (10,20] (20,40] (40,60] (60,80] (80,90] (90,100] % of remaining distance Number of paths Image 4: On-line results It was considered that a new detection point that remained stable for some meters, could be defined as a decision point. The spatial pertinent value seemed to be 120 meters. This value adds these amount of time and space to the decision point, being specially harmful for the paths in which the decision arrived very late (cases on the left of the graphic where the remaining distance to reach the destination is less than the 10% of the total distance path), as it causes the arrival to the destination comes before we can predict it. However, the capacity to predict future context can be very helpful as it is shown in the next section. 4. Scenarios To illustrate the power of OnTheWay system, possible scenarios will be shown where the prediction of destinations is helpful. Management of alerts: The possibility to track person movements can be very useful (e.g. in the case of Alzheimer or Schizophrenic) when someone gets lost in an external environment. It is possible to track and compare usual routes with current ones and decide to send an alarm before the situation might put the person in risky situations. Future interest zones: Predicting that our destination is the place C, our system could track the buildings associated to our to-do-list. It could give us notice of the routes to reach marketplaces, chemist’s or civil service buildings before going to C. Tourist information: Saving the frequent tourist’s journeys, the optimisation of new visits could be possible: Information about the best path, the fastest transport to use or the timetable of museums where the tourist wants to go could be notified when the destination has been predicted. Providing the same help to civil service could be helpful for citizens. Prediction of traffic jams: If the probable destination of a set of motorists is actually the same and their paths pass by the same point, then calculating the number of cars that can pass in an hour, the OnTheWay system applied to all the GPS of these