  We address the problem of mitigating damage to a power grid following a storm
by managing a vehicle that has to be routed while simultaneously performing two
tasks: learning about damage from the grid (which requires direct observation)
and repairing damage that it observes. The learning process is assisted by
calls from customers notifying the utility that they have lost power
(``lights-out calls''). However, when a tree falls and damages a line, it
triggers the first upstream circuit breaker, which results in power outages for
everyone on the grid below the circuit breaker. We present a dynamic routing
model that captures observable state variables such as the location of the
truck and the state of the grid on segments the truck has visited, and beliefs
about outages on segments that have not been visited. Trucks are routed over a
physical transportation network, but the pattern of outages is governed by the
structure of the power grid. We introduce a form of Monte Carlo tree search
based on information relaxation that we call {\it optimistic MCTS} which
improves its application to problems with larger action spaces. We show that
the method significantly outperforms standard escalation heuristics used in
industry.}
