We analyse the problem of meeting times for interdependent stochastic agents: random walkers whose behaviour is stochastic but controlled by their selections from some set of allowed actions, and the inference problem of when these agents are all in the same state for the first time. We consider the case where we are epistemically uncertain about the selected actions of these agents, and show how their behaviour can be modelled using imprecise Markov chains. This allows us to use results and algorithms from the literature, to exactly compute bounds on their meeting time, which are tight with respect to our epistemic uncertainty models. After focussing on the two-agent case, we analyse and discuss how it can be extended to an arbitrary number of agents, and how the corresponding combinatorial explosion can be partly mitigated by exploiting symmetries inherent in the problem.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Upper Expected Meeting Times for Interdependent Stochastic Agents

  • Marco Sangalli,
  • Erik Quaeghebeur,
  • Thomas Krak

摘要

We analyse the problem of meeting times for interdependent stochastic agents: random walkers whose behaviour is stochastic but controlled by their selections from some set of allowed actions, and the inference problem of when these agents are all in the same state for the first time. We consider the case where we are epistemically uncertain about the selected actions of these agents, and show how their behaviour can be modelled using imprecise Markov chains. This allows us to use results and algorithms from the literature, to exactly compute bounds on their meeting time, which are tight with respect to our epistemic uncertainty models. After focussing on the two-agent case, we analyse and discuss how it can be extended to an arbitrary number of agents, and how the corresponding combinatorial explosion can be partly mitigated by exploiting symmetries inherent in the problem.