Negotiated path planning for non-cooperative multi-robot systems
As autonomous systems are deployed at a large scale in both public and private spaces, robots owned and operated by competing organisations will be required to interact. Interactions in such settings will be inherently non-cooperative. In this paper, we address the problem of non-cooperative multi-a...
| Main Authors: | , , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Association for Computing Machinery
2022
|
| _version_ | 1797109028827955200 |
|---|---|
| author | Gautier, A Stephens, A Lacerda, B Hawes, N Wooldridge, M |
| author_facet | Gautier, A Stephens, A Lacerda, B Hawes, N Wooldridge, M |
| author_sort | Gautier, A |
| collection | OXFORD |
| description | As autonomous systems are deployed at a large scale in both public and private spaces, robots owned and operated by competing organisations will be required to interact. Interactions in such settings will be inherently non-cooperative. In this paper, we address the problem of non-cooperative multi-agent path finding. We design an auction mechanism that allows a group of agents to reach their goals whilst minimising the total cost of the system. In particular, we aim to design a mechanism such that rational agents are incentivised to participate. Our privileged knowledge auction consists of a modified combinatorial Vickrey-Clarke-Groves auction. Our approach limits the initial number of bids in the Vickrey-Clarke-Groves auction, then uses the privileged knowledge of the auctioneer to identify and solve path conflicts. In order to maintain agent autonomy in the non-cooperative system, individual agents are provided with final say over paths. The mechanism provides a heuristic method to maximise social welfare whilst remaining computationally efficient. We also consider single-agent bid generation and propose a similarity metric to use in dissimilar shortest path generation. We then show this bid generation method increases the success likelihood of both the limited-bid VCG auction and our novel approach on synthetic data. Our experiments with synthetic data outperform existing work on the non-cooperative problem. |
| first_indexed | 2024-03-07T07:36:19Z |
| format | Conference item |
| id | oxford-uuid:599f816c-5d90-4b8d-a139-977ce308f9eb |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:36:19Z |
| publishDate | 2022 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:599f816c-5d90-4b8d-a139-977ce308f9eb2023-03-13T14:30:15ZNegotiated path planning for non-cooperative multi-robot systemsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:599f816c-5d90-4b8d-a139-977ce308f9ebEnglishSymplectic ElementsAssociation for Computing Machinery2022Gautier, AStephens, ALacerda, BHawes, NWooldridge, MAs autonomous systems are deployed at a large scale in both public and private spaces, robots owned and operated by competing organisations will be required to interact. Interactions in such settings will be inherently non-cooperative. In this paper, we address the problem of non-cooperative multi-agent path finding. We design an auction mechanism that allows a group of agents to reach their goals whilst minimising the total cost of the system. In particular, we aim to design a mechanism such that rational agents are incentivised to participate. Our privileged knowledge auction consists of a modified combinatorial Vickrey-Clarke-Groves auction. Our approach limits the initial number of bids in the Vickrey-Clarke-Groves auction, then uses the privileged knowledge of the auctioneer to identify and solve path conflicts. In order to maintain agent autonomy in the non-cooperative system, individual agents are provided with final say over paths. The mechanism provides a heuristic method to maximise social welfare whilst remaining computationally efficient. We also consider single-agent bid generation and propose a similarity metric to use in dissimilar shortest path generation. We then show this bid generation method increases the success likelihood of both the limited-bid VCG auction and our novel approach on synthetic data. Our experiments with synthetic data outperform existing work on the non-cooperative problem. |
| spellingShingle | Gautier, A Stephens, A Lacerda, B Hawes, N Wooldridge, M Negotiated path planning for non-cooperative multi-robot systems |
| title | Negotiated path planning for non-cooperative multi-robot systems |
| title_full | Negotiated path planning for non-cooperative multi-robot systems |
| title_fullStr | Negotiated path planning for non-cooperative multi-robot systems |
| title_full_unstemmed | Negotiated path planning for non-cooperative multi-robot systems |
| title_short | Negotiated path planning for non-cooperative multi-robot systems |
| title_sort | negotiated path planning for non cooperative multi robot systems |
| work_keys_str_mv | AT gautiera negotiatedpathplanningfornoncooperativemultirobotsystems AT stephensa negotiatedpathplanningfornoncooperativemultirobotsystems AT lacerdab negotiatedpathplanningfornoncooperativemultirobotsystems AT hawesn negotiatedpathplanningfornoncooperativemultirobotsystems AT wooldridgem negotiatedpathplanningfornoncooperativemultirobotsystems |