Chase-evasion (de la cual policías y ladrones y búsqueda de gráficos son variantes ) es una familia de problemas en matemáticas e informática en la que un grupo intenta atrapar a miembros de otro grupo en un entorno particular. Los primeros trabajos sobre problemas de este tipo modelaron el entorno geométricamente [1] . En 1976, Torrens Parsons introdujo una formulación en la que los movimientos están restringidos a un gráfico [2] . La formulación geométrica a veces se denomina persecución-evasión continua , y la formulación gráfica, persecución-evasión discreta (a veces también búsqueda gráfica ). La investigación actual generalmente se limita 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 variaciones de la evasión del acecho, aunque tienden a compartir muchos elementos. Un ejemplo básico típico de tal tarea es el juego de policías y ladrones. Los perseguidores y los perseguidos ocupan los vértices del grafo. Los oponentes se mueven alternativamente y cada movimiento consiste en no moverse o moverse a lo largo de un borde hacia un nodo vecino. Si el perseguidor ocupa el mismo nodo que el perseguido, se considera capturado y eliminado del juego. La pregunta suele formularse así: cuántos perseguidores se necesitan para capturar a todos los perseguidos. Si la persecución tiene éxito, el gráfico se denomina gráfico de policía ganador . En este caso, una perseguida siempre puede ser capturada en tiempo lineal a partir del número de vértices n del gráfico. La captura de r perseguido por k perseguido ocurre en un tiempo de orden rn , pero no se conocen los límites exactos para más de un perseguidor.
A menudo, las normas de tráfico se modifican modificando la velocidad del perseguido. La velocidad es el número máximo de aristas que el perseguido puede pasar en un solo movimiento. En el ejemplo anterior, la persona perseguida tiene una velocidad igual a uno. Otro extremo es el concepto de velocidad infinita , que permite que el perseguido se mueva a cualquier nodo en el que haya un camino entre las posiciones inicial y final que no contenga nodos con perseguidores. Del mismo modo, algunas variantes proporcionan a los perseguidores "helicópteros" que les permiten moverse a cualquier cima.
Las otras opciones ignoran las restricciones de que los perseguidores y los perseguidos deben estar en el nodo y permiten que esté en algún lugar dentro del borde. Estas variantes a menudo se denominan tareas de barrido, mientras que las variantes anteriores caen en la categoría de tareas de búsqueda.
Algunas opciones son equivalentes a parámetros gráficos importantes. En particular, encontrar el número de perseguidores necesarios para capturar a un perseguido con velocidad infinita en el gráfico G (cuando los perseguidores y los perseguidos no se limitan a moverse movimiento a movimiento, sino que pueden moverse simultáneamente) es equivalente a encontrar el ancho del árbol del gráfico G , y la estrategia ganadora para la perseguida se puede describir en términos de esconderse en el gráfico G. Si este perseguido 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 perseguidor invisible en el gráfico G en un solo movimiento es equivalente a encontrar el número del conjunto menos dominante del gráfico G , asumiendo que los perseguidores pueden estar inicialmente en cualquier lugar que deseen.
El juego de mesa "Scotland Yard" es una variante del problema de persecución-evasión.
La complejidad de algunas variantes de los problemas de persecución-evasión, a saber, cuántos perseguidores se necesitan para despejar un gráfico determinado y cómo debe moverse un número determinado de perseguidores a lo largo del gráfico para despejarlo con la suma mínima de sus distancias recorridas o con el tiempo mínimo para completar el juego, fue estudiado por Nimrod Megiddo, S. L. Hakimi, Michael R. Garay, David S. Johnson and Christos H. Papadimitriou and R. Bori, K. Tovey and S. Koenig [4] .
Resolver juegos de persecución y evasión multijugador también está recibiendo una atención cada vez mayor. Véanse los artículos de R. Vidal et al [5] , Chang y Furukawa [6] , Espaniya, Kim y Sastri [7] y las referencias en dichos artículos. Marcos A. M. Vieira, Ramesh Govindan y Gaurav S. Sukatmi [8] propusieron un algoritmo que calcula una estrategia con un tiempo de ejecución mínimo para que los perseguidores capturen a todos los perseguidores cuando todos los jugadores toman una decisión óptima basada en un conocimiento completo. Este algoritmo también se puede utilizar en los casos en que los perseguidos son mucho más rápidos que los perseguidores. Desafortunadamente, este algoritmo no escala más allá de una pequeña cantidad de robots. Para superar este problema, Marcos A. M. Vieira, Ramesh Govindan y Gaurav S. Sukatmi desarrollaron e implementaron un algoritmo de partición en el que los perseguidores capturan a los perseguidos al descomponer el juego en juegos con un perseguido y múltiples perseguidores.
En una formulación continua de juegos de persecución y evasión, el entorno se modela geométricamente, generalmente tomando la forma de un plano euclidiano u otra variedad . Las variaciones del juego pueden imponer restricciones a la maniobrabilidad de los jugadores, como límites de velocidad o aceleración. También se pueden utilizar obstáculos.
Una de las primeras aplicaciones del problema de persecución-evasión fueron los sistemas de control de misiles. Las tareas para estos sistemas fueron formuladas por Rufus Isaacs de RAND Corporation [1] .