Multilevel Approach to Agent-Based Task Allocation in Transportation

We present a hybrid algorithm for distributed task allocation problem in a cooperative logistics domain. Our approach aims to achieve superior computational performance by combining the classic negotiation techniques and acquaintance models from agent technology field with methods from the operation research and AI planning. The algorithm is multi-stage and makes a clear separation between discreet planning that defines the tasks and allocation of resources to available tasks. Task allocation starts with centralized planning based on acquaintance model information that prepares a framework for efficient distributed negotiation. The subsequent distributed part of the task allocation process is parallel for all tasks and allows the agents to optimally allocate their resources to proposed tasks and to further optimize the allocation by negotiation with other agents. Parallel execution of the task allocation mechanism allows the algorithm to answer the planning request in predictable time, albeit at expense of possible non-optimality. In the experiments, we evaluate the relative importance of OR and negotiation parts of the task allocation process.