Solving multi-agent path planning by local search algorithms

• Main Author: Wang, Wenjie
• Other Authors: Goh Wooi Boon
• Format: Theses and Dissertations
• Language: English
• Published: 2015
• Subjects: DRNTU::Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence
• Online Access: https://hdl.handle.net/10356/62106
• Institution: Nanyang Technological University

Multi-Agent Path Planning (MAPP) in discrete space requires finding a collision-free path for each agent such that every agent can move from their starting positions to their respective destinations without colliding with other agents and static obstacles. With additional optimality criterion imposed, the MAPP problems can become intractable as the number of agents or the map size increases. This thesis specifically addresses two MAPP optimization problems, namely total energy cost minimized MAPP and makespan minimized MAPP. The total energy cost minimized MAPP aims at finding an optimal MAPP solution with respect to a cumulative objective function, while makespan minimized MAPP attempts to find an optimal MAPP solution with respect to a minimax objective function. Though finding an optimal solution for these two MAPP problems can be solved by existing optimal MAPP algorithms, the required computational time can be unacceptable even for relatively small map size and number of agents. This work aims at finding a sufficiently good MAPP solution in a reasonable time and therefore adopts a local search approach for MAPP since local search algorithms are widely used to find a good enough solution for computationally hard problems in a reasonable time. A basic local search algorithm called Iterative Path Coordination (IPC) for MAPP is first introduced. The IPC algorithm iteratively improves the path quality for one of the agents with respect to a cost function until no further improvement is possible within the current MAPP solution or a preset time bound is reached. Based on this framework, three variants of IPC are proposed to address the inherent drawbacks of IPC, such as the problem of being trapped in local optima and the high computational cost. The first is a deterministic variant called Guided Iterative Path Coordination (GIPC) which adopts a guided cost function for MAPP. Each time an infeasible locally optimal solution is encountered, the guided cost function is modified. In doing so, the guided cost function helps steer the search away from infeasible local optima. The second is a stochastic variant called Probabilistic Iterative Path Coordination (PIPC) that employs a probabilistic solution generation mechanism for MAPP. The mechanism generates a better neighboring solution with a higher probability. As such, an optimal MAPP solution can be quickly obtained with the highest probability. The final variant of IPC is a hybrid technique called Reactive Iterative Path Coordination (RIPC). This hybrid approach is able to combine the strengths of both the deterministic and stochastic variants as it has PIPC's computational efficiency in searching for a solution in the local neighborhood while maintaining GIPC's superior ability of escaping from infeasible local optima. The performance of the proposed IPC-based algorithms were separately evaluated and compared with other MAPP algorithms designed for total cost minimized and makespan minimized MAPP. The comparative results show that the proposed variants of IPC strike a good tradeoff between the solution quality and the computational time incurred. With a limited computational time, they are able to outperform existing state-of-the-art MAPP algorithms in finding a superior MAPP solution using both the optimality criteria evaluated.