Right place, right time: proactive multi-robot task allocation under spatiotemporal uncertainty
For many multi-robot problems, tasks are announced during execution, where task announcement times and locations are uncertain. To synthesise multi-robot behaviour that is robust to early announcements and unexpected delays, multi-robot task allocation methods must explicitly model the stochastic pr...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
AI Access Foundation
2024
|
| _version_ | 1826312437903654912 |
|---|---|
| author | Street, C Lacerda, B Mühlig, M Hawes, N |
| author_facet | Street, C Lacerda, B Mühlig, M Hawes, N |
| author_sort | Street, C |
| collection | OXFORD |
| description | For many multi-robot problems, tasks are announced during execution, where task announcement times and locations are uncertain. To synthesise multi-robot behaviour that is robust to early announcements and unexpected delays, multi-robot task allocation methods must explicitly model the stochastic processes that govern task announcement. In this paper, we model task announcement using continuous-time Markov chains which predict when and where tasks will be announced. We then present a task allocation framework which uses the continuous-time Markov chains to allocate tasks proactively, such that robots are near or at the task location upon its announcement. Our method seeks to minimise the expected total waiting duration for each task, i.e. the duration between task announcement and a robot beginning to service the task. Our framework can be applied to any multi-robot task allocation problem where robots complete spatiotemporal tasks which are announced stochastically. We demonstrate the efficacy of our approach in simulation, where we outperform baselines which do not allocate tasks proactively, or do not fully exploit our task announcement models. |
| first_indexed | 2024-04-09T03:54:33Z |
| format | Journal article |
| id | oxford-uuid:448f43b1-6837-4333-9bd4-532133a3d2b7 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-04-09T03:54:33Z |
| publishDate | 2024 |
| publisher | AI Access Foundation |
| record_format | dspace |
| spelling | oxford-uuid:448f43b1-6837-4333-9bd4-532133a3d2b72024-03-11T06:42:59ZRight place, right time: proactive multi-robot task allocation under spatiotemporal uncertaintyJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:448f43b1-6837-4333-9bd4-532133a3d2b7EnglishSymplectic ElementsAI Access Foundation2024Street, CLacerda, BMühlig, MHawes, NFor many multi-robot problems, tasks are announced during execution, where task announcement times and locations are uncertain. To synthesise multi-robot behaviour that is robust to early announcements and unexpected delays, multi-robot task allocation methods must explicitly model the stochastic processes that govern task announcement. In this paper, we model task announcement using continuous-time Markov chains which predict when and where tasks will be announced. We then present a task allocation framework which uses the continuous-time Markov chains to allocate tasks proactively, such that robots are near or at the task location upon its announcement. Our method seeks to minimise the expected total waiting duration for each task, i.e. the duration between task announcement and a robot beginning to service the task. Our framework can be applied to any multi-robot task allocation problem where robots complete spatiotemporal tasks which are announced stochastically. We demonstrate the efficacy of our approach in simulation, where we outperform baselines which do not allocate tasks proactively, or do not fully exploit our task announcement models. |
| spellingShingle | Street, C Lacerda, B Mühlig, M Hawes, N Right place, right time: proactive multi-robot task allocation under spatiotemporal uncertainty |
| title | Right place, right time: proactive multi-robot task allocation under spatiotemporal uncertainty |
| title_full | Right place, right time: proactive multi-robot task allocation under spatiotemporal uncertainty |
| title_fullStr | Right place, right time: proactive multi-robot task allocation under spatiotemporal uncertainty |
| title_full_unstemmed | Right place, right time: proactive multi-robot task allocation under spatiotemporal uncertainty |
| title_short | Right place, right time: proactive multi-robot task allocation under spatiotemporal uncertainty |
| title_sort | right place right time proactive multi robot task allocation under spatiotemporal uncertainty |
| work_keys_str_mv | AT streetc rightplacerighttimeproactivemultirobottaskallocationunderspatiotemporaluncertainty AT lacerdab rightplacerighttimeproactivemultirobottaskallocationunderspatiotemporaluncertainty AT muhligm rightplacerighttimeproactivemultirobottaskallocationunderspatiotemporaluncertainty AT hawesn rightplacerighttimeproactivemultirobottaskallocationunderspatiotemporaluncertainty |