RUNTIME VERIFICATION AND PREDICTIVE SAFETY SHIELDS FOR AUTONOMOUS AGENTS: A GRIDWORLD SIMULATION STUDY

Gaurav Chaulagain; Medhavee Upadhyaya

doi:10.31149/ijhcs.v3i3.5851

Authors

Gaurav Chaulagain Department of Electrical and Computer Engineering, San Francisco Bay University
Medhavee Upadhyaya Department of Electrical and Computer Engineering, San Francisco Bay University

Vol. 3 No. 3 (2021): IJHCS

Articles

May 2, 2021

Downloads

View Article

Abstract
How to Cite
Metrics
References
License

Autonomous agents perform in variable conditions where acquired or heuristic decision-making procedures could engage in actions that contradict safety guidelines. While safety shields can react before a potentially harmful action is executed, runtime verification finds differences from formal requirements. However, when these factors are combined, it leads to a trade-off between safety and utility due to inaccurate observations, unclear barrier dynamics, and limited time for decision-making. Modules such as a three-valued temporal monitor, a finite-horizon action risk filter, a minimum-modeled-risk contingency plan, and an observation-focused probabilistic motion prediction system are presented in this paper as Runtime Verification with Predictive Shielding (RV-PS). In a controlled setting, there are 240 navigational realms evaluated at four levels of sensor mislocalization; in five simplified controllers, there are 960 shared environments and 4,800 paired policy implementations. In comparison to the unshielded control (24.17%) and traditional predictive shielding (16.98%), the proposed RV-PS shows an average collision-episode rate of 2.08% across several scenarios at a three-step interval and a modeled-risk threshold of 0.075. As an example of the consequences of being too careful, its mean task completion rate is 71.35%, which is lower than the conventional shield's 82.50%. Completion rates are increased from 73.75% to 88.75% with a relaxed threshold of 0.20 and collision rates are raised from 2.92% to 4.17% when there is 25% sensor noise. Ablations expose vulnerabilities that can be addressed through anticipatory actions, dealing with uncertainty, and choosing backup plans. Under any given sensor-noise scenario, all policy variants use the identical generated obstacle pathways. In addition to a thorough analysis of safety, efficacy, and any remaining shortcomings, the research offers concrete evidence at the level of specifications.

Gaurav Chaulagain, & Medhavee Upadhyaya. (2021). RUNTIME VERIFICATION AND PREDICTIVE SAFETY SHIELDS FOR AUTONOMOUS AGENTS: A GRIDWORLD SIMULATION STUDY. International Journal on Human-Computing Studies, 3(3), 55–70. https://doi.org/10.31149/ijhcs.v3i3.5851

Download Citation

C. Sánchez et al., “A survey of challenges for runtime verification from advanced application domains (beyond software),” Formal Methods in System Design, vol. 54, pp. 279–335, 2019. https://doi.org/10.1007/s10703-019-00337-w

G. Avni, R. Bloem, K. Chatterjee, T. A. Henzinger, B. Könighofer, and S. Pranger, “Run-Time Optimization for Learned Controllers Through Quantitative Games,” in Computer Aided Verification (CAV), LNCS 11561, pp. 630–649, 2019. https://doi.org/10.1007/978-3-030-25540-4_36

S. Bharadwaj, R. Bloem, R. Dimitrova, B. Könighofer, and U. Topcu, “Synthesis of Minimum-Cost Shields for Multi-agent Systems,” in American Control Conference, pp. 1048–1055, 2019. https://doi.org/10.23919/ACC.2019.8815233

N. Jansen, B. Könighofer, S. Junges, A. Serban, and R. Bloem, “Safe Reinforcement Learning Using Probabilistic Shields,” in CONCUR, LIPIcs 171, pp. 3:1–3:16, 2020. https://doi.org/10.4230/LIPIcs.CONCUR.2020.3

B. Könighofer, F. Lorber, N. Jansen, and R. Bloem, “Shield Synthesis for Reinforcement Learning,” in ISoLA, LNCS 12476, pp. 290–306, 2020. https://doi.org/10.1007/978-3-030-61362-4_16

R. Cheng, G. Orosz, R. M. Murray, and J. W. Burdick, “End-to-End Safe Reinforcement Learning through Barrier Functions for Safety-Critical Continuous Control Tasks,” in AAAI, vol. 33, pp. 3387–3395, 2019. https://doi.org/10.1609/aaai.v33i01.33013387

J. F. Fisac, A. K. Akametalu, M. N. Zeilinger, S. Kaynama, J. Gillula, and C. J. Tomlin, “A General Safety Framework for Learning-Based Control in Uncertain Robotic Systems,” IEEE Transactions on Automatic Control, vol. 64, no. 7, pp. 2737–2752, 2019. https://doi.org/10.1109/TAC.2018.2876389

J. Choi, F. Castañeda, C. J. Tomlin, and K. Sreenath, “Reinforcement Learning for Safety-Critical Control under Model Uncertainty, using Control Lyapunov Functions and Control Barrier Functions,” in Robotics: Science and Systems, 2020. https://roboticsconference.org/2020/program/papers/88.html

A. Taylor, A. Singletary, Y. Yue, and A. Ames, “Learning for Safety-Critical Control with Control Barrier Functions,” in Learning for Dynamics and Control, PMLR 120, pp. 708–717, 2020. https://proceedings.mlr.press/v120/taylor20a.html

A. Stooke, J. Achiam, and P. Abbeel, “Responsive Safety in Reinforcement Learning by PID Lagrangian Methods,” in ICML, PMLR 119, pp. 9133–9143, 2020. https://proceedings.mlr.press/v119/stooke20a.html

A. Wachi and Y. Sui, “Safe Reinforcement Learning in Constrained Markov Decision Processes,” in ICML, PMLR 119, pp. 9797–9806, 2020. https://proceedings.mlr.press/v119/wachi20a.html

T.-Y. Yang, J. Rosca, K. Narasimhan, and P. J. Ramadge, “Projection-Based Constrained Policy Optimization,” in ICLR, 2020. https://mlanthology.org/iclr/2020/yang2020iclr-projectionbased/

C. Tessler, D. J. Mankowitz, and S. Mannor, “Reward Constrained Policy Optimization,” in ICLR, 2019. https://mlanthology.org/iclr/2019/tessler2019iclr-reward/

A. Ray, J. Achiam, and D. Amodei, “Benchmarking Safe Exploration in Deep Reinforcement Learning,” arXiv preprint, 2019. https://openai.com/index/benchmarking-safe-exploration-in-deep-reinforcement-learning/

T. Dreossi, D. J. Fremont, S. Ghosh, E. Kim, H. Ravanbakhsh, M. Vazquez-Chanlatte, and S. A. Seshia, “VerifAI: A Toolkit for the Formal Design and Analysis of Artificial Intelligence-Based Systems,” in CAV, LNCS 11561, pp. 432–442, 2019. https://doi.org/10.1007/978-3-030-25540-4_25

S. Riedmaier, T. Ponn, D. Ludwig, B. Schick, and F. Diermeyer, “Survey on Scenario-Based Safety Assessment of Automated Vehicles,” IEEE Access, vol. 8, pp. 87456–87477, 2020. https://doi.org/10.1109/ACCESS.2020.2993730

E. Yurtsever, J. Lambert, A. Carballo, and K. Takeda, “A Survey of Autonomous Driving: Common Practices and Emerging Technologies,” IEEE Access, vol. 8, pp. 58443–58469, 2020. https://doi.org/10.1109/ACCESS.2020.2983149

H.-D. Tran, X. Yang, D. M. Lopez, P. Musau, L. V. Nguyen, W. Xiang, S. Bak, and T. T. Johnson, “NNV: The Neural Network Verification Tool for Deep Neural Networks and Learning-Enabled Cyber-Physical Systems,” in CAV, LNCS 12224, pp. 3–17, 2020. https://doi.org/10.1007/978-3-030-53288-8_1

G. Katz et al., “The Marabou Framework for Verification and Analysis of Deep Neural Networks,” in CAV, LNCS 11561, pp. 443–452, 2019. https://doi.org/10.1007/978-3-030-25540-4_26

R. Ivanov, J. Weimer, R. Alur, G. J. Pappas, and I. Lee, “Verisig: Verifying Safety Properties of Hybrid Systems with Neural Network Controllers,” in HSCC, pp. 169–178, 2019. https://doi.org/10.1145/3302504.3311806

L. Hewing, K. P. Wabersich, M. Menner, and M. N. Zeilinger, “Learning-Based Model Predictive Control: Toward Safe Learning in Control,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 3, pp. 269–296, 2020. https://doi.org/10.1146/annurev-control-090419-075625

L. Hewing, J. Kabzan, and M. N. Zeilinger, “Cautious Model Predictive Control Using Gaussian Process Regression,” IEEE Transactions on Control Systems Technology, vol. 28, no. 6, pp. 2736–2743, 2020. https://doi.org/10.1109/TCST.2019.2949757

M. Turchetta, A. Kolobov, S. Shah, A. Krause, and A. Agarwal, “Safe Reinforcement Learning via Curriculum Induction,” in Advances in Neural Information Processing Systems, vol. 33, 2020. https://papers.neurips.cc/paper_files/paper/2020/hash/8df6a65941e4c9da40a4fb899de65c55-Abstract.html

H. Krasowski, X. Wang, and M. Althoff, “Safe Reinforcement Learning for Autonomous Lane Changing Using Set-Based Prediction,” in IEEE Intelligent Transportation Systems Conference (ITSC), 2020. https://doi.org/10.1109/ITSC45102.2020.9294259

S. Gros, M. Zanon, and A. Bemporad, “Safe Reinforcement Learning via Projection on a Safe Set: How to Achieve Optimality?” IFAC-PapersOnLine, vol. 53, no. 2, pp. 8076–8081, 2020. https://doi.org/10.1016/j.ifacol.2020.12.2276

Y. Liu, J. Ding, and X. Liu, “IPO: Interior-Point Policy Optimization under Constraints,” in AAAI, vol. 34, no. 4, pp. 4940–4947, 2020. https://doi.org/10.1609/aaai.v34i04.5932

Y. Zhang, Q. Vuong, and K. W. Ross, “First Order Constrained Optimization in Policy Space,” in Advances in Neural Information Processing Systems, vol. 33, 2020. https://proceedings.neurips.cc/paper/2020/file/af5d5ef24881f3c3049a7b9bfe74d58b-Paper.pdf

S. Dean, S. Tu, N. Matni, and B. Recht, “Safely Learning to Control the Constrained Linear Quadratic Regulator,” in American Control Conference, pp. 5582–5588, 2019. https://doi.org/10.23919/ACC.2019.8814865

T. Koller, F. Berkenkamp, M. Turchetta, J. Boedecker, and A. Krause, “Learning-based Model Predictive Control for Safe Exploration and Reinforcement Learning,” arXiv preprint arXiv:1906.12189, 2019. https://arxiv.org/abs/1906.12189

S. Grigorescu, B. Trasnea, T. Cocias, and G. Macesanu, “A Survey of Deep Learning Techniques for Autonomous Driving,” Journal of Field Robotics, vol. 37, no. 3, pp. 362–386, 2020. https://doi.org/10.1002/rob.21918

V. Tjeng, K. Y. Xiao, and R. Tedrake, “Evaluating Robustness of Neural Networks with Mixed Integer Programming,” in ICLR, 2019. https://dblp.org/rec/conf/iclr/TjengXT19.html

R. Toro Icarte, T. Q. Klassen, R. Valenzano, and S. A. McIlraith, “Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning,” arXiv preprint arXiv:2010.03950, 2020. https://arxiv.org/abs/2010.03950