Optimierung von Polizeipatrouillen und Einsatzleitungsoperationen
Eine Studie zur Verbesserung der Reaktionszeiten der Polizei durch kombinierte Patrouillen- und Dispatch-Strategien.
Matthew Repasky, He Wang, Yao Xie
― 9 min Lesedauer
Inhaltsverzeichnis
- Überblick
- Gemeinsam optimierte Richtlinien für Patrouille und Dispatch
- Neuartige Optimierungsansätze
- Fokus auf Fairness in Dienstleistungssystemen
- Hintergrundinformationen
- Rahmen für Polizeiarbeit
- Problemformulierung
- Gemeinsamer Zustand und Aktionsraum
- Belohnungsstruktur
- Markov-Spiel-Zerlegung
- Methodik
- Gemeinsame Richtlinie für Patrouille und Dispatch
- Experimente
- Fazit
- Originalquelle
Polizeipatrouillen verbringen oft ihre Zeit zwischen präventiven Patrouillen und der Reaktion auf dringende Notrufe. Die Forschung hat diese beiden Aufgaben normalerweise getrennt betrachtet. In dieser Arbeit schauen wir uns an, wie man sowohl Patrouille als auch Einsatzoptimierung kombinieren kann, um die Polizeiarbeit effizienter zu gestalten und die Reaktionen auf Notfälle zu beschleunigen.
Überblick
Die Reaktionszeit der Polizei auf Notfälle ist entscheidend für die öffentliche Sicherheit und zur Verhinderung von Verbrechen. Neueste Berichte zeigen jedoch, dass die Reaktionszeiten in grossen US-Städten steigen, teilweise aufgrund von Personalmangel. Diese Studie konzentriert sich darauf, die Patrouillenoperationen der Polizei zu verbessern und die Reaktionszeiten bei Notfällen mithilfe von Multi-Agenten-Verstärkungslernen zu verkürzen, wobei jedes Polizeiauto als Agent betrachtet wird.
Die Koordinierung von Patrouillen mehrerer Polizeieinheiten in einem gemeinsamen Bereich ist seit vielen Jahren ein interessantes Thema. Forscher haben verschiedene Strategien angewendet, von Variationen des Traveling Salesman-Problems bis hin zu fortgeschrittenen Techniken des maschinellen Lernens. Bei der Multi-Agenten-Patrouille tauchen viele Herausforderungen auf, darunter die Vielzahl möglicher Aktionen, die Notwendigkeit der Zusammenarbeit zwischen Agenten und wie man die unterschiedlichen Zustände jedes Agenten darstellt.
Frühere Studien haben Patrouillenrichtlinien auf der Grundlage bewertet, wie gut sie ein Gebiet abdecken, indem sie sicherstellen, dass alle Orte häufig besucht werden. Im Gegensatz dazu bewertet diese Studie Patrouillenstrategien danach, wie sie mit den Einsatzagenten interagieren.
Die kombinierte Aufgabe von Patrouille und Einsatz erfordert Entscheidungen darüber, ob eine Patrouilleneinheit von ihrem üblichen Gebiet zu einem Vorfall geschickt werden soll oder ob die nächste Einheit reagieren soll, auch wenn das bedeutet, eine grössere Strecke zurückzulegen.
Traditionell wurde die Polizeidispatching durch die Linse der Multi-Server-Prioritätswarteschlangen betrachtet. Die Rolle des Dispatchers besteht darin, auszuwählen, welche Patrouilleneinheit zu einem Vorfallsort geschickt werden soll. Neueste Forschungen haben auch untersucht, wie Einsatzrichtlinien durch den Standort und die Routenentscheidungen der Patrouilleneinheiten beeinflusst werden können. Oft gibt es spezifische Ziele für die Reaktionszeit, die erreicht werden müssen.
Die Platzierung der Patrouilleneinheiten ist für eine effektive Disposition entscheidend, doch viele Studien zum Dispatching haben sich auf grundlegende Patrouillenstrategien gestützt. Frühere Arbeiten konzentrierten sich auf individuelle Agentenentscheidungen mit Heuristiken, die auf der Untätigkeit nahegelegener Einheiten basierten. Andere haben Einzelagentenprobleme auf mehrere Agenten ausgeweitet. Multi-Agenten-Verstärkungslernen (MARL) wurde für diese Aufgaben untersucht, bei denen Agenten Belohnungen teilen, um die Untätigkeitszeiten zu minimieren. Frühe Ansätze beinhalteten Einheiten, die nur lokale Informationen hatten, aber ihre Absichten mit anderen Einheiten teilen konnten. Neuere Methoden haben bayessisches Lernen und tiefes Verstärkungslernen angewendet, um Richtlinien zu optimieren, während unterschiedliche Kommunikationsniveaus zwischen Agenten erlaubt wurden.
Die Notwendigkeit für effiziente Polizeiarbeit ist aufgrund von Personalmangel und begrenzten Ressourcen gewachsen. Fairness in der Polizeiarbeit, wie Patrouille und Dispatching, hat mehr Aufmerksamkeit erhalten. Forschungen zeigen, dass Polizeibeamte, die als fair wahrgenommen werden, mehr Respekt von den Gemeinschaften verdienen, die sie bedienen. Darüber hinaus haben viele Polizeibehörden in den USA Verpflichtungen zu fairen Praktiken eingehen, was die Zusammenarbeit mit der Öffentlichkeit verbessern kann. Fairness in der Polizeiarbeit zielt meistens darauf ab, Gleichheit zwischen verschiedenen Gruppen zu gewährleisten.
Soweit wir wissen, ist dies die erste Studie, die die Patrouillen- und Dispositionsrichtlinien gemeinsam optimiert. Unsere Beiträge sind im Folgenden umreisst:
Gemeinsam optimierte Richtlinien für Patrouille und Dispatch
Frühere Optimierungsstrategien für Dispatch haben oft einfache Patrouillenmethoden vorausgesetzt. Ebenso haben frühere Multi-Agenten-Patrouillenstrategien die gemeinsame Optimierung der Dispatchaufgaben nicht berücksichtigt. Wir bieten eine detaillierte Methode zur gleichzeitigen Optimierung von Patrouille und Dispatch an, die bestehende Strategien, die sich auf nur eine Aufgabe konzentrieren, übertrifft.
Neuartige Optimierungsansätze
Wir wenden verteiltes MARL mit gemeinsamen Parametern an, um die Gemeinsamkeiten zwischen den Patrouilleneinheiten optimal zu nutzen, während wir einen Dispatcher-Agenten optimieren, dessen Entscheidungen komplexe Wahlmöglichkeiten beinhalten. Wir erweitern frühere Arbeiten zur kombinatorischen Verstärkung des Lernens in Systeme mit unsicheren Ergebnissen und integrieren diese in unser MARL-Rahmenwerk durch koordinierte Optimierung von Patrouille- und Dispatchrichtlinien.
Fokus auf Fairness in Dienstleistungssystemen
Unser Ansatz ist anpassbar an verschiedene Belohnungssysteme, einschliesslich Definitionen, die Gleichheit fördern. Richtlinien basierend auf gerechten Belohnungen führen zu ausgewogeneren Reaktionen auf verschiedene Gruppen. Darüber hinaus wenden wir unsere Methode auf echte Servicedaten an.
Hintergrundinformationen
Verstärkendes Lernen (RL) ist eine Methode des maschinellen Lernens, die einen Agenten trainiert, Entscheidungen in unsicheren Umgebungen zu treffen. Tiefes RL verwendet neuronale Netzwerke, um Strategien zu erlernen. Eine der Hauptschwierigkeiten im MARL ist das Management der erhöhten Anzahl von Aktionen, da mehr Agenten beteiligt sind. Unabhängiges Lernen (IQL) zerlegt das Problem in kleinere, einzelne RL-Aufgaben. Obwohl alle Agenten in derselben Umgebung agieren, gibt es keine Garantien für Zusammenarbeit. Dennoch hat sich die Erweiterung des tiefen Q-Lernens auf IQL als einigermassen erfolgreich erwiesen.
Um die Zusammenarbeit zwischen Agenten zu verbessern, hat sich das Teilen von Parametern als nützlich erwiesen. Grösseres Teilen funktioniert gut, wenn Agenten ähnliche Belohnungen und Wertbereiche haben. Multi-Agenten-Patrouille wurde aus verschiedenen Blickwinkeln untersucht, einschliesslich Operationsforschung, bayessisches Lernen und tiefen MARL-Ansätzen, wobei viele Forscher dieses Problem als Herausforderung der Graphenverarbeitung betrachten.
Viele frühere Studien erkannten die Komplexität der Zentralisierung von Entscheidungen für zahlreiche Agenten und verwendeten stattdessen verteilte Optimierung. In ähnlicher Weise zielt unsere Methode darauf ab, Multi-Agenten-Patrouillenrichtlinien zu entwickeln und dabei eine separate Dispatchaufgabe zu berücksichtigen.
Das Dispatching mehrerer Patrouilleneinheiten wird im Allgemeinen durch Warteschlangentheorie oder Rangsysteme betrachtet. Forscher haben diese Systeme sowohl mit statischen als auch dynamischen Warteschlangen untersucht und sie mit der Gestaltung effektiver Einsatzrichtlinien in Verbindung gebracht. Allerdings optimieren frühere Arbeiten oft die Patrouillenrichtlinien nicht in Verbindung mit dem Dispatching und stützen sich im Allgemeinen auf grundlegende Heuristiken.
Rahmen für Polizeiarbeit
Polizeijurisdiktionen sind normalerweise hierarchisch organisiert. Zum Beispiel unterteilt die Polizei von Atlanta die Stadt in Zonen und Beats. Jede Patrouilleneinheit wird einem bestimmten Beat zugewiesen. Wenn Notrufe eingehen, werden die Beamten in derselben Zone entsandt, aber sie können bei Bedarf auch ausserhalb ihres zugewiesenen Gebiets geschickt werden. Diese Studie untersucht die kombinierte Herausforderung von Patrouille und Dispatch.
Problemformulierung
Lassen Sie uns Patrouilleneinheiten betrachten, die über die Zeit Entscheidungen treffen. Die gemeinsame Patrouillen- und Einsatzherausforderung kann als Markov-Entscheidungsprozess (MDP) formuliert werden, mit einer zentralen Einheit, die dann in ein Multi-Agentenspiel unter Beteiligung aller Agenten unterteilt wird.
Patrouilleneinheiten agieren auf einem verbundenen, ungerichteten Graphen, der aus Knoten und Kanten besteht. Jede Einheit ist einem bestimmten Gebiet (Beat) zugewiesen, und das Patrouillenproblem besteht darin, zu entscheiden, wie sich jede Einheit bewegt. Wenn die Einheiten nicht mit Vorfällen beschäftigt sind, folgen sie einer Patrouillenrichtlinie zu einem nahegelegenen Knoten.
Jeder Vorfall tritt mit bestimmten Raten auf und benötigt eine bestimmte Menge an Zeit, damit die Patrouilleneinheit ihn bearbeitet. Das Dispatching-Problem besteht darin, verfügbare Einheiten den anhängigen Vorfällen zuzuordnen. Eine Dispatch-Richtlinie wird aus verschiedenen Optionen auswählen, darunter, Vorfälle unbeaufsichtigt zu lassen oder sie mit verfügbaren Einheiten zu paaren.
Wenn eine Patrouilleneinheit entsandt wird, muss sie zum Vorfall fahren. Wenn sie ihr zugewiesenes Gebiet verlässt, kehrt sie zurück, sobald der Vorfall bearbeitet wurde. Die Reaktionszeit misst, wie lange der Vorfall gewartet hat, bevor die Patrouilleneinheit ankam.
Gemeinsamer Zustand und Aktionsraum
Der gemeinsame Zustandsraum umfasst die Standorte und Status der Patrouilleneinheiten sowie laufender Vorfälle. Der gemeinsame Aktionsraum besteht aus Entscheidungen im Zusammenhang mit Patrouille und Dispatching. Jede Patrouilleneinheit hat je nach aktuellem Zustand Optionen, und die Einsatzeinheit wählt aus allen potenziellen Gruppierungen von Patrouilleneinheiten und Vorfällen aus.
Belohnungsstruktur
Die Belohnungsfunktion konzentriert sich auf die Minimierung der gesamten Reaktionszeiten und bestraft Vorfälle, die zu lange unbeaufsichtigt bleiben.
Markov-Spiel-Zerlegung
Patrouille und Dispatching können als ein Multi-Agenten-Spiel ausgedrückt werden, wobei jede Patrouilleneinheit einem einzelnen Agenten entspricht und die Dispatch-Einheit eine eigene separate Rolle hat. Jede Einheit sieht eine einzigartige Zustandsperspektive, während der Dispatch-Agent den gesamten gemeinsamen Zustand sieht.
Methodik
Wir lernen Patrouillenrichtlinien mithilfe von Multi-Agenten-Verstärkungslernen, mit gemeinsamen Parametern unter allen Patrouilleneinheiten. Die Dispatch-Richtlinien verwenden ein gemischtes ganzzahliges Programm und Wertschätzung zur Zuordnung von Vorfällen. Diese Kombination führt zu einem gemeinsamen Optimierungsprozess für Patrouille und Dispatch.
MARL mit gemeinsamen Parametern für Patrouillen
Die Patrouillenrichtlinien werden mithilfe eines gemeinsamen neuronalen Netzwerks erlernt, das eine Zustands-Aktions-Wertfunktion für alle Patrouilleneinheiten bereitstellt. Diese Methode ermöglicht zentrales Lernen über ähnliche Agenten hinweg und verbessert die Effizienz des Ansatzes. Die Annahme ist, dass ein umfassendes neuronales Netzwerk erfolgreich die erforderlichen Patrouillenstrategien erlernen kann.
Richtlinieniteration für Dispatching
Wir wenden einen Richtlinieniterationsansatz für das Dispatching basierend auf dem gemischten ganzzahligen Programm an. Dieser Ansatz ermöglicht Berechnungen, die auf dem bestehenden Wissen über die Einheiten und den Status der Anrufe basieren.
Gemeinsame Richtlinie für Patrouille und Dispatch
Die gemeinsame Richtlinie kombiniert die Patrouillen- und Einsatzstrategien und optimiert deren Parameter abwechselnd. Jede Aktualisierungsrunde konzentriert sich auf eine Strategie, während die andere konstant bleibt. Dieser Prozess hat sich als wirksam erwiesen und führt zu effektiven Richtlinien, die besser sind als die, die separat optimiert wurden.
Experimente
Wir vergleichen die kombinierte Optimierung von Patrouille und Dispatch mit Methoden, die sich ausschliesslich auf Patrouillen oder Dispatching konzentrieren. Das Ziel ist es, die Reaktionen auf Vorfälle über mehrere Simulationsepisoden hinweg zu untersuchen.
Fazit
Diese Studie präsentiert einen neuen Ansatz zur gleichzeitigen Optimierung von Patrouillen- und Dispatch-Richtlinien mithilfe von Multi-Agenten-Verstärkungslernen. Indem wir Patrouillenrichtlinien durch gemeinsames tiefes Lernen und Dispatching durch einen systematischen Ansatz erlernen, stellen wir fest, dass gemeinsam optimierte Strategien eine bessere Leistung erbringen als solche, die sich nur auf eine Aufgabe konzentrieren. Die Methode zeigt vielversprechende Ansätze zur Verbesserung der Polizeiarbeit in realen Szenarien, insbesondere in Gebieten mit hohem Anrufvolumen oder unterschiedlichen Bedürfnissen der Gemeinschaft.
Zukünftige Arbeiten könnten sich damit beschäftigen, weitere Vorfallsdaten in den Entscheidungsprozess zu integrieren, was möglicherweise die Fairness und Effizienz in den Patrouillen- und Einsatzoperationen der Polizei verbessern könnte.
Titel: Multi-Agent Reinforcement Learning for Joint Police Patrol and Dispatch
Zusammenfassung: Police patrol units need to split their time between performing preventive patrol and being dispatched to serve emergency incidents. In the existing literature, patrol and dispatch decisions are often studied separately. We consider joint optimization of these two decisions to improve police operations efficiency and reduce response time to emergency calls. Methodology/results: We propose a novel method for jointly optimizing multi-agent patrol and dispatch to learn policies yielding rapid response times. Our method treats each patroller as an independent Q-learner (agent) with a shared deep Q-network that represents the state-action values. The dispatching decisions are chosen using mixed-integer programming and value function approximation from combinatorial action spaces. We demonstrate that this heterogeneous multi-agent reinforcement learning approach is capable of learning joint policies that outperform those optimized for patrol or dispatch alone. Managerial Implications: Policies jointly optimized for patrol and dispatch can lead to more effective service while targeting demonstrably flexible objectives, such as those encouraging efficiency and equity in response.
Autoren: Matthew Repasky, He Wang, Yao Xie
Letzte Aktualisierung: 2024-09-03 00:00:00
Sprache: English
Quell-URL: https://arxiv.org/abs/2409.02246
Quell-PDF: https://arxiv.org/pdf/2409.02246
Lizenz: https://creativecommons.org/licenses/by/4.0/
Änderungen: Diese Zusammenfassung wurde mit Unterstützung von AI erstellt und kann Ungenauigkeiten enthalten. Genaue Informationen entnehmen Sie bitte den hier verlinkten Originaldokumenten.
Vielen Dank an arxiv für die Nutzung seiner Open-Access-Interoperabilität.