A simultaneous descending auction for task allocation

Abstract

The coalition formation problem for task allocation is a difficult and increasingly studied problem (e.g., [1-3]); however, less studied is the notion of task preemption in multi-robot systems. A previously proposed ascending auction based task allocation protocol, RACHNA, is one of the few algorithms that explicitly allows task preemption. This paper demonstrates that the manner in which RACHNA permits task preemption has an undesirable side effect in which RACHNA needlessly changes the coalition assigned to a given task, even when the original coalition can still complete the task. A simultaneous descending auction based approach to task allocation is introduced that allows task preemption and never exhibits the unnecessary task reassignments exhibited by RACHNA.