Conflict-oriented windowed hierarchical cooperative A
2014 ieee international conference on robotics and automation (icra), 2014•ieeexplore.ieee.org
In the Multi-Agent Path Finding problem (MAPF), we are given a map and a set of agents
with distinct source and goal locations. The task is to compute a path for each agent from its
initial location to its goal location without conflicting with other agents. MAPF solvers can be
divided into classes based on their purpose. One of these classes is the class of online
MAPF algorithms, in which the search for paths is interleaved with the actual physical moves
of the agents. A prominent algorithm in this class is the Windowed Hierarchical Cooperative …
with distinct source and goal locations. The task is to compute a path for each agent from its
initial location to its goal location without conflicting with other agents. MAPF solvers can be
divided into classes based on their purpose. One of these classes is the class of online
MAPF algorithms, in which the search for paths is interleaved with the actual physical moves
of the agents. A prominent algorithm in this class is the Windowed Hierarchical Cooperative …
In the Multi-Agent Path Finding problem (MAPF), we are given a map and a set of agents with distinct source and goal locations. The task is to compute a path for each agent from its initial location to its goal location without conflicting with other agents. MAPF solvers can be divided into classes based on their purpose. One of these classes is the class of online MAPF algorithms, in which the search for paths is interleaved with the actual physical moves of the agents. A prominent algorithm in this class is the Windowed Hierarchical Cooperative A∗ algorithm (WHCA∗) where paths are planned for each agent individually and cooperation is obtained using a reservation table. A number of extensions for WHCA∗ already exist. In this paper we propose a general approach for the baseline WHCA∗ algorithm which is orthogonal to all other existing extensions. We improve WHCA∗ by introducing the Conflict Oriented (CO) principle for focusing the agent coordination around conflicts. In addition, we provide a conflict-oriented prioritization mechanism that intelligently chooses which agent should act next. Experimental results demonstrate the advantage of our approach over WHCA∗.
ieeexplore.ieee.org