Dynamic Traveling Repairmen Bounty Hunters

Vehicle routing problems such as the multiagent dynamic traveling repariman problem (DTRP) are of interest to many fields and of increasing practical importance in light of advances in autonomous vehicles. DTRP is NP-hard, making approximation methods attractive. However, current approaches do not adequately consider issues special to DTRP, such as discontiguous-space scenarios or alternatives to equitably partitioning the task space. We tackle this problem in a novel way, using a multiagent task allocation technique called bounty hunting. In bounty hunting, agents compete to perform tasks non-exclusively in return for reward, and rapidly learn which agents are more adept at various tasks, implicitly splitting up the task space. We demonstrate that bounty hunting can perform efficiently in discontiguous environments, and Pareto-dominates the state-of-the-art heuristic technique, and is particularly good in large-scale scenarios.