2016/03/22 by Ehlers, Ruediger, Salar Moarref, Ufuk Topcu +2
Computer Science · #FOS: Computer and information sciences #FOS: Electrical engineering #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Petri Nets in System Modeling #Real-Time Systems Scheduling #Robotics (cs.RO) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1603.06716
openalex publication_date 2016/03/22 · openalex created_date 2022/09/03 · openalex updated_date 2026/08/01
Many control problems in environments that can be modeled as Markov decision\nprocesses (MDPs) concern infinite-time horizon specifications. The classical\naim in this context is to compute a control policy that maximizes the\nprobability of satisfying the specification. In many scenarios, there is\nhowever a non-zero probability of failure in every step of the system's\nexecution. For infinite-time horizon specifications, this implies that the\nspecification is violated with probability 1 in the long run no matter what\npolicy is chosen, which prevents previous policy computation methods from being\nuseful in these scenarios.\n In this paper, we introduce a new optimization criterion for MDP policies\nthat captures the task of working towards the satisfaction of some\ninfinite-time horizon \ω-regular specification. The new criterion is\napplicable to MDPs in which the violation of the specification cannot be\navoided in the long run. We give an algorithm to compute policies that are\noptimal in this criterion and show that it captures the ideas of optimism and\nrisk-averseness in MDP control: while the computed policies are optimistic in\nthat a MDP run enters a failure state relatively late, they are risk-averse by\nalways maximizing the probability to reach their respective next goal state. We\ngive results on two robot control scenarios to validate the usability of\nrisk-averse MDP policies.\n