Title: Auction-Based Scheduling
Abstract:
I will describe a "decentralized synthesis" framework called "auction-based scheduling" in planning domains. Given a pair of non-contradicting objectives, the idea is, rather than constructing a monolithic plan for the conjunction of the objectives, to construct separately two "policies", one for each objective and compose the two policies at runtime. In order to resolve conflicts between the policies’ actions at runtime, we apply a bidding mechanism: each policy is allocated a budget, in each turn, a policy associates a "bid" with their proposed action, and the policy that bids higher, chooses the action and pays the other policy. Algorithms to solve auction-based scheduling rely on results on bidding games on graphs, which I will survey. I will then describe an extension of traditional bidding games, which addresses some of the limitations of auction-based scheduling, by allowing the players' budgets to be "charged" throughout the game by numeric values that appear on the vertices (similar to a gas station).