Routing and time allocation problems in designing automatic control of unmanned aerial vehicles for information collection
Unmanned aerial vehicles (UAVs) have been proven successful and efficient for information collection in a modern battlefield, especially in areas that are considered too dangerous for human pilots. Currently, a UAV is remotely controlled by a ground station through frequent data communications, which make the current system vulnerable in a threat environment. To enhance the survivability of the current UAV system, a UAV can operate under automatic and decentralized control, which significantly reduces the system's dependency on data communications. This work studies two important problems that arise when such control is designed. The first problem studies the routing and time allocation decisions for a fleet of UAVs to collect uncertain information from a set of regions while maintaining radio silence during the entire mission. It is demonstrated that a region-sharing strategy is beneficial even when there is no extra reward gained from additional information collection. Implementing a region-sharing strategy requires solving a decentralized time-allocation problem, which is computationally intractable. To overcome this, an approximate formulation is developed under an independency assumption. This approximate formulation allows the problem to be decomposed, by vehicle, into individual time allocation problems, and obtain an easily implementable policy that takes on a Markovian form. A sufficient condition is developed under which the approximate formulation becomes exact. The second problem considers a single vehicle problem where each region may contain an uncertain number of "entities", each of which refers to a valuable piece of information. We investigate how the shape of the entity distribution in each region affects the vehicle's optimal time-allocation decisions. When the number of entities in each region follows a Poisson distribution, it is shown that a ''fixed-time'' policy, which allocates a fixed amount of time to each region, is optimal. An approximate but asymptotically optimal method is developed for the general scenario to obtain a time-allocation policy by truncating the entity distributions at a finite threshold. It is shown that the time-allocation policy obtained under a small truncation threshold by the approximate method can outperform the best fixed-time policy significantly. Furthermore, the number of entities found under the time-allocation policy obtained by the approximate method can have a larger expectation than that found under the best fixed-time policy while maintaining a smaller variance.