TY - GEN

T1 - Measuring Target Predictability for Optimal Environment Design

AU - Ornik, Melkior

N1 - Publisher Copyright:
© 2020 IEEE.

PY - 2020/12/14

Y1 - 2020/12/14

N2 - Motivated by the study of deceptive strategies, this paper considers the problems of detecting an agent's objective from its partial path and determining an optimal environment to enable such detection. We focus on a scenario where the agent's objective is to reach a particular target state from a set of potential targets, while an observer seeks to correctly identify such a state prior to the agent reaching it. In order to quantify the predictability of the agent's target given the observed path, we introduce the notion of target entropy, where higher entropy implies lower target predictability. The problem of optimal environment design, i.e., optimal target placement, then becomes a minimax problem with target entropy as an objective function. Under the assumption that the agent chooses its path towards its target maximally unpredictably, we consider models of the agent's motion on both discrete and continuous state spaces. Using dynamic programming, we establish a simple way of computing target entropy for the discrete state space. In a continuous state space, we obtain a formula for target entropy by employing geometrical arguments on volumes of hypersimplices. Additionally, we provide an algorithm yielding an optimal environment in a discrete state space, discuss its computational complexity, and provide a computationally simpler approximation that yields a locally optimal environment. We validate our results on a previously developed model of deceptive agent motion.

AB - Motivated by the study of deceptive strategies, this paper considers the problems of detecting an agent's objective from its partial path and determining an optimal environment to enable such detection. We focus on a scenario where the agent's objective is to reach a particular target state from a set of potential targets, while an observer seeks to correctly identify such a state prior to the agent reaching it. In order to quantify the predictability of the agent's target given the observed path, we introduce the notion of target entropy, where higher entropy implies lower target predictability. The problem of optimal environment design, i.e., optimal target placement, then becomes a minimax problem with target entropy as an objective function. Under the assumption that the agent chooses its path towards its target maximally unpredictably, we consider models of the agent's motion on both discrete and continuous state spaces. Using dynamic programming, we establish a simple way of computing target entropy for the discrete state space. In a continuous state space, we obtain a formula for target entropy by employing geometrical arguments on volumes of hypersimplices. Additionally, we provide an algorithm yielding an optimal environment in a discrete state space, discuss its computational complexity, and provide a computationally simpler approximation that yields a locally optimal environment. We validate our results on a previously developed model of deceptive agent motion.

UR - http://www.scopus.com/inward/record.url?scp=85099886487&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85099886487&partnerID=8YFLogxK

U2 - 10.1109/CDC42340.2020.9304082

DO - 10.1109/CDC42340.2020.9304082

M3 - Conference contribution

AN - SCOPUS:85099886487

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 5023

EP - 5028

BT - 2020 59th IEEE Conference on Decision and Control, CDC 2020

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 59th IEEE Conference on Decision and Control, CDC 2020

Y2 - 14 December 2020 through 18 December 2020

ER -