I have a bidirected graph which represents rooms in a building. I have scanners set up on doorways which can detect an object moving through them (but not direction). Based on this information what would be an optimal algorithm to detect the current location of the object based on past events?
Also as these scanners may not be fully optimized, they may not detect certain movements through doorways. Is there anyway to determine whether or not a calculated path based on the events is illegal? Or to calculate a confidence value and a predicted location despite this? If it is not, then an algorithm which solves the problem outlined in the first paragraph will suffice.
Thank you!
With perfect scanners on each edge (doorway) the sequence of detections pretty much determines the path through the vertices (rooms).
That's because detection on edge $AB$ followed by detection on $BC$ implies movement from $A$ to $B$ to $C$.
That should handle most cases. The two edge cases are detection on $AB$ followed by detection on $AB$ again. That could be a trip from $A$ to $B$ and back or from $B$ to $A$ and back. But if you had a different vertex before the first of these you would know which was correct. The other edge case might be a person starting from $A$ to $B$, changing their mind and turning back, only tripping the detector once.
With uncertainty the problem is harder. If it's relatively rare you can deduce missing events: motion from $A$ to $B$ and then from $C$ to $D$ will usually imply a missed detection on a trip from $B$ to $C$.
A better analysis of the uncertainty requires much more information on the probabilities of mixed events and on the structure of the graph.