Cooperative Road-Network Search Planning of Multiple UAVs Using Dubins Paths
Hyondong Oh, Seungkeun Kim, Antonios Tsourdos, Brian A. White · 2011
in the map considering the physical constraints, as well as giving a real time solution in the context of the Chinese postman problem. Since the typical Chinese postman algorithm involves constructing an even graph from the road-network graph which has a set of vertices with an even number of edges attached to them, it can be applied solely to a connected road-network. In this paper, the Chinese postman algorithm is modied to be used for a general type of roadmap including unconnected roads. For this, a nearest insertion based algorithm is introduced for a single UAV dealing with the physical constraints of the UAV using the Dubins path. In particular, circular-circular-circular type of the Dubins path is derived from a dierential geometry to follow the road precisely in a densely distributed road environment. Moreover, having the characteristic of the modied Chinese postman algorithm for the single UAV, it is extended to be used for multiple UAVs using an auction-based negotiation. The properties and performance of the proposed algorithm are evaluated via Monte Carlo simulations on randomly generated maps with dierent parameters.