I am trying to design a system for determining the absolute position of a vehicle without using GPS. The idea is that I will record data from sensors onboard a vehicle at specified time intervals, primarily the altitude, heading, and distance traveled, and use this to create some model of the route driven (note: the absolute heading itself cannot be trusted, but I can rely on the change in heading between data captures). I then would like to compare this against data extracted from open street maps in order to locate the vehicle.

I am considering using a rule-based approach in which I segment the drive into a sequence of drive maneuvers, such as straight, left turn, right turn, by thresholding the cumulative heading change over a sliding window to detect turns. I can then also segment the data based on altitude change and distance traveled. I would apply the same algorithm to the sensor data and the data from open street maps, with the idea that it would produce the same sequence of segment for both data sources. In an ideal world I could then search the first segment from the sensor data against the open street maps data, get a list of matching candidates (and the subsequent maneuvers for those candidates), and then search the second segment, and so on.

However, this is proving to be much more difficult in practice. The rule-based approach I wrote works well, but it still produces differences between the two data sources, as sensor data does not match the ideal open street map data exactly, which prevents me from using the naive search algorithm.

This leads me into my two questions:

1. What is a good approach for organizing the data? Is segmenting the road into maneuvers a good idea? For each maneuver, I store certain information such as total heading change, distance traveled, starting altitude, and altitude change in a feature vector which I can then use for a search. Is there a better approach for how I should be organizing the data? The open street maps data gives me nodes along the road at even spaces intervals, whereas the sensor data can vary in distance as the car can be stationary, in which I have many data points with a small distance delta, or can be moving very fast (large distance delta).

2. What is a matching algorithm I can use that is tolerant for faults in the data. In the above example, if my algorithm misclassified a sensor data segment or believes a segment should be divided in two (when it only creates a single segment from the map data), then it totally throws the naive search algorithm off. What is a better algorithm that I can use, that has more tolerance for these errors. An search algorithm that looks at the whole picture, that is able to search for the entire sequence of maneuvers together (even if there are some errors). I have heard hidden markov model and dynamic time warping thrown around, but not sure if they would be useful or how I can apply them.