A two-layer semi-Markov model for recognizing the destination of a moving agent

Recognizing the destination of a moving agent is quite significant in many systems such as real time strategy games. Probabilistic graphical models are widely used to solve this problem, but existing models cannot recognize the changeable destination with noisy and partially missing observations in a grid based map. To solve this problem, a two-layer semi-Markov model (TLSMM) is proposed. In this model, two layers represent the transition of destinations and the grids where the agent is respectively; the duration of being in one grid is modeled by a discrete Coxian distribution. The particle filtering is also used to solve inference problem of TLSMM with noisy and partial data. In experiments, we simulate an agent's movements in an urban field and employ the agent's traces to evaluate the performance of TLSMM and PF. The results indicate that no matter the destination changes or not, our methods can effectively recognize it. In addition, through comparing the metrics like precision, recall, and F-measure of our model and a two-layer Markov model, we conclude that the explicit duration modeling improves the recognizing performance when the agent is not closed to the destination.