Patent Publication Number: US-8543320-B2

Title: Inferring a behavioral state of a vehicle

Description:
BACKGROUND 
     Cities on this planet are facing immense challenges with continually increasing population growth. Urbanization is increasing at a faster pace than ever in many developing countries, while some modern cities in developed countries are engaging in reconstruction, urban renewal, and suburbanization. These phenomenal changes are posing severe challenges for fragile urban transportation systems and effective land use planning. 
     SUMMARY 
     In one example, trajectory data representing tracked positions of a vehicle along a trajectory having a start and end point is accessed. The trajectory data may include spatio-temporal information about the vehicle at different points along the trajectory. The trajectory may be divided into segments based, at least in part, on knowledge of inferred-parking locations. The segments may be map-matched to corresponding road segments. Additionally, historical data representing spatio-temporal travel patterns of vehicles learned from historical trajectories of vehicles corresponding to the map-matched-road segments may also be accessed. A behavioral state of the vehicle for a segment or position within a segment may be inferred, based, at least in part, on (i) the vehicle&#39;s spatio-temporal information corresponding to the segment or position within a segment, (ii) knowledge of the map-matched-road segment, and (iii) the historical data. 
     This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter. The term “techniques,” for instance, may refer to device(s), system(s), method(s) and/or computer-readable instructions as permitted by the context above and throughout the document. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The detailed description is described with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the drawings to reference like features and components. Drawings are not drawn to scale. 
         FIG. 1  illustrates an example environment in which a behavior state of a vehicle may be inferred. 
         FIG. 2  is a block diagram illustrating select components of an example computer that is configured to infer a behavioral state of a vehicle in the example architecture of  FIG. 1 . 
         FIG. 3  illustrates select components of an example inference module from the computer of  FIG. 2 . 
         FIG. 4  shows a trajectory of an example vehicle (here, a taxi) after the inference module has automatically inferred behavior states of the taxi. 
         FIG. 5  shows an example architecture for implementing an inference module. 
         FIGS. 6A ,  6 B,  6 C, and  6 D illustrate logical representations of a density-based-clustering algorithm. 
         FIGS. 7A and 7B  illustrate logical representations of a filtering algorithm to reduce false positives of parking-place locations. 
         FIG. 8  shows charts showing emission probabilities, learned from the labeled trajectories, of two road segments of levels  1  and  2 , respectively. 
         FIG. 9  shows an example knowledge-road graph. 
         FIG. 10  illustrates an example method for inferring the behavior state of a vehicle, such as a taxi. 
     
    
    
     DETAILED DESCRIPTION 
     Described herein are techniques to automatically infer the behavioral state of passenger-transportation vehicles, such as taxis. Specifically, in one example, an inference is made whether a taxi is occupied (i.e., transporting at least one passenger), unoccupied (i.e., operating with no passengers), or is parked. By inferring particular-behavioral states of a vehicle, it is possible to more accurately sense traffic flow and mobility patterns of people in an urban environment, among other uses. 
     In one embodiment, a taxi equipped with a navigation system tracks the position of the taxi. The tracked position of the taxi is recorded at regular intervals revealing trajectories of the taxi. Specifically, the time of day, direction, speed, and location of the taxi at different points along the trajectories are recorded. The recorded data is then analyzed to deduce what behavioral states the taxi is in while traversing an urban area. 
     In one aspect, when attempting to understand traffic flows and mobility patterns of people, trajectories of taxis transporting passengers are analyzed in lieu of trajectories representing taxis in an unoccupied state (i.e., not transporting at least one passenger). Analyzing trajectories of taxis transporting passengers reveal traffic flows and mobility of passengers more accurately than trajectories of taxis in an unoccupied state. For instance, taxis searching for a fare typically drive slower than taxis transporting a passenger, even if traffic conditions allow for faster speeds. Further, taxis searching for a fare often drive in patterns not necessarily reflective of mobility patterns of people. 
     On the other hand, understanding when a taxi is unoccupied can help taxi companies conserve energy and resources. For example, a taxi dispatcher can send a passenger&#39;s pick-up request to unoccupied taxis rather than all taxis. 
     Additionally, by automatically inferring the state of a taxi, the fleet operator of a taxi company is able to monitor not only the movement of each taxi but also identify higher-performing and poorer-performing drivers, based on understanding which drivers&#39; taxis have a higher proportion of recorded operation while in an occupied state than those in an unoccupied state. 
     Still further, awareness of the state of a taxi can be relied on to facilitate context-aware computing. For instance, some location-based advertisement can be pushed to a taxi only when it has passengers. Also, the fleet operator of a taxi company may identify drivers who provide passengers rides without charging a fare, or who pocket a fare without accounting to the taxi company. 
     So, by understanding the state of a taxi—such as, whether occupied, unoccupied, or parked—it is possible to sense traffic flow and mobility of vehicles in an urban environment. Knowledge of the state of taxis may also facilitate better management of taxis, and for performing other acts, such as pushing content to the vehicle, only when the vehicle is occupied. 
     Although some of the discussion herein focuses on behavioral states of taxis as the sample vehicle, methodologies and principles described herein are not necessarily limited to taxis, and may be applied to other vehicles to infer different behavioral states. 
       FIG. 1  illustrates an example environment  100  within which a behavior state of a vehicle may be inferred, such as whether the vehicle is transporting a passenger, operating without passengers, or is waiting at a parking location. Example environment  100  includes vehicles  102 ( 1 ),  102 ( 2 ), . . .  102 (N). 
     Each vehicle, referred to generally as reference number  102 , may be equipped with a transmitting device  104 ( 1 ),  104 ( 2 ), . . .  104 (N) on or inside vehicle  102 . Examples of a transmitting device, referred to generally as reference number  104 , may include, but are not limited to, a portable Global Positioning System (GPS) device, a mobile-computing device, a mobile phone, passive or active radio transmitters, and an in-car-navigation system. 
     Each transmitting device  104  tracks the position of a vehicle. Specifically, each transmitting device  104  records spatio-temporal data  110 ( 1 ),  110 ( 2 ), . . . ,  110 (N), respectively, indicating the history of a vehicle&#39;s speed, position, and time at various points along the vehicle&#39;s trajectory. The spatio-temporal data is also referred to interchangeably throughout this disclosure as “trajectory data.” 
     Each transmitting device  104  records spatio-temporal data  110  by communicating with a GPS system  106 , or any satellite-positioning system. In another embodiment, transmitting devices  104  may communicate with other suitable location-tracking technology, such as Radio-frequency identification (RFID) systems (not shown). 
     In one embodiment, each transmitting device  104  transmits tracked positions of a vehicle, such as the spatio-temporal data  110 , to memory  112  accessible by a computer  108 . For example, spatio-temporal data  110  may be transmitted over a network  114  to memory  112 . Network  114  may be any type of communication network, including, but not limited to, the Internet, a wide-area network, a local-area network, a satellite communication network, a cellular-telephone-communications network, or a communications interface, or a combination of the foregoing. Alternatively, spatio-temporal data  110  may be transmitted to an intermediary device (e.g., a universal serial bus (USB) storage device), which is then used to transfer the data to a computer  108  or other intermediary devices. 
       FIG. 2  is a block diagram illustrating select components of an example computer  108  that is configured to infer a behavioral state of a vehicle in the example architecture  100  of  FIG. 1 . Computer  108  may represent any suitable computing device having one or more processors  202  and the ability to access memory  112 . Examples of computer  108  may include, but are not limited to, a personal computer, a mobile computer, notepad, server, or distributed-computer systems. Further, although not shown, any number of system busses, communication and peripheral interfaces, input/output devices, and other devices may be included in computer  108 , as appreciated by those skilled in the art. 
     Memory  112  may include any suitable computer-storage media including volatile and non-volatile memory, and any combination thereof. For example, computer storage media includes volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other non-transmission medium that can be used to store information for access by a computing device. 
     In contrast, communication media may embody computer readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave, or other transmission mechanism. As defined herein, computer-storage media does not include communication media. 
     Further, memory  112  may be local and/or offsite to computer  108 . For instance, one or more portions of, or all of spatio-temporal data  110  stored in memory  112 , may be accessed from a computer-storage medium local to computer  108  and/or remote (not shown) to computer  108 , such as from a storage medium connected to network  114 . 
     Resident in memory  112  are one or more operating systems  204 , and any number of other program applications  206 , which are executed on processor  202  to enable processing of spatio-temporal data  110  or other functionality. 
     A file system  208  may reside as a component in the form of computer-executable instructions and/or logic within memory  112 , that when executed serves as a logical interface between code stored in memory  112 . File system  208  may also assist in storing, retrieving, organizing files, and performing other related tasks associated with code and/or data. That is, file system  208  has the ability to read, write, erase, and manage files. 
     Resident in and/or accessible to computer  108  is an inference module  210  configured to automatically infer a behavioral state of a vehicle at different tracked positions along a historical trajectory of a vehicle, based in part, on spatio-temporal data  110  accessed from memory  112 . Although illustrated in  FIG. 2  as being stored in memory  112  of computer  108 , inference module  210 , or portions thereof, may be implemented using any form of computer-readable media accessible by computer  108 . 
     For example, inference module  210  may be implemented as code in the form of computer-readable instructions that execute on one or more processors  202 . For purposes of illustration, programs and other executable-program modules are illustrated herein as discrete blocks, although it is recognized that such programs and components may reside at various times in different storage components. Further, such code may be implemented as one or more applications or modules, or may be integrated as components within a single application. 
     In one embodiment, inference module  210 , infers behavior states of a taxi, which may include a parking state (P), an occupied state (O) (i.e., transporting a passenger), or an unoccupied state, also referred to as non-occupied (N), (i.e., not transporting a passenger). Again, inferring behavior states of a taxi contributes to identifying the real mobility of people, and the estimation of real-time traffic flows on road surfaces. Other potential features, not repeated here, may be realized as mentioned above and herein. 
     Introductory Terminology 
     Before discussing inference module  210  in more detail, below is an introduction to some terminology used in this disclosure. 
     “Road Segment (r)” refers to a directed edge that is associated with a direction symbol (r.dir, one-way or two-way), two terminal points (r.s, r.e), and a list of intermediate points describing the segment using a polyline. Additional information is maintained for each road segment: level (r.level) and length (r.length). For example, a highway&#39;s level is usually 0 and that of a ring road in a city is 1. 
     “Road Network (G r )” refers to a directed graph, G r =(V r , E r ), where E r  is the set of edges representing road segments, and V r  is a collection of terminal points of corresponding road segments. 
     “A taxi trajectory (Taxi Trajectory (Traj)”—also referred to as a “trajectory”—is denoted as a sequence of GPS points (or location points), i.e., Traj: p 1 →p 2 → . . . →p n . Each point is represented as p i =(l, t, v, s), where l denotes the location of a taxi at time t, travelling with (instantaneous) speed of v, and given state s. Note again that the state s of a taxi may be occupied (O), not-occupied (N), or parked (P). 
     Given a trajectory, Traj: p 1 →p 2 → . . . →p n , a “Parking Location (Pk)” (also referred to as a “parking place”) is a sub-trajectory Traj: p i → . . . →p j , which satisfies the conditions where ∀kε[i, j), distance(p k , p k+1 )&lt;δ, t j −t i &gt;τ and speed(p i )&lt;ε. Thus, a parking location may include any location in which a taxi has stayed and/or queued for a while with the intention to eventually pick-up a passenger, or it may also indicate a situation when a taxi driver is taking a break. Thus, a “parking location,” as used herein is not merely limited to a parking lot or parking garage. A “taxi segment” is a sub-trajectory between two parking places. A taxi segment could contain one or more trips. In other words, each segment includes one or more sub-trajectories between two parking locations. 
     Example Inference Module 
       FIG. 3  illustrates select components of an example inference module  210 . Example inference module  210  includes a trajectory-analyzer module  302 , a map-matching module  304 , and a historical-inference module  306 . On the right hand side of  FIG. 3  are logical views representing data and operations performed by each module. The logical views are for example purposes. The order in which each view is described is not intended to be construed as a limitation, and any number of the described operations associated with each module can be combined in any order. Additionally, some steps may be deleted from the logical operation without departing from the spirit and scope of the subject matter described herein 
     As depicted in  FIG. 3 , trajectory-analyzer module  302  analyzes trajectory data  110  representing tracked positions of a vehicle along a trajectory  308  having a start point S and end point D. The raw data is represented logically in view A. 
     That is, trajectory data  110  is raw in view A, and does not provide an indication as to the behavioral state s of the vehicle such as P, N, or O. Trajectory data  110  may include spatio-temporal information indicating a vehicle&#39;s speed, position, and time at various points along the vehicle&#39;s trajectory  308 . 
     Trajectory-analyzer module  302  may also identify one or more potential parking locations P of a vehicle along a trajectory as depicted in view B, and then parses the trajectory into taxi segments S  312  based (as depicted in view C of  FIG. 3 ), at least in part, on the knowledge of the identified parking locations P. As shown in view C each taxi segment S  312  may include a plurality of different trips  314  within a segment  312 , with multiple states yet to be determined. 
     As depicted in view D, map-matching module  504  maps the identified taxi segments or sub-segments to corresponding road networks or road segments within a road network. By using the mapped knowledge from geographical information related to each road network and point-of-interest (POI) such as a hospital  316  or park  318 , it is possible to assign inference data to each taxi segment. For instance in one example, metadata may be assigned to a road network, including but not limited to, a (i) value associated with a highway indicative that a taxi cannot drop off or pickup passengers on the highway, or (ii) a value associated with road segments proximal to a POI or commercial area that a taxi is more likely than not to pick-up a passengers near these POIs or commercial areas. 
     As depicted in view E, historical-inference module  506  may access historical data representing spatio-temporal-travel patterns of vehicles learned from historical trajectories of vehicles corresponding to the map-matched-road segments. Additionally, historical-interface module  506  may mine other aspects of knowledge from historical trajectories, such as a passengers&#39; travel patterns. That is, how long a passenger usually occupies a taxi, P(O→N|ΔT), and how long a taxi would be non-occupied until picking up a passenger, P(N→O|ΔT). Still further, historical-interface module  506  may access other aspects of knowledge from historical trajectories including a prior probability of a taxi being in a state, N or O, on a road segment. Specifically, historical-interface module  506  may map historical-taxi trajectories to a road network, and perform a statistical learning on the historical-taxi trajectories to obtain prior probabilities of a state on a road segment r i , e.g., P(N|r i ) and P(O|r i ), and the transition probabilities between N and O given the taxi&#39;s transition between two road segments r i  and r j , i.e., P(N→O|r i →r j ) and P(O→N|r i →r j ). Note that, the temporal information is also considered in these aspects of knowledge, e.g., P(O→N|ΔT, t), P(N|r, t) and P(N→O|r i →r j , t), where t is a timestamp. 
     However, due to limited coverage of the labeled datasets, there may not be sufficient samples (GPS points) for computing the priors for each road segment. For example, it is not possible to claim P(O|r)=1 if there are only two GPS points with a state of O on r. To address this problem, historical-interface module  506  may use a clustering algorithm (explained in more detail below), which groups similar road segments according to a road segment&#39;s physical features, such as length, in/out-degrees, and the POI distribution along the road. Because road segments from the same cluster may have similar pick-up and drop-off possibilities, it is possible to calculate the probabilities like P(N|r) based on the samples aggregated from all the road segments in the cluster C, rεC. 
     P(N|C) is used to represent the probabilities of each road segment in C. Also, the transition probabilities, such as P(O→N|r i →r j ), are replaced by P(O→N|C i →C j ), where r i εC i  and r j εC j . A knowledge road graph may be built, where a node is a cluster of road segments and an edge is the transition probability between the clusters. 
     Thus, with the benefit of a learned road graph and travel patterns, it is possible for inference module  210  to serve as a probabilistic-inference model, which infers the behavior states of with each point in a taxi segment by choosing the sequence with a maximum probability. 
       FIG. 4  shows a trajectory  110  of a taxi after inference module  210 , automatically infers behavior states for the taxi. As depicted in  FIG. 4 , inference module  210  determined that a taxi first sent passengers to a location X, then drove to a parking location in an unoccupied state N. After waiting for a while, the taxi took another passenger(s) to the location Y, and maintained its non-occupied state N until reaching a location Z, where the taxi picked up passengers again. 
       FIG. 5  shows an example architecture for implementing an interference module  210  such as depicted in  FIGS. 3 and 4  and described herein. As shown in  FIG. 5 , inference module  210  analyzes data from three different levels: Level  1 , Level  2 , and Level  3 . More or less levels of analysis may be used as would be appreciated by those skilled in the art with the benefit of this disclosure. 
     As depicted in  FIG. 5 , Level  1 : (i) determines basic spatio-temporal information of a trajectory to be inferred, (ii) detects parking states, and (iii) reduces the complexity of an overall inference by partitioning a taxi trajectory into some short segments based on detected parking places. 
     Level  2  maps taxi segments to corresponding road segments (also known as “map-matching”), and analyzes the probability of the taxi being in state N and O on these road segments. Intuitively, map-matching implies commonsense knowledge supporting an inference. For example, taxis cannot drop or pick up passengers on a high way, and taxis are more likely to pick up passengers on some road segments close to commercial areas. 
     Level  3  mines two aspects of knowledge (data) from historical trajectories with state labels. The first-knowledge aspect mined from historical trajectories is taxis and passengers&#39; travel patterns. The second-knowledge aspect mined from historical trajectories is the prior probability of a taxi being a state, N or O, on a road segment. More specifically, the historical taxi trajectories are mapped to the road network, and a statistical learning on the historical data is learned to obtain the prior probabilities of a state on a road segment r i , e.g., P(N|r i ) and P(O|r i ), and the transition probabilities between N and O given the taxi&#39;s transition between two road segments r i  and r j , i.e., P(N→O|r i →r j ) and P(O→N|r i →r j ). Note that, the temporal information is also considered in these aspects of knowledge, e.g., P(O→N|ΔT, t), P(N|r, t) and P(N→O|r i →r j , t), where t is a discretized timestamp. 
     Again, due to limited coverage of a labeled dataset, each road segment may not have sufficient samples (GPS points) for computing the priors. For example, it may be difficult to claim P(O|r)=1 if there are only two GPS points with a state of O on r. To address this problem, a clustering algorithm (explained below) may be performed. The clustering algorithm groups similar road segments according to a road segment&#39;s physical features, such as length, in/out-degrees and the POI distribution along the road. With the knowledge-road graph and travel patterns, a probabilistic inference model  210  may be implemented, that infers the states of each point in a taxi segment by choosing the sequence with the maximum probability of being occupied, not occupied or parked. 
     Example Parking-Place Detection 
     As described above, trajectory-analyzer module  302  ( FIG. 3 ) (and level  1  of  FIG. 5 ) performs parking-place candidates. In one embodiment, a density-based-clustering algorithm may be used to fully or partially implement trajectory-analyzer module  302 .  FIGS. 6A ,  6 B,  6 C, and  6 D illustrate a logical representation of a density-based-clustering algorithm. Further, a process flow for an example density-based clustering algorithm is shown in Table 1 below. 
     
       
         
           
               
             
               
                 TABLE 1 
               
               
                   
               
               
                 ParkingPlaceDetection (G r , Traj, δ, τ, ε) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                   
                 Input: A road network G r , a trajectory Traj, distance 
               
               
                   
                 threshold δ, time threshold τ and speed threshold ε. 
               
               
                   
                 Output: A set of candidate parking place Pk = {c} 
               
            
           
           
               
               
               
            
               
                   
                  1. 
                 i ← 0, M ← |Traj|, c ← Ø, Pk ← Ø; 
               
               
                   
                  2. 
                 while i &lt; (M − 1) do 
               
            
           
           
               
               
               
               
            
               
                   
                  3. 
                 | 
                 if (p i .v &gt; ε) then 
               
            
           
           
               
               
               
               
            
               
                   
                  4. 
                 | 
                 i ← i + 1; continue; 
               
            
           
           
               
               
               
               
            
               
                   
                  5. 
                 | 
                 j ← i + 1; flag ← false; 
               
               
                   
                  6. 
                 | 
                 while j &lt; M do 
               
            
           
           
               
               
               
               
               
            
               
                   
                  7. 
                 | 
                 | 
                 dist ← Distance (p i , p j ); 
               
               
                   
                  8. 
                 | 
                 | 
                 if dist &lt; δ and p j .v &lt; ε then 
               
               
                   
                  9. 
                 | 
                 └ 
                   j ← j + 1; flag ← true; 
               
               
                   
                 10. 
                 | 
                   
                 else break; 
               
            
           
           
               
               
               
               
            
               
                   
                 11. 
                 | 
                 if (p j−1 .t − p i .t) &gt; τ and flag = true 
               
            
           
           
               
               
               
               
               
            
               
                   
                 12. 
                 | 
                 └ 
                 foreach point p ε Traj[i,j)    p ∉ Pk do 
               
            
           
           
               
               
               
               
            
               
                   
                 13. 
                 └ 
                   c.Add (p); //build a candidate place 
               
            
           
           
               
               
               
            
               
                   
                 14. 
                 if i = (j − 1) then 
               
            
           
           
               
               
               
            
               
                   
                 16. 
                 Pk.Add(c); c ← Ø; //a parking 
               
            
           
           
               
               
               
            
               
                   
                 15. 
                 i ← i + 1; 
               
            
           
           
               
               
               
            
               
                   
                 16. 
                 return Pk; 
               
               
                   
               
            
           
         
       
     
     Filtering of false candidates caused by traffic jams or traffic lights from the candidate set determined by the density-based-clustering algorithm may be performed, after a density-based-clustering algorithm (or suitable alternative process) is performed. A logical representation of an example filtering algorithm is depicted in  FIGS. 7A and 7B . An example process flow for the filtering algorithm is shown in Table 2 below. 
     
       
         
           
               
             
               
                 TABLE 2 
               
               
                   
               
               
                 FilterParking (Pk, G r , γ) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                   
                 Input: A set of candidate Parking places Pk, Road 
               
               
                   
                     Network G r , and a ratio threshold γ, 
               
               
                   
                 Output: A real parking place collection Pk = {c}. 
               
            
           
           
               
               
               
            
               
                   
                  1. 
                 Index←SpatialIndexing (G r );  
               
               
                   
                  2. 
                 foreach candidate parking place c ∈ Pk; 
               
            
           
           
               
               
               
               
            
               
                   
                  3 
                 | 
                 MBR c  ← MinimalBoundingRect(c); 
               
               
                   
                  4. 
                 | 
                 R ← search(Index, MBR c , l); 
               
               
                   
                   
                 | 
                 //find the road segments of level l 
               
               
                   
                   
                 | 
                 // and intersecting MBR c ; 
               
               
                   
                  5. 
                 | 
                 foreach road segment r ∈ R 
               
            
           
           
               
               
               
               
               
            
               
                   
                  6. 
                 | 
                 | 
                 Θ ← the points p ∈ r and inside MBR c ; 
               
               
                   
                  7. 
                 | 
                 | 
                 MBR r  ← MinimalBoudingRect(Θ); 
               
               
                   
                   
               
               
                   
                  8. 
                 | 
                 | 
                 
                   
                     
                       
                         
                           
                             Compute 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             Γ 
                           
                           ← 
                           
                             
                               area 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   MBR 
                                   r 
                                 
                                 ) 
                               
                             
                             
                               area 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   MBR 
                                   c 
                                 
                                 ) 
                               
                             
                           
                         
                         ; 
                       
                     
                   
                 
               
               
                   
                   
               
               
                   
                  9. 
                 — 
                 | 
                 if (Γ &gt; γ) then 
               
            
           
           
               
               
               
               
               
               
            
               
                   
                 10. 
                   
                 — 
                   
                 Pk · remove (c); break; 
               
            
           
           
               
               
               
               
            
               
                   
                 11. 
                   
                 return Pk; 
               
               
                   
                   
               
            
           
         
       
     
     The density-based-clustering algorithm will now be explained in more detail.  FIGS. 6A ,  6 B,  6 C, and  6 D illustrate a parking place candidate detection algorithm that may be used trajectory-analyzer module  302 . Suppose there is a taxi trajectory (p 1 →p 2 → . . . →p 7 ). First, a speed is checked at each point, and the distance between consecutive points until both values (speed and distance) are smaller than a corresponding threshold. 
     As depicted in  FIG. 6B , p 1  and p 2  cannot formulate a parking place as the distance between them dist(p 1 , p 2 ) exceeds the corresponding threshold δ. Next, p 2  is analyzed to find that dist(p 2 , p 3 )&lt;δ, dist(p 2 , p 4 )&lt;δ while dist(p 2 , p 5 )&gt;δ ( FIG. 6C )). If the speed values of these three points are less than the threshold and the time interval between p 2 .t and p 4 .t is larger than the time threshold τ, the three points form a small cluster represent a parking place candidate. 
     However, the points might not represent an entire set of the points in this parking place. Therefore, the parking-place-candidate points are expanded by continuously checking a distance between p 3  and the remaining points in the trajectory (p 4 , p 5 , p 6 , p 7 ). As depicted in  FIG. 6D , p 5  and p 6  are added into the parking set, because they also meet the speed, distance, and time interval constraints. Finally, points (p 2 , p 3 , p 4 , p 5 , p 6 ) are detected as a parking-place candidate because the cluster cannot be expanded further, i.e., all the points in the cluster have a distance farther than δ to p 7 . 
     As shown, an example suitable algorithm detects locations where the GPS points of a taxi are densely clustered, with spatial, temporal and speed constraints. The example algorithm can detect locations where a taxi remains stationary, such as a taxi stand, and the queue-structured regions in which a taxi keeps on moving forward slowly, like a taxi queue in an airport. 
     However, a parking-place candidate may sometimes correspond to taxis stuck in traffic jams, or waiting for signals at a traffic light, instead of a parking location. To reduce such false positives, a filtering algorithm may be used that differentiates between real-parking places close to a street from the above-mentioned scenarios, as illustrated in  FIGS. 7A and 7B . 
     Intuitively, a minimal bounding box (MBR c )  702  of the GPS points  704  generated in a real parking place  706  close to a street could have some spatial overlap (MBR r  denoted as the gray box) with the street. However, the ratio Γ between MBR r  and MBR c  shown in  FIG. 7A  could be much smaller than that of the traffic jam depicted in  FIG. 7B , where a taxi moves slowly on a road, creating GPS points which are distributed along the road. In short, if Γ is larger than a threshold γ, the parking place candidate is removed from the list of potential candidates. Thus, based on a labeled-parking-place dataset, it is possible to learn a proper value for δ, , τ, and γ, ensuring high precision and recall of detected parking places. 
     Example Map Matching 
     As described above, map-matching module  304  ( FIG. 3 ) (and Level  2  of  FIG. 5 ) maps taxi segments to the most likely road segments. In one embodiment, an interactive-voting-based-map-matching (IVMM) algorithm may be used as an element to fully or partially implement map-matching module  304 . 
     In one aspect, IVMM algorithm maps GPS points from a taxi segment to the most likely road segments, and will with low-sampling-rate trajectories. As a result, an individual GPS-taxi trajectory is transformable into a sequence of road segments. 
     To infer the state of a given taxi trajectory, empirical insights on cruising patterns of taxis from the historical data is useful. For example, it is possible to focus on learning two travel patterns: 
     1) Pr(O→N|Δt O , t): indicates the state transition probability of a taxi transitioning from O to N conditioned on the fact that the taxi has been occupied for a time duration Δt O , starting at time t. This pattern is usually determined by a passenger&#39;s travel behavior. 
     2) Pr(N→O|Δt N , t): indicates the state transition probability of a taxi transitioning from N to O conditioned on the fact that the taxi has been non-occupied for a time duration Δt O , starting at time t discretized by hours. 
     Example Historic Knowledge Base 
     Historical-inference module  306  ( FIG. 3 ) (and Level  3  of  FIG. 5 ) may use a knowledge-road graph to identify following features derived from the underlying road structure and POIs such as: 
     (1) L: The actual length of a road segment. 
     (2) L/E: The ratio between L and the Euclidean length (between the terminal points) E of a road segment. The larger the value, the more tortuous the road segment is. 
     (3) dir: The directionality of a road segment, i.e., one-way or two-way. 
     (4) Lanes: The number of lanes in a given road segment (single or multiple lanes). 
     (5) Degree: Given a road segment r, the in-degree of the start node (d sin ) is defined as the number of directed edges terminating at node s, while the out-degree of the start node (d sout ) as the number of directed edges originating at node s. Similarly, the in-degree and out-degree for the terminal node is defined as e as d ein  and d eout . Note that when computing the degree of a road segment, it is possible to take into account its directionality(r.dir). 
     (6) POI: The distribution of POIs along a road segment r is also considered. In one aspect, POIs falling in the minimal bounding box of r and within a certain perpendicular distance to r, are considered. For each road segment, a POI vector, &lt;f 1 , f 2 , . . . , f n &gt;, is formulated in which an item f i  represents the TF-IDF value of a POI category i, like restaurants and shopping malls, along the road segment. 
     
       
         
           
             
               
                 
                   
                     
                       f 
                       i 
                     
                     = 
                     
                       
                         
                           n 
                           i 
                         
                         N 
                       
                       × 
                       log 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                            
                           R 
                            
                         
                         
                            
                           
                             { 
                             
                               Road 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               segments 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               containing 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               i 
                             
                             } 
                           
                            
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
     Where n i  is the number of POIs of category i along r and N stands for the total number of POIs along r. The second part of Equation 1 denotes the inverse location frequency of a category, in which |R| is the number of road segments in the road network. In other words, a POI category (e.g., “museum” and “nature parks”) that occurs rarely in other regions is more representative for the region than a common POI category, e.g., “restaurant”, which could appear in many places. 
     Features identified above may have a strong correlation with taxis&#39; travel patterns and subsequently their pick-up and drop-off locations. So, it possible to conclude that road segments with similar features have similar traffic flow, and human mobility patterns, and will therefore behave similarly in space and time. 
     An example, historical-inference module  306  may also use a bisective-clustering algorithm (or other suitable algorithm), which respectively groups the road segments of the same level into a certain number of clusters according to the above-defined features. This algorithm is based on K-means (with K=2) clustering and is performed recursively. 
     All the road segments may be partitioned into two respective clusters {left, right} by using a 2-mean clustering algorithm. Now, for each cluster Cε{left, right}, keep on sub-dividing the cluster C via 2-means unless and until the total of samples (GPS points) inside C≦. Typically, this clustering is only performed on road segments with the same level, e.g., r. level=2. 
     It is also possible to combine bisective-clustering techniques with statistical learning. 
     Given clustered road segments and the processed taxi trajectories, statistical learning is performed to help determine the following two types of prior probabilities: “emission probability” and “transition probability.” 
     “Emission Probability” indicates the probability of a taxi to be in state s conditioned on the fact that it is presently traveling on road segment r at time t. Each road segment of a given road level is typically mapped to a specific cluster. This emission probability is denoted as Pr(s|r→C, t), sε{N, O}. 
     
       
         
           
             
               
                 
                   
                     
                       Pr 
                       ⁡ 
                       
                         ( 
                         
                           
                             s 
                             | 
                             
                               r 
                               → 
                               C 
                             
                           
                           , 
                           t 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         
                           ∑ 
                           
                             r 
                             ∈ 
                             C 
                           
                         
                         ⁢ 
                         
                           r 
                           · 
                           
                             Num 
                             ⁡ 
                             
                               ( 
                               s 
                               ) 
                             
                           
                         
                       
                       
                         
                           ∑ 
                           
                             r 
                             ∈ 
                             C 
                           
                         
                         ⁢ 
                         
                           r 
                           · 
                           
                             Num 
                             ⁡ 
                             
                               ( 
                               All 
                               ) 
                             
                           
                         
                       
                     
                   
                   ; 
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     where r.Num (s) is the number of GPS points generated at time t and with a label state s on road segment r, and r.Num(All) means number of all the points on r at time t. 
       FIG. 8  shows the emission probabilities, learned from the labeled trajectories, of two road segments of different levels:  1  and  2 , respectively. First, the probabilities of the same road segment vary in times of day. The reason for Pr(O) being higher in time slot 3-4 AM than others is that drivers usually do not cruise empty in the middle of the night. Instead, they shut down their taxis or join a taxi queue or opt to sleep for a while, till they get a passenger on board. Second, taxis traveling on the road segment of level  1  (representing ring roads) have a higher probability of being occupied than that of level  2  (representing service roads). This result matches commonsense knowledge that taxi drivers would not actively take the ring roads when non-occupied. Since pedestrians are not allowed to walk on these roads in the example city, it is not possible to pick-up passengers there. 
     Transition Probability indicates the probability of a taxi, transitioning from s i  to s j . It is the production of the following two parts, i.e., Pr(T)×Pr(D). 
     1) Travel Pattern Pr(T) indicates the state transition probability of a taxi transferring from s i  to s j  conditioned on the fact that the taxi has spent a time duration Δt s     i    at state s i , starting at time t i , Pr(s i →s j |Δt s     i   , t i ). 
     2) Destination Pr(D): In this example, there are three kinds of Pr(D) applying to different parts of a taxi segment. 
     Pr(P→s|Δt p , r→C, t a ): For taxis originating from a parking place P from , the probability of transitioning to sε{N, O} depends on the duration it has spent on parking Δt p , the location of parking place r (which is mapped to a road segment cluster C), and the time of arrival at the parking place t a . This transition probability is typically applied to the first point next to a parking place. It has been observed that the time spent in parking for potential passengers has strong temporal correlations with the immediate next state just after parking; and it is one of the main reasons to model parking as a separate state in our inference model. 
     Pr(s j →s j |r i →r j =&gt;C i =C j , t i ): indicates the state transition probability of a taxi transitioning from s i  to s j , s j , s j ε{N, O}, conditioned on the fact that it has traversed from road segment r i  to r j  at time t i , where r i εC i  and r j εC j . 
     Pr(s→P|t, r→C): For taxis terminating to a parking place, the transition probability of a taxi transferring from sε{N, O} to P depends on the timestamp t of the taxi with state s and the location of parking place (first represented by a road segment r and then transferred to a cluster C). This probability is typically applied to the point immediately before a parking place. Note that P to  will be a P from  for the next segment. 
     Given the learned parameters and clustering, it is possible to construct a knowledge-road graph. For instance,  FIG. 9  shows an example knowledge-road graph. 
     Specifically, the example knowledge-road graph is defined as a weighted directed graph G k =(V k , E k ), where each vertex vεV k  represents a cluster C which is assigned a emission probability of Pr(s↑rεC), sε{N, O}. And, each edge is represented by E={(v i , v j )|r i εC i  and r j εC j }, which is assigned a transition probability of Σ r     i     εC     i     , r     j     εC     j    Pr(s i →s j |r i →r j ), s i , s j ε{N, O, P}. 
     Example Inference Operation 
     As mentioned above, inference module  210  infers the state of a taxi at any given point in time and space. As illustrated in  FIG. 9 , a taxi segment, p 1 →p 2 →p 3 →p 4    902  is accessed. After parking place detection there is an originating and terminating parking place P form  and P to , respectively. As shown in  FIG. 9 , each GPS point in the taxi segment has two possible states, O and N. That is, there may be four possible edges (N→N,N→O,O→O,O→N) between the states of two consecutive points. By connecting all the possible edges, it is possible to formulate an inference graph (formally defined below). 
     Also, as shown in  FIG. 9 , emission probabilities, Pr(s i |r i →c i , t i ), s i ε{N, O}  904  are assigned to each point in the inference graph, and the transition probabilities are allocated to corresponding edges. More specifically, Pr(P→s|Δt p , r→C, t a ), sε{N,O} is assigned to the edge connecting the P form  and p 1 , Pr(s→P|t, r→C), sε{N,O} is allocated to the edge directing from p 4  to P to , while the rest of edges are assigned with Pr(s i →s j |r i →r j =&gt;C i →C j , t i ), s i ε{N,O}. 
     As described above, these probabilities can be learned from the labeled taxi trajectories. For example, p 1  generated at time t 1  is mapped to road segment r 1  after map-matching. By searching the knowledge road graph, r 1  is found to belong to road segment cluster C 1 . So, it is possible set the probability on r 1  using the cluster-based probabilities, e.g., Pr(O|r 1 , t 1 )←Pr(O|C 1 , t 1 ). 
     Inference Graph: Given a taxi segment, Traj: p 1 →p 2 → . . . →p k , an inference graph G I =(V I ,E I ) corresponding to Traj is a directed graph, where Vertex set V I  is {p from , p to }∪V O ∪V N  given that P from  and P to  represent taxi&#39;s originating and terminating parking states (P) respectively. Additionally, set V O ={O 1 , . . . , O k } and V N ={N 1 , . . . , N k }, denotes the collection of states of the taxi in occupied (O) and non-occupied state (N) respectively. 
     Edge set E I  contains three kinds of edges amongst the vertices set: 1) P from  to {O 1 ,N 1 }, 2) {(s i ,s i+1 )|s i −{O,N}, iε[1,k−1]}, and 3) {O k ,N k } to P to . 
     Given a map-matched taxi segment and the inference graph, the probabilities on each node and edge (in the graph) are computed. Then, the problem of deriving the most probable state sequence for the segment p 1 →p 2 → . . . →p k  is formulated as deriving a state sequence S 1 . . . k : s 1 →s 2 → . . . →s k  such that: 
                       S     1   ⁢           ⁢   …   ⁢           ⁢   k       =     arg   ⁢           ⁢       max     S     1   ⁢           ⁢   …   ⁢           ⁢   k         ⁢       ∏     i   =   1     k     ⁢           ⁢         W   V     ⁡     (     s   i     )       ×       W   e     ⁡     (       s   i     -&gt;     s     i   +   1         )                 ;           (   3   )                 W   v ( S   i )= Pr ( S   i   |r   i   →c   i   ,t   i ), S   i   ε{O,N};   (4)
 
 W   e ( S   i   →S   i+1 )= Pr ( D )* Pr ( T );  (5)
 
     where W v (•) and W e (•) denotes the vertex weight and edge weight respectively. Pr(D) is the destination-based transition probability, and Pr(T) stands for the travel patterns (as discussed above). 
     A standard dynamic programming is applied to infer and derive the possible taxis&#39; state sequence S 1 . . . k . In other words, the state sequence problem can be formulated as finding the longest path in a directed weighted acyclic graph, see the bolded-dashed line in  FIG. 9 . 
     It is also appreciated that an inference module can also handle a situation when taxi segments do not begin and end with a parking place (for instance, when a taxi starts the day with non-occupied, or when a taxi ends its day returning empty to its residence) by skipping the edge from P form  and to its immediately next point, or the edge directing to P to  from the last point of the trajectory. 
       FIG. 10  illustrates an example method  1000  for inferring the behavior state of a vehicle such as a taxi. Method  1000  includes operational blocks  1002 ,  1004 ,  1006 ,  1008 ,  1010 , and  1012 . The method is illustrated as collections of blocks in logical flow graphs, which represent sequences of operations that can be implemented in hardware, software, or a combination thereof. In the context of software, the blocks represent computer-executable instructions (or code) stored on one or more computer storage media that, when executed by one or more processors, cause the processors to perform the recited operations. Note that the order in which the method is described is not intended to be construed as a limitation, and any number of the described method blocks can be combined in any order to implement the illustrated method, or alternate methods. Additionally, individual blocks may be deleted from the method without departing from the spirit and scope of the subject matter described herein. Further, while the method is described with reference to computer  108  described above with reference to  FIG. 1 , other computer architectures may implement one or more portions of this method, in whole or in part. 
     Referring to  FIG. 10 , in block  1002  trajectory data representing tracked positions of a vehicle along a trajectory having a start and end point is accessed. For example, inference module  210  ( FIG. 2 ) may access trajectory data  110  from memory  112 . Trajectory data may include spatio-temporal information indicating a vehicle&#39;s speed, position, and time at various points along the vehicle&#39;s trajectory. 
     In block  1004 , one or more parking locations of the vehicle along a trajectory are identified. For example, inference module  210  identifies when a speed and distance between one or more consecutive points along a trajectory is less than a predefined threshold. 
     In block  1006 , the trajectory is divided in segments, based at least in part, on knowledge of the identified parking locations from block  204 . For example, by dividing a trajectory into short segments bounded by one more detected-parking places, reduces the complexity of an overall inference. 
     In block  1008 , the segments are map-matched to corresponding road segments. As part of the map-matching process attributes associated with a road segment. Such attributes may include metadata indicative of whether the road segment is a highway, one-way road, two-way road, single-lane or multiple-lane road, a length of the road, a point-of-interest, or other suitable attribute information. 
     In block,  1010  historical data representing spatio-temporal-travel patterns of vehicles learned from historical trajectories of vehicles corresponding to the map-matched-road segments are accessed. Such historical data may include prior probabilities that the vehicle transitions from (i) a first-behavioral state—in which the vehicle is occupied by a passenger—to (ii) a second-behavioral state in which the vehicle is unoccupied by a passenger—and vice versa. The historical data may also include the probability of a taxi to be in state s conditioned on the fact that it is presently traveling on a road segment r at time t. Accessing historical data may also include mining data corresponding to similar road segments with similar features and similar traffic flow at specific times of day. 
     In block  1012 , a behavior state of the vehicle for a segment or position within a segment is inferred. Again, the inference is performed based at least in part, on (i) the position, time of day, and speed of the vehicle corresponding to the segment or position within a segment, (ii) knowledge of the map-matched-road segment, and (iii) the historical data. 
     Conclusion 
     Reference herein to “one embodiment”, “an embodiment”, or similar formulations, means that a particular feature, structure, operation, or characteristic described in connection with the subject matter of this disclosure, is included in at least one embodiment. Thus, the appearances of such phrases or formulations herein are not necessarily all referring to the same embodiment. Furthermore, various particular features, structures, operations, or characteristics may be combined in any suitable manner in one or more embodiments. 
     Although the subject matter has been described in language specific to structural features and/or methodological operations, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or operations described. Rather, the specific features and acts are disclosed as example forms of implementing the claims.