Multi-agent route planning using delegate MAS

摘要

Multi-agent route planning (MARP) is a problem that occurs in many applications such as automated guided vehicles, robotics, intelligent transportation networks and airplane taxiing. MARP becomes especially challenging when the application domain is dynamic, large scale and requires continual planning. Due to its decentralized nature, a multi-agent system (MAS) is an ideal candidate for solving dynamic and large scale MARP problems. Delegate MAS is a coordination mechanism based on the idea of intention propagation via the environment inspired by ant behavior. We evaluate delegate MAS on automated guided vehicle routing under realistic conditions. Delegate MAS is compared with context-aware routing, a state-of-the-art centralized approach for dynamic MARP. Two variants of MARP are considered, single-stage where vehicles each have to visit a single destination and multi-stage where a sequence of destinations has to be visited. The experiment results show that delegate MAS and context-aware routing have comparable solution quality while delegate MAS is more scalable for multi-stage routing in dynamic environments and offers higher throughput when continual planning is required.