추격-회피

Pursuit–evasion

추적-회피(경찰, 강도, 그래프 검색이라고 하는 변종)는 수학 및 컴퓨터 과학에서 한 그룹이 환경에서 다른 그룹의 구성원을 추적하려고 시도하는 문제의 집합입니다.이런 유형의 문제에 대한 초기 연구는 환경을 [1]기하학적으로 모델링했습니다.1976년, 토렌스 파슨스는 그래프에 [2]의해 움직임이 제한되는 공식을 도입했다.기하학적 공식은 때때로 연속 추월-회피라고 불리며, 그래프 공식은 이산 추월-회피라고도 불린다.현재의 연구는 일반적으로 이 두 가지 공식 중 하나로 제한된다.

이산 제제

추적-회피 문제의 이산적 공식에서 환경은 그래프로 모델링된다.

문제의 정의

많은 요소를 공유하는 경향이 있지만, 추구 회피에는 무수히 많은 변형이 있습니다.일반적인 기본적인 예는 다음과 같습니다(경찰 및 강도 게임).추적자와 회피자는 그래프의 노드를 점유합니다.양쪽이 번갈아가며 돌아가며 각 부재는 그대로 있거나 인접한 노드로 가장자리를 따라 이동한다.추적자가 회피자와 같은 노드를 점유하고 있는 경우, 회피자는 캡처되어 그래프에서 삭제됩니다.일반적으로 제기되는 질문은 모든 탈주자를 최종적으로 체포하기 위해 얼마나 많은 추적자가 필요한가 하는 것이다.추적자 하나가 만족하면 그래프는 cop-win 그래프라고 불립니다.이 경우 단일 회피자는 항상 그래프의 n개 노드 수에 선형으로 시간 내에 캡처할 수 있습니다.추적자를 k명으로 캡처하는 것도 rn 시간 순서로 진행할 수 있지만, 두 명 이상의 추적자에 대한 정확한 경계는 아직 알려지지 않았습니다.

종종 이동 규칙은 회피자의 속도를 변경함으로써 변경됩니다.이 속도는 회피자가 한 번에 이동할 수 있는 최대 에지 수입니다.위의 예에서 회피자의 속도는 1입니다.또 다른 극단적인 것은 무한 속도의 개념으로, 추적자가 점유하는 노드를 포함하지 않는 원래 위치와 최종 위치 사이에 경로가 있는 한 회피자가 그래프 내의 어떤 노드로든 이동할 수 있도록 합니다.마찬가지로, 일부 변형은 추적자를 "헬리콥터"로 무장시켜, 추적자가 차례대로 정점으로 이동할 수 있도록 합니다.

다른 변형은 추적자와 회피자가 항상 노드를 점유해야 한다는 제한을 무시하고 가장자리를 따라 배치될 가능성을 허용합니다.이러한 변형은 흔히 전면적인 문제로 불리며, 이전 변형은 검색 문제의 범주에 속합니다.

변종

몇 가지 변형은 중요한 그래프 매개 변수와 동일합니다.구체적으로는 그래프 G에서 무한속도로 단일의 회피자를 포착하기 위해 필요한 추적자의 수를 구하는 것(추적자와 회피자가 교대로 이동하도록 제약받지 않고 동시에 이동하는 경우)은 G의 나무폭을 구하는 것과 동등하며, 이 회피자의 승리 전략은 G의 안식처로 기술할 수 있다.er는 추적자에게 보이지 않습니다. 그러면 문제는 경로 폭이나 정점 [3]분리를 찾는 것과 같습니다.그래프 G에서 단일 보이지 않는 회피자를 한 번에 포착하는 데 필요한 추적자 수(즉, 최초 배치에서 추적자에 의한 한 번의 움직임)를 찾는 것은 추적자가 원하는 곳에 초기에 배치할 수 있다고 가정할 때 G의 최소 지배 집합의 크기를 찾는 것과 같다(이 추후의 가정은 포스할 때 유지됨).유저와 회피자는 교대로 이동하는 것으로 가정한다.)

보드게임 Scotland Yard는 추격-회피 문제의 변형이다.

복잡성

니로드 메기도, S. L. Hakimi, Michael R.는 여러 추적자 변형, 즉 주어진 그래프를 삭제하기 위해 얼마나 많은 추적자가 이동해야 하는지를 연구했다. Garey, David S. Johnson, Christos H. Papadimitriou(J. ACM 1988) 및 R.보리, C토비와 S. 코닉.[4]

멀티플레이어 추적 회피 게임

멀티플레이어 추격 회피 게임도 주목받고 있다.R Vidal 등, Chung 및 Furukawa [1], Hespanha 등 및 그 참조를 참조한다.마르코스 A.M. 비에이라, 라메시 고빈단, 가우라브 S.Sukhatme은 모든 플레이어가 완전한 지식을 바탕으로 최적의 결정을 내릴 때 추적자가 모든 회피자를 포착할 수 있는 최소 완료 시간 전략을 계산하는 알고리즘을 제공했습니다.이 알고리즘은 추적자보다 훨씬 빠른 회피자에도 적용할 수 있습니다.안타깝게도 이러한 알고리즘은 소수의 로봇을 넘어서는 확장성이 없습니다.이 문제를 극복하기 위해 마르코스 A.M. 비에이라, 라메시 고빈단, 가우라브 S.Sukhatme은 추적자가 게임을 여러 개의 다중 퍼서 싱글 에이버 게임으로 분해하여 회피자를 포착하는 파티션 알고리즘을 설계하고 구현합니다.

연속 제제

추격 회피 게임의 연속적인 공식화에서 환경은 기하학적으로 모델링되며, 일반적으로 유클리드 평면이나 다른 다양체의 형태를 취한다.게임의 변형은 플레이어에게 제한된 속도 또는 가속 범위와 같은 기동성 제약을 가할 수 있습니다.장애물을 사용할 수도 있습니다.

적용들

추적-회피 문제의 최초 적용 중 하나는 RAND Corporation의 [1]Ruffus Isaacs가 공식화한 비산물 유도 시스템이었다.

「 」를 참조해 주세요.

메모들

  1. ^ a b 아이작스 1965
  2. ^ 파슨스 1976
  3. ^ 엘리스 1994
  4. ^ 보리 2009

레퍼런스

  • Isaacs, R. (1965). "Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization". New York: John Wiley & Sons. OCLC 489835778. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  • Parsons, T. D. (1976). "Pursuit–evasion in a graph". Theory and Applications of Graphs. Springer-Verlag. pp. 426–441.
  • Borie, R.; Tovey, C.; Koenig, S. (2009). "Algorithms and Complexity Results for Pursuit–Evasion Problems". In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). Retrieved 2010-03-11.
  • Ellis, J.; Sudborough, I.; Turner, J. (1994). "The vertex separation and search number of a graph". Information and Computation. 113 (1): 50–79. doi:10.1006/inco.1994.1064.
  • Fomin, F.V.; Thilikos, D. (2008). "An annotated bibliography on guaranteed graph searching". Theoretical Computer Science. 399 (3): 236–245. doi:10.1016/j.tcs.2008.02.040.
  • Kirousis, M.; Papadimitriou, C. (1986). "Searching and pebbling". Theoretical Computer Science. 42 (2): 205–218. doi:10.1016/0304-3975(86)90146-5.
  • Nowakowski, R.; Winkler, P. (1983). "Vertex-to-vertex pursuit in a graph". 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). "Graph searching, and a min-max theorem for tree-width". Journal of Combinatorial Theory, Series B. 58 (1): 22–33. doi:10.1006/jctb.1993.1027.
  • Vidal; et al. (2002). "Probabilistic pursuit–evasion games: theory, implementation, and experimental evaluation" (PDF). IEEE Transactions on Robotics and Automation. 18 (5): 662–669. doi:10.1109/TRA.2002.804040.
  • Marcos A. M. Vieira; Ramesh Govindan & Gaurav S. Sukhatme. "Scalable and Practical Pursuit–Evasion with Networked Robots". Journal of Intelligent Service Robotics: [2].
  • Chung and Furukawa (2008). "A Reachability-Based Strategy for the Time-Optimal Control of Autonomous Pursuers". Engineering Optimization. 40 (1): 67–93. Bibcode:2008EnOp...40...67C. doi:10.1080/03052150701593133. S2CID 120015118.
  • Hespanha; et al. (1999). "Multiple-agent probabilistic pursuit–evasion games". Proceedings of the 38th IEEE Conference on Decision and Control. pp. 2432–2437.