  In this paper, we study the use of deception for strategic planning in
adversarial environments. We model the interaction between the agent (player 1)
and the adversary (player 2) as a two-player concurrent game in which the
adversary has incomplete information about the agent's task specification in
temporal logic. During the online interaction, the adversary can infer the
agent's intention from observations and adapt its strategy so as to prevent the
agent from satisfying the task. To plan against such an adaptive opponent, the
agent must leverage its knowledge about the adversary's incomplete information
to influence the behavior of the opponent, and thereby being deceptive. To
synthesize a deceptive strategy, we introduce a class of hypergame models that
capture the interaction between the agent and its adversary given asymmetric,
incomplete information. A hypergame is a hierarchy of games, perceived
differently by the agent and its adversary. We develop the solution concept of
this class of hypergames and show that the subjectively rationalizable strategy
for the agent is deceptive and maximizes the probability of satisfying the task
in temporal logic. This deceptive strategy is obtained by modeling the opponent
evolving perception of the interaction and integrating the opponent model into
proactive planning. Following the deceptive strategy, the agent chooses actions
to influence the game history as well as to manipulate the adversary's
perception so that it takes actions that benefit the goal of the agent. We
demonstrate the correctness of our deceptive planning algorithm using robot
motion planning examples with temporal logic objectives and design a detection
mechanism to notify the agent of potential errors in modeling of the
adversary's behavior.
