Fair allocation of operations and makespan minimization for multiple robotic agents

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Sengupta, Raunak

Contributors dc:contributor

• Nagi, Rakesh

• Makespan Minimization
• Fair Allocation
• Decentralized Task Allocation
• Approximation Factor

Statement dc:rights

• Copyright 2021 Raunak Sengupta

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/113064

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/113064