  This paper introduces the correlated arc orienteering problem (CAOP), where
the task is to find routes for a team of robots to maximize the collection of
rewards associated with features in the environment. These features can be
one-dimensional or points in the environment, and can have spatial correlation,
i.e., visiting a feature in the environment may provide a portion of the reward
associated with a correlated feature. A robot incurs costs as it traverses the
environment, and the total cost for its route is limited by a resource
constraint such as battery life or operation time. As environments are often
large, we permit multiple depots where the robots must start and end their
routes. The CAOP generalizes the correlated orienteering problem (COP), where
the rewards are only associated with point features, and the arc orienteering
problem (AOP), where the rewards are not spatially correlated. We formulate a
mixed integer quadratic program (MIQP) that formalizes the problem and gives
optimal solutions. However, the problem is NP-hard, and therefore we develop an
efficient greedy constructive algorithm. We illustrate the problem with two
different applications: informative path planning for methane gas leak
detection and coverage of road networks.
