This paper presents an approach for multi-robot long-term planning under uncertainty over the duration of actions. The proposed methodology takes advantage of generalized stochastic Petri nets with rewards (GSPNR) to model multi-robot problems. A GSPNR allows for unified modeling of action selection, uncertainty on the duration of action execution, and for goal specification through the use of transition rewards and rewards per time unit. Our approach relies on the interpretation of the GSPNR model as an equivalent embedded Markov reward automaton (MRA). We then build on a state-of-the-art method to compute the long-run average reward over MRAs, extending it to enable the extraction of the optimal policy. We provide an empirical evaluation of the proposed approach on a simulated multi-robot monitoring problem, evaluating its performance and scalability. The results show that the synthesized policy outperforms a policy obtained from an infinite horizon discounted reward formulation as well as a carefully hand-crafted policy.


    Access

    Download


    Export, share and cite



    Title :

    Long-run multi-robot planning under uncertain action durations for persistent tasks


    Contributors:
    Azevedo, C (author) / Lacerda, B (author) / Hawes, N (author) / Lima, P (author)

    Publication date :

    2020-10-20



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English


    Classification :

    DDC:    629



    Heterogeneous Multi-robot Mission Planning for Coordinated Tasks Execution

    Dwiyasa, Felis / Lim, Meng-Hiot / Kang, Pyo et al. | Springer Verlag | 2020



    Planning surface cleaning tasks by learning uncertain drag actions outcomes

    Martínez, David / Alenyà, Guillem / Torras, Carme | BASE | 2013

    Free access

    Planning surface cleaning tasks by learning uncertain drag actions outcomes

    Martínez Martínez, David / Alenyà Ribas, Guillem / Torras, Carme | BASE | 2013

    Free access

    A Planning System for robot construction tasks

    Fahlman, Scott Elliott | TIBKAT | 1973