Counter-example Guided Learning of Bounds on Environment Behavior

Yuxiao Chen, Sumanth Dathathri, Tung Phan-Minh, Richard M. Murray
Proceedings of the Conference on Robot Learning, PMLR 100:898-909, 2020.

Abstract

There is a growing interest in building autonomous systems that interact with complex environments. The difficulty associated with obtaining an accurate model for such environments poses a challenge to the task of assessing and guaranteeing the system’s performance. We present a data-driven solution that allows for a system to be evaluated for specification conformance without an accurate model of the environment. Our approach involves learning a conservative reactive bound of the environment’s behavior using data and specification of the system’s desired behavior. First, the approach begins by learning a conservative reactive bound on the environment’s actions that captures its possible behaviors with high probability. This bound is then used to assist verification, and if the verification fails under this bound, the algorithm returns counter-examples to show how failure occurs and then uses these to refine the bound. We demonstrate the applicability of the approach through two case-studies: i) verifying controllers for a toy multi-robot system, and ii) verifying an instance of human-robot interaction during a lane-change maneuver given real-world human driving data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v100-chen20b, title = {Counter-example Guided Learning of Bounds on Environment Behavior}, author = {Chen, Yuxiao and Dathathri, Sumanth and Phan-Minh, Tung and Murray, Richard M.}, booktitle = {Proceedings of the Conference on Robot Learning}, pages = {898--909}, year = {2020}, editor = {Kaelbling, Leslie Pack and Kragic, Danica and Sugiura, Komei}, volume = {100}, series = {Proceedings of Machine Learning Research}, month = {30 Oct--01 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v100/chen20b/chen20b.pdf}, url = {https://proceedings.mlr.press/v100/chen20b.html}, abstract = {There is a growing interest in building autonomous systems that interact with complex environments. The difficulty associated with obtaining an accurate model for such environments poses a challenge to the task of assessing and guaranteeing the system’s performance. We present a data-driven solution that allows for a system to be evaluated for specification conformance without an accurate model of the environment. Our approach involves learning a conservative reactive bound of the environment’s behavior using data and specification of the system’s desired behavior. First, the approach begins by learning a conservative reactive bound on the environment’s actions that captures its possible behaviors with high probability. This bound is then used to assist verification, and if the verification fails under this bound, the algorithm returns counter-examples to show how failure occurs and then uses these to refine the bound. We demonstrate the applicability of the approach through two case-studies: i) verifying controllers for a toy multi-robot system, and ii) verifying an instance of human-robot interaction during a lane-change maneuver given real-world human driving data.} }
Endnote
%0 Conference Paper %T Counter-example Guided Learning of Bounds on Environment Behavior %A Yuxiao Chen %A Sumanth Dathathri %A Tung Phan-Minh %A Richard M. Murray %B Proceedings of the Conference on Robot Learning %C Proceedings of Machine Learning Research %D 2020 %E Leslie Pack Kaelbling %E Danica Kragic %E Komei Sugiura %F pmlr-v100-chen20b %I PMLR %P 898--909 %U https://proceedings.mlr.press/v100/chen20b.html %V 100 %X There is a growing interest in building autonomous systems that interact with complex environments. The difficulty associated with obtaining an accurate model for such environments poses a challenge to the task of assessing and guaranteeing the system’s performance. We present a data-driven solution that allows for a system to be evaluated for specification conformance without an accurate model of the environment. Our approach involves learning a conservative reactive bound of the environment’s behavior using data and specification of the system’s desired behavior. First, the approach begins by learning a conservative reactive bound on the environment’s actions that captures its possible behaviors with high probability. This bound is then used to assist verification, and if the verification fails under this bound, the algorithm returns counter-examples to show how failure occurs and then uses these to refine the bound. We demonstrate the applicability of the approach through two case-studies: i) verifying controllers for a toy multi-robot system, and ii) verifying an instance of human-robot interaction during a lane-change maneuver given real-world human driving data.
APA
Chen, Y., Dathathri, S., Phan-Minh, T. & Murray, R.M.. (2020). Counter-example Guided Learning of Bounds on Environment Behavior. Proceedings of the Conference on Robot Learning, in Proceedings of Machine Learning Research 100:898-909 Available from https://proceedings.mlr.press/v100/chen20b.html.

Related Material