A framework for simultaneous task allocation and planning under uncertainty
We present novel techniques for simultaneous task allocation and planning in multi-robot systems operating under uncertainty. By performing task allocation and planning simultaneously, allocations are informed by individual robot behaviour, creating more efficient team behaviour. We go beyond existi...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Association for Computing Machinery
2024
|
| _version_ | 1826316773418336256 |
|---|---|
| author | Faruq, F Lacerda, B Hawes, N Parker, D |
| author_facet | Faruq, F Lacerda, B Hawes, N Parker, D |
| author_sort | Faruq, F |
| collection | OXFORD |
| description | We present novel techniques for simultaneous task allocation and planning in multi-robot systems operating under uncertainty. By performing task allocation and planning simultaneously, allocations are informed by individual robot behaviour, creating more efficient team behaviour. We go beyond existing work by planning for task reallocation across the team given a model of partial task satisfaction under potential robot failures and uncertain action outcomes. We model the problem using Markov decision processes, with tasks encoded in co-safe linear temporal logic, and optimise for the expected number of tasks completed by the team. To avoid the inherent complexity of joint models, we propose an alternative model that simultaneously considers task allocation and planning, but in a sequential fashion. We then build a joint policy from the sequential policy obtained from our model, thus allowing for concurrent policy execution. Furthermore, to enable adaptation in the case of robot failures, we consider replanning from failure states and propose an approach to preemptively replan in an anytime fashion, replanning for more probable failure states first. Our method also allows us to quantify the performance of the team by providing an analysis of properties such as the expected number of completed tasks under concurrent policy execution. We implement and extensively evaluate our approach on a range of scenarios. We compare its performance to a state-of-the-art baseline in decoupled task allocation and planning: sequential single-item auctions. Our approach outperforms the baseline in terms of computation time and the number of times replanning is required on robot failure. |
| first_indexed | 2024-09-25T04:08:43Z |
| format | Journal article |
| id | oxford-uuid:46550cd8-d7ff-4037-b26c-a5d3f4cdf030 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2025-02-19T04:28:08Z |
| publishDate | 2024 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:46550cd8-d7ff-4037-b26c-a5d3f4cdf0302024-12-13T09:03:53ZA framework for simultaneous task allocation and planning under uncertaintyJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:46550cd8-d7ff-4037-b26c-a5d3f4cdf030EnglishSymplectic ElementsAssociation for Computing Machinery2024Faruq, FLacerda, BHawes, NParker, DWe present novel techniques for simultaneous task allocation and planning in multi-robot systems operating under uncertainty. By performing task allocation and planning simultaneously, allocations are informed by individual robot behaviour, creating more efficient team behaviour. We go beyond existing work by planning for task reallocation across the team given a model of partial task satisfaction under potential robot failures and uncertain action outcomes. We model the problem using Markov decision processes, with tasks encoded in co-safe linear temporal logic, and optimise for the expected number of tasks completed by the team. To avoid the inherent complexity of joint models, we propose an alternative model that simultaneously considers task allocation and planning, but in a sequential fashion. We then build a joint policy from the sequential policy obtained from our model, thus allowing for concurrent policy execution. Furthermore, to enable adaptation in the case of robot failures, we consider replanning from failure states and propose an approach to preemptively replan in an anytime fashion, replanning for more probable failure states first. Our method also allows us to quantify the performance of the team by providing an analysis of properties such as the expected number of completed tasks under concurrent policy execution. We implement and extensively evaluate our approach on a range of scenarios. We compare its performance to a state-of-the-art baseline in decoupled task allocation and planning: sequential single-item auctions. Our approach outperforms the baseline in terms of computation time and the number of times replanning is required on robot failure. |
| spellingShingle | Faruq, F Lacerda, B Hawes, N Parker, D A framework for simultaneous task allocation and planning under uncertainty |
| title | A framework for simultaneous task allocation and planning under uncertainty |
| title_full | A framework for simultaneous task allocation and planning under uncertainty |
| title_fullStr | A framework for simultaneous task allocation and planning under uncertainty |
| title_full_unstemmed | A framework for simultaneous task allocation and planning under uncertainty |
| title_short | A framework for simultaneous task allocation and planning under uncertainty |
| title_sort | framework for simultaneous task allocation and planning under uncertainty |
| work_keys_str_mv | AT faruqf aframeworkforsimultaneoustaskallocationandplanningunderuncertainty AT lacerdab aframeworkforsimultaneoustaskallocationandplanningunderuncertainty AT hawesn aframeworkforsimultaneoustaskallocationandplanningunderuncertainty AT parkerd aframeworkforsimultaneoustaskallocationandplanningunderuncertainty AT faruqf frameworkforsimultaneoustaskallocationandplanningunderuncertainty AT lacerdab frameworkforsimultaneoustaskallocationandplanningunderuncertainty AT hawesn frameworkforsimultaneoustaskallocationandplanningunderuncertainty AT parkerd frameworkforsimultaneoustaskallocationandplanningunderuncertainty |