  We consider a class of two-player turn-based zero-sum games on graphs with
reachability objectives, known as reachability games, where the objective of
Player 1 (P1) is to reach a set of goal states, and that of Player 2 (P2) is to
prevent this. In particular, we consider the case where the players have
asymmetric information about each other's action capabilities: P2 starts with
an incomplete information (misperception) about P1's action set, and updates
the misperception when P1 uses an action previously unknown to P2. When P1 is
made aware of P2's misperception, the key question is whether P1 can control
P2's perception so as to deceive P2 into selecting actions to P1's advantage?
We show that there might exist a deceptive winning strategy for P1 that ensures
P1's objective is achieved with probability one from a state otherwise losing
for P1, had the information being symmetric and complete. We present three key
results: First, we introduce a dynamic hypergame model to capture the
reachability game with evolving misperception of P2. Second, we present a
fixed-point algorithm to compute the Deceptive Almost-Sure Winning (DASW)
region and DASW strategy. Finally, we show that DASW strategy is at least as
powerful as Almost-Sure Winning (ASW) strategy in the game in which P1 does not
account for P2's misperception. We illustrate our algorithm using a robot
motion planning in an adversarial environment.
