Utility-Maximizing Task Scheduling for Partially Observable Multiagent Systems

摘要

Task scheduling in a multiagent system makes decision on assigning which (and how many) tasks to which neighbour agents, therefore has immediate impact on the efficiency of resource utilization of the multiagent systems. In a large scale partially observable multiagent system, a globally optimal scheduling is more challenging because agents only have a partial view and limited information of the whole system. In this paper, we consider the problem of utility-maximizing task scheduling for a large scale partially observable multiagent system to achieve global optimum in a decentralized manner. We model the task scheduling as a nonlinear discrete optimization problem with coupled objective and constraints. We design a distributed primal-dual algorithm based on Lagrangian relaxation and solve the primal problem with a novel greedy algorithm and the dual algorithm with subgradient method respectively. We demonstrate the efficiency of our solution with a simple network but characterizing the essence of resource competition among agents and show that our algorithm can converge to the global optimum within limited steps of iteration.