Evasão de perseguição - Pursuit-evasion

A evasão de perseguição (variantes das quais são referidas como policiais e ladrões e busca de gráficos ) é uma família de problemas em matemática e ciência da computação em que um grupo tenta rastrear membros de outro grupo em um ambiente. Os primeiros trabalhos em problemas desse tipo modelaram o ambiente geometricamente. Em 1976, Torrence Parsons introduziu uma formulação em que o movimento é restringido por um gráfico . A formulação geométrica é às vezes chamada de busca-evasão contínua , e a formulação de gráfico de busca-evasão discreta (também chamada de busca de gráfico ). A pesquisa atual é normalmente limitada a uma dessas duas formulações.

Formulação discreta

Na formulação discreta do problema de perseguição-evasão, o ambiente é modelado como um gráfico.

Definição de problema

Existem inúmeras variantes possíveis de evasão de perseguição, embora elas tendam a compartilhar muitos elementos. Um exemplo básico típico é o seguinte (jogos de polícia e ladrão): Perseguidores e evasores ocupam nós de um gráfico. Os dois lados fazem turnos alternados, que consistem em cada membro ficar parado ou se mover ao longo de uma aresta para um nó adjacente. Se um perseguidor ocupa o mesmo nó que um evasor, o evasor é capturado e removido do gráfico. A questão geralmente colocada é quantos perseguidores são necessários para garantir a eventual captura de todos os evasores. Se um perseguidor for suficiente, o gráfico é chamado de gráfico cop-win . Nesse caso, um único evasor sempre pode ser capturado no tempo linear ao número de n nós do gráfico. Capturar r sonegadores com k perseguidores pode tomar na ordem de rn tempo também, mas os limites exatos para mais de um perseguidor ainda são desconhecidos.

Freqüentemente, as regras de movimento são alteradas mudando a velocidade dos evasores. Essa velocidade é o número máximo de arestas que um evasor pode mover em uma única volta. No exemplo acima, os evasores têm velocidade de um. No outro extremo está o conceito de velocidade infinita , que permite que um evasor se mova para qualquer nó no gráfico, desde que haja um caminho entre suas posições original e final que não contenha nós ocupados por um perseguidor. Da mesma forma, algumas variantes equipam os perseguidores com "helicópteros" que permitem que eles se movam para qualquer vértice em sua vez.

Outras variantes ignoram a restrição de que perseguidores e evasores devem sempre ocupar um nó e permitir a possibilidade de que estejam posicionados em algum lugar ao longo de uma borda. Essas variantes são freqüentemente chamadas de problemas de varredura, enquanto as variantes anteriores cairiam na categoria de problemas de pesquisa.

Variantes

Várias variantes são equivalentes a parâmetros gráficos importantes. Especificamente, encontrar o número de perseguidores necessários para capturar um único evasor com velocidade infinita em um gráfico G (quando perseguidores e evasores não são forçados a se moverem turno a turno, mas se movem simultaneamente) é equivalente a encontrar a largura da árvore de G , e uma vitória estratégia para autores da evasão pode ser descrito em termos de um refúgio em L . Se esse evasor for invisível para os perseguidores, o problema é equivalente a encontrar a largura do caminho ou a separação do vértice. Encontrar o número de perseguidores necessário para capturar um único evasor invisível em um gráfico G em uma única volta (ou seja, um movimento dos perseguidores desde sua implantação inicial) é equivalente a encontrar o tamanho do conjunto mínimo dominante de G , assumindo que perseguidores podem inicialmente implantar onde quiserem (esta suposição posterior é válida quando perseguidores e evasores se movem turno a turno).

O jogo de tabuleiro Scotland Yard é uma variante do problema de evasão de perseguição.

Complexidade

A complexidade de várias variantes de evasão de perseguição, ou seja, quantos perseguidores são necessários para limpar um determinado gráfico e como um determinado número de perseguidores deve se mover no gráfico para eliminá-lo com uma soma mínima de suas distâncias de viagem ou tempo mínimo de conclusão da tarefa , foi estudado por Nimrod Megiddo , SL Hakimi , Michael R. Garey , David S. Johnson e Christos H. Papadimitriou (J. ACM 1988) e R. Borie, C. Tovey e S. Koenig.

Jogos multijogador de evasão de perseguição

A resolução de jogos de evasão de perseguição com vários jogadores também tem recebido maior atenção. Ver R Vidal et al., Chung e Furukawa [1] , Hespanha et al. e as referências nele contidas. Marcos AM Vieira e Ramesh Govindan e Gaurav S. Sukhatme forneceram um algoritmo que calcula a estratégia de tempo mínimo de conclusão para os perseguidores capturarem todos os evasores quando todos os jogadores tomam decisões ótimas com base no conhecimento completo. Este algoritmo também pode ser aplicado quando o evasor é significativamente mais rápido do que os perseguidores. Infelizmente, esses algoritmos não vão além de um pequeno número de robôs. Para superar esse problema, Marcos AM Vieira e Ramesh Govindan e Gaurav S. Sukhatme projetam e implementam um algoritmo de partição em que os perseguidores capturam evasores decompondo o jogo em vários jogos de um único evasor com vários perseguidores.

Formulação contínua

Na formulação contínua de jogos de perseguição-evasão, o ambiente é modelado geometricamente, geralmente assumindo a forma do plano euclidiano ou outra variedade . Variantes do jogo podem impor restrições de manobrabilidade aos jogadores, como uma faixa limitada de velocidade ou aceleração. Obstáculos também podem ser usados.

Formulários

Uma das aplicações iniciais do problema de evasão de perseguição foram os sistemas de orientação de mísseis formulados por Rufus Isaacs na RAND Corporation.

Veja também

Notas

Referências

  • Isaacs, R. (1965). "Jogos Diferenciais: Uma Teoria Matemática com Aplicações à Guerra e Perseguição, Controle e Otimização". Nova York: John Wiley & Sons. OCLC  489835778 . Citar diário requer |journal=( ajuda )
  • Parsons, TD (1976). "Perseguição-evasão em um gráfico". Teoria e aplicações de gráficos . Springer-Verlag. pp. 426–441.
  • Borie, R .; Tovey, C .; Koenig, S. (2009). "Resultados de algoritmos e complexidade para problemas de evasão de perseguição" . Em Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) . Página visitada em 2010-03-11 .
  • Ellis, J .; Sudborough, I .; Turner, J. (1994). "A separação do vértice e o número de pesquisa de um gráfico" . Informação e computação . 113 (1): 50–79. doi : 10.1006 / inco.1994.1064 .
  • Fomin, FV; Thilikos, D. (2008). "Uma bibliografia comentada sobre a busca garantida de gráficos" . Ciência da Computação Teórica . 399 (3): 236–245. doi : 10.1016 / j.tcs.2008.02.040 .
  • Kirousis, M .; Papadimitriou, C. (1986). "Procurando e pebbling" . Ciência da Computação Teórica . 42 (2): 205–218. doi : 10.1016 / 0304-3975 (86) 90146-5 .
  • Nowakowski, R .; Winkler, P. (1983). "Perseguição vértice a vértice em um gráfico" . Discrete Mathematics . 43 (2–3): 235–239. doi : 10.1016 / 0012-365X (83) 90160-7 .
  • Petrosjan, Leon (1993). "Differential Games of Pursuit (Series on Optimization, Vol 2)". World Scientific Pub Co Inc . 2 .
  • Seymour, P .; Thomas, R. (1993). "Pesquisa de grafos e um teorema min-max para a largura da árvore" . Journal of Teoria Combinatória, Série B . 58 (1): 22–33. doi : 10.1006 / jctb.1993.1027 .
  • Vidal; et al. (2002). "Jogos probabilísticos de perseguição-evasão: teoria, implementação e avaliação experimental" (PDF) . IEEE Transactions on Robotics and Automation . 18 (5): 662–669. doi : 10.1109 / TRA.2002.804040 .
  • Marcos AM Vieira; Ramesh Govindan e Gaurav S. Sukhatme. "Perseguição-Evasão Escalável e Prática com Robôs em Rede". Journal of Intelligent Service Robotics : [2] .
  • Chung e Furukawa (2008). "Uma Estratégia Baseada em Acessibilidade para o Controle Otimizado em Tempo de Perseguidores Autônomos". Otimização de Engenharia . 40 (1): 67–93. Bibcode : 2008EnOp ... 40 ... 67C . doi : 10.1080 / 03052150701593133 . S2CID  120015118 .
  • Hespanha; et al. (1999). "Jogos de evasão e perseguição probabilística de múltiplos agentes". Proceedings of the 38th IEEE Conference on Decision and Control . pp. 2432–2437.