Events Calendar

PhD Defense - Xiaoming Zheng

Thesis Title: Auction and Negotiation Algorithms for Decentralized Task Allocation

Date: May 29th, 2014
Time: 2:00 pm
Location: GFS 111

Committee: Prof. Sven Koenig (Chair)
Prof. Craig Tovey
Prof. David Kempe
Prof. Maged Dessouky (Outside Member)

Abstract:

It is often important to coordinate a team of robots
well in a distributed computing environment. In this dissertation, we study how to allocate and re-allocate tasks to distributed robots so that the team cost is as small as possible (= the team performance is as high as possible). Researchers have developed several algorithms based on auction-like and negotiation-like protocols for decentralized task allocation. However, the majority of these existing algorithms use either single-item auctions, in which only one task is allocated to some robot in one round so that the team cost increases the least, or single-item exchanges, in which only one task is transferred between two robots in one round so that the team cost decreases the most. These algorithms usually result in highly sub-optimal allocations and do not apply to complex tasks that need to be executed by more than one robot
simultaneously.

We develop a new auction algorithm, called sequential auctions
with bundles, that extends single-item auctions to be able to
allocate more than one task to robots in one round so that the team cost increases the least. We introduce a novel data structure, called bid trees, that each robot can construct and submit to the auctioneer independently. Theoretical results show that the bids from bid trees can succinctly characterize all necessary local information of robots needed by the auctioneer to allocate multiple tasks to robots in one round so that the team cost increases the least. Experimental results show that sequential auctions with bundles reduce the team costs of single-item auctions significantly.

We develop a new negotiation algorithm, called sequential
negotiations with K-swaps, that extends single-item exchanges to
be able to re-allocate more than one task among robots in one round so that the team cost decreases the most. We introduce a novel data structure, called partial k-swaps, that each robot can
construct and propose to other robots independently. Theoretical
results show that profitable partial k-swaps can succinctly
characterize all necessary local information of robots needed to
re-allocate multiple tasks among them so that the team cost
decreases the most. Experimental results show that sequential
negotiations with K-swaps reduce the team costs of given
initial allocations significantly.

We develop a new auction algorithm, called sequential auctions
with reaction functions, that extends single-item auctions to be
able to allocate either a simple or complex task to robots in one
round so that the team cost increases the least. We introduce a novel data structure, called reaction functions, that each robot can construct and submit to the auctioneer independently. Theoretical results show that reaction functions can succinctly characterize all necessary local information of robots needed by the auctioneer to allocate either a simple or complex task to robots in one round so that the team cost increases the least. Experimental results show that sequential auctions with reaction functions reduce the team costs of an existing auction algorithm significantly.

Finally, we develop a new negotiation algorithm, called sequential negotiations with reaction functions, that extends single-item exchanges to be able to re-allocate complex or simple tasks among robots in one round so that the team cost decreases the most. Theoretical results show that reaction functions can succinctly characterize all necessary local information of robots needed to re-allocate complex or simple tasks among them so that the team cost decreases the most. Experimental results show that sequential negotiations with reaction functions reduce the team costs of given initial allocations significantly.

To summarize, in this dissertation we develop new auction and
negotiation algorithms for solving task-allocation problems with
simple and complex tasks and demonstrate empirically that
these new algorithms reduce the team costs of existing ones
significantly.

Location: Grace Ford Salvatori Hall Of Letters, Arts & Sciences (GFS) - 111

Audiences: Everyone Is Invited

Contact: Lizsl De Leon