  We consider a problem where autonomous agents enter a dynamic and unknown
environment described by a network of weighted arcs. These agents move within
the network from node to node according to a decentralized policy using only
local information, with the goal of finding a path to an unknown sink node to
leave the network. This policy makes each agent move to some adjacent node or
stop at the current node. The transition along an arc is allowed or denied
based on a threshold mechanism that takes into account the number of agents
already accumulated in the arc's end nodes and the arc's weight. We show that
this policy ensures path-length optimality in the sense that, in a finite time,
all new agents entering the network reach the closer sinks by the shortest
paths. Our approach is later extended to support constraints on the paths that
agents can follow.
