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 la que un grupo intenta rastrear 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 por la cual el movimiento está restringido por un gráfico . [2] La formulación geométrica a veces se llama persecución-evasión continua , y la formulación de gráfico discreta persecución-evasión (también llamadabúsqueda de gráficos ). La investigación actual se limita típicamente a una de estas dos formulaciones.
Formulación discreta
En la formulación discreta del problema de persecución-evasión, el entorno se modela como un gráfico.
Definición del problema
Hay 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 los nodos de un gráfico. Los dos lados toman turnos alternos, que consisten en que cada miembro se quede 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 se suele plantear es cuántos perseguidores son necesarios para asegurar la eventual captura de todos los evasores. Si un perseguidor es suficiente, la gráfica se llama gráfica de cop-win . En este caso, siempre se puede capturar un único evasor en el tiempo lineal al número de n nodos del gráfico. Capturar r evasores con k perseguidores también puede llevar rn tiempo, pero aún se desconocen los límites exactos para más de un perseguidor.
A menudo, las reglas de movimiento se modifican al cambiar 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 que un evasor se mueva a cualquier nodo del gráfico siempre que haya una ruta entre sus posiciones original y final que no contenga nodos ocupados por un perseguidor. Del mismo modo, 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 colocados en algún lugar a lo largo de un borde. Estas variantes a menudo se denominan problemas de barrido, mientras que las variantes anteriores entrarían en la categoría de problemas de búsqueda.
Variantes
Varias variantes son equivalentes a parámetros de gráficos importantes. Específicamente, encontrar el número de perseguidores necesarios para capturar a un solo evasor con velocidad infinita en un gráfico G (cuando los perseguidores y el evasor no están obligados a moverse giro a giro, sino que se mueven simultáneamente) es equivalente a encontrar el ancho del árbol de G , y un ganador. estrategia para el evasor puede ser descrita 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 de la ruta o la separación de los vértices. [3] Encontrar el número de perseguidores necesarios para capturar 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 mínimo dominante de G , asumiendo que los perseguidores pueden desplegarse inicialmente donde quieran (esta suposición posterior se mantiene 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 la persecución-evasión.
Complejidad
La complejidad de varias variantes de persecución-evasión, es decir, cuántos perseguidores se necesitan para borrar un gráfico dado y cómo un número dado de perseguidores debe moverse en el gráfico para borrarlo con una suma mínima de sus distancias de viaje o con el tiempo mínimo de finalización de 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]
Juegos de persecución y evasión multijugador
También se ha prestado mayor atención a la resolución de juegos de persecución y evasión de varios jugadores. Véase R. Vidal y col., Chung y Furukawa [1] , Hespanha y col. y las referencias en el mismo. Marcos AM Vieira y Ramesh Govindan y Gaurav S. Sukhatme proporcionaron un algoritmo que calcula la estrategia de tiempo de finalización mínimo 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 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.
Formulación continua
En la formulación continua de los juegos de persecución-evasión, el entorno se modela geométricamente, típicamente tomando la forma del plano euclidiano u otra variedad . Las variantes del juego pueden imponer limitaciones de maniobrabilidad a los jugadores, como un rango limitado de velocidad o aceleración. También se pueden utilizar obstáculos.
Aplicaciones
Una de las aplicaciones iniciales del problema de la persecución-evasión fueron los sistemas de guía de misiles formulados por Rufus Isaacs en la Corporación RAND. [1]
Ver también
Notas
Referencias
- Isaacs, R. (1965). "Juegos diferenciales: una teoría matemática con aplicaciones a la guerra y persecución, control y optimización". Nueva York: John Wiley & Sons. OCLC 489835778 . Cite journal requiere
|journal=
( ayuda )CS1 maint: ref duplica el valor predeterminado ( enlace ) - Parsons, TD (1976). "Persecución-evasión en un gráfico". Teoría y aplicaciones de gráficos . Springer-Verlag. págs. 426–441.
- Borie, R .; Tovey, C .; Koenig, S. (2009). "Algoritmos y resultados de complejidad para problemas de persecución-evasión" . En Actas de la Conferencia Internacional Conjunta sobre Inteligencia Artificial (IJCAI) . Consultado el 11 de marzo de 2010 .
- Ellis, J .; Sudborough, I .; Turner, J. (1994). "La separación de vértices y el número de búsqueda de un gráfico". Información y Computación . 113 (1): 50–79. doi : 10.1006 / inco.1994.1064 .
- Fomin, FV; Thilikos, D. (2008). "Una bibliografía comentada sobre la búsqueda de gráficos garantizada". Informática Teórica . 399 (3): 236–245. doi : 10.1016 / j.tcs.2008.02.040 .
- Kirousis, M .; Papadimitriou, C. (1986). "Búsqueda y guijarros". Informática Teórica . 42 (2): 205–218. doi : 10.1016 / 0304-3975 (86) 90146-5 .
- Nowakowski, R .; Winkler, P. (1983). "Búsqueda de vértice a vértice en un gráfico". Matemáticas discretas . 43 (2-3): 235-239. doi : 10.1016 / 0012-365X (83) 90160-7 .
- Petrosjan, León (1993). "Juegos diferenciales de persecución (serie sobre optimización, Vol 2)". World Scientific Pub Co Inc . 2 .
- Seymour, P .; Thomas, R. (1993). "Búsqueda de gráficos y un teorema mínimo-máximo para el ancho del árbol". Revista de Teoría Combinatoria, Serie B . 58 (1): 22–33. doi : 10.1006 / jctb.1993.1027 .
- Vidal; et al. (2002). "Juegos probabilísticos de persecución-evasión: teoría, implementación y evaluación experimental" (PDF) . Transacciones IEEE sobre robótica y automatización . 18 (5): 662–669. doi : 10.1109 / TRA.2002.804040 .
- Marcos AM Vieira; Ramesh Govindan y Gaurav S. Sukhatme. "Evasión-persecución escalable y práctica con robots en red". Revista de robótica de servicio inteligente : [2] .
- Chung y Furukawa (2008). "Una estrategia basada en la accesibilidad para el control óptimo en el tiempo de los perseguidores autónomos". Optimización de ingeniería . 40 (1): 67–93. Código Bibliográfico : 2008EnOp ... 40 ... 67C . doi : 10.1080 / 03052150701593133 . S2CID 120015118 .
- Hespanha; et al. (1999). "Juegos probabilísticos de persecución-evasión de múltiples agentes". Actas de la 38ª Conferencia IEEE sobre Decisión y Control . págs. 2432–2437.