Lifelong multi-agent pathfinding with online tasks

• Main Author: Tay, David Ang Peng
• Other Authors: Tang Xueyan
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence; Engineering::Computer science and engineering::Computing methodologies::Simulation and modeling
• Online Access: https://hdl.handle.net/10356/166023
• Institution: Nanyang Technological University

The Multi-Agent Pathfinding (MAPF) problem involves finding optimal or near-optimal paths for multiple agents in a shared environment while avoiding collisions and conflicts. However, traditional MAPF is limited in its ability to handle real-life scenarios, such as automated warehouses, where agents face a continuous stream of tasks. To address this, we investigate the Multi-Agent Pickup and Delivery (MAPD) problem, which requires agents to complete tasks in an online, lifelong manner where tasks are added dynamically. To evaluate the effectiveness of recent algorithms in this field, we implement and test three different algorithms: Token Passing (TP), Token Passing with Task Swapping (TPTS), and CENTRAL. Our experiments reveal that the number of agents and frequency of task additions significantly impact algorithm performance. We also explore the relationship between agent energy levels, which corresponds to fuel and battery levels in real-world domains, and algorithm performance. We introduce variations of TP and TPTS algorithms for energy-restricted scenarios and find that such restrictions significantly affect performance. Thereafter, we also found significant relationship between performance and the energy level of agents. The project confirms the correlation between MAPD algorithm performance and various parameters. Furthermore, we introduce new techniques to handle energy restrictions and study their relationship with different parameters.