Enhancing Market-Based Task Allocation with Optimal Initial Schedules

Abstract

Task allocation impacts the performance efficiency of agent teams in significant ways. Due to their efficient and proven performance, Market-based task allocation approaches have grown in popularity for many such multi-agent domains. In addition, market-based approaches are very well suited to dynamic domains such as emergency response, in which the set of the tasks or the environment changes in real time. However, market-based approaches are not guaranteed to produce optimal solutions and researchers have investigated many techniques for improving their performance in different scenarios. Since many application domains have a significant static component coupled with dynamic elements, we explore the option of enhancing team performance in these domains by seeding market-based task allocation with optimal schedules pre-computed for the static tasks. We compare the performance of the TraderBots market-based algorithm with and without the seeded optimal schedules in simulation and on a team of robots. Our results demonstrate that seeding market-based allocation with optimal schedules can improve team performance, particularly when the proportion of static tasks is high.