Self-organizing multi-agent systems for shared space operations: Using genetic algorithms and contract net protocols to solve the pickup and delivery problem

Abstract

Automation of on-site scheduling and route planning of units in a mining operation presents interesting challenges. The dynamic properties of real-life operations necessitate AI-inspired decentralized methods, which tend to be more robust under real conditions. Moreover, route planning in a mining environment, consisting of narrow passageways, requires vehicles to communicate and cooperate for safe and efficient transportation. We model this as a dynamic multiple-agent pickup and delivery problem; a problem in which multiple agents cooperate to complete transportation tasks that are revealed continuously. Taking inspiration from novel solutions, using auction-like bidding systems based on genetically optimized heuristics, we tackle the pickup and delivery problem (PDP) from two different angles. Firstly, we show that existing solutions to the planar variant of the PDP can be improved by giving agents the ability to communicate. Secondly, we present a solution method to the PDP in a shared space environment, applicable for real world scenarios such as a mining operation. Apart from using the aforementioned bidding system to assign tasks to agents, we also implement a method for solving decentralized multiple-agent path finding.