The full text of this item is not available at this time because the student has placed this item under an embargo for a period of time. The Libraries are not authorized to provide a copy of this work during the embargo period, even for Texas A&M users with NetID.
Linear Sum Assignment Algorithms for Distributed Multi-robot Systems
dc.contributor.advisor | Shell, Dylan A. | |
dc.creator | Liu, Lantao | |
dc.date.accessioned | 2013-10-02T21:28:59Z | |
dc.date.available | 2015-05-01T05:57:08Z | |
dc.date.created | 2013-05 | |
dc.date.issued | 2013-04-30 | |
dc.date.submitted | May 2013 | |
dc.identifier.uri | https://hdl.handle.net/1969.1/149316 | |
dc.description.abstract | Multi-robot task assignment (allocation) involves assigning robots to tasks in order to optimize the entire team’s performances. Until now, one of the most useful non-domain-specific ways to coordinate multi-robot systems is through task allocation mechanisms. This dissertation addresses the classic task assignment problems in which robots and tasks are eventually matched by forming a one-to-one mapping, and their overall performances (e.g., cost, utility, and risk) can be linearly summed. At a high level, this research emphasizes two facets of the multi-robot task assignment, including (1) novel extensions from classic assignment algorithms, and (2) completely newly designed task allocation methods with impressive new features. For the former, we first propose a strongly polynomial assignment sensitivity analysis algorithm as well as a means to measure the assignment uncertainties; after that we propose a novel method to address problems of multi-robot routing and formation morphing, the trajectories of which are obtained from projections of augmenting paths that reside in a new three-dimensional interpretation of embedded matching graphs. For the latter, we present two optimal assignment algorithms that are distributable and suitable for multi-robot task allocation problems: the first one is an anytime assignment algorithm that produces non-decreasing assignment solutions along a series of task-swapping operations, each of which updates the assignment configurations and thus can be interrupted at any moment; the second one is a new market-based algorithm with a novel pricing policy: in contrast to the buyers’ “selfish” bidding behaviors in conventional auction/market-based approaches, we employ a virtual merchant to strategically escalate market prices in order to reach a state of equilibrium that satisfies both the merchant and buyers. Both of these newly developed assignment algorithms have a strongly polynomial running time close to the benchmark algorithms but can be easily decentralized in terms of computation and communication. | en |
dc.format.mimetype | application/pdf | |
dc.language.iso | en | |
dc.subject | Multi-robot systems | en |
dc.subject | task allocation | en |
dc.subject | assignment algorithms | en |
dc.subject | assignment uncertainty | en |
dc.subject | 3D matching graph | en |
dc.subject | task swapping | en |
dc.subject | optimal market-based | en |
dc.subject | distributed assignment | en |
dc.title | Linear Sum Assignment Algorithms for Distributed Multi-robot Systems | en |
dc.type | Thesis | en |
thesis.degree.department | Computer Science and Engineering | en |
thesis.degree.discipline | Computer Engineering | en |
thesis.degree.grantor | Texas A&M University | en |
thesis.degree.name | Doctor of Philosophy | en |
thesis.degree.level | Doctoral | en |
dc.contributor.committeeMember | Klappenecker, Andreas | |
dc.contributor.committeeMember | Song, Dezhen | |
dc.contributor.committeeMember | Ntaimo, Lewis | |
dc.type.material | text | en |
dc.date.updated | 2013-10-02T21:28:59Z | |
local.embargo.terms | 2015-05-01 |
Files in this item
This item appears in the following Collection(s)
-
Electronic Theses, Dissertations, and Records of Study (2002– )
Texas A&M University Theses, Dissertations, and Records of Study (2002– )