Flight plans of unmanned aerial vehicles (UAVs) equipped with optical remote sensor systems often need to ensure the complete coverage of a designated region. More recently, UAVs have been utilized for surveillance tasks in case of emergencies such as gas leaks or fires. In this scenario, the time available for collecting information is limited and it is essential to focus on the most relevant areas during the flight.

In this talk, we present an approach for planning the route of an UAV for surveying potentially contaminated areas after the breakout of a fire. As the vehicle is required to stop when taking images, this corresponds to a discrete routing problem. The objective is to maximise total route utility. The utility of performing a measurement at a point in space is determined by either its temperature or the concentration of a contaminant. Such measurements are typically spatially correlated between neighbouring areas, which allows making predictions about unobserved points. In order to improve the route by taking into account both direct as well as indirect observations, we model the planning problem as a Correlated Orienteering Problem (COP).

For solving the COP we present a Constraint Programming based Large Neighbourhood Search. We evaluate the approach on benchmark instances as well as on a use case in firefighting. The results indicate that the approach yields good solutions within the available time span, and that it is robust towards different utility measures.