Tech Report CS-91-44

A Probabilistic Analysis of Marker-Passing Techniques for Plan Recognition

Glenn Carroll and Eugene Charniak

June 1991


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.

(complete text in pdf or gzipped postscript)