Multi-agent Pathfinding Based on Improved Cooperative A* in Kiva System

Abstract

In the Multi-Agent Pathfinding problem, a set of agents with distinct start and goal ports are assigned to finish different jobs. The problem's task is to use a typical algorithm to compute a path for each agent, so that every agent can finish their jobs with satisfied performance. The study of this problem can improve the efficiency of robots in warehouse material transportation and logistics sorting. In this paper, we propose an algorithm named Improved Cooperative A*(ICA*) by introducing addition pathfinding cost for less turns and overlapping among paths. Furthermore, we propose a principle called Dynamic Weight Guidance that can dynamically provide a guiding strategy for each agent. Experimental results demonstrate that our algorithm can reduce the total number of moving steps, makespan and waiting times of all agents to a certain extent.