Year: 2019

Abstract:
Goal recognition based on the observations of the behaviors collected online has been used to model some potential applications. Newly formulated problem of goal recognition design aims at facilitating the online goal recognition process by performing offline redesign of the underlying environment with hard action removal. In this paper, we propose the stochastic goal recognition control (S-GRC) problem with two main stages: (1) deceptive opponent modeling based on maximum entropy regularized Markov decision processes (MDPs) and (2) goal recognition control under proactively static interdiction. For the purpose of evaluation, we propose to use the worst case distinctiveness (wcd) as a measure of the nondistinctive path without revealing the true goals, the task of S-GRC is to interdict a set of actions that improve or reduce the wcd. We empirically demonstrate that our proposed approach control the goal recognition process based on opponent’s deceptive behavior.

text: Goal recognition based on the observations of the behaviors collected online has been used to model some potential applications. Newly formulated problem of goal recognition design aims at facilitating the online goal recognition process by performing offline redesign of the underlying environment with hard action removal. In this paper, we propose the stochastic goal recognition control (S-GRC) problem with two main stages: (1) deceptive opponent modeling based on maximum entropy regularized Markov decision processes (MDPs) and (2) goal recognition control under proactively static interdiction. For the purpose of evaluation, we propose to use the worst case distinctiveness (wcd) as a measure of the nondistinctive path without revealing the true goals, the task of S-GRC is to interdict a set of actions that improve or reduce the wcd. We empirically demonstrate that our proposed approach control the goal recognition process based on opponent’s deceptive behavior.

heading: 1 INTRODUCTION
text: Goal recognition (GR), also called intention recognition, is the task of inferring the goals of an agent according to the observed actions or states collected online (Sadri, 2011), which enables humans or agents to make proactive response plans. Goal recognition design (GRD) is to deliberately redesign the environment for improved online goal recognition ability (Keren et al., 2014), which includes two key models, the first measures how efficiently and effectively the online goal recognition system performs in a given setting, the second optimizes the goal recognition setting via redesign (Keren et al., 2019). Goal recognition control (GRC) aims at soft action interdiction under bounded resource by adding cost compared to the hard action removal of GRD (Luo et al., 2019), in which the interdiction can be proactively static inhibition or online dynamic block by allocating security resources to protect goals against the attacker.
In fact, under complex environment (both adversarial and cooperative), the information of an opponent’s goals are asymmetric and can not be obtained through communication (Le Guillarme, 2016). Most recent advancements in GR utilize planning recognition as planning (PRAP) (Ramı́rez & Geffner, 2009), generative game-theoretic frameworks (Ang et al., 2017), and goal recognition as planning (GRAP) (Pereira et al., 2019). There are three key assumptions widely used: (1) agents performs optimal plans to real the goals; (2) the environment is fully observable, that is the states and actions of the agents are observable; and (3) the agent’s actions are deterministic. However, these existing frameworks seldom address the deceptive behaviors of actively misleading the goal recognition process. We will relax the first and third assumptions to handle non-optimal agents and stochastic actions. Such as one game-theoretic approach provided with a unified treatment of both threat assessment and response planning in (Guillarme et al., 2017), after evaluating the threat, the defender will allocate road barrier or patrolling force to protect critical infrastructure, as illustrated in Figure 1.
In order to identify the goals and improve security, we employ opponent modeling to deal with the non-stationary strategies stemming from deception, in which maximum entropy regularized Markov decision process (MDP) is utilized to shape the multi-modal adversarial strategies (Shen & How,
2019). After finding the maximal non-distinctive agent path, we are seeking some optimal modifications (e.g., interdiction to block or inhibit action) to accelerate the online goal recognition.
In this work, we propose the stochastic goal recognition design (S-GRC) problem with deceptive opponent modeling and proactive network interdiction: the opponent’s deceptive policy is modeled as one soft multi-criteria decision policy with one tunable parameter to balance goal achievement and deception preference; and the primary objective is offline redesigning the environment by soft action interdiction to control online GR.
To validate the model, we evaluate our approach in two different environment representations: random generated connected graph and real road network. Our experiments demonstrate that (1) deceptive opponent modeling with entropy regularization make it robust to multi-modal stochastic behaviors; (2) soft decision policy based stochastic goal recognition design model for action removal bridge the gap between observation and decision making.

heading: 2 RELATED WORK

heading: 2.1 GOAL RECOGNITION AND DESIGN
text: Goal Recognition (GR): The ability of inferring the goals of others can assist us to reason about what they are doing, why they are doing it, and what they will do next (Sukthankar et al., 2014). The recognition setting can be generally be divided into keyhole, where the agent is unaware of being observed and recognized as if the agent is looking through a keyhole; adversarial, where the agent is actively hostile to the observations of the actions and the inference of the goals; and intended, where the agent wants to convey the goal to be understood and helps the recognizer to detect the objective (Keren et al., 2019). In this work, we focus on the adversarial setting, where the agent would hide the goal and attempt to thwart the recognition process by deception. GR is strongly related to the topic of privacy-preserving and explainable planning (Keren et al., 2016; Chakraborti et al., 2019; Kulkarni et al.).
Goal Recognition Design (GRD): The GRD problems contains two models: one goal recognition setting analyzed environments, acting agent (attacker), and recognition system (recognizer, observer); one design model of possible ways to change the environment (Keren et al., 2019). The environment will induce a set of possible behaviors for the attacker, GRD can be divided into deterministic GRD (Keren et al., 2019), stochastic GRD (S-GRD) (Wayllace et al., 2018; Wayllace, 2019), GRD for Agents with partial knowledge (GRD-APK) (Sarah et al., 2019), and gametheoretic GRD (Ang et al., 2017; Masters & Sardina, 2017). Also, many design measures have been employed, such as action removal (AR), action sensor refinement (SAR), and action conditioning (AC) (Keren et al., 2018; Wayllace et al., 2018).

heading: 2.2 OPPONENT MODELING AND NETWORK INTERDICTION
text: Deceptive Opponent Modeling: Opponent modeling has been employed to reason the nonstationary strategies of autonomous agents (Albrecht & Stone, 2018; Papoudakis et al., 2019). Deception involves combination of hiding the truth and showing the false (Masters & Sardina, 2017), which articulated three distinct strategies in each case: dissimulation (masking, repackaging, and dazzling), simulation (mimicking, inventing, and decoying) (Ettinger & Jehiel, 2010). As for deceptive path planning, game-theoretic method (Root, 2005) and model based (Masters & Sardina, 2017) method have been investigated.
Network Interdiction: In recent researches, interdiction has been used to counter the attacker’s behavior, MDP interdiction (Panda & Vorobeychik, 2017), plan interdiction (Vorobeychik & Pritchard, 2018), and network interdiction (Xu et al.) show one promising research thread of Observe-OrientDecide-Act (OODA).

heading: 2.3 REGULARIZED MDPS
text: Most sequential decision-making problems can be described as MDP based reinforcement learning problems or stochastic game problems. Regularization for MDPs can be divided into temporal regularization problems in temporal space (Thodoroff et al., 2018), spatial regularization in feature or state space (Farahmand, 2011; Harrigan), and entropy or information regularization in policy space (Neu et al., 2017; Geist et al., 2019; Belousov & Peters, 2019). Regularized reinforcement learning focuses on the smoothness and sparsity of the value function (Farahmand, 2011), acquiring of diverse robot skills (Haarnoja, 2018), and sparsity and multi-modality of the optimal policy (Lee et al., 2019). Regularized stochastic game employees various entropy constraints to balance or control behavior (Grau-Moya et al., 2018; Savas et al., 2019; Ahmadi et al., 2018; Tian et al., 2019).

heading: 3 STOCHASTIC GOAL RECOGNITION CONTROL
text: The goal recognition control (GRC) problems try to balance the intended and adversarial goal recognition process under network interdiction (Luo et al., 2019), which extends to assume that the agent can choose to reveal or obfuscate (Kulkarni et al., 2019b;a), share or hide (Strouse et al., 2018) the goals. In this paper, we focus on stochastic GRC (S-GRC) under adversarial, cooperative, and non-stationary environment. The framework of our proposed approach is illustrated in Figure 3.
We embed deceptive opponent modeling and proactive network interdiction into the OODA cycle as two modules, which could bridge the gap between observation and decision-making. The deceptive opponent modeling module will shape the multi-modal opponent, the proactive network interdiction module will provide bounded resource allocation for defense. So, GRC will identify the goals with topological soft q learning and provide proactive interdiction resource allocation.

heading: 3.1 SSP-MDP FOR S-GRC
text: Different from the GRD problem, we employ more applicable and soft measure of interdiction with bounded resource to control the goal recognition process. With this motivation in mind, we use the Stochastic Shortest-Path MDP (SSP-MDP) (Kolobov & Kolobov, 2012) model, which is widely used for uncertainty given an initial state, a set of goal states, actions with probabilistic outcomes and an action cost function. A SSP-MDP is represented as a tuple 〈S, s0,A,T,C,G〉, which consists a set of states S, a initial state s0, a set of actions A, a transition function T : S×A× S→ [0, 1] of state transition from s to s′ after executing the action a, and a cost function C : S ×A × S → R that gives the cost of executing action a, and a set of terminal goals G ⊆ S. With a cost function to replace the reward function, the objective is to find a optimal policy π so as to minimize the smallest expected cost or travel time of the policy, which forms the map from states to actions.
So, the optimal policy of the SSP-MDP can be find by using the Value Iteration (VI) algorithm, which use a value function V to represent expected costs. The expected cost of an optimal policy π∗ for the starting state s0 ∈ S is the expected cost V (s0), and the expected cost for all states s ∈ S can be calculated by the Bellman equation (Kolobov & Kolobov, 2012):
V (s) = min a∈A ∑ s′∈S T (s, a, s′) [C (s, a, s′) + V (s′)] (1)
A previous work on stochastic shortest path network interdiction modeled the problem as one sequential bi-level attacker-defender game, where the defender moves first by deploying sensors to the arcs in the network maximizing the expected shortest traveling time of the adversary (Zhang et al., 2018). Here we formulate the stochastic goal recognition control (S-GRC) problem as an extension of the GRD problem to allows non-optimal agents and stochastic actions, which means the agent’s action are not deterministic and the possible successor states are with probability, the measures we can take are interdictions with cost. The bounded interdiction resources allocations can better model the real world applications. A S-GRC problem is represented as a tuple P = 〈D,G〉, the domain information D = 〈S, s0,A,T,C,G〉 can be represented as SSP-MDPs. Similar to the S-GRD (Wayllace et al., 2018), we employ a metric to assess the largest number of actions an agent can take or the largest cost an agent will incur before revealing the goal. Given a problem P = 〈D,G〉, the worst case distinctiveness (wcd) of the problem can be defined as:
wcd(P ) = max π∈II Vπ (s0) (2)
So the objective of S-GRC under network interdiction can be reformulated as one optimization problem of finding a subset of actions ∆A∗ ⊂ A:
∆A∗ = argmin ∆A⊂A wcd(P̂ )
s.t. Vπ;s (s0) = Vτ̂ ;ŝ (s0) ∀g ∈ G∑ (1∆A∗ × I) ≤ k
(3)
where P = 〈D̂,G〉 is the problem with domain D̂ = 〈 S, s0, Â,T,C,G 〉 , Â is the redesigned action set with ∆A∗ interdicted, I is the corresponding cost to the interdiction resource, the total interdiction resource allocation is bounded by k.

heading: 3.2 AUGMENTED SSP-MDP WITH SCCS
text: With the metric wcd, we can measure the maximal number of actions an agent can take before its goal is revealed. However, the formal wcd related metrics for S-GRDs are inconsistent with the intuitive definition, the wcd computation is not Markovian owing to the set of possible goals depend on the observed trajectory to a state. To deal with the uncertain inconsistence, wcdag and
ECD together with topological value iteration are employed to model the problem, in which the augmented MDPs with strongly connected components do not have loops (Wayllace et al.).
The state space of an MDP can be represented as a directed connectivity graph. One example MDP is shown in Figure 3(a), where the states are denoted by nodes, the actions are denoted by edges, the transitions are related to the arrow. The wcd may be infinite when the state space contains some cycle loop, here we can use the Tarjan algorithm (Tarjan, 1972; Hou et al., 2014) to generate strongly connected components (SCCs), which form a directed acyclic graph (DAG) as shown in Figure 3(b).
Augmented SSP-MDP for S-GRC: Given a SSP-MDP, an augmented SSP-MDP〈 S̃, s̃0, Ã, T̃, C̃, G̃ 〉 augments each component of the tuple:
• Each state ŝ ∈ Ŝ is represented by 〈s,G′〉. • The augmented initial state is s̃0 = 〈s0,G〉.
• Each augmented action â ∈ Â is a tuple 〈a,G′〉, where aA and G′ is the set of all goals for which that action is an optimal action.
• The new transition function T̃ : S̃ × Ã × S̃ → [0, 1] gives the probability T̃ (s̃, ã, s̃′), where s̃ = 〈s,G′〉, ã = 〈a,G′〉, and s̃′ = 〈s′,G′ ∩G′′〉, T̃ (s̃, ã, s̃′) = T (s, a, s′), if |G′ ∩G′′| > 1 and equals 0 otherwise.
• The cost function C̃ : S̃ × Ã × S̃ → R+ gives the cost C̃ (s̃, ã, s̃′) of executing action ã in augmented state s̃ and arriving in s̃′′. This cost equals the cost C̃ (s̃, ã, s̃′) = C(s, a, s′) under the same condition as above.
• The augmented goal states G̃ ⊆ S̃ are those augmented states 〈s,G′〉 for which any execution of an augmented action will transition to an augmented state 〈s′,G′′′〉 with one goal or no goals.

heading: 3.3 DECEPTIVE OPPONENT MODELING
text: As the opponent may change the goals midway to mislead the goal recognition process. We use a binary variable λ ∈ {0, 1} to characterize whether the opponent is a optimal or deceptive with decoy goals.
Depending on λ, the opponent is expected to exhibit different behaviors, which is fully described by an opponent policy πo(aot |st). This model is restrictive since the action probability only depend on the current state. Nonetheless, we use this model only for policy learning, and use a general history dependent opponent policy for the evaluation of the learned autonomous agent policy. Another implicit assumption of this model is that the opponent has full observability over the states. This assumption could be released by modeling the opponent as a POMDP agent.
Neutral Opponent: If the opponent is a civilian, i.e. λ = 0, we assume a simple reactive policy πcil(aot |st) is available to model the opponent:
πo(aot |st, λ = 0) = πcil(aot |st). (4)
Deceptive Opponent: We use the following equation to model an adversarial agent’s policy πo:
πo(aot |st, λ = 1;α, β) =argminπ∈∆{KL(π|πMDPα ) + βKL(π|πo(·|st, λ = 0))}, (5)
πMDPα (a o t |st, λ = 1) = eαQ(st,a o t )/Z(st), (6)
where KL(·|·) denotes the Kullback–Leibler divergence between two distributions, The goalachieving policy πMDPα is associated with the optimal Q function Q(st, a o t ), of a goal-achieving adversary MDP defined later. The temperature parameter α in (6) represents the level of rationality of the adversary. The other parameter β indicates the level of deception. Z(st) is the partition function that normalizes πMDPα .
Soft Q Learning: We use soft-Q learning (Haarnoja, 2018) to learn a stochastic belief space policy. The soft Q learning objective is to maximize the expected reward regularized by the entropy of the policy, ∑
t
Ebt,st,at∼ρπγt[r(bt, st, at) + σH(π(·|bt, st))]. (7)
The parameter σ controls the ‘softness’ of the policy. The nice interpretation of this objective function is maximizing accumulative reward while behaving as uncertain as possible, which is a desired property against an adversary. This maximum entropy problem is solved using soft Q iteration. For discrete action space, the fixed point iteration:
Qsoft(bt, st, at)← rt + γEbt+1,st+1∼ps [Vsoft(bt+1, st+1)], (8) Vsoft(bt, st)← σ log ∑ a∈A exp( 1 σ Qsoft(bt, st, a)), (9)
converges to the optimal soft value functionsQ∗soft and V ∗
soft (Haarnoja, 2018), and the optimal policy can be obtained from:
π∗MaxEnt(at|bt, st) = exp( 1
σ (Q∗soft(bt, st, at)− V ∗soft(bt, st))). (10)

heading: 3.4 PROACTIVE NETWORK INTERDICTION
text: Proactive network interdiction

heading: 4 EXPERIMENTS

heading: 4.1 GRID WORLD

heading: 4.2 NETWORK GRAPH

heading: 4.3 RESULTS

heading: 5 CONCLUSION AND FUTURE WORK
text: Risk-Sensitive MDPs (Hou et al., 2014) illustrate one applicable scenario where the cost function is constrained with one threshold or deadline.
See Table 1.

heading: ACKNOWLEDGMENTS
text: This work is partially sponsored by the National Natural Science Foundation of China under Grants No. 61702528, No. 61806212.

Review summaries:
This paper studies goal recognition control given a deceptive opponent, who selects actions to intentionally mislead or confusing the learner to learn the true goal. The problem has been studied in the security game, resource allocation game and Stackelberg game, where the defender is to play a resource allocation game given the best response of the attacker. in this paper, the authors use stochastic-shortest-path MDP to model the attacker's planning problem. The defender's objective is stated in eq (2) and (3) but not explained clearly.

This paper proposes to use reinforcement learning to model an agent that is reaching goal that it is intended to reach. The authors consider the case where the agent is (1) indifferent to being observed, (2) trying to help an observer reach its goal, and (3) trying to fool the observer into not reach its goal. The paper propose to use a value function to quantify how easy it is to predict where the agent is going ("worst case distinctiveness"). The authors propose to then train an agent to modify the action space to make it difficult for an agent to fool the observer.

This paper aims to provide a goal recognition framework. The paper reviews previous literature and outlines a model, but it seems to be at the draft stage as it stands as the experiment section is missing (section 4). Also, in some parts the sentences are broken and hard to follow, for example, “Here we formulate the stochastic goal recognition control (S-GRC) problem as an extension of the GRD problem to allows non-optimal agents and stochastic actions, which means the agent’s action are not deterministic and the possible successor states are with probability, the measures we can take are interdictions with cost.”