Tech Report CS-91-44
A Probabilistic Analysis of Marker-Passing Techniques for Plan Recognition
Glenn Carroll and Eugene Charniak
Useless paths are a chronic problem for marker-passing techniques. We use a probabilistic analysis to justify a method for quickly identifying and rejecting useless paths. Using the same analysis, we identify key conditions and assumptions necessary for marker passing to perform well.