  In this paper, we consider the problem of exploring unknown environments with
autonomous agents. We model the environment as a graph with edge weights and
analyze the task of visiting all vertices of the graph at least once. The
hardness of this task heavily depends on the knowledge and the capabilities of
the agent. In our model, the agent sees the whole graph in advance, but does
not know the weights of the edges. As soon as it arrives in a vertex, it can
see the weights of all the outgoing edges. We consider the special case of two
different edge weights $1$ and $k$ and prove that the problem remains hard even
in this case. We prove a lower bound of $11/9$ on the competitive ratio of any
deterministic strategy for exploring a ladder graph and complement this result
by a $4$-competitive algorithm. All of these results hold for undirected
graphs. Exploring directed graphs, where the direction of the edges is not
known beforehand, seems to be much harder. Here, we prove that a natural greedy
strategy has a linear lower bound on the competitive ratio both in ladders and
square grids.
