  In this work, we study a class of deception planning problems in which an
agent aims to alter a security monitoring system's sensor readings so as to
disguise its adversarial itinerary as an allowed itinerary in the environment.
The adversarial itinerary set and allowed itinerary set are captured by regular
languages. To deviate without being detected, we investigate whether there
exists a strategy for the agent to alter the sensor readings, with a minimal
cost, such that for any of those paths it takes, the system thinks the agent
took a path within the allowed itinerary. Our formulation assumes an offline
sensor alteration where the agent determines the sensor alteration strategy and
implement it, and then carry out any path in its deviation itinerary. We prove
that the problem of solving the optimal sensor alteration is NP-hard, by a
reduction from the directed multi-cut problem. Further, we present an exact
algorithm based on integer linear programming and demonstrate the correctness
and the efficacy of the algorithm in case studies.
