This paper proposes a sweep coverage formulation for a multi-agent system to cover a region with uncertain workload density, and provides a decentralized coverage algorithm based on the formulation. To achieve the coverage, the covered region is divided into a finite number of stripes, and an algorithm is proposed by incorporating two operations on stripes: workload partition and sweeping. Theoretical analysis is given to estimate the error between the actual coverage time and the optimal time, and numerical analysis is provided to illustrate the proposed algorithm. (C) 2013 Elsevier Ltd. All rights reserved.