Negotiated path planning for non-cooperative multi-robot systems

Conference item

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.

Authors: Gautier, A; Stephens, A; Lacerda, B; Hawes, N; Wooldridge, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Host title: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022)
• Volume: 1
• Pages: 472-480
• Publication date: 2022-05-09
• Acceptance date: 2021-12-18
• Event title: 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022)
• Event location: Auckland, New Zealand
• Event website: https://aamas2022-conference.auckland.ac.nz/
• Event start date: 2022-05-09
• Event end date: 2022-05-13
• EISSN: 1558-2914
• ISSN: 1548-8403
• ISBN: 9781713854333
• Language: English
• Keywords: FFR