•   When: Tuesday, May 01, 2018 from 10:00 AM to 12:00 PM
•   Speakers: Drew Wicke
•   Location: ENGR 4801
•   Export to iCal

Fundamental to many applications of multiagent systems is the problem of dynamically allocating tasks to agents that can solve them. Such dynamic task-allocation problems occur in a variety of real-life scenarios, ranging from automated delivery services to disaster response. The most popular current approach to solving this problem is based on auctioning tasks to the agents.  This relies on nonintuitive assumptions such as an infinite money supply, exclusive allocation of tasks, and lack of incentive to complete the task. Such assumptions fail to hold in many real-world scenarios.

To address these issues, we propose an alternate system for multiagent task allocation inspired by the behavior of bounty hunters and bail bondsmen.  In this model the bondsman assigns each task a reward called a bounty, and the bounty hunters myopically compete to finish the tasks.  Upon completion, the bounty is awarded to the bounty hunter that completes the task first.  The competition caused by nonexclusive allocation causes multiple agents to work on the same task, leading to an inefficient system. To solve this problem we study methods where the agents learn to split up the tasks so as to improve overall efficiency.

We study this technique and compare it to a number of exclusive methods including an auction-based approach.  We first consider an environment where the agents must commit to tasks and find that bounty hunting is robust in a number of dynamic environments.  We then relax task commitment to allow agents to change which task they are working on in order to address the problem of emergent and high-priority tasks.  This new approach outperforms not only commitment-based bounty hunting methods, but also exclusive methods.  Finally, we use bounty hunting as a heuristic to solve the dynamic traveling repairman problem, a dynamic task-allocation problem.  We find that the bounty hunting approach Pareto-dominates the state-of-the-art heuristic, Nearest Neighbor.  Finally, we give a demonstration of bounty hunting in cloud robotics and argue for its use in human-agent task allocation.