An efficient lightweight coordination model to multi-agent planning

摘要

The main issue in multi-agent planning (MAP) is the agents’ coordination process that is a computationally hard problem. Thus, many works focus on the planning strategy considering the computational process, agents’ distribution roles, information privacy, and the resources coupling level. But domain-independent models that explore the balance between coordination process and privacy leading to efficient execution are missing. In this manuscript, we present a Lightweight Coordination Multi-agent Planning (LCMAP), a domain-independent model that balances the coordination process and privacy through three independent phases: (i) verification—each agent verifies its capabilities of reaching the goals; (ii) transformation—the coordinator selects agents through their capabilities and distributes the goals, transforming the original problem into single-agent problems; and (iii) validation—each plan is validated to check whether it can be parallel. LCMAP was compared to the state-of-the-art models to evaluate time efficiency and plan length during the problem-solving process using loosely and tightly coupled domains with specific evaluation metrics inherited from planning competitions. Furthermore, we conducted experiments to evaluate the execution efficiency regarding different configurations concerning planning time and plan length of the models, when LCMAP execution proves to be efficient.