Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm
This work addresses combinatorial optimization problems with constraints and multiple agents, offering an incremental improvement in computational efficiency for specific applications like assignment tasks.
The authors tackled constrained deterministic dynamic programming problems, particularly multiagent combinatorial optimization, by extending the rollout algorithm with a base heuristic and showing it maintains feasibility and cost improvement. They demonstrated the approach on multidimensional assignment problems using the auction algorithm, achieving computational efficiency suitable for many-agent scenarios.
We consider an extension of the rollout algorithm that applies to constrained deterministic dynamic programming, including challenging combinatorial optimization problems. The algorithm relies on a suboptimal policy, called base heuristic. Under suitable assumptions, we show that if the base heuristic produces a feasible solution, the rollout algorithm has a cost improvement property: it produces a feasible solution, whose cost is no worse than the base heuristic's cost. We then focus on multiagent problems, where the control at each stage consists of multiple components (one per agent), which are coupled either through the cost function or the constraints or both. We show that the cost improvement property is maintained with an alternative implementation that has greatly reduced computational requirements, and makes possible the use of rollout in problems with many agents. We demonstrate this alternative algorithm by applying it to layered graph problems that involve both a spatial and a temporal structure. We consider in some detail a prominent example of such problems: multidimensional assignment, where we use the auction algorithm for 2-dimensional assignment as a base heuristic. This auction algorithm is particularly well-suited for our context, because through the use of prices, it can advantageously use the solution of an assignment problem as a starting point for solving other related assignment problems, and this can greatly speed up the execution of the rollout algorithm.