Linear Sum Assignment Algorithms for Distributed Multi-robot Systems
dc.contributor | Shell, Dylan A. | |
dc.creator | Liu, Lantao | |
dc.date.accessioned | 2015-05-01T05:57:08Z | |
dc.date.accessioned | 2017-04-07T20:04:08Z | |
dc.date.available | 2015-05-01T05:57:08Z | |
dc.date.available | 2017-04-07T20:04:08Z | |
dc.date.created | 2013-05 | |
dc.date.issued | 2013-04-30 | |
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. | |
dc.identifier.uri | http://hdl.handle.net/1969.1/149316 | |
dc.language.iso | en | |
dc.subject | Multi-robot systems | |
dc.subject | task allocation | |
dc.subject | assignment algorithms | |
dc.subject | assignment uncertainty | |
dc.subject | 3D matching graph | |
dc.subject | task swapping | |
dc.subject | optimal market-based | |
dc.subject | distributed assignment | |
dc.title | Linear Sum Assignment Algorithms for Distributed Multi-robot Systems | |
dc.type | Thesis |