TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

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

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut337–370
Sivumäärä34
JulkaisuAnnals of Mathematics and Artificial Intelligence
Vuosikerta79
Numero4
Varhainen verkossa julkaisun päivämäärä28 syyskuuta 2016
DOI - pysyväislinkit
TilaJulkaistu - huhtikuuta 2017
OKM-julkaisutyyppiA1 Alkuperäisartikkeli

Tiivistelmä

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.

Tutkimusalat

Julkaisufoorumi-taso

Tilastokeskuksen tieteenalat