论文标题
用拍卖算法有限的多构推出和多维分配
Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm
论文作者
论文摘要
我们考虑适用于有限的确定性动态编程的推广算法的扩展，包括具有挑战性的组合优化问题。该算法依赖于次优政策，称为基础启发式。在适当的假设下，我们表明，如果基本启发式构成产生可行的解决方案，则推出算法具有提高成本的属性：它会产生可行的解决方案，其成本并不比基本启发式的成本差。 然后，我们专注于多基因问题，每个阶段的控制由多个组件（每个代理）组成，这些组件通过成本函数或约束或两者兼而有之。我们表明，通过替代实现的成本提高属性可大大降低计算要求，并可以在许多代理商的问题中使用推出。我们通过将其应用于涉及空间结构和时间结构的分层图问题来证明这种替代算法。我们详细考虑了此类问题的一个重要例子：多维分配，在其中使用拍卖算法将二维分配作为基础启发式。该拍卖算法特别适合我们的上下文，因为通过使用价格，它可以有利地使用分配问题的解决方案作为解决其他相关任务问题的起点，这可以大大加快推广算法的执行。
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.
