This paper presents a road-network search planning algorithm by which multiple unmanned aerial vehicles visit every road identified 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 modified 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 differential geometry to follow the road precisely in a densely distributed road environment. Moreover, having the characteristic of the modified 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 different parameters.
展开▼
