Stochastic and Dynamic Routing Problems for Multiple Uninhabited Aerial Vehicles

摘要

Consider a routing problem for a team of vehicles in the plane: target points appear randomly over time in anbounded environment and must be visited by one of the vehicles. It is desired to minimize the expected system time fornthe targets, that is, the expected time elapsed between the appearance of a target point and the instant it is visited. Innthis paper, such a routing problem is considered for a team of uninhabited aerial vehicles, modeled as vehicles movingnwith constant forward speed along paths of bounded curvature. Three algorithms are presented, each designed for andistinct set of operating conditions. Each is proven to provide a system time within a constant factor of the optimalnwhen operating under the appropriate conditions. It is shown that the optimal routing policy depends on problemnparameters such as the workload per vehicle and the vehicle density in the environment. Finally, there is discussion ofna phase transition between two of the policies as the problem parameters are varied. In particular, for the case innwhich targets appear sporadically, a dimensionless parameter is identified which completely captures this phasentransition and an estimate of the critical value of the parameter is provided.