Verifiable Multi-Agent Multi-Task Assignment

This paper aims to solve security issues in online centralized multi-agent multi-task assignment (MAMTA) problems. Combining cutting-edge cryptographic protocols with MAMTA algorithms, we propose a securely centralized architecture for dispatching tasks among agents. Our approach suits agents with low computing power and can fit various systems well. The proposed architecture is similar to an account-based blockchain or a zk-rollup. It also potentially brings privacy to the agents. Using verifiable computation to prove proper task allocation to the agents, the central server furnishes proof that the computation is indeed as expected and that there were no errors or misbehavior. We developed a proof-of-concept for a specific use case based on the SKATE algorithm, a lightweight meta-heuristic approach for combinatorial optimization that is compatible with verifiable computation. Our use case is a robotic aerial mission in which the proposed architecture was implemented and then deployed in a real-world flight. Average proof generation and verification times were also assessed. Our results suggest the approach is suitable for future on-board use in mobile agents.