Inference Engine
The inference engine provides functionality equivalent to a Automatic Vehicle Location (AVL) system, matching a vehicle to a trip/block in the schedule for use in providing customer information or operational performance data. This process is done with minimal data from the vehicle--complex statistical algorithms combine static schedule data, vehicle position data, bus operator-entered data (which may contain errors) and other data collected from the bus (e.g. from the bus headsign) to make a best "guess" as to what stopping pattern (expressed as any trip) the vehicle is serving. When the system has enough confidence in its inputs, it also generates a block assignment, allowing the transit agency to understand how the bus is performing in comparison to its schedule (and implying one trip of many potential equals) and also predict what the bus will do at the completion of its current trip.
At the core of the inference engine is a particle filter which uses a particle to represent the probability of a bus being in a certain location and serving a certain trip via likelihood calculations. A configurable number of particles represent the set of likely states, of which the most likely is returned after sampling all particles.
The inference engine (IE) is comprised of several modules listed below. For a sequence-based discussion see Inference-Engine-Sequence-Discussion
Provides the Spring configuration, controllers, and views to deploy the IE to a JEE web container as a Web Archive File (WAR). The webapp listens to the input queue which contains raw messages from buses, processes them in an individual thread run per vehicle, and puts the inference output result on the output queue. The data structures involved are covered in Inferred-Bus-Data (for processed output data) and Real-time-bus-data (for raw input data).
The Vehicle Tracking Webapp (VTW) also contains a simulator to simulate vehicles given the loaded static schedule data (aka "bundle"), a status screen to indicate the status of which buses the VTW is tracking (in real time or via the simulator), a page to manually change bundles upon request, and a "data debug" screen that lists likely problems with the loaded bundle (deprecated). This is available by navigating to the root page of the VTW (e.g. http://localhost:8080/onebusaway-nyc-vehicle-tracking-webapp/). More on the simulator is available here
The core inference engine module, containing queue listening logic, inference record model classes, inference logic and services, simulation services for playback, and queue output logic.
Package layout overview:
Modules that are used to weight particles. Each has a likelihood() method that returns a conditional probability that is used to generate a final weight for the entire particle. Each weights a certain characteristic of the particle--e.g. Destination Sign Code (DSC), whether the vehicle has moved or not, scheduled position vs. actual position along route, etc.
Some key services/implementations:
Pertains to free movement and movement along edges (i.e. segments of the geometry of a trip). Computations are based on estimated velocities; free movement assumes that the current average velocity is distributed normally around the previous observed average velocity, edge movement assumes that the average velocity along the edge is distributed normally around the average velocity per the surrounding stops and distance. The variance is proportional to an acceleration error of 1 m/s.
Schedule deviation is measured in minutes and modeled by a mixture of two Student-T distributions: one for when run information does not match, another for when it does. Those distributions have parameters in ScheduleLikelihood.java.
States that are used as part of the particles generated by the system. States include block (assignment to a block, with trip implied), journey phase (operational phase: deadhead, in progress, etc.), motion (recent movement, time stationary, etc. used for layover detection) and vehicle (a collection of the previous states).
VehicleState is a convenient collection of all other state objects.
NycRawLocationRecord - Internal representation of real time data. The RealtimeEnvelope message generated by the http-queue-proxy is translated into this upon receipt by the IE.
NycTestInferredLocationRecord - Simulation, test, and debugging tools tend to output this record for ease of integration; it allows actual results to be included alongside inferred results for later comparison. Itegration tests take advantage of this to verify correctness.
Supporting services that make up the particle filter and models.
Generates a distribution of BlockStates given an observation input, based on proximity to routes, scheduled location vs. actual location and run information. These are not filtered or weighted--this method is deliberately exhaustive in its proposals, sampling is done by the class below.
A service to sample/weight BlockStates given observational inputs (e.g. DSC, location, movement compared to the last observation, scheduled position, etc.)
Based on likelihoods, assigns detour status:
- Detour status is given when a vehicle previously in-progress, or already with a detour status, maintains movement in the general direction of a run and is not snapped to its trip's geometry. A bus with observed GPS coordinates that is within (as of the date of this revision of the document) 60 meters of its route geometry will not be considered detoured, but rather IN_PROGRESS on that route. The parameter determining the distance in which observations are snapped to a geometry is tripSearchRadius, defined in BlockStateService. These parameters are fully outlined at here
An instance of a vehicle being tracked by the system. One of these is instantiated for each vehicle being tracked by the core particle filter. This is also the module that translates internal data structures (e.g. BlockState) into the queued output that is exposed to the rest of the system. This is colloquially known as the "wrapper" for the inference engine.
VehicleInferenceInstance also assigns stalled status:
- Stalled status is given when a vehicle is in-progress has not moved for more than a certain amount of time. The amount of time is defined by a parameter from the TDM's configuration API. These parameters are fully outlined at here
Key Methods:
-
handleUpdate(): accepts a raw bus message and passes it through the inference engine, along with production-logic to match observations to crew dispatch records and other internal data references. This module also has methods to massage data in response to bus hardware anomalies, such as missing timestamps and timestamps with improbable dates due to misset clocks. This method is run within a new thread that is forked off from the message reception thread that is part of the InputQueueListener.
-
handleBypassUpdate(): used by the simulator only, used to pass a previously generated inference output result through the inference engine straight into the TDS for simulating data on the front-ends.
-
getCurrentStateAsNycQueuedInferredLocationBean(): fetches the current particle filter's state (i.e. the most likely/result of the process) as a model class suitable for queueing onto the inference output queue.
-
getCurrentManagementState(): called as part of getCurrentStateAsNycQueuedInferredLocationBean(), fetches current IE telemetry as represented by the NycVehicleManagementStatusBean. It includes the last location update time, the lat/lon for that update, and the DSC and assigned run id.
-
getMostRecentParticleAsNycTestInferredLocationRecord(): used by both the simulator to generate output, and getCurrentStateAsNycQueuedInferredLocationBean() as the basis of the latter's output to the inference queue. This method is the core of the inference engine wrapper, and the place where most of the translation between internal IE states and output classes takes place.
The manager of VehicleInferenceInstances, forks off a new thread for each received message and passes it off to the VehicleInferenceInstance for that vehicle. Also maps data in the raw queue format to the proper input model classes, and manages message processing relative to bundle readiness and error logging.
Supporting classes for a particle filter in Java. No system-specific logic is contained in this package.
Classes to read and write to the raw message input and output message queues.
Some key services/implementations:
A dummy output queue implementation that sends the output to the TDS embedded within the IE. Useful for running the entire system on one local machine.
A dummy input queue task. Generates no input. Useful for running the system with the simulator only, but not required to run the simulator.
The output implementation used to send inference output to the message queue, where a remote TDS might pickup and ingest the input. (used as part of NYC project in production)
The input implementation used to pull raw bus messages from the queue and process them. This listener uses a partitioned strategy where only vehicles assigned to the depot that the IE is configured to process messages for are processed; the rest are simply ignored. (used as part of NYC project in production)
An input implementation used to pull the messages for a single bus only; the rest are ignored. Useful for debugging only.
Classes that make up the vehicle simulator, which can run logged raw input through the system, or generate simulated vehicles based on the static schedule only.
The Transit Data Federation module provides the Java interface known as the Transit Data Service (TDS), which is embedded in the inference engine for querying static and realtime data associated with the bundle. The TDS is internal to the vehicle tracking component; it is not shared with the front-ends which also embedd a TDS. The front-ends and the vehicle tracking component embed the TDS for performance and latency reasons, preferring local Java calls to the Hessian binary webservice alternative.
A Federated Transit Data Bundle is the internal representation of GTFS and other schedule data. The Inference Engine uses this internally for trip and block matching, and accesses the data through the TransitGraphDao. The core OBA format is used as part of the NYC project, along with some extra NYC-specific data formats that are overlaid on top of the OBA-core bundle and defined in NycFederatedTransitDataBundle.
The Inference engine supports hot swappable bundle changes--meaning that as one set of schedule data expires, the system will seamlessly load a new set of data behind it, when available.
Specific to the inference process however, vehicles' inference state will be reset if data has changed in the underlying bundle enough to require it--e.g. if a vehicle is matched to a trip or block that is not in the new bundle, as defined by the same trip ID/block ID not being in the bundle.
Other bundle considerations are common to all components and are summarized in the Bundle Management section of the design document.
Depending on the inputs received by the system, and the confidence with which the system thinks it can make a match to the schedule, two kinds of results can be produced--the difference is identified as part of the "status" output of the NycQueuedLocationBean:
-
Formal inference (status includes "blockInf"): the system is confident enough to assign the vehicle to a particular trip/block, which implies schedule deviation can be trusted. For the NYC project, formal inference requires a run ID match to be made between the inferred run ID and either the operator provided run information or bus operator crew assignments available via crew dispatch records (see below in Data Integration). Distance along trip/block is calculated when in this mode, as is a route and direction.
-
Informal inference (status does NOT include "blockInf"): the system is not confident enough to assign the vehicle to a particular trip/block, and so is using any trip as a model of a stopping pattern the system is confident of. For this reason, the schedule deviation cannot be trusted--the trip selected by the system may be many hours ahead or behind the current bus' actual in-service trip. Distance along trip/block is calculated when in this mode, as is a route and direction and schedule deviation.
UI logic that takes these states into account is outlined here
The system assigns one of the following operational phases to each vehicle:
- AT_BASE: Vehicle is at depot. This state is assigned forcibly, and based only on the location being strictly within a base's geometry (detected via BaseLocationService). Trip, block and run inference occur regardless, since in some instances it is important to maintain this information during its departure from the geometry.
- DEADHEAD_BEFORE: Non-revenue travel to the start of a block, typically from the depot. This phase is the initial state for inference and will often appear during IE resets. On these occasions, and when sampled states have near zero likelihood, DEADHEAD_BEFORE states without trip, block and run information will appear. These "empty" states are fixed at low likelihood and will arise in situations of ambiguity or error.
- LAYOVER_BEFORE: A pause before a block starts, while the bus is stationary at a terminal.
- IN_PROGRESS: The vehicle is actively serving a block and trip and is located on a road, moving.
- DEADHEAD_DURING: Non-revenue travel occurring during the course of a block. Instances in which this phase occur are: a) travel between trip segments of a block (that are far enough away from terminals for the system to detect the bus is no longer snapped to a route), b) significant off-trip detour travel or c) when an out-of-service DSC is reported during a scheduled revenue portion of a run. This whole phase only occurs for formally inferred blocks where ordering of deadhead/revenue trips can be determined.
- LAYOVER_DURING: A pause occurring near a layover location and within the course of a run.
- DEADHEAD_AFTER: Non-revenue travel from the end of a block back to the depot. This phase only occurs for formally inferred blocks where ordering of deadhead/revenue trips can be determined.
- UNKNOWN: The vehicle is doing something unexpected. This is a catch-all status to ensure the phase is never empty; in typical usage it will not be observed.
At least one of these states will always be assigned to a vehicle.
This diagram illustrates the relationships between a bus block, trips within that block and driver runs that overlap the block. Time proceeds from left to right on the X axis. Space is collapsed into one distance dimension on the Y axis. Bus trips composing the block are dark blue lines. Driver run segments are the red, green and light blue lines. Grey callouts indicate places where non-GPS data in the Vehicle Location Message is expected to change. Specifically, Driver Login will update the operatorID and runID fields. Changes in DSC will update the destSignCode field.
Terminal locations are determined by searching a fixed radius around the current observation for a start or end stop of a trip. The current implementation searches for start and end stops for trips within a 400m radius. (See VehicleStateLibrary)
The layover states are inferred by their current motion state (i.e. in motion, or not), the currently inferred block state, and whether the vehicle is within a distance along the current block and from a terminal. Specifically, when the vehicle is not in motion, within the terminal location, and after/before the last/first stop time:
- LAYOVER_DURING: when there is a trip that follows the current trip in the inferred block.
- LAYOVER_BEFORE: when at the terminal location of the first stop in the inferred block.
- LAYOVER_AFTER: when at the terminal location of the last stop in the inferred block.
A vehicle is at base when it is within a polygon in the BaseLocations.txt file. The BaseLocationServceImpl is the service via which this data is accessed.
The inference engine assigns one (or many, except in the case of "DEFAULT" and "BLOCKINF") of the following statuses to each vehicle:
- DEFAULT: The default, normal status.
- DEVIATED: The vehicle has deviated significantly from its normal route (threshold configurable).
- STALLED: The vehicle has not made any forward progress in a particular amount of time (configurable).
- BLOCKINF: A "formal" block-level inference has been made.
At least one of these states will always be assigned to a vehicle.
Vehicle location is snapped to the trip's shape (from GTFS) whenever the bus is in IN_PROGRESS or LAYOVER_* states. Else, the observed GPS location is used. This logic is contained in the inference engine wrapper here.
The following outlines data used as "hints" to refine IE results, particularly around block-level inference.
In NYC, vehicle operators log-in to the fare box with two pieces of information that are useful for the inference process: an operator ID (a 7 digit number), and a run ID, which consists of a "run-route" (usually 1-3 numbers) and a run number (1-3 numbers).
The inference algorithm can use this combination of operator ID, run ID and data from crew assignment service to match a vehicle to the schedule, subject to the inference process that attempts to allow for noise in this data.
Operator ID
The operator ID can be looked up in the Crew Assignment Service to find that operator's scheduled run ID, which can be used to match that operator/vehicle to the schedule (allowing the Inference Engine to be certain of which trip the vehicle is serving, and therefore be "formal").
The only wrinkle here is that operator IDs can duplicate across agencies. To resolve this, we consult the agency ID of the vehicle that the operator is logging into, and assume the operator belongs to the same bus company/agency as the vehicle does, since labor rules typically ensure this is the case.
Operator IDs can be mis-entered, in such cases, leaving run ID available for use (see below).
Run ID
The Run ID is a combination of the "run route" and a run number. The run number is a completely numeric value, and should match the value in the schedule.
The run route is typically (but not always) the same as a bus route from that same depot, minus the "B", "M", "Q", etc. prefix, since the keyboards provided to operators do not have letters. The run-route is not necessarily the same route as any of the trips that may be part of the run. A wrinkle: for unscheduled trips, which do not have a run route, operator behavior is undefined. Some operators may log in with a run route that is all zeros, or ones, while other operators may choose a random number they like. Moreover, some run routes have no numbers at all (e.g. "MISC") and have had numeric conventions defined for entry in the operator's login keyboard (e.g. 999). The system uses a fuzzy matching algorithm (defined below) to handle for this variance in operator performance.
Parsed Input Formats
The current implementation expects bundle Run-route's of the following RegEx format:
([a-zA-Z]+)0*(\\d*)[a-zA-Z]*
Example: http://rubular.com/r/hinmQKDuRO
Operator-entered Run-Id's are expected to have the format:
0*([0-9]+)-0*(\\d+)
Example: http://rubular.com/r/6670jxlQGq
Implementation Details
When a record with a new reported run-id is found the following is performed:
- Check that the operator entered run-id has the form 2. Fail otherwise.
- Create a synthetic operator-entered run-id from "$1-$2" of 2.
- For each run-id in the bundle: 3.1. If the run-route of the current bundle run-id is MISC, then create a synthetic run-id consisting of 999 , the depot code of the pullout, and the bundle run-id's run-number, then find the Levenshtein distance between the synthetic run-id and the synthetic operator entered run-id. 3.2. Otherwise, create a synthetic bundle run-id from $1 of 1 and the run-number of the current bundle run-id, then find the Levenshtein distance between the synthetic operator-entered run-id.
- Return a map of ordered Levenshtein distances to bundle run-id's.
All matches tied for the smallest Levenshtein distance are then considered "fuzzy matches" and used in inference.
Example
- Input: 044-030
- Run-id's in Bundle: {X1-10, B63-5, X0102-80, S4469-30, MISC-98}
- Fabricated Bundle Run-id's: {1-10, 63-5, 102-80, 4469-30, 999-98}
- Comparable Input Run-id: 44-30
- Output: {2 -> {S4469-30}, 3 -> {X1-10}, 4 -> {X0102-80, B63-5}, 5 -> {MISC-98}}
- The only fuzzy match that would be considered an candidate for assignment would be the one with the min Levenshtein distance among the set (i.e. 2) which is S4469-30
Check out the unit tests on github for further details of this logic.
The following events are thought to be useful in prompting the system to consider the idea that a vehicle's block assignment has possibly changed, and should be re-evaluated with currently available information:
- Operator-entered DSC, run ID or operator ID changes (received from vehicle every 30s).
- Operator assignment to a run changes in the crew assignment data.
- Vehicle deviates from its inferred route, beyond any distance that is thought to be a detour (location received from vehicle every 30s).
High-Level Exception Condition Descriptions
- Vehicles can be (re)assigned to a different run/trip/block at any point in their operational cycle: before leaving the depot, while at a layover, or even during service. If a change is not accompanied by an operator switch, no operator (re)login will occur--just a DSC switch.
- Vehicles can end service at any point in their operational cycle: while in layover, or even during service. When vehicles go out of service unexpectedly, DSC switches will almost always occur. A replacement vehicle may or may not be dispatched to finish the first vehicle's run.
- Extra service ("wildcat") runs are never present in the schedule. These trips can only be matched to an itinerary via the DSC, and are not entered in the crew assignment service at all. Extra trips may be part of an existing run, or a completely new "run".
- Input data will be of varying quality, all with noise. Data, in order from most likely accurate to least likely accurate, might be: vehicle location, DSC, operator ID, operator run ID, with DSC and operator ID being equally important.
For each actively transmitting inference engine -- a primary, there is also a backup secondary for failover purposes. The distinction is this:
Primary: actively listening for realtime records, processing inference, output results onto queue
Seconday: actively listening for realtime records, processing inference, not outputing results
Primary vs Secondary is dynamically determined every 10 seconds based on a DNS convention. If the IP of the configured primary DNS pointer resolves to an IP present on the local interface, the machine is primary. If no primary DNS pointer is configured, the machine is assumed to be primary. Otherwise the machine is considered a secondary instance. The status API at /onebusaway-nyc-vehicle-tracing-webapp/status.do details the primary vs secondary status.