Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find an algorithm to win this battle against crime!

A crime committed in a city and the suspect starts to run away. A map of the city is given. At the moment, there are some police cars at some given places and they try to stop the suspect. The car of police and the suspect have a same maximum speed. The suspect can only pass a point if he reaches it earlier than any police car. There are several exits in the map, and the suspect evades if he reaches any of them. Find an algorithm allocating the police cars so that no path can the suspect take to evade.

For example, below is a possible city map.

enter image description here

White circle is where the suspect starts, black circles are police cars, and little squares are exits. In this situation, suspect can be stopped. A possible plan is police car A goes to A', B stays and C goes to C'.


An equivalent description of my problem could be:

A chemical factory (marked by the white circle) explodes and poisonous fluid starts to flow at each possible direction at speed v, and the rescue teams (marked by black circles) whose maximum speed is also v are trying to block it. The little squares are villagers they are protecting.


My Thoughts

If we have n police cars, a highly inefficient approach is to list all possible k-element subsets P of vertices such that:

a) k <= n;

b) Remove all vertices in P in the map will cause any exit unreachable to the suspect;

c) Remove any proper subset of P will let at least one exit reachable to the suspect.

Then we can easily determine if every vertex in P can be covered by a police no later than the suspect.

But how do I list all the possible Ps?


@Lior Kogan:

Look at this map:

enter image description here

If it is a turning game in which both sides knowing other's strategy, the police will win because he can just guard the side where the suspect go.

But in my problem, the police loses because he'll never know which side the suspect may choose.

like image 739
xzhu Avatar asked Oct 13 '11 05:10

xzhu


People also ask

How are algorithms used in the criminal justice system?

One class of algorithmic tools, called risk assessment instruments (RAIs), are designed to predict a defendant's future risk for misconduct. These predictions inform high-stakes judicial decisions, such as whether to incarcerate an individual before their trial.

What type of algorithm is suitable for detecting crime in an area?

Different types of classification algorithms such as Logistic Regression, Decision Tree, Random Forest, Support Vector Machines and Neural Networks have been used in order to identify the method that works best in terms of predicting the type of crime occurring in a particular incident recorded.

How does AI predict crime?

Predictive policing tools are built by feeding data — such as crime reports, arrest records and license plate images — to an algorithm, which is trained to look for patterns to predict where and when a certain type of crime will occur in the future.

What are risk assessment algorithms?

Abstract. Risk assessment algorithms—statistical formulas that predict the likelihood a person will commit crime in the future—are used across the country to help make life-altering decisions in the criminal process, including setting bail, determining sentences, selecting probation conditions, and deciding parole.


1 Answers

Edit2: Based on your clarifications:

I couldn't find any research concerning the exact posed problem.

Another close subject is virus spread and inoculation in networks. Here are some papers:

  • Inoculation strategies for victims of viruses and the sum-of-squares partition problem
  • Worm Versus Alert: Who Wins in a Battle for Control of a Large-Scale Network?
  • Protecting Against Network Infections: A Game Theoretic Perspective

I think that the posed problem is very interesting. Though I believe it is NP-hard.

Sorry for being unable to help any further.

--

Edit1: Changed from Cops and Robbers game to Graph guarding game.

New answer:

This is a variant of the Graph Guarding game.

A team of mobile agents, called guards, tries to keep an intruder out of an assigned area by blocking all possible attacks. In a graph model for this setting, the agents and the intruder are located on the vertices of a graph, and they move from node to node via connecting edges.

See: Guard Games on Graphs and How to Guard a Graph?

In your variant, there are two differences:

  • You are trying to guard more than one area
  • Each guarded area is a single node

--

Original answer:

This is a variant of the well studied Cops and Robbers game.

The Cops and Robbers game is played on undirected graphs where a group of cops tries to catch a robber. The game was defined independently by Winkler-Nowakowski and Quilliot in the 1980s and since that time has been studied intensively. Despite of that, its computation complexity is still an open question.

The problem of determining if k cops can capture a robber on an undirected graph, as well as the problem of computing the minimum number of cops that can catch a robber on a given graph were proven to be NP-hard.

Here are some resources:

  • Chapter 6 of The Game of Cops and Robbers on Graphs
  • On tractability of Cops and Robbers game
  • Complexity of Cops and Robber Game
  • Talks on GRASTA 2011 (see ch.3)
like image 136
Lior Kogan Avatar answered Oct 12 '22 01:10

Lior Kogan