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-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. CCS CONCEPTS • Computing methodologies → Multi-agent planning; • Theory of computation → Algorithmic mechanism design.