Tampere University of Technology

TUTCRIS Research Portal

Meeting a deadline: shortest paths on stochastic directed acyclic graphs with information gathering

Research output: Contribution to journalArticleScientificpeer-review


Original languageEnglish
Pages (from-to)337–370
Number of pages34
JournalAnnals of Mathematics and Artificial Intelligence
Issue number4
Early online date28 Sep 2016
Publication statusPublished - Apr 2017
Publication typeA1 Journal article-refereed


We consider the problem of an agent traversing a directed graph with the objective of maximizing the probability of reaching a goal node before a given deadline. Only the probability of the travel times of edges is known to the agent. The agent must balance between traversal actions towards the goal, and delays due to actions improving information about graph edge travel times. We describe the relationship of the problem to the more general partially observable Markov decision process. Further, we show that if edge travel times are independent and the underlying directed graph is acyclic, a closed loop solution can be computed. The solution specifies whether to execute a traversal or information-gathering action as a function of the current node, the time remaining until the deadline, and the information about edge travel times. We present results from two case studies, quantifying the usefulness of information-gathering as opposed to applying only traversal actions.


  • Applied probability, Decision processes, Dynamic programming, Markov processes, Transportation

Publication forum classification

Field of science, Statistics Finland