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 -