We consider a task assignment problem for a fleet of UAVs in a surveillance/search mission. We formulate the problem as a restless bandits problem with switching costs and discounted rewards: there are TV sites to inspect, each one of them evolving as a Markov chain, with different transition probabilities if the site is inspected or not. The sites evolve independently of each other, there are transition costs cij for moving between sites i and j set membership or element in (1,..., N), rewards when visiting the sites, and we maximize a mixed objective function of these costs and rewards. This problem is known to be PSPACE-hard. We present a systematic method, inspired from the work of Bertsimas and Nino-Mora (2000) on restless bandits, for deriving a linear programming relaxation for such locally decomposable MDPs. The relaxation is computable in polynomial-time offline, provides a bound on the achievable performance, as well as an approximation of the cost-to-go which can be used online in conjunction with standard suboptimal stochastic control methods. In particular, the one-step lookahead policy based on this approximate cost-to-go reduces to computing the optimal value of a linear assignment problem of size N. We present numerical experiments, for which we assess the quality of the heuristics using the performance bound.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Multi-agent task assignment in the bandit framework


    Contributors:
    Le Ny, J. (author) / Dahleh, M. (author) / Feron, E. (author)


    Publication date :

    2006


    Size :

    6 Seiten, 14 Quellen



    Type of media :

    Conference paper


    Type of material :

    Print


    Language :

    English




    Cooperative Multi-Agent UAS Task Assignment for Disaster Response Scenario

    Degroote, Nicholas S. / Cohen, Kelly | TIBKAT | 2022


    Cooperative Multi-Agent UAS Task Assignment for Disaster Response Scenario

    DeGroote, Nicholas S. / Cohen, Kelly | AIAA | 2022


    Base Defense Using a Task Assignment Framework

    Kingston, D. / Rasmussen, S. / Mears, M. et al. | British Library Conference Proceedings | 2009


    Base Defense Using a Task Assignment Framework

    Kingston, Derek / Rasmussen, Steven / Mears, Mark | AIAA | 2009