title: Artificial Intelligent-Based Multi-Agent Collaborative Path Planning Methods
Creators: name: Xiao, Ziren
Publisher: name: University of Liverpool Repository
Year: 2024

description: Artificial intelligence-driven navigation for multi-user interaction is rapidly gaining attraction in various research fields. This technology offers efficient resource planning and management capabilities, playing a vital role in mitigating traffic congestion. By leveraging AI approaches, the navigation systems can dynamically plan paths for multiple users, maximising transport efficiency while minimising energy consumption and travel times, which enhances individual user experiences and improves overall transportation infrastructure sustainability.

Among navigation methods, I particularly focus on an emerging navigation problem, Dynamic Multi-Sources to Single Destination (DMS-SD), which had yet to be well addressed in past studies. Traditionally, navigation solvers, such as global path planning solutions, mainly consider the accuracy of the destination, preferences of multiple users and global obstacle (e.g., a closed road) avoidance. The DMS-SD problem involves those typical considerations and further includes (i) the dynamicity of the destination, where the planned path or the destination is not a fixed point and can be dynamically shifted to another position, based on users' current location and their preferences, and (ii) the collaboration between multiple users, where collected information from other agents and makes the best choice for all agents, rather than only considering its own (local) status. These two considerations are challenging, on the one hand, the solver must deal with a time-sensitive environment, such as real-time or near-real-time, on mobile devices, where the computational resources and power consumption are strictly limited; on the other hand, it is difficult to balance preferences (e.g., shortest distance or time) between multiple users, where a trade-off has to be made for specific users (e.g., a user moves a longer distance while all other users move a relatively shorter distance). 

To address these challenges, I have proposed three solutions to enable software agents to automatically and efficiently plan an optimal or sub-optimal path to a temporary common destination, where all agents can fairly reach this point under their current situations. The first solution integrates Monte Carlo Tree Search (MCTS) into a swarm intelligent algorithm, Ant Colony Optimisation (ACO), to initially address DMS-SD. The main advantage of this method is to reduce the randomisation of ACO using MCTS without much prior knowledge about the entire map, enabling collaboration between multiple users with a faster computation than enumerating methods. This approach indicates up to 20 times faster than the enumerated approaches with less than 10 steps to the optimal solution in the experiments. However, this approach can only be suitably applied on a small map (e.g., a university campus), or otherwise the method costs an intolerant time for users. Therefore, the second solution I proposed relies on the Deep Reinforcement Learning (DRL) technique, a promising paradigm used to deal with highly dynamic and complex problems. It models the problem and environment as a Markov Decision Process, and consequently generates a well-trained DRL model that stores the moving pattern based on agents' current states. The use of DRL has improved the response time by up to 100ms (i.e., process latency of the model) to a millisecond level, enhancing the user experience. Moreover, the trained DRL model can be easily deployed on lightweight devices, such as Internet of Things (IoT) devices and mobile phones. 
The third solution integrates a Graph Neural Network into the policy network of a state-of-the-art DRL algorithm for the decision-making of individual agents. It is a complement of the previous solution, which can dynamically change the number of agents without fully retraining the DRL model, while the second solution needs a new model. In the evaluation, it also indicates a faster training speed and generates results that are closer to the optimal than the second solution. It also shows up to 500 times better in the step taken to the destination and up to 3 times faster training time (i.e., time spent converging to the optimal solution) compared with other state-of-the-art DRL algorithms. Additionally, to demonstrate our approach in a real environment, I have built a web-based application and implemented it under a real-world map based on the third solution. 

The main purpose of the solver is to efficiently manage the computational resources while maintaining an excellent user experience (e.g., fast response time and accurate destination). Further, the solver of this problem is especially useful and applicable to industrial areas or domains, such as industrial manufacturing, port management, warehouse scheduling, and real-time navigation of multiple robots in factories.