Files in this item

FilesDescriptionFormat

application/pdf

application/pdfSENGUPTA-THESIS-2021.pdf (823kB)
(no description provided)PDF

Description

Title:Fair allocation of operations and makespan minimization for multiple robotic agents
Author(s):Sengupta, Raunak
Advisor(s):Nagi, Rakesh
Department / Program:Industrial&Enterprise Sys Eng
Discipline:Industrial Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(s):Makespan Minimization
Fair Allocation
Decentralized Task Allocation
Approximation Factor
Abstract:We study the problem of allocating a set of indivisible operations to a set of agents in a fair and efficient manner while also minimizing the makespan. We first present the Operation Trading Algorithm that generates allocations satisfying the DEQx (Duplicated Equitability up to any operation) fairness criterion while also guaranteeing an upper bound of 2 on the makespan for identical agents. The algorithm also guarantees an upper bound of 1.618 for 2 uniformly related agents and (1+√(4n−3))/2 for n uniformly related agents. The pairwise approach used in this algorithm has the added advantages of being decentralizable, reactive and robust. A new protocol named as the Decentralized Random Group Formation (DRGF) Protocol is presented for implementing the Operation Trading Algorithm in a decentralized manner and for dealing with communication failures. We then define a relaxed version of the DEQ1 (Duplicated Equitability upto some operation) fairness criterion called partial-DEQ1. A market-based algorithm is presented to achieve partial-DEQ1 along with Pareto Optimality. Following this, it is shown that the algorithm also guarantees an upper bound of 1.618 on the makespan for 2 non-identical agents. Parametric pruning further improves the upper bound to 1.5, which is theoretically the best possible upper bound. To the best of our knowledge, these are the first algorithms designed to achieve the mentioned fairness criteria. The algorithms additionally guarantee upper bounds on the makespan. Finally, we show the efficacy of the algorithms in generating allocations with near optimal makespans by numerically evaluating the algorithms on randomly generated problem instances.
Issue Date:2021-07-20
Type:Thesis
URI:http://hdl.handle.net/2142/113064
Rights Information:Copyright 2021 Raunak Sengupta
Date Available in IDEALS:2022-01-12
Date Deposited:2021-08


This item appears in the following Collection(s)

Item Statistics