La persecución-evasión (variantes de las cuales se conocen como policías y ladrones y búsqueda de gráficos ) es una familia de problemas en matemáticas e informática en los que un grupo intenta localizar a miembros de otro grupo en un entorno. Los primeros trabajos sobre problemas de este tipo modelaron el entorno geométricamente. [1] En 1976, Torrence Parsons introdujo una formulación según la cual el movimiento está restringido por un gráfico . [2] La formulación geométrica a veces se denomina búsqueda-evasión continua , y la formulación gráfica búsqueda-evasión discreta (también llamada búsqueda de gráficos ). La investigación actual suele limitarse 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 .
Hay innumerables variantes posibles de persecución-evasión, aunque tienden a compartir muchos elementos. Un ejemplo típico y básico es el siguiente (juegos de policías y ladrones): Los perseguidores y evasores ocupan nodos de un gráfico. Los dos lados toman giros alternos, que consisten en que cada miembro permanezca quieto o se mueva a lo largo de un borde hasta un nodo adyacente. Si un perseguidor ocupa el mismo nodo que un evasor, el evasor es capturado y eliminado del gráfico. La pregunta que suele plantearse es cuántos perseguidores son necesarios para asegurar la eventual captura de todos los evasores. Si un perseguidor es suficiente, el gráfico se llama gráfico de victoria del policía . En este caso, siempre se puede capturar un único evasor en un tiempo lineal al número de n nodos del gráfico. La captura de invasores con k perseguidores también puede llevar en el orden de r n tiempo, pero aún se desconocen los límites exactos para más de un perseguidor .
A menudo, las reglas de movimiento se modifican cambiando la velocidad de los evasores. Esta velocidad es el número máximo de bordes por los que un evasor puede moverse en un solo giro. En el ejemplo anterior, los evasores tienen una velocidad de uno. En el otro extremo está 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 arman 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 estén ubicados 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 equivalen a parámetros gráficos importantes. Específicamente, encontrar el número de perseguidores necesarios para capturar a un único evasor con velocidad infinita en un gráfico G (cuando los perseguidores y el evasor no están obligados a moverse turno por turno, sino que se mueven simultáneamente) es equivalente a encontrar el ancho del árbol de G , y un ganador La estrategia para el evasor puede describirse en términos de un refugio en G . Si este evasor es invisible para los perseguidores, entonces el problema equivale a encontrar el ancho del camino o la separación de los vértices. [3] Encontrar el número de perseguidores necesarios para capturar a un único evasor invisible en un gráfico 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 paso a paso).
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 borrar un gráfico determinado y cómo un número determinado de perseguidores debe moverse en el gráfico para borrarlo con una suma mínima de sus distancias de viaje o un tiempo mínimo para completar la tarea. , ha sido estudiado 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 y evasión multijugador también ha recibido mayor atención; véase R Vidal et al., Chung y Furukawa [1], Hespanha et al. y las referencias en el mismo. Marcos AM Vieira, Ramesh Govindan y Gaurav S. Sukhatme proporcionaron un algoritmo que calcula la estrategia de tiempo mínimo de finalización para que los perseguidores capturen a todos los evasores cuando todos los jugadores toman decisiones óptimas basadas en un 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 se extienden más allá de una pequeña cantidad de robots. Para superar este problema, Marcos AM Vieira, Ramesh Govindan y Gaurav S. Sukhatme diseñan e implementan un algoritmo de partición en el que 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 juegos de persecución-evasión, el entorno se modela geométricamente, normalmente 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 con la misma velocidad, entonces está claro 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, parecía probable que el león atrapara 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 RAND Corporation . [1]