Integration of Efficient Techniques Based on Endpoints in Solution Method for Lifelong Multiagent Pickup and Delivery Problem

Abstract

We investigate the integration of several additional efficient techniques that improve a solution method for the lifelong multiagent pickup-and-delivery (MAPD) problem to reduce the redundancy in the concurrent task execution and space usage of a warehouse map. The lifelong MAPD problem is an extended class of iterative multiagent pathfinding problems where a set of shortest collision-free travel paths of multiple agents is iteratively planned. This problem models a system in automated warehouses with robot-carrier agents that are allocated to pickup-and-delivery tasks generated on demand. In the task allocation to agents, several solution methods for lifelong MAPD problems consider the endpoints of the agents’ travel paths to avoid the deadlock situations among the paths due to the conflict of the endpoints. Since redundancies are found in the problem settings themselves and the concurrency of allocated tasks, several additional techniques have been proposed to reduce them in solution methods. However, there should be opportunities to investigate the integration of additional techniques with improvements for more practical solution methods. As analysis and an improved understanding of the additional solution techniques based on endpoints, we incrementally integrate the techniques and experimentally investigate their contributions to the quality of task allocation and the paths of the agents. Our result reveals significant complementary effects of the additionally integrated techniques and trade-offs among them in several different problem settings.

Keywords

• multiagent pickup-and-delivery
• multiagent pathfinding
• lifelong problem
• endpoints