Optimized any-angle safe interval path planning for lifelong multi-agent pickup and delivery

Abstract

Multiagent Pickup and Delivery is an abstraction of real-world warehouse logistics problems that requires continuous replanning in response to a continuous stream of tasks, and thus faces a tradeoff of computational performance and delivery performance, as measured by both throughput and latency. In this thesis, we design, implement and evaluate a novel algorithm for the Lifelong Multi-Agent Pickup and Delivery problem. We construct a relatively simple decoupled algorithm with a greedy task assigner and a single-agent dynamic obstacle path planner as the foundation to investigate potential enhancements. We implement recently proposed cutting-edge features such as speculative task swaps, any-angle path planning, bounded suboptimality and space-utilization heuristics with novel formulations and optimizations. All the algorithms are simulated and benchmarked to show their relative contribution in combination to both computational scalability and delivery performance. The results show that we can achieve satisfactory delivery performance in real-time, scaling to very large warehouse scenarios on modern computing hardware.

Date of Award	2024
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology
Supervisor	Ling SHI (Supervisor)