Long-run multi-robot planning under uncertain action durations for persistent tasks
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...
| Główni autorzy: | , , , |
|---|---|
| Format: | Conference item |
| Język: | English |
| Wydane: |
IEEE
2021
|
| _version_ | 1826288459892916224 |
|---|---|
| author | Azevedo, C Lacerda, B Hawes, N Lima, P |
| author_facet | Azevedo, C Lacerda, B Hawes, N Lima, P |
| author_sort | Azevedo, C |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T02:14:01Z |
| format | Conference item |
| id | oxford-uuid:a19cd643-0e9a-42ee-9cc9-82487b69d30c |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T02:14:01Z |
| publishDate | 2021 |
| publisher | IEEE |
| record_format | dspace |
| spelling | oxford-uuid:a19cd643-0e9a-42ee-9cc9-82487b69d30c2022-03-27T02:14:24ZLong-run multi-robot planning under uncertain action durations for persistent tasksConference itemhttp://purl.org/coar/resource_type/c_5794uuid:a19cd643-0e9a-42ee-9cc9-82487b69d30cEnglishSymplectic ElementsIEEE2021Azevedo, CLacerda, BHawes, NLima, PThis 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. |
| spellingShingle | Azevedo, C Lacerda, B Hawes, N Lima, P Long-run multi-robot planning under uncertain action durations for persistent tasks |
| title | Long-run multi-robot planning under uncertain action durations for persistent tasks |
| title_full | Long-run multi-robot planning under uncertain action durations for persistent tasks |
| title_fullStr | Long-run multi-robot planning under uncertain action durations for persistent tasks |
| title_full_unstemmed | Long-run multi-robot planning under uncertain action durations for persistent tasks |
| title_short | Long-run multi-robot planning under uncertain action durations for persistent tasks |
| title_sort | long run multi robot planning under uncertain action durations for persistent tasks |
| work_keys_str_mv | AT azevedoc longrunmultirobotplanningunderuncertainactiondurationsforpersistenttasks AT lacerdab longrunmultirobotplanningunderuncertainactiondurationsforpersistenttasks AT hawesn longrunmultirobotplanningunderuncertainactiondurationsforpersistenttasks AT limap longrunmultirobotplanningunderuncertainactiondurationsforpersistenttasks |