  This paper proposes a control method for the multi-agent pickup and delivery
problem (MAPD problem) by extending the priority inheritance with backtracking
(PIBT) method to make it applicable to more general environments. PIBT is an
effective algorithm that introduces a priority to each agent, and at each
timestep, the agents, in descending order of priority, decide their next
neighboring locations in the next timestep through communications only with the
local agents. Unfortunately, PIBT is only applicable to environments that are
modeled as a bi-connected area, and if it contains dead-ends, such as
tree-shaped paths, PIBT may cause deadlocks. However, in the real-world
environment, there are many dead-end paths to locations such as the shelves
where materials are stored as well as loading/unloading locations to
transportation trucks. Our proposed method enables MAPD tasks to be performed
in environments with some tree-shaped paths without deadlock while preserving
the PIBT feature; it does this by allowing the agents to have temporary
priorities and restricting agents' movements in the trees. First, we
demonstrate that agents can always reach their delivery without deadlock. Our
experiments indicate that the proposed method is very efficient, even in
environments where PIBT is not applicable, by comparing them with those
obtained using the well-known token passing method as a baseline.
