Department of Mathematics and Statistics

Department of Mathematics and Statistics
Department of Mathematics and Statistics

Control Theory Seminar


Friday, May 17th, 2019

Time: 10:30 a.m Place: Jeffery 110

Speaker: Prof. Melkior Ornik (University of Illinois at Urbana-Champaign)

Title: Deception and Unpredictability in Stochastic Control

Abstract: In a number of adversarial scenarios, the success of an agent at achieving its objective rests on its use of a deceptive strategy: a strategy that enables the agent to progress towards its objective while manipulating the beliefs of the agent’s adversary about the nature of the agent. For instance, the agent may wish to instill incorrect beliefs about its location, identity, or objective, or it may simply wish to act seemingly unpredictably while still progressing towards its objective. In this talk, I will outline recent work on formalizing the notions of deception and unpredictability within the setting of Markov decision processes. I will begin by describing a basic approach that encodes deception through introducing a belief space for an adversary and a belief-induced reward objective, thus expressing deceptive strategies as control policies on a product state space. I will then discuss notions of unpredictability, deception, and counter-deception in scenarios with a temporal logic objective. I will relate unpredictability of an agent to the total Shannon entropy of its paths, and show that maximal unpredictability is achieved by following a policy that results in maximal total entropy of the induced Markov chain. Finally, I will express the notion of deception for temporal logic objectives using Kullback-Leibler divergence and show that optimal deceptive (for the agent) and counter-deceptive (for the adversary) policies can be synthesized as solutions of a convex optimization problem and a non-convex min-max problem, respectively. I will conclude with a brief discussion of open problems in the area of deceptive planning.