The Wayback Machine - https://web.archive.org/web/20221028230758/https://baike.sogou.com/kexue/d10186.htm

追逃

编辑

追逐-逃避(其变体被称为警察、强盗和图形搜索)是数学和计算机科学中的一个问题系列,其中一个群体试图在一个环境中追踪另一个群体的成员。关于这类问题的早期工作以几何方式模拟了环境。[1] 1976年,托伦斯·帕森斯提出了一个公式,用图形来约束运动。[2] 几何公式有时被称为连续追逐逃避,而图形公式被称为离散追逐逃避(也称为图搜索)。目前的研究通常局限于这两种配方中的一种。

1 离散公式编辑

在追逐-规避问题的离散公式中,环境被建模为图。

1.1 问题定义

追逐逃避有无数种可能的变体,尽管它们往往有许多共同点。一个典型的、基本的例子如下(警察和强盗游戏):追捕者和逃跑者占据一个图的节点。两边角色轮流交替,每个角色要么保持不动,要么沿着边移动到相邻节点。如果追捕者与逃跑者占据同一个节点,逃跑者将被捕获并从图中移除。常见的问题是需要多少追捕者才能确保最终抓获所有逃跑者。如果一个追捕者足够,这个图被称为双赢图。在这种情况下,单个逃避者总是可以在一定时间上被捕获,该时间与图的节点的数量n成线性关系。用k个追踪器捕捉r个逃亡者也需要大约rn个时间,但是一个以上追踪器的确切界限仍然未知。

通常通过改变逃避者的速度来改变运动规则。这个速度是一个躲避者在一个转弯中可以移动的最大边数。在上例中,逃逸者的速度为1。另一个极端是无限速度的概念,它允许逃避者移动到图中的任何节点,只要在它的原始位置和最终位置之间有一条不包含被追赶者占据的节点的路径。类似地,一些变种用“直升机”武装追踪者,允许他们在转弯时移动到任何顶点。

其他变体忽略了追捕者和逃跑者必须始终占据一个节点的限制,并允许他们可能位于边的某个地方。这些变体通常被称为扫描问题,而之前的变体属于搜索问题的范畴。

1.2 变体

几个变量相当于重要的图参数。具体来说,在图G中找到捕获具有无限速度的单个逃逸者所必需的追踪者的数量(当追踪者和逃逸者不受限制地依次移动,而是同时移动)相当于找到G的树宽,并且逃逸者的获胜策略可以用G中的避难所来描述。如果这个逃逸者对追踪者不可见,那么问题相当于找到路径宽或顶点分离。[3] 假设追踪者最初可以部署在他们喜欢的任何地方(当假设追踪者和逃逸者依次移动时,假设成立),在单个转弯中找到图G中的单个隐形逃逸者所必需的追踪者的数量(即追踪者从其初始部署开始的一次移动)相当于找到最小支配集合G的大小。

棋盘游戏苏格兰场是追逐-逃避问题的变体。

1.3 复杂性

尼姆罗德·梅吉多、哈基米、迈克尔·加雷伊、大卫·约翰逊和克里斯特斯·帕帕迪米特里奥(1988)以及博里、托维和柯尼希研究了几个追逐逃避变量的复杂性,即需要多少个追逐者来清除给定的图,以及给定数量的追逐者应该如何在图上移动,以最小的移动距离之和或最小的任务完成时间来清除它。[4]

1.4 多人追逐逃避游戏

多人追逐规避游戏的求解方法也越来越受到关注。马科斯·维埃拉(Marcos A. M. Vieira)和拉梅什·戈文丹(Ramesh Govindan)和高拉夫·苏哈托姆(Gaurav S. Sukhatme)提供了一种算法,当所有玩家基于完全的知识做出最佳决策时,该算法计算追捕者捕获所有逃跑者的最短完成时间策略。这种算法也可以应用于逃避者明显快于追赶者的情况。不幸的是,这些算法不能扩展到少数机器人之外。为了克服这个问题,马科斯·维埃拉(Marcos A. M. Vieira)和拉梅什·戈文丹(Ramesh Govindan)以及高拉夫·苏哈特姆(Gaurav S. Sukhatme)设计并实现了一种分割算法,其中追捕者通过将游戏分解成多个多追捕者单逃跑者游戏来捕获逃跑者。

2 连续配方编辑

在连续性的追逃游戏中,环境被几何建模,通常采用欧几里德平面或另一个流形的形式。游戏的变体可以对玩家施加机动性限制,例如限制速度或加速度的有限范围。也可以使用障碍物。

3 应用程序编辑

追避问题的最初应用之一是兰德公司鲁弗斯·艾萨克斯(Rufus Isaacs)开发的导弹制导系统。[1]

4 笔记编辑

参考文献

  • [1]

    ^Isaacs 1965.

  • [2]

    ^Parsons 1976.

  • [3]

    ^Ellis 1994.

  • [4]

    ^Borie 2009.

阅读 23
版本记录
  • 暂无