Heterogeneous Multi-Agent Planning Using Actuation Maps

Abstract

Many real-world robotic scenarios require performing task planning to decide courses of actions to be executed by (possibly heterogeneous) robots. A classical centralized planning approach that considers in the same search space all combinations of robots and goals could lead to inefficient solutions that do not scale well. Multi-Agent Planning (MAP) provides a good framework to solve this kind of tasks efficiently. Some MAP techniques have proposed to previously assign goals to agents (robots) so that the planning effort decreases. However, these techniques do not scale when the number of agents and goals grow, as in most real world scenarios with big maps or goals that cannot be reached by subsets of robots. In this paper we propose to help the computation of which goals should be assigned to each agent by using Actuation Maps (AMs). Given a map, AMs can determine the regions each agent can actuate on. They help on alleviating the effort of MAP techniques knowing which goals can be tackled by each agent, as well as cheaply estimating the cost of using each agent to achieve every goal. Experiments show that when information extracted from AMs is provided to the Multi Agent planner, goal assignment is significantly faster, speeding-up the planning process considerably. Experiments also show that this approach greatly outperforms classical centralized planning.