A Memetic Approach for Sequential Security Games on a Plane with Moving Targets
A Memetic Approach for Sequential Security Games on a Plane with Moving Targets
复制标题
具有移动目标的平面上顺序安全博弈的模因方法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Bo An
中科院分区：
文献类型：
--
作者：
Jan Karwowski;J. Mańdziuk;A. Żychowski;Filip Grajek;Bo An
本文介绍了一种在平面上进行的新型安全游戏 (SG)，目标沿预定义的直线轨迹移动，及其各自的混合整数线性规划 (MILP) 公式。提出并实验评估了解决该游戏的三种方法：应用 MILP 求解器来寻找小型游戏的精确解，基于 MILP 的最近发布的零和 SG 方法扩展到一般和游戏的情况，以寻找中型游戏的近似解，以及使用模因算法（MA）来处理中型和大型游戏实例，这些都超出了 MILP 的可扩展性。据我们所知，MA的利用是SG领域的一个新想法。所提出的解决方案的新颖性具体在于高效的基于染色体的游戏编码和专用的局部改进启发式。在绝大多数具有已知平衡曲线的测试案例中，该方法可得出具有高稳定性和近似线性时间可扩展性的最佳解决方案。另一个优点是基于迭代的系统构建，这使得该方法本质上是一种随时可用的方法。在时间限制有限的情况下，此属性至关重要，这可能会阻碍计算精确解的可能性。总的来说，我们认为，对于需要应用近似求解方法的复杂游戏，基于 MA 的方法可以为 MILP 求解器提供可行的替代方案。
This paper introduces a new type of Security Games (SG) played on a plane with targets moving along predefined straight line trajectories and its respective Mixed Integer Linear Programming (MILP) formulation. Three approaches for solving the game are proposed and experimentally evaluated: application of an MILP solver to finding exact solutions for small-size games, MILP-based extension of recently published zero-sum SG approach to the case of generalsum games for finding approximate solutions of medium-size games, and the use of Memetic Algorithm (MA) for mediumsize and large-size game instances, which are beyond MILP’s scalability. Utilization of MA is, to the best of our knowledge, a new idea in the field of SG. The novelty of proposed solution lies specifically in efficient chromosome-based game encoding and dedicated local improvement heuristics. In vast majority of test cases with known equilibrium profiles, the method leads to optimal solutions with high stability and approximately linear time scalability. Another advantage is an iteration-based construction of the system, which makes the approach essentially an anytime method. This property is of paramount importance in case of restrictive time limits, which could hinder the possibility of calculating an exact solution. On a general note, we believe that MA-based methods may offer a viable alternative to MILP solvers for complex games that require application of approximate solving methods.
DOI：
10.1609/aaai.v31i1.10614
发表时间：
2017-02
期刊：
--
影响因子：
--
作者：
Jiarui Gan;Bo An;Yevgeniy Vorobeychik;B. Gauch
通讯作者：
Jiarui Gan;Bo An;Yevgeniy Vorobeychik;B. Gauch