La persecución-evasión (cuyas variantes se conocen como policías y ladrones y búsqueda en grafos ) es una familia de problemas en matemáticas e informática en los que un grupo intenta rastrear a los miembros de otro grupo en un entorno. Los primeros trabajos sobre problemas de este tipo modelaban el entorno geométricamente. [1] En 1976, Torrence Parsons introdujo una formulación mediante la cual el movimiento está restringido por un grafo . [2] La formulación geométrica a veces se denomina persecución-evasión continua y la formulación de grafo persecución-evasión discreta (también llamada búsqueda en grafos ). La investigación actual se limita típicamente a una de estas dos formulaciones.
En la formulación discreta del problema de persecución-evasión, el entorno se modela como un gráfico .
Existen innumerables variantes posibles de persecución-evasión, aunque tienden a compartir muchos elementos. Un ejemplo básico típico es el siguiente (juegos de policías y ladrones): los perseguidores y los evasores ocupan nodos de un grafo. Los dos lados toman turnos alternativos, que consisten en que cada miembro se quede en el mismo lugar o se mueva a lo largo de un borde hacia un nodo adyacente. Si un perseguidor ocupa el mismo nodo que un evasor, el evasor es capturado y eliminado del grafo. La pregunta que generalmente se plantea es cuántos perseguidores son necesarios para asegurar la captura final de todos los evasores. Si un perseguidor es suficiente, el grafo se llama grafo de policía-victoria . En este caso, siempre se puede capturar un solo evasor en un tiempo lineal al número de n nodos del grafo. Capturar r evasores con k perseguidores también puede llevar del orden de r n tiempo, pero los límites exactos para más de un perseguidor aún son desconocidos .
A menudo, las reglas de movimiento se modifican modificando la velocidad de los evasores. Esta velocidad es el número máximo de aristas que un evasor puede recorrer en un solo turno. En el ejemplo anterior, los evasores tienen una velocidad de uno. En el otro extremo se encuentra el concepto de velocidad infinita , que permite a un evasor moverse a cualquier nodo del gráfico siempre que haya un camino entre sus posiciones original y final que no contenga nodos ocupados por un perseguidor. De manera similar, algunas variantes equipan a los perseguidores con "helicópteros" que les permiten moverse a cualquier vértice en su turno.
Otras variantes ignoran la restricción de que los perseguidores y evasores siempre deben ocupar un nodo y permiten la posibilidad de que se ubiquen en algún lugar a lo largo de un borde. Estas variantes suelen denominarse problemas de barrido , mientras que las variantes anteriores entrarían en la categoría de problemas de búsqueda .
Varias variantes son equivalentes a parámetros gráficos importantes. Específicamente, encontrar el número de perseguidores necesarios para capturar a un solo evasor con velocidad infinita en un grafo G (cuando los perseguidores y el evasor no están restringidos a moverse turno a turno, sino que se mueven simultáneamente) es equivalente a encontrar el ancho del árbol de G , y una estrategia ganadora para el evasor puede describirse en términos de un refugio en G . Si este evasor es invisible para los perseguidores, entonces el problema es equivalente a encontrar el ancho del camino o la separación de vértices. [3] Encontrar el número de perseguidores necesarios para capturar a un solo evasor invisible en un grafo G en un solo turno (es decir, un movimiento de los perseguidores desde su despliegue inicial) es equivalente a encontrar el tamaño del conjunto dominante mínimo de G , asumiendo que los perseguidores pueden desplegarse inicialmente donde quieran (esta última suposición se cumple cuando se supone que los perseguidores y el evasor se mueven turno a turno).
El juego de mesa Scotland Yard es una variante del problema de persecución-evasión.
La complejidad de varias variantes de persecución-evasión, es decir, cuántos perseguidores se necesitan para despejar un grafo dado y cómo un número dado de perseguidores debe moverse en el grafo para despejarlo con una suma mínima de sus distancias de viaje o un tiempo mínimo de finalización de la tarea, ha sido estudiada por Nimrod Megiddo , SL Hakimi , Michael R. Garey , David S. Johnson y Christos H. Papadimitriou (J. ACM 1988), y R. Borie, C. Tovey y S. Koenig. [4]
La resolución de juegos de persecución-evasión con varios jugadores también ha recibido una mayor atención; consulte R Vidal et al., Chung y Furukawa [1], Hespanha et al. y las referencias allí citadas. Marcos AM Vieira y Ramesh Govindan y Gaurav S. Sukhatme proporcionaron un algoritmo que calcula la estrategia de tiempo de finalización mínima para que los perseguidores capturen a todos los evasores cuando todos los jugadores toman decisiones óptimas basadas en el conocimiento completo. Este algoritmo también se puede aplicar cuando los evasores son significativamente más rápidos que los perseguidores. Desafortunadamente, estos algoritmos no escalan más allá de una pequeña cantidad de robots. Para superar este problema, Marcos AM Vieira y Ramesh Govindan y Gaurav S. Sukhatme diseñan e implementan un algoritmo de partición donde los perseguidores capturan a los evasores descomponiendo el juego en múltiples juegos de múltiples perseguidores y un solo evasor.
En la formulación continua de los juegos de persecución y evasión, el entorno se modela geométricamente, generalmente tomando la forma del plano euclidiano u otra variedad . Las variantes del juego pueden imponer restricciones de maniobrabilidad a los jugadores, como un rango limitado de velocidad o aceleración. También se pueden utilizar obstáculos.
Si un león persigue a un hombre a la misma velocidad, entonces es evidente que el hombre puede escapar en un plano o en una esfera moviéndose siempre en línea recta alejándose del león. Cuando ambos están confinados en un disco circular, parece probable que el león atrape al hombre. Besicovitch demostró en 1952 que el hombre tiene una estrategia para evadir la captura indefinidamente contra cualquier estrategia. [5]
Una de las aplicaciones iniciales del problema de persecución-evasión fueron los sistemas de guía de misiles formulados por Rufus Isaacs en la Corporación RAND . [1]