公开(公告)号：US20090119239A1

公开(公告)日：2009-05-07

申请号：US12251766

申请日：2008-10-15

Applicant: Milind Tambe ,  Praveen Paruchuri ,  Fernando Ordonez ,  Sarit Kraus ,  Jonathan Pearce ,  Janusz Marecki

Inventor： Milind Tambe ,  Praveen Paruchuri ,  Fernando Ordonez ,  Sarit Kraus ,  Jonathan Pearce ,  Janusz Marecki

IPC: G06N5/02 ,  G06F17/00

CPC classification number: G06N7/005 ,  G06F17/11 ,  G06Q10/063

Abstract: Efficient heuristic methods are described for approximating the optimal leader strategy for security domains where threats come from unknown adversaries. These problems can be modeled as Bayes-Stackelberg games. An embodiment of the heuristic method can include defining a patrolling or security domain problem as a mixed-integer quadratic program. The mixed-integer quadratic program can be converted to a mixed-integer linear program. For a single follower (e.g., robber or terrorist) scenario, the mixed-integer linear program can be solved, subject to appropriate constraints. For embodiments applicable to multiple follower situations, the relevant mixed-integer quadratic program and related mixed-integer linear program can be decomposed, e.g., by changing the response function for the follower from a pure strategy to a weighted combination over various pure follower strategies where the weights are probabilities of occurrence of each of the follower types.

Abstract translation: 描述了有效的启发式方法，用于近似来自未知对手的威胁的安全域的最优引导策略。 这些问题可以被建模为Bayes-Stackelberg游戏。 启发式方法的实施例可以包括将巡逻或安全域问题定义为混合整数二次方案。 混合整数二次方程可以转换为混合整数线性程序。 对于单个追随者（例如强盗或恐怖分子）场景，可以在适当的约束条件下解决混合整数线性程序。 对于适用于多个跟随者情况的实施例，可以分解相关的混合整数二次方程和相关的混合整数线性程序，例如通过将各种纯粹的跟随器策略的纯粹策略的追随者的响应函数改变为加权组合， 权重是每个跟随器类型的发生概率。

公开(公告)号：US20120330727A1

公开(公告)日：2012-12-27

申请号：US13479884

申请日：2012-05-24

Applicant: Milind Tambe ,  Praveen Paruchuri ,  Fernando Ordóñez ,  Sarit Kraus ,  Jonathan Pearce ,  Janusz Marecki

Inventor： Milind Tambe ,  Praveen Paruchuri ,  Fernando Ordóñez ,  Sarit Kraus ,  Jonathan Pearce ,  Janusz Marecki

IPC: G06Q10/04

CPC classification number: G06N7/005 ,  G06F17/11 ,  G06Q10/063

Abstract: Efficient heuristic methods are described for approximating the optimal leader strategy for security domains where threats come from unknown adversaries. These problems can be modeled as Bayes-Stackelberg games. An embodiment of the heuristic method can include defining a patrolling or security domain problem as a mixed-integer quadratic program. The mixed-integer quadratic program can be converted to a mixed-integer linear program. For a single follower (e.g., robber or terrorist) scenario, the mixed-integer linear program can be solved, subject to appropriate constraints. For embodiments applicable to multiple follower situations, the relevant mixed-integer quadratic program and related mixed-integer linear program can be decomposed, e.g., by changing the response function for the follower from a pure strategy to a weighted combination over various pure follower strategies where the weights are probabilities of occurrence of each of the follower types.

Abstract translation: 描述了有效的启发式方法，用于近似来自未知对手的威胁的安全域的最优引导策略。 这些问题可以被建模为Bayes-Stackelberg游戏。 启发式方法的实施例可以包括将巡逻或安全域问题定义为混合整数二次方案。 混合整数二次方程可以转换为混合整数线性程序。 对于单个追随者（例如强盗或恐怖分子）场景，可以在适当的约束条件下解决混合整数线性程序。 对于适用于多个跟随者情况的实施例，可以分解相关的混合整数二次方程和相关的混合整数线性程序，例如通过将各种纯粹的跟随器策略的纯粹策略的追随者的响应函数改变为加权组合， 权重是每个跟随器类型的发生概率。

公开(公告)号：US08224681B2

公开(公告)日：2012-07-17

申请号：US12253695

申请日：2008-10-17

Applicant: Milind Tambe ,  Praveen Paruchuri ,  Fernando Ordóñez ,  Sarit Kraus ,  Jonathan Pearce ,  Janusz Marecki

Inventor： Milind Tambe ,  Praveen Paruchuri ,  Fernando Ordóñez ,  Sarit Kraus ,  Jonathan Pearce ,  Janusz Marecki

IPC: G06Q10/00 ,  G06G7/48

CPC classification number: G06F15/16 ,  G06F17/11 ,  G06N7/005 ,  G06Q10/063

Abstract: Techniques are described for Stackelberg games, in which one agent (the leader) must commit to a strategy that can be observed by other agents (the followers or adversaries) before they choose their own strategies, in which the leader is uncertain about the types of adversaries it may face. Such games are important in security domains, where, for example, a security agent (leader) must commit to a strategy of patrolling certain areas, and robbers (followers) have a chance to observe this strategy over time before choosing their own strategies of where to attack. An efficient exact algorithm is described for finding the optimal strategy for the leader to commit to in these games. This algorithm, Decomposed Optimal Bayesian Stackelberg Solver or “DOBSS,” is based on a novel and compact mixed-integer linear programming formulation. The algorithm can be implemented in a method, software, and/or system including computer or processor functionality.

Abstract translation: Stackelberg游戏描述了一些技巧，其中一个代理人（领导者）必须承诺在选择自己的策略之前，其他代理商（追随者或对手）可以遵守的策略，其中领导者不确定 对手可能会面对。 这样的游戏在安全领域很重要，例如，安全代理（领导者）必须承诺对某些地区进行巡逻的策略，强盗（追随者）有机会在选择自己的策略之前，随时随地观察此策略 去攻击。 描述了一种有效的精确算法，用于找到领导者在这些游戏中承诺的最佳策略。 该算法，分解最优贝叶斯堆栈解算器或“DOBSS”是基于一种新颖紧凑的混合整数线性规划公式。 该算法可以在包括计算机或处理器功能的方法，软件和/或系统中实现。

公开(公告)号：US20110282801A1

公开(公告)日：2011-11-17

申请号：US12780650

申请日：2010-05-14

Applicant: Janusz Marecki

Inventor： Janusz Marecki

IPC: G06Q40/00

CPC classification number: G06Q40/08 ,  G06Q40/06

Abstract: System, method and computer program product for modelling Risk-Sensitive Partially-Observable Markov Decision Processes (POMDPs), e.g., in a high-risk domain such as financial planning and solving such equations exactly, such that agents maximize the expected utility of their actions. The system and method employs an exact algorithm for solving Risk-Sensitive POMDPs, for piecewise linear utility functions, by representing underlying value functions with sets of piecewise bilinear functions—computed using functional value iteration—and pruning the dominated bilinear functions using efficient linear programming approximations of underlying non-convex bilinear programs. Considering piecewise linear approximations of utility functions, (i) there is defined the Risk-Sensitive POMDP model that incorporates value functions V(b,w) where argument “b” is a belief state and argument “w” is a continuous wealth dimension; (ii) derive the fundamental properties of the underlying value functions and provide a functional value iteration technique to compute them; and (iii) determine the dominated value functions, to speed up the algorithm.

Abstract translation: 系统，方法和计算机程序产品，用于建模风险敏感的部分可观察马尔可夫决策过程（POMDP），例如在高风险领域（如财务计划）和精确解决这些方程式，使代理人最大化其行为的预期效用 。 该系统和方法采用精确的算法来解决风险敏感性POMDP，用于分段线性效用函数，通过使用功能值迭代计算的分段双线性函数集来表示底层值函数，并使用有效的线性规划近似来修剪主导双线性函数 潜在的非凸双线性程序。 考虑效用函数的分段线性近似，（i）定义了风险敏感性POMDP模型，其包含价值函数V（b，w），其中参数“b”是信念状态，参数“w”是连续的财富维度; （ii）导出基础值函数的基本属性，并提供函数值迭代技术来计算它们; 和（iii）确定主导价值函数，以加快算法。

公开(公告)号：US20130204412A1

公开(公告)日：2013-08-08

申请号：US13364843

申请日：2012-02-02

Applicant: Janusz Marecki ,  Richard B. Segal ,  Gerald J. Tesauro

Inventor： Janusz Marecki ,  Richard B. Segal ,  Gerald J. Tesauro

IPC: G06F19/00

CPC classification number: G07F17/32

Abstract: A system, method and computer program product for planning actions in a repeated Stackelberg Game, played for a fixed number of rounds, where the payoffs or preferences of the follower are initially unknown to the leader, and a prior probability distribution over follower types is available. In repeated Bayesian Stackelberg games, the objective is to maximize the leader's cumulative expected payoff over the rounds of the game. The optimal plans in such games make intelligent tradeoffs between actions that reveal information regarding the unknown follower preferences, and actions that aim for high immediate payoff. The method solves for such optimal plans according to a Monte Carlo Tree Search method wherein simulation trials draw instances of followers from said prior probability distribution. Some embodiments additionally implement a method for pruning dominated leader strategies.

Abstract translation: 一种用于在重复的Stackelberg游戏中规划动作的系统，方法和计算机程序产品，用于固定数量的回合，其中追随者的收益或偏好最初对于领导者是未知的，并且可以使用在跟随者类型上的先前概率分布 。 在重复的贝叶斯Stackelberg游戏中，目标是最大限度地提高领先者在游戏中的累积预期回报。 这些游戏中的最佳计划使得智能权衡行为之间的关系，揭示关于未知的追随者偏好的信息，以及旨在高度立即回报的行动。 该方法根据蒙特卡洛树搜索方法来解决这样的最佳计划，其中模拟试验从所述先验概率分布中抽取跟随者的实例。 一些实施例另外实现了修剪主导的领导策略的方法。

公开(公告)号：US20090099987A1

公开(公告)日：2009-04-16

申请号：US12253695

申请日：2008-10-17

Applicant: Milind Tambe ,  Praveen Paruchuri ,  Fernando Ordonez ,  Sarit Kraus ,  Jonathan Pearce ,  Janusz Marecki

Inventor： Milind Tambe ,  Praveen Paruchuri ,  Fernando Ordonez ,  Sarit Kraus ,  Jonathan Pearce ,  Janusz Marecki

IPC: G06F15/18

CPC classification number: G06F15/16 ,  G06F17/11 ,  G06N7/005 ,  G06Q10/063

Abstract: Techniques are described for Stackelberg games, in which one agent (the leader) must commit to a strategy that can be observed by other agents (the followers or adversaries) before they choose their own strategies, in which the leader is uncertain about the types of adversaries it may face. Such games are important in security domains, where, for example, a security agent (leader) must commit to a strategy of patrolling certain areas, and robbers (followers) have a chance to observe this strategy over time before choosing their own strategies of where to attack. An efficient exact algorithm is described for finding the optimal strategy for the leader to commit to in these games. This algorithm, Decomposed Optimal Bayesian Stackelberg Solver or “DOBSS,” is based on a novel and compact mixed-integer linear programming formulation. The algorithm can be implemented in a method, software, and/or system including computer or processor functionality.

Abstract translation: Stackelberg游戏描述了一些技巧，其中一个代理人（领导者）必须承诺在选择自己的策略之前，其他代理商（追随者或对手）可以遵守的策略，其中领导者不确定 对手可能会面对。 这样的游戏在安全领域很重要，例如，安全代理（领导者）必须承诺对某些地区进行巡逻的策略，强盗（追随者）有机会在选择自己的策略之前，随时随地观察此策略 去攻击。 描述了一种有效的精确算法，用于找到领导者在这些游戏中承诺的最佳策略。 该算法，分解最优贝叶斯堆栈解算器或“DOBSS”是基于一种新颖紧凑的混合整数线性规划公式。 该算法可以在包括计算机或处理器功能的方法，软件和/或系统中实现。

公开(公告)号：US08793211B2

公开(公告)日：2014-07-29

申请号：US12806686

申请日：2010-08-19

Applicant: Janusz Marecki ,  Mudhakar Srivatsa

Inventor： Janusz Marecki ,  Mudhakar Srivatsa

IPC: G06F15/00 ,  G06F15/18

CPC classification number: G06Q30/00 ,  G06Q10/10 ,  H04L63/104 ,  H04L63/1416 ,  H04L2209/603 ,  H04L2209/606 ,  H04L2209/608 ,  H04L2463/101

Abstract: System, method and computer program product for modelling information sharing domains as Partially Observable Markov Decision Processes (POMDP), and that provides solutions that view the information sharing as a sequential process where the trustworthiness of the information recipients is monitored using data leakage detection mechanisms. In one embodiment, the system, method and computer program product performs (i) formulating information sharing decisions using Partially Observable Markov Decision Processes combined with a digital watermarking leakage detection mechanism, and (ii) deriving optimal information sharing strategies for the sender and optimal information leakage strategies for a recipient as a function of the efficacy of the underlying monitoring mechanism. By employing POMDPs in information sharing domains, users (senders) can maximize the expected reward of their data/information sharing actions.

Abstract translation: 用于将信息共享域建模为部分可观察马尔可夫决策过程（POMDP）的系统，方法和计算机程序产品，并提供将信息共享视为顺序过程的解决方案，其中使用数据泄漏检测机制监控信息接收者的可信赖性。 在一个实施例中，系统，方法和计算机程序产品执行（i）使用与数字水印泄漏检测机制结合的部分可观察马尔可夫决策过程来制定信息共享决策，以及（ii）为发送者获得最佳信息共享策略和最佳信息 受体的渗漏策略作为底层监测机制的功效的函数。 通过在信息共享域中使用POMDP，用户（发件人）可以最大限度地提高其数据/信息共享行为的预期报酬。

公开(公告)号：US08545332B2

公开(公告)日：2013-10-01

申请号：US13364843

申请日：2012-02-02

Applicant: Janusz Marecki ,  Richard B. Segal ,  Gerald J. Tesauro

Inventor： Janusz Marecki ,  Richard B. Segal ,  Gerald J. Tesauro

IPC: A63F13/00

CPC classification number: G07F17/32

Abstract: A system, method and computer program product for planning actions in a repeated Stackelberg Game, played for a fixed number of rounds, where the payoffs or preferences of the follower are initially unknown to the leader, and a prior probability distribution over follower types is available. In repeated Bayesian Stackelberg games, the objective is to maximize the leader's cumulative expected payoff over the rounds of the game. The optimal plans in such games make intelligent tradeoffs between actions that reveal information regarding the unknown follower preferences, and actions that aim for high immediate payoff. The method solves for such optimal plans according to a Monte Carlo Tree Search method wherein simulation trials draw instances of followers from said prior probability distribution. Some embodiments additionally implement a method for pruning dominated leader strategies.

Abstract translation: 一种用于在重复的Stackelberg游戏中规划动作的系统，方法和计算机程序产品，用于固定数量的回合，其中追随者的收益或偏好最初对于领导者是未知的，并且可以使用在跟随者类型上的先前概率分布 。 在重复的贝叶斯Stackelberg游戏中，目标是最大限度地提高领先者在游戏中的累积预期回报。 这些游戏中的最佳计划使得智能权衡行为之间的关系，揭示关于未知的追随者偏好的信息，以及旨在高度立即回报的行动。 该方法根据蒙特卡洛树搜索方法来解决这样的最佳计划，其中模拟试验从所述先验概率分布中抽取跟随者的实例。 一些实施例另外实现了修剪主导的领导策略的方法。

公开(公告)号：US08364511B2

公开(公告)日：2013-01-29

申请号：US13479884

申请日：2012-05-24

Applicant: Milind Tambe ,  Praveen Paruchuri ,  Fernando Ordóñez ,  Sarit Kraus ,  Jonathan Pearce ,  Janusz Marecki

Inventor： Milind Tambe ,  Praveen Paruchuri ,  Fernando Ordóñez ,  Sarit Kraus ,  Jonathan Pearce ,  Janusz Marecki

IPC: G06Q10/00 ,  G06G7/48

CPC classification number: G06N7/005 ,  G06F17/11 ,  G06Q10/063

Abstract: Efficient heuristic methods are described for approximating the optimal leader strategy for security domains where threats come from unknown adversaries. These problems can be modeled as Bayes-Stackelberg games. An embodiment of the heuristic method can include defining a patrolling or security domain problem as a mixed-integer quadratic program. The mixed-integer quadratic program can be converted to a mixed-integer linear program. For a single follower (e.g., robber or terrorist) scenario, the mixed-integer linear program can be solved, subject to appropriate constraints. For embodiments applicable to multiple follower situations, the relevant mixed-integer quadratic program and related mixed-integer linear program can be decomposed, e.g., by changing the response function for the follower from a pure strategy to a weighted combination over various pure follower strategies where the weights are probabilities of occurrence of each of the follower types.

公开(公告)号：US08195490B2

公开(公告)日：2012-06-05

申请号：US12251766

申请日：2008-10-15

Applicant: Milind Tambe ,  Praveen Paruchuri ,  Fernando Ordóñez ,  Sarit Kraus ,  Jonathan Pearce ,  Janusz Marecki

Inventor： Milind Tambe ,  Praveen Paruchuri ,  Fernando Ordóñez ,  Sarit Kraus ,  Jonathan Pearce ,  Janusz Marecki

IPC: G06Q10/00 ,  G06G7/48

CPC classification number: G06N7/005 ,  G06F17/11 ,  G06Q10/063

Abstract: Efficient heuristic methods are described for approximating the optimal leader strategy for security domains where threats come from unknown adversaries. These problems can be modeled as Bayes-Stackelberg games. An embodiment of the heuristic method can include defining a patrolling or security domain problem as a mixed-integer quadratic program. The mixed-integer quadratic program can be converted to a mixed-integer linear program. For a single follower (e.g., robber or terrorist) scenario, the mixed-integer linear program can be solved, subject to appropriate constraints. For embodiments applicable to multiple follower situations, the relevant mixed-integer quadratic program and related mixed-integer linear program can be decomposed, e.g., by changing the response function for the follower from a pure strategy to a weighted combination over various pure follower strategies where the weights are probabilities of occurrence of each of the follower types.

Abstract translation: 描述了有效的启发式方法，用于近似来自未知对手的威胁的安全域的最优引导策略。 这些问题可以被建模为Bayes-Stackelberg游戏。 启发式方法的实施例可以包括将巡逻或安全域问题定义为混合整数二次方案。 混合整数二次方程可以转换为混合整数线性程序。 对于单个追随者（例如强盗或恐怖分子）场景，混合整数线性程序可以在适当的约束条件下得到解决。 对于适用于多个跟随者情况的实施例，相关的混合整数二次方程和相关的混合整数线性程序可以被分解，例如通过在各种纯跟随器策略中将从追随者的响应函数从纯策略改变为加权组合， 权重是每个跟随器类型的发生概率。