Suppose we are given a set of agents (say $P_1 , \dotsc, P_M$), an undirected graph G(V,A) and a set of initial vertices on $G$ where each agent is located. Initially only the edges connected to these initial set of vertices are globally known to all agents. At each step, the agents can traverse an edge connected to their current vertex. If the agent happens to arrive at a vertex $v$ which was previously unvisited by any player, then all the edges connected to $v$ becomes global knowledge to all agents. The aim of the agents is to reach a vertex $v_G$, it suffices if any one agent reaches $v_G$.
I was wondering if this community can point me to problems that have a similar flavor in literature that has been studied before.
One interesting question would be to find the minimum number of steps required to reach $v_G$. I can think of a simple Dynamic Programming(DP) based algorithm for computing the minimum number of steps. A state in the DP would be, the number of steps elapsed, the vertices visited by all agents and the current vertex occupied by each agent. It is simple to expand these states and compute the minimum number of steps. However the number of states expanded can be exponential in $|V|, |A|, M$. I am wondering if one can do better than the DP sketch I just described. More formally, what is the complexity in determining the minimum number of steps.