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.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Multi-agent task assignment in the bandit framework


    Beteiligte:
    Le Ny, J. (Autor:in) / Dahleh, M. (Autor:in) / Feron, E. (Autor:in)


    Erscheinungsdatum :

    2006


    Format / Umfang :

    6 Seiten, 14 Quellen



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Print


    Sprache :

    Englisch




    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