Towards addressing dynamic multi-agent task allocation in law enforcement

摘要

Police officers conduct routine patrols and perform tasks in response to reported incidents. The importance of each task varies from low (e.g. noise complaint) to high (e.g. murder). The workload associated with each task, indicating the amount of work to be completed for the incident to be processed, may vary as well. Multiple officers with heterogeneous skills may work together on important tasks to share the workload and improve response time. To deal with the underlying law enforcement problem (LEPH), one needs to allocate police officers to dynamic tasks whose locations, arrival times, and importance levels are unknown a priori. Addressing this challenge and inspired by real police logs, this research aims to solve the LEPH problem by using and comparing three methods: Fisher market-based FMC_TAH+, swarm intelligence HDBA, and Simulated Annealing SA algorithms. FMC_TAH+ is implemented, using agents as buyers and tasks as goods, to compute fair allocations (i.e. envy-free), and efficient (i.e. Pareto-optimal) in a polynomial or pseudo-polynomial time. FMC_TAH+ allocations are heuristically scheduled, considering inter-agent constraints on shared tasks. HDBA, a probabilistic swarm intelligence algorithm inspired by the emergent behavior of social bees, was previously implemented to allocate agents to tasks based on agent performance, task priorities, and distances between agents and task-execution locations. SA is a meta-heuristic for approximating the global optimums in large optimization problems. The three methods were compared in this study for five different performance measures that are commonly used by law enforcement authorities. The results indicate an advantage for FMC_TAH+ both in total utility and in the average arrival time to tasks. Also, compared respectively to HDBA and SA, FMC_TAH+ leads to 34% and 32% higher team utility in the highest shift workload.