* Cohen et al. (2018) Daniel Cohen, Liu Yang, and W Bruce Croft. 2018.  WikiPassageQA: A benchmark collection for research on non-factoid answer passage retrieval. In _The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval_. 1165–1168.
  * Curto et al. (2014) Sérgio Curto, Ana Cristina Mendes, Pedro Curto, Luísa Coheur, and Ângela Costa. 2014.  JUST.ASK, a QA system that learns to answer new questions from previous interactions. In _LREC_. European Language Resources Association (ELRA), 2603–2607.
  * Damljanovic et al. (2010) Danica Damljanovic, Milan Agatonovic, and Hamish Cunningham. 2010\.  Natural Language Interfaces to Ontologies: Combining Syntactic Analysis and Ontology-Based Lookup through the User Interaction. In _ESWC (1)_ _(Lecture Notes in Computer Science, Vol. 6088)_. Springer, 106–120.
  * Das et al. (2019) Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, and Andrew McCallum. 2019.  Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering. In _ICLR (Poster)_. OpenReview.net.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ (2018).
  * Dhingra et al. (2017) Bhuwan Dhingra, Kathryn Mazaitis, and William W Cohen. 2017\.  Quasar: Datasets for question answering by search and reading.  _arXiv preprint arXiv:1707.03904_ (2017).
  * Do et al. (2019) Tuong Do, Huy Tran, Thanh-Toan Do, Erman Tjiputra, and Quang D. Tran. 2019.  Compact Trilinear Interaction for Visual Question Answering. In _ICCV_. IEEE, 392–401.
  * Dunn et al. (2017) Matthew Dunn, Levent Sagun, Mike Higgins, V Ugur Guney, Volkan Cirik, and Kyunghyun Cho. 2017\.  Searchqa: A new q&a dataset augmented with context from a search engine.  _arXiv preprint arXiv:1704.05179_ (2017).
  * Etzioni (2011) Oren Etzioni. 2011\.  Search needs a shake-up.  _Nat._ 476, 7358 (2011), 25–26.
  * Fagin et al. (2003) Ronald Fagin, Amnon Lotem, and Moni Naor. 2003.  Optimal aggregation algorithms for middleware.  _Journal of computer and system sciences_ 66, 4 (2003), 614–656.
  * Feng et al. (2015) Minwei Feng, Bing Xiang, Michael R Glass, Lidan Wang, and Bowen Zhou. 2015.  Applying deep learning to answer selection: A study and an open task. In _2015 IEEE Workshop on Automatic Speech Recognition and Understanding (ASRU)_. 813–820.
  * Ferrández and Peral (2010) Antonio Ferrández and Jesús Peral. 2010.  The benefits of the interaction between data warehouses and question answering. In _EDBT/ICDT Workshops_ _(ACM International Conference Proceeding Series)_. ACM.
  * Fukumoto et al. (2013) Jun-ichi Fukumoto, Noriaki Aburai, and Ryosuke Yamanishi. 2013\.  Interactive Document Expansion for Answer Extraction of Question Answering System. In _KES_ _(Procedia Computer Science, Vol. 22)_. Elsevier, 991–1000.
  * Gao et al. (2019) Peng Gao, Haoxuan You, Zhanpeng Zhang, Xiaogang Wang, and Hongsheng Li. 2019.  Multi-Modality Latent Interaction Network for Visual Question Answering. In _ICCV_. IEEE, 5824–5834.
  * Gordon et al. (2018) Daniel Gordon, Aniruddha Kembhavi, Mohammad Rastegari, Joseph Redmon, Dieter Fox, and Ali Farhadi. 2018\.  IQA: Visual Question Answering in Interactive Environments. In _CVPR_. Computer Vision Foundation / IEEE Computer Society, 4089–4098.
  * Goyal et al. (2017) Yash Goyal, Tejas Khot, Douglas Summers-Stay, Dhruv Batra, and Devi Parikh. 2017.  Making the v in vqa matter: Elevating the role of image understanding in visual question answering. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 6904–6913.
  * Guo et al. (2018) Daya Guo, Duyu Tang, Nan Duan, Ming Zhou, and Jian Yin. 2018.  Dialog-to-Action: Conversational Question Answering Over a Large-Scale Knowledge Base. In _NeurIPS 2018_. 2946–2955.
  * Habibi et al. (2016) Maryam Habibi, Parvaz Mahdabi, and Andrei Popescu-Belis. 2016\.  Question answering in conversations: Query refinement using contextual and semantic information.  _Data Knowl. Eng._ 106 (2016), 38–51.
  * Han et al. (2019) Hojae Han, Seungtaek Choi, Haeju Park, and Seung-won Hwang. 2019.  MICRON: Multigranular Interaction for Contextualizing RepresentatiON in Non-factoid Question Answering. In _EMNLP/IJCNLP (1)_. Association for Computational Linguistics, 5889–5894.
  * Hazrina et al. (2017) Sofian Hazrina, Nurfadhlina Mohd Sharef, Hamidah Ibrahim, Masrah Azrifah Azmi Murad, and Shahrul Azman Mohd. Noah. 2017.  Review on the advancements of disambiguation in semantic question answering system.  _Inf. Process. Manag._ 53, 1 (2017), 52–69.
  * He et al. (2019) Shizhu He, Kang Liu, and Weiting An. 2019.  Learning to Align Question and Answer Utterances in Customer Service Conversation with Recurrent Pointer Networks. In _AAAI_. AAAI Press, 134–141.
  * Hirschman and Gaizauskas (2001) Lynette Hirschman and Robert J. Gaizauskas. 2001.  Natural language question answering: the view from here.  _Nat. Lang. Eng._ 7, 4 (2001), 275–300.
  * Hong et al. (2019) Yining Hong, Jialu Wang, Yuting Jia, Weinan Zhang, and Xinbing Wang. 2019.  Academic Reader: An Interactive Question Answering System on Academic Literatures. In _AAAI_. AAAI Press, 9855–9856.
  * Hu et al. (2018) Jun Hu, Shengsheng Qian, Quan Fang, and Changsheng Xu. 2018\.  Attentive Interactive Convolutional Matching for Community Question Answering in Social Multimedia. In _ACM Multimedia_. ACM, 456–464.
  * Huang et al. (2018) Hsin-Yuan Huang, Eunsol Choi, and Wen-tau Yih. 2018.  Flowqa: Grasping flow in history for conversational machine comprehension.  _arXiv preprint arXiv:1810.06683_ (2018).
  * Hulburd (2020) Eric Hulburd. 2020\.  Exploring BERT Parameter Efficiency on the Stanford Question Answering Dataset v2.0.  _CoRR_ abs/2002.10670 (2020).
  * Jang et al. (2017) Yunseok Jang, Yale Song, Youngjae Yu, Youngjin Kim, and Gunhee Kim. 2017.  TGIF-QA: Toward Spatio-Temporal Reasoning in Visual Question Answering. In _CVPR_. IEEE Computer Society, 1359–1367.
  * Jin et al. (2019) Weike Jin, Zhou Zhao, Mao Gu, Jun Yu, Jun Xiao, and Yueting Zhuang. 2019\.  Multi-interaction Network with Object Relation for Video Question Answering. In _ACM Multimedia_. ACM, 1193–1201.
  * Joshi et al. (2017) Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. 2017.  Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension.  _arXiv preprint arXiv:1705.03551_ (2017).
  * Ju et al. (2019) Ying Ju, Fubang Zhao, Shijie Chen, Bowen Zheng, Xuefeng Yang, and Yunfeng Liu. 2019\.  Technical report on Conversational Question Answering.  _CoRR_ abs/1909.10772 (2019).
  * Kafle and Kanan (2017) Kushal Kafle and Christopher Kanan. 2017.  An analysis of visual question answering algorithms. In _Proceedings of the IEEE International Conference on Computer Vision_. 1965–1973.
  * Kaiser et al. (2020) Magdalena Kaiser, Rishiraj Saha Roy, and Gerhard Weikum. 2020\.  Conversational Question Answering over Passages by Leveraging Word Proximity Networks. In _SIGIR_. ACM, 2129–2132.
  * Khot et al. (2020) Tushar Khot, Peter Clark, Michal Guerquin, Peter Jansen, and Ashish Sabharwal. 2020.  Qasc: A dataset for question answering via sentence composition. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 8082–8090.
  * Kim et al. (2017) Kyung-Min Kim, Min-Oh Heo, Seong-Ho Choi, and Byoung-Tak Zhang. 2017.  Deepstory: Video story qa by deep embedded memory networks.  _arXiv preprint arXiv:1707.00836_ (2017).
  * Konstantinova and Orasan (2013) Natalia Konstantinova and Constantin Orasan. 2013.  Interactive question answering.  In _Emerging applications of natural language processing: concepts and new research_. IGI Global, 149–169.
  * Krishna et al. (2017) Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, et al. 2017\.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  _International journal of computer vision_ 123, 1 (2017), 32–73.
  * Kulkarni and Boyer (2018) Mayank Kulkarni and Kristy Elizabeth Boyer. 2018.  Toward Data-Driven Tutorial Question Answering with Deep Learning Conversational Models. In _BEA@NAACL-HLT_. Association for Computational Linguistics, 273–283.
  * Kumar et al. (2018) Girish Kumar, Matthew Henderson, Shannon Chan, Hoang Nguyen, and Lucas Ngoo. 2018.  Question-Answer Selection in User to User Marketplace Conversations. In _IWSDS_ _(Lecture Notes in Electrical Engineering, Vol. 579)_. Springer, 397–403.
  * Kundu et al. (2020) Souvik Kundu, Qian Lin, and Hwee Tou Ng. 2020.  Learning to Identify Follow-Up Questions in Conversational Question Answering. In _ACL_. Association for Computational Linguistics, 959–968.
  * Kuo et al. (2020) Chia-Chih Kuo, Shang-Bao Luo, and Kuan-Yu Chen. 2020\.  An Audio-Enriched BERT-Based Framework for Spoken Multiple-Choice Question Answering. In _INTERSPEECH_. ISCA, 4173–4177.
  * Latcinnik and Berant (2020) Veronica Latcinnik and Jonathan Berant. 2020.  Explaining Question Answering Models through Text Generation.  _CoRR_ abs/2004.05569 (2020).
  * Lee et al. (2019) Changyoon Lee, Donghoon Han, Hyoungwook Jin, and Alice Oh. 2019\.  automaTA: Human-Machine Interaction for Answering Context-Specific Questions. In _L@S_. ACM, 44:1–44:4.
  * Lei et al. (2018) Jie Lei, Licheng Yu, Mohit Bansal, and Tamara L Berg. 2018\.  Tvqa: Localized, compositional video question answering.  _arXiv preprint arXiv:1809.01696_ (2018).
  * Li and Jagadish (2014) Fei Li and H. V. Jagadish. 2014.  Constructing an Interactive Natural Language Interface for Relational Databases.  _Proc. VLDB Endow._ 8, 1 (2014), 73–84.
  * Li et al. (2017) Huayu Li, Martin Renqiang Min, Yong Ge, and Asim Kadav. 2017\.  A Context-aware Attention Network for Interactive Question Answering. In _KDD_. ACM, 927–935.
  * Li et al. (2018a) Qing Li, Jianlong Fu, Dongfei Yu, Tao Mei, and Jiebo Luo. 2018a.  Tell-and-Answer: Towards Explainable Visual Question Answering using Attributes and Captions. In _EMNLP_. Association for Computational Linguistics, 1338–1346.
  * Li et al. (2019) Qian Li, Hui Su, Cheng Niu, Daling Wang, Zekang Li, Shi Feng, and Yifei Zhang. 2019.  Answer-Supervised Question Reformulation for Enhancing Conversational Machine Comprehension. In _MRQA@EMNLP_. Association for Computational Linguistics, 38–47.
  * Li et al. (2018b) Qing Li, Qingyi Tao, Shafiq R. Joty, Jianfei Cai, and Jiebo Luo. 2018b.  VQA-E: Explaining, Elaborating, and Enhancing Your Answers for Visual Questions. In _ECCV (7)_ _(Lecture Notes in Computer Science, Vol. 11211)_. Springer, 570–586.
  * Li et al. (2020) Ronghan Li, Zejun Jiang, Lifang Wang, Xinyu Lu, and Meng Zhao. 2020.  Directional attention weaving for text-grounded conversational question answering.  _Neurocomputing_ 391 (2020), 13–24.
  * Li et al. (2016) Yuncheng Li, Yale Song, Liangliang Cao, Joel R. Tetreault, Larry Goldberg, Alejandro Jaimes, and Jiebo Luo. 2016.  TGIF: A New Dataset and Benchmark on Animated GIF Description. In _CVPR_. IEEE Computer Society, 4641–4650.
  * Liu et al. (2019) Aiting Liu, Ziqi Huang, Hengtong Lu, Xiaojie Wang, and Caixia Yuan. 2019.  BB-KBQA: BERT-Based Knowledge Base Question Answering. In _CCL_ _(Lecture Notes in Computer Science, Vol. 11856)_. Springer, 81–92.
  * Liu et al. (2018) Siyuan Liu, Sourav S. Bhowmick, Wanlu Zhang, Shu Wang, and Wanyi Huang. 2018.  NEURON: An Interactive Natural Language Interface for Understanding Query Execution Plans in RDBMS.  _CoRR_ abs/1805.05670 (2018).
  * Liu et al. (2013) Song Liu, Yixin Zhong, and Fuji Ren. 2013.  Interactive Question Answering Based on FAQ. In _CCL_ _(Lecture Notes in Computer Science, Vol. 8202)_. Springer, 73–84.
  * Lockett et al. (2019) James Lockett, Sanith Wijesinghe, Jasper Phillips, Ian Gross, Michael Schoenfeld, Walter T. Hiranpat, Phillip J. Marlow, Matt Coarr, and Qian Hu. 2019.  Intelligent Voice Agent and Service (iVAS) for Interactive and Multimodal Question and Answers. In _FQAS_ _(Lecture Notes in Computer Science, Vol. 11529)_. Springer, 396–402.
  * Lopez et al. (2013) Vanessa Lopez, Christina Unger, Philipp Cimiano, and Enrico Motta. 2013.  Evaluating question answering over linked data.  _Journal of Web Semantics_ 21 (2013), 3–13.
  * Maarek (2018) Yoelle Maarek. 2018\.  Alexa and Her Shopping Journey. In _CIKM_. ACM, 1\.
  * Maitra et al. (2020) Anutosh Maitra, Shivam Garg, and Shubhashis Sengupta. 2020\.  Enabling Interactive Answering of Procedural Questions. In _NLDB_ _(Lecture Notes in Computer Science, Vol. 12089)_. Springer, 73–81.
  * Mandya et al. (2019) Angrosh Mandya, Danushka Bollegala, and Frans Coenen. 2019\.  Evaluating Co-reference Chains Based Conversation History in Conversational Question Answering. In _PACLING_ _(Communications in Computer and Information Science, Vol. 1215)_. Springer, 280–292.
  * Mandya et al. (2020) Angrosh Mandya, James O’Neill, Danushka Bollegala, and Frans Coenen. 2020.  Do not let the history haunt you: Mitigating Compounding Errors in Conversational Question Answering. In _LREC_. European Language Resources Association, 2017–2025.
  * Mass et al. (2019) Yosi Mass, Haggai Roitman, Shai Erera, Or Rivlin, Bar Weiner, and David Konopnicki. 2019\.  A Study of BERT for Non-Factoid Question-Answering under Passage Length Constraints.  _CoRR_ abs/1908.06780 (2019).
  * McCarley (2019) J. S. McCarley. 2019\.  Pruning a BERT-based Question Answering Model.  _CoRR_ abs/1910.06360 (2019).
  * Mendes et al. (2012) Pablo N Mendes, Max Jakob, and Christian Bizer. 2012\.  _DBpedia: A multilingual cross-domain knowledge base_.  European Language Resources Association (ELRA).
  * Mészáros and Dobrowiecki (2017) Tamás Mészáros and Tadeusz P. Dobrowiecki. 2017.  Agent-based Reconfigurable Natural Language Interface to Robots - Human-Agent Interaction using Task-specific Controlled Natural Languages. In _ICAART (2)_. SciTePress, 632–639.
  * Mihaylov et al. (2018) Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. 2018.  Can a suit of armor conduct electricity? a new dataset for open book question answering.  _arXiv preprint arXiv:1809.02789_ (2018).
  * Moon et al. (2019) Seungwhan Moon, Pararth Shah, Anuj Kumar, and Rajen Subba. 2019\.  Memory Graph Networks for Explainable Memory-grounded Question Answering. In _CoNLL_. Association for Computational Linguistics, 728–736.
  * Müller et al. (2019) Thomas Müller, Francesco Piccinno, Peter Shaw, Massimo Nicosia, and Yasemin Altun. 2019\.  Answering Conversational Questions on Structured Data without Logical Forms. In _EMNLP/IJCNLP (1)_. Association for Computational Linguistics, 5901–5909.
  * Naeem et al. (2012) M. Asif Naeem, Saif Ullah, and Imran Sarwar Bajwa. 2012\.  Interacting with Data Warehouse by Using a Natural Language Interface. In _NLDB_ _(Lecture Notes in Computer Science, Vol. 7337)_. Springer, 372–377.
  * Nakov et al. (2019) Preslav Nakov, Lluís Màrquez, Walid Magdy, Alessandro Moschitti, James Glass, and Bilal Randeree. 2019.  Semeval-2015 task 3: Answer selection in community question answering.  _arXiv preprint arXiv:1911.11403_ (2019).
  * Nie et al. (2019) Allen Nie, Erin D. Bennett, and Noah D. Goodman. 2019\.  Learning to Explain: Answering Why-Questions via Rephrasing.  _CoRR_ abs/1906.01243 (2019).
  * Nothdurft and Minker (2016) Florian Nothdurft and Wolfgang Minker. 2016.  Justification and transparency explanations in dialogue systems to maintain human-computer trust.  In _Situated Dialog in Speech-Based Human-Computer Interaction_. Springer, 41–50.
  * Osama et al. (2019) Reham A. Osama, Nagwa M. El-Makky, and Marwan Torki. 2019\.  Question Answering Using Hierarchical Attention on Top of BERT Features. In _MRQA@EMNLP_. Association for Computational Linguistics, 191–195.
  * Otegi et al. (2020) Arantxa Otegi, Aitor Gonzalez-Agirre, Jon Ander Campos, Aitor Soroa, and Eneko Agirre. 2020\.  Conversational Question Answering in Low Resource Scenarios: A Dataset and Case Study for Basque. In _LREC_. European Language Resources Association, 436–442.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a Method for Automatic Evaluation of Machine Translation. In _ACL_. ACL, 311–318.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014.  Glove: Global vectors for word representation. In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_. 1532–1543.
  * Perera and Nand (2014) Rivindu Perera and Parma Nand. 2014.  Interaction History Based Answer Formulation for Question Answering. In _KESW_ _(Communications in Computer and Information Science, Vol. 468)_. Springer, 128–139.
  * Petukhova et al. (2015) Volha Petukhova, Desmond Darma Putra, Alexandr Chernov, and Dietrich Klakow. 2015.  Understanding Questions and Extracting Answers: Interactive Quiz Game Application Design. In _LTC_ _(Lecture Notes in Computer Science, Vol. 10930)_. Springer, 246–261.
  * Pradhan et al. (2018) Akshit Pradhan, Pragya Shukla, Pallavi Patra, Rohit Pathak, and Ajay Kumar Jena. 2018.  Enhancing Interaction with Social Networking Sites for Visually Impaired People by Using Textual and Visual Question Answering. In _CICBA (2)_ _(Communications in Computer and Information Science, Vol. 1031)_. Springer, 3–14.
  * Qi et al. (2019) Zihao Qi, Dario Bertero, Ian D. Wood, and Pascale Fung. 2019\.  Incorporate User Representation for Personal Question Answer Selection Using Siamese Network. In _ICASSP_. IEEE, 7540–7544.
  * Qu et al. (2020) Chen Qu, Liu Yang, Cen Chen, Minghui Qiu, W. Bruce Croft, and Mohit Iyyer. 2020\.  Open-Retrieval Conversational Question Answering. In _SIGIR_. ACM, 539–548.
  * Qu et al. (2019a) Chen Qu, Liu Yang, Minghui Qiu, W. Bruce Croft, Yongfeng Zhang, and Mohit Iyyer. 2019a.  BERT with History Answer Embedding for Conversational Question Answering. In _SIGIR_. ACM, 1133–1136.
  * Qu et al. (2019b) Chen Qu, Liu Yang, Minghui Qiu, Yongfeng Zhang, Cen Chen, W. Bruce Croft, and Mohit Iyyer. 2019b.  Attentive History Selection for Conversational Question Answering. In _CIKM_. ACM, 1391–1400.
  * Rajpurkar et al. (2018) Pranav Rajpurkar, Robin Jia, and Percy Liang. 2018.  Know What You Don’t Know: Unanswerable Questions for SQuAD. In _ACL (2)_. Association for Computational Linguistics, 784–789.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  SQuAD: 100, 000+ Questions for Machine Comprehension of Text. In _EMNLP_. The Association for Computational Linguistics, 2383–2392.
  * Reddy et al. (2019) Siva Reddy, Danqi Chen, and Christopher D. Manning. 2019\.  CoQA: A Conversational Question Answering Challenge.  _Trans. Assoc. Comput. Linguistics_ 7 (2019), 249–266.
  * Ren et al. (2015) Mengye Ren, Ryan Kiros, and Richard S. Zemel. 2015.  Exploring Models and Data for Image Question Answering. In _NIPS_. 2953–2961.
  * Riley and Sridharan (2019) Heather Riley and Mohan Sridharan. 2019.  Integrating Non-monotonic Logical Reasoning and Inductive Learning With Deep Learning for Explainable Visual Question Answering.  _Frontiers Robotics AI_ 6 (2019), 125.
  * Rücklé and Gurevych (2017) Andreas Rücklé and Iryna Gurevych. 2017.  End-to-End Non-Factoid Question Answering with an Interactive Visualization of Neural Attention Weights. In _ACL (System Demonstrations)_. Association for Computational Linguistics, 19–24.
  * Saha et al. (2018) Amrita Saha, Vardaan Pahuja, Mitesh M. Khapra, Karthik Sankaranarayanan, and Sarath Chandar. 2018\.  Complex Sequential Question Answering: Towards Learning to Converse Over Linked Question Answer Pairs with a Knowledge Graph.  _arXiv:1801.10314_ (2018).
  * Sakata et al. (2019) Wataru Sakata, Tomohide Shibata, Ribeka Tanaka, and Sadao Kurohashi. 2019.  FAQ Retrieval using Query-Question Similarity and BERT-Based Query-Answer Relevance. In _SIGIR_. ACM, 1113–1116.
  * Schwarzer et al. (2016) Malte Schwarzer, Jonas Düver, Danuta Ploch, and Andreas Lommatzsch. 2016.  An Interactive e-Government Question Answering System. In _LWDA_ _(CEUR Workshop Proceedings, Vol. 1670)_. CEUR-WS.org, 74–82.
  * Sen et al. (2020) Bhaskar Sen, Nikhil Gopal, and Xinwei Xue. 2020.  Support-BERT: Predicting Quality of Question-Answer Pairs in MSDN using Deep Bidirectional Transformer.  _CoRR_ abs/2005.08294 (2020).
  * Shao et al. (2019) Huan Shao, Yunlong Xu, Yi Ji, Jianyu Yang, and Chunping Liu. 2019.  Intra-Modality Feature Interaction Using Self-attention for Visual Question Answering. In _ICONIP (5)_ _(Communications in Computer and Information Science, Vol. 1143)_. Springer, 215–222.
  * Shen et al. (2019) Tao Shen, Xiubo Geng, Tao Qin, Daya Guo, Duyu Tang, Nan Duan, Guodong Long, and Daxin Jiang. 2019.  Multi-Task Learning for Conversational Question Answering over a Large-Scale Knowledge Base. In _EMNLP-IJCNLP (1)_. Association for Computational Linguistics, 2442–2451.
  * Shi et al. (2020) Lei Shi, Shijie Geng, Kai Shuang, Chiori Hori, Songxiang Liu, Peng Gao, and Sen Su. 2020.  Multi-Layer Content Interaction Through Quaternion Product for Visual Question Answering. In _ICASSP_. IEEE, 4412–4416.
  * Shin et al. (2018) Andrew Shin, Yoshitaka Ushiku, and Tatsuya Harada. 2018\.  Customized Image Narrative Generation via Interactive Visual Question Generation and Answering. In _CVPR_. Computer Vision Foundation / IEEE Computer Society, 8925–8933.
  * Siblini et al. (2019) Wissam Siblini, Charlotte Pasqual, Axel Lavielle, and Cyril Cauchois. 2019.  Multilingual Question Answering from Formatted Text applied to Conversational Agents.  _CoRR_ abs/1910.04659 (2019).
  * Sorokin and Gurevych (2018) Daniil Sorokin and Iryna Gurevych. 2018.  Interactive Instance-based Evaluation of Knowledge Base Question Answering. In _EMNLP (Demonstration)_. Association for Computational Linguistics, 114–119.
  * Su et al. (2019) Lixin Su, Jiafeng Guo, Yixing Fan, Yanyan Lan, Ruqing Zhang, and Xueqi Cheng. 2019\.  An Adaptive Framework for Conversational Question Answering. In _AAAI_. AAAI Press, 10041–10042.
  * Su et al. (2018) Yu Su, Ahmed Hassan Awadallah, Miaosen Wang, and Ryen W. White. 2018.  Natural Language Interfaces with Fine-Grained User Interaction: A Case Study on Web APIs. In _SIGIR_. ACM, 855–864.
  * Su et al. (2016) Yu Su, Huan Sun, Brian Sadler, Mudhakar Srivatsa, Izzeddin Gür, Zenghui Yan, and Xifeng Yan. 2016.  On generating characteristic-rich question sets for qa evaluation. In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_. 562–572.
  * Sugiyama et al. (2016) Hiroaki Sugiyama, Toyomi Meguro, and Ryuichiro Higashinaka. 2016\.  Evaluation of Question-Answering System About Conversational Agent’s Personality. In _IWSDS_ _(Lecture Notes in Electrical Engineering, Vol. 427)_. Springer, 183–194.
  * Vakulenko et al. (2021) Svitlana Vakulenko, Shayne Longpre, Zhucheng Tu, and Raviteja Anantha. 2021.  Question Rewriting for Conversational Question Answering. In _WSDM_. ACM, 355–363.
  * van Aken et al. (2019) Betty van Aken, Benjamin Winter, Alexander Löser, and Felix A. Gers. 2019.  How Does BERT Answer Questions?: A Layer-Wise Analysis of Transformer Representations. In _CIKM_. ACM, 1823–1832.
  * Waltinger et al. (2012) Ulli Waltinger, Alexa Breuing, and Ipke Wachsmuth. 2012\.  Connecting Question Answering and Conversational Agents - Contextualizing German Questions for Interactive Question Answering Systems.  _Künstliche Intell._ 26, 4 (2012), 381–390.
  * Wang et al. (2007) Mengqiu Wang, Noah A Smith, and Teruko Mitamura. 2007\.  What is the Jeopardy model? A quasi-synchronous grammar for QA. In _Proceedings of the 2007 joint conference on empirical methods in natural language processing and computational natural language learning (EMNLP-CoNLL)_. 22–32.
  * Wang et al. (2019) Zhiguo Wang, Patrick Ng, Xiaofei Ma, Ramesh Nallapati, and Bing Xiang. 2019.  Multi-passage BERT: A Globally Normalized BERT Model for Open-domain Question Answering. In _EMNLP/IJCNLP (1)_. Association for Computational Linguistics, 5877–5881.
  * Weston et al. (2015) Jason Weston, Antoine Bordes, Sumit Chopra, Alexander M Rush, Bart Van Merriënboer, Armand Joulin, and Tomas Mikolov. 2015.  Towards ai-complete question answering: A set of prerequisite toy tasks.  _arXiv preprint arXiv:1502.05698_ (2015).
  * Wong et al. (2012a) Wilson Wong, Lawrence Cavedon, John Thangarajah, and Lin Padgham. 2012a.  Mixed-initiative conversational system using question-answer pairs mined from the web. In _CIKM_. ACM, 2707–2709.
  * Wong et al. (2012b) Wilson Wong, Lawrence Cavedon, John Thangarajah, and Lin Padgham. 2012b.  Strategies for Mixed-Initiative Conversation Management using Question-Answer Pairs. In _COLING_. Indian Institute of Technology Bombay, 2821–2834.
  * Wong et al. (2011) Wilson Wong, John Thangarajah, and Lin Padgham. 2011\.  Health conversational system based on contextual matching of community-driven question-answer pairs. In _CIKM_. ACM, 2577–2580.
  * Wu et al. (2017) Fei Wu, Xinyu Duan, Jun Xiao, Zhou Zhao, Siliang Tang, Yin Zhang, and Yueting Zhuang. 2017.  Temporal Interaction and Causal Influence in Community-Based Question Answering.  _IEEE Trans. Knowl. Data Eng._ 29, 10 (2017), 2304–2317.
  * Wu et al. (2020b) Jinmeng Wu, Tingting Mu, Jeyarajan Thiyagalingam, and John Yannis Goulermas. 2020b.  Building interactive sentence-aware representation based on generative language model for community question answering.  _Neurocomputing_ 389 (2020), 93–107.
  * Wu et al. (2020a) Zhiyong Wu, Ben Kao, Tien-Hsuan Wu, Pengcheng Yin, and Qun Liu. 2020a.  PERQ: Predicting, Explaining, and Rectifying Failed Questions in KB-QA Systems. In _WSDM_. ACM, 663–671.
  * Xie (2017) Zhipeng Xie. 2017\.  Enhancing Document-Based Question Answering via Interaction Between Question Words and POS Tags. In _NLPCC_ _(Lecture Notes in Computer Science, Vol. 10619)_. Springer, 136–147.
  * Xiong et al. (2016) Kun Xiong, Anqi Cui, Zefeng Zhang, and Ming Li. 2016\.  Neural Contextual Conversation Learning with Labeled Question-Answering Pairs.  _CoRR_ abs/1607.05809 (2016).
  * Xu et al. (2016) Jun Xu, Tao Mei, Ting Yao, and Yong Rui. 2016\.  MSR-VTT: A Large Video Description Dataset for Bridging Video and Language. In _CVPR_. IEEE Computer Society, 5288–5296.
  * Xu et al. (2019) Jingjing Xu, Yuechen Wang, Duyu Tang, Nan Duan, Pengcheng Yang, Qi Zeng, Ming Zhou, and Xu Sun. 2019\.  Asking Clarification Questions in Knowledge-Based Question Answering. In _EMNLP-IJCNLP (1)_. Association for Computational Linguistics, 1618–1629.
  * Yang et al. (2019a) Wei Yang, Yuqing Xie, Aileen Lin, Xingyu Li, Luchen Tan, Kun Xiong, Ming Li, and Jimmy Lin. 2019a.  End-to-End Open-Domain Question Answering with BERTserini. In _NAACL-HLT (Demonstrations)_. Association for Computational Linguistics, 72–77.
  * Yang et al. (2019b) Wei Yang, Yuqing Xie, Luchen Tan, Kun Xiong, Ming Li, and Jimmy Lin. 2019b.  Data Augmentation for BERT Fine-Tuning in Open-Domain Question Answering.  _CoRR_ abs/1904.06652 (2019).
  * Yang et al. (2015) Yi Yang, Wen-tau Yih, and Christopher Meek. 2015.  Wikiqa: A challenge dataset for open-domain question answering. In _Proceedings of the 2015 conference on empirical methods in natural language processing_. 2013–2018.
  * Yang et al. (2020) Zekun Yang, Noa Garcia, Chenhui Chu, Mayu Otani, Yuta Nakashima, and Haruo Takemura. 2020\.  BERT Representations for Video Question Answering. In _WACV_. IEEE, 1545–1554.
  * Yang et al. (2018) Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhutdinov, and Christopher D Manning. 2018\.  HotpotQA: A dataset for diverse, explainable multi-hop question answering.  _arXiv preprint arXiv:1809.09600_ (2018).
  * Yih et al. (2016) Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming-Wei Chang, and Jina Suh. 2016.  The value of semantic parse labeling for knowledge base question answering. In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_. 201–206.
  * Yuan et al. (2019) Xingdi Yuan, Marc-Alexandre Côté, Jie Fu, Zhouhan Lin, Chris Pal, Yoshua Bengio, and Adam Trischler. 2019\.  Interactive Language Learning by Question Answering. In _EMNLP/IJCNLP (1)_. Association for Computational Linguistics, 2796–2813.
  * Zhang et al. (2018a) Hongzhi Zhang, Guandong Xu, Xiao Liang, Tinglei Huang, and Kun Fu. 2018a.  An Attention-Based Word-Level Interaction Model: Relation Detection for Knowledge Base Question Answering.  _CoRR_ abs/1801.09893 (2018).
  * Zhang et al. (2017) Sheng Zhang, Xin Zhang, Hui Wang, Jiajun Cheng, Pei Li, and Zhaoyun Ding. 2017\.  Chinese Medical Question Answer Matching Using End-to-End Character-Level Multi-Scale CNNs.  _Applied Sciences_ 7, 8 (2017), 767.
  * Zhang et al. (2018b) Sheng Zhang, Xin Zhang, Hui Wang, Lixiang Guo, and Shanshan Liu. 2018b.  Multi-Scale Attentive Interaction Networks for Chinese Medical Question Answer Selection.  _IEEE Access_ 6 (2018), 74061–74071.
  * Zhang et al. (2019b) Xinbo Zhang, Lei Zou, and Sen Hu. 2019b.  An Interactive Mechanism to Improve Question Answering Systems via Feedback. In _CIKM_. ACM, 1381–1390.
  * Zhang et al. (2019a) Yingying Zhang, Shengsheng Qian, Quan Fang, and Changsheng Xu. 2019a.  Multi-modal Knowledge-aware Hierarchical Attention Network for Explainable Medical Question Answering. In _ACM Multimedia_. ACM, 1089–1097.
  * Zheng et al. (2019) Weiguo Zheng, Hong Cheng, Jeffrey Xu Yu, Lei Zou, and Kangfei Zhao. 2019.  Interactive natural language question answering over knowledge graphs.  _Inf. Sci._ 481 (2019), 141–159.
  * Zhou et al. (2016) Guangyou Zhou, Yin Zhou, Tingting He, and Wensheng Wu. 2016\.  Learning semantic representation with neural networks for community question answering retrieval.  _Knowledge-Based Systems_ 93 (2016), 75–83.
  * Zhou et al. (2017) Zhiheng Zhou, Man Lan, Yuanbin Wu, and Jun Lang. 2017\.  Single turn Chinese emotional conversation generation based on information retrieval and question answering. In _IALP_. IEEE, 103–106.
  * Zhu et al. (2018) Chenguang Zhu, Michael Zeng, and Xuedong Huang. 2018\.  SDNet: Contextualized Attention-based Deep Network for Conversational Question Answering.  _CoRR_ abs/1812.03593 (2018).
  * Zhu et al. (2016) Yuke Zhu, Oliver Groth, Michael Bernstein, and Li Fei-Fei. 2016\.  Visual7w: Grounded question answering in images. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 4995–5004.


Hitting two BSM particles with one lepton-jet: search for a top partner
decaying to a dark photon, resulting in a lepton-jet

K. du Plessis1, M. M. Flores1,2, D. Kar1*, S. Sinha1 H. van der Schyf1,

1 School of Physics, University of Witwatersrand, Johannesburg, South Africa.

2 National Institute of Physics, University of the Philippines, Diliman,
Quezon City, Philippines.

*<EMAIL_ADDRESS>
## Abstract

A maverick top partner model, decaying to a dark photon was suggested in Ref.
[1]. The dark photon decays to two overlapping electrons for dark photon
masses of $\approx 100$ GeV, and results in a so-called lepton-jet. The event
includes a top quark as well, which results in events with two boosted
objects, one heavy and the other light. We propose a search strategy
exploiting the unique signal topology. We show that for a set of kinematic
selections, both in hadronic and leptonic decay channel of the SM top quark,
almost all background can be eliminated, leaving enough signal events up to
top partner mass of about 3 TeV for the search to be viable at the LHC.

###### Contents

  1. 1 Introduction
  2. 2 Maverick Top Partners
    1. 2.1 Brief Survey of the Model
    2. 2.2 Event Generation
    3. 2.3 Current experimental bounds on VLTs
  3. 3 Analysis strategy
    1. 3.1 Overview
    2. 3.2 Analysis with the top quark decaying hadronically
    3. 3.3 Analysis with the top quark decaying leptonically
  4. 4 Conclusions

##  1 Introduction

The Standard Model (SM) of particle physics [2] has by far been successful in
explaining almost all the experimentally observed microscopic phenomena.
However, it is deemed an incomplete theory due to a number of reasons, one of
which is its failure to explain dark matter (DM), whose existence is
empirically established from various astrophysical data [3, 4]. Although the
presence of dark matter is pretty much a consensus, little is known regarding
its interaction with itself and with the elementary particles of SM. One
possibility is that dark matter particles may interact through some dark force
akin to the electromagnetic force felt by ordinary particles. This leads to
the conjecture of the existence of a new gauge boson that would mediate this
dark force, analogous to the role of the photon in Quantum Electrodynamics.
For this reason, the new gauge boson is referred to in literature as the dark
photon [5] (which will be denoted in this paper as $\gamma_{d}$), although the
terms paraphoton [6] and U-boson [7] have been used.

In this paper, we propose a new search strategy for a chimera-like scenario,
where a dark photon will come not from known SM particles, but rather from
hypothetical vectorlike quarks (VLQ), $T$ (also known as top partners), dubbed
the maverick top partners [1], i.e., VLTs [8, 9, 10, 11] with unconventional
decays. The primary model is motivated by [1], in which a top-partner is
charged under both the SM and a new gauge $U(1)_{d}$ group, where the SM is
neutral under the $U(1)_{d}$.

The paper is divided into the following sections: in Section 2 we discuss the
general idea of maverick top partners and the model in concern, followed by
event generation procedure which is provided in 2.2. In Section 3, we discuss
the particle - level analysis performed for the model in question, and
estimate our ability to experimentally probe such a chimera-like scenario, and
finally present our conclusions in Section 4.

##  2 Maverick Top Partners

###  2.1 Brief Survey of the Model

There are theoretical reasons to believe that dark photons could be massless
or massive [5], and their respective features and experimental signatures are
quite distinct. In this paper we focus on the massive photon since it is more
readily accessible in the collider searches (due to the fact that it couples
to ordinary matter).

Typical production mechanisms of massive dark photons include [5, 12]:

  * •

Bremsstrahlung, whereby an incoming electron scatters off a nuclei target (Z)
and emits dark photon, i.e., $e^{-}Z\rightarrow e^{-}Z\gamma_{d}$;

  * •

Annihilation, whereby an electron-positron pair annihilates into a photon and
a dark photon, i.e., $e^{-}e^{+}\rightarrow\gamma\gamma_{d}$; and

  * •

Drell-Yan, whereby a quark-antiquark pair annihilates into a dark photon,
which consequently decays into a lepton pair or hadrons, i.e.,
$q\bar{q}\rightarrow\gamma_{d}\rightarrow
l^{-}l^{+}\,\,\mbox{or}\,\,h^{-}h^{+}$.

Here we consider a special production mechanism where the dark photon comes
from a VLT, and thus the production chain will look like VLT$\rightarrow
t\gamma_{d}$, where $t$ is the SM top quark.

The decay modes of the massive dark photon is further divided into whether it
is visible or invisible, with the borderline requirement of visibility being
$m_{\gamma_{d}}>2m_{e}\simeq 1~{}\mbox{MeV}$ because then it can decay into SM
charged particles (electron-positron pairs being the extreme case) which leave
a signature in the detectors. Otherwise, it cannot decay into known SM charged
particles and the decay is therefore invisible. We choose to study this
extreme case of dark photon decaying into electron-positron pairs since these
final states result into the lesser studied unusual topology known as lepton-
jets. This choice constrains our massive photon to have a mass between 1 MeV
to 200 MeV, otherwise the braching ratio (BR) into electron-positron pairs is
not 100% and we get non-zero BR into muon-antimuon pairs [12, 1].

Figure 1: Feynman diagram showing the production mechanism of VLT going to a
top quark and a dark photon, which subsequently decays to two leptons.

Hence, we perform a phenomenological study on final states involving a lepton-
jet in association with the top quark, investigating both the scenarios where
the top quark decays hadronically or leptonically.

No evidence in favor of VLTs has been found at the Large Hadron Collider (LHC)
when probing via its traditional decays into SM particles. Hence,
nontraditional decays are searched for, including decay into the dark photon
which becomes dominant provided that its mass is very less compared to the SM
electroweak sector $(m_{\gamma_{d}}<<m_{Z})$. This appealing scenario provides
a probe for light dark sector by searching for heavy particles at the LHC,
thus bridging the two heavy and light mass regimes of BSM particles, VLTs and
dark photons respectively.

In order for the VLT decays into the dark photon to be dominant, we follow the
model discussed in-depth in [1], where a new Abelian gauge symmetry $U(1)_{d}$
is introduced whose gauge boson is the dark photon itself (i.e., SM is
extended to $SU(3)\times SU(2)_{L}\times U(1)_{Y}\times U(1)_{d}$). The SM
particles are singlets under this new symmetry while the VLT has a charge
$+1$. Specifically, this VLT is a singlet under $SU(2)_{L}$ with SM
hypercharge $Y=2/3$. With this, the dark photon gauge boson kinetically mixes
with the SM $U(1)_{Y}$ field. While this opens up a decay channel of VLT into
the dark photon (plus top), its decay into fully SM final states (such as
$W/Z/h$ plus top) is still feasible. To enhance the former, we take the
$U(1)_{d}$ scale to be significantly smaller than the electroweak scale
($m_{\gamma_{d}}<<m_{Z}$) since the partial widths of VLT decay into
$\gamma_{d}$ relative to SM electroweak bosons is proportional to
$(v_{EW}/v_{d})^{2}$, where $v_{EW}=246$ GeV is the Higgs boson vacuum
expectation value (vev) and $v_{d}$ is the vev of the dark sector Higgs boson.

It should be noted that VLTs at the LHC can either be pair produced
$(pp\rightarrow T\bar{T})$, or produced singly in association with a jet
$(pp\rightarrow T/\bar{T}+\mbox{jet})$. The single production mechanism
surpasses the pair production in a wide range of $m_{VLT}$, with the latter
only outmatching the former in relatively low $M_{VLT}$ masses
($M_{VLT}\lesssim 1000$ GeV) [1, 13]. In this work, we only focus on the
single VLT production since not only is it the more favored production phase
space, the final state it produces is also relatively “cleaner” as opposed to
pair production.

With the requirement that the kinetic mixing $\varepsilon$ is small on top of
the $m_{\gamma_{d}}<<m_{Z}$ mass requirement, enhances VLT decay into dark
photons, and the $U(1)_{d}$ gauge boson inherits couplings to SM particles
through the electromagnetic current with coupling strength $\varepsilon eQ$
[1]. This in turn, kinematically opens up dark photon decays into
$e^{+}e^{-}$, for the values of $m_{\gamma_{d}}$ considered in this paper.

###  2.2 Event Generation

We generated events using MadGraph5 interfaced with Pythia8 [14] (using the
default NN23LO1 parton distribution function set [15]) from UFO [16] files
based on the maverick top partner model in [1], with the relevant parameters
above set as: $v_{d}=10$ GeV, $\varepsilon=0.001$. We vary the VLT masses from
$1$ TeV, $3$ TeV to $5$ TeV (with cross sections of $47.6$ fb, $0.41$ fb and
$0.0054$ fb respectively) to make sure that we remain at the phase space where
it is singly produced. Also, we chose $m_{\gamma_{d}}=0.1$ GeV which ensures
that the branching ratio (BR) to $e^{+}e^{-}$ is 1.

For each signal mass point, 100,000 events were generated, while for each
background processes, 1 million events were generated. All the background
processes have been generated using Pythia8 as well. While a leading order
generator cannot model all the background accurately, our aim here is to get
the general characteristics of the background processes, and suggest ways to
reduce them, for which Pythia8 is adequate. In any case, the region of
interest is the tail of reconstructed VLT mass distribution, so only general
features can be studied in a particle level analysis with limited Monte Carlo
statistics. Finally, all distributions below are normalised using an
integrated luminosity of $300$ fb-1, corresponding to projected combined
integrated luminosity after LHC Run 3.

###  2.3 Current experimental bounds on VLTs

Currently, the most stringent limits on VLT masses are set by the ATLAS and
CMS experiments [17, 18, 19, 20]. The excluded masses for VLT depend on the
branching ratios (BR) assumed; and for extreme values of 100% BR, a singlet
VLT is excluded for masses below 2 TeV.

##  3 Analysis strategy

###  3.1 Overview

The signal is characterised by an opposite sign electron pair with high
$p_{\mathrm{T}}$ and very little angular separation. They form what is known
as a lepton-jet (more specifically electron-jet in our case), where tracks
from the two electrons will overlap, and the energy deposits will be collected
in a single jet. Electron reconstruction algorithm used in LHC experiments
will mostly mis-reconstruct it as a single electron. So unlike standard
searches, electron multiplicity is a misleading observable here.

lepton-jets have been studied sparingly at the LHC [21, 22, 23], mostly to
search for SUSY and Higgs portal models with relatively high mass bosons
compared to the dark photon considered here. As mass calibration for jets in
experiments is deemed unreliable below 10 GeV, we are in no position to
exploit the lepton-jet mass. However, since the lepton-jet will be boosted,
the mass over transverse momentum ratio (subsequently referred to as
$m/$$p_{\mathrm{T}}$) of such jets can be used as a discriminating variable,
even accounting for the inherent uncertainty in the measured mass value. The
standard jets from quarks and gluons tend to have a much higher mass compared
to $\approx$ 100-200 MeV. Experimentally, the lepton-jet is expected to have a
larger than usual fraction of energy deposited in electromagnetic calorimeter,
which can be exploited as well.

The event also contain a top quark, and a at least one more jet coming from
the initial quark. A sketch of the event topology is shown in Fig. 2. We do
note this is aid visualisation, not an accurate indicator of the event
kinematics.

Figure 2: A cartoon of different objects produced in a typical signal event.
All decays shown are prompt.The large-radius jet shows the hadroniccaly
decalying top quark, the the b-tagged jet shown as shaded. In leptonic decay
mode of the top quark, it will contain a charged lepton and corresponding
neutrino, along with the b-tagged jet.

The decay mode of the top quark on the other side will determine the full
topology. We investigate the two scenarios of the top quark decaying
hadronically and leptonically separately.

We note that due to the lepton-jet being very boosted, the resulting two
electrons will have a very skewed energy (hence transverse momentum)
distribution, with one usually produced with a much higher $p_{\mathrm{T}}$.
This has crucial implications in the leptonic channel, as we will see. We also
note that the initial quark produced along with the VLT can be a bottom quark,
so we expect two b-tagged jets in some events.

In the following analysis, we will use objects as they are commonly used in
experiments. Jets will be the ones reconstructed using anti-$k_{t}$ [24]
algorithm with radius parameter of 0.4, $p_{\mathrm{T}}$$>30$ GeV and
$|\eta|<4.4$. Large radius jets are reconstructed using anti-$k_{t}$ algorithm
with radius parameter of 1.0, with $p_{\mathrm{T}}$$>150$ GeV and $|\eta|<2$.
We have not used any grooming as it is a particle level study without any
pileup, but application of standard trimming or soft-drop would not change any
conclusions. Muons or neutrinos are not used as jet inputs, and the presence
of a b-hadron inside a jet is used to determine if the jet is b-tagged or not.
Lepton are chosen with $p_{\mathrm{T}}$$>25$ GeV and $|\eta|<2.5$, dressed
with photons within a radius of $0.1$ and not originating from hadron decays.
The missing transverse momentum is calculated from the negative four-vector
sum of all visible particles. The most inclusive suggested trigger will be a
single electron trigger with appropriate threshold. Rivet analysis toolkit
[25] has been used.

###  3.2 Analysis with the top quark decaying hadronically

The signal topology in hadronic channel is two electrons being identified as
one as a part of a high $p_{\mathrm{T}}$, low mass lepton-jet, a boosted top
quark jet, and at least another jet. The event selection requirement is at
least one electron, no muons, and at least three jets, at least one of them
being b-tagged.

The largest background by far is the usual multijet processes, where a jet is
misreconstructed as an electron. Top quark pair production and all-hadronic
and (electron-channel) semileptonic decay modes will consist of the other
significant background processes. The cross-sections of other possible
background processes, like $\textrm{top}+Z+$jets. $\textrm{top}+W+$jets,
$\textrm{top}+\gamma+$jets are tiny, and therefore neglected. We required
there be at least one small radius jet and at least three large radius jets.

The lepton-jet candidate is the jet closest in $\Delta R$ to the leading
$p_{\mathrm{T}}$ electron. This is verified by checking the $\Delta R$ between
the two electrons and between the leading electron and the closest jet in Fig.
3.

Figure 3: Distributions of $\Delta R$ between the two electrons (left) and
$\Delta R$ between leading electron and closest jet (right) for three
representative signal points

As expected, the two electrons are almost on top of each other, and there is
always a jet collinear with them. In order to be consistent with the
experimental signature, we require minimum of only one electron, not two.
However, for multijet and hadronic $t\overline{t}$ backgrounds, this one
electron requirement had to be relaxed, as jets misidentified as electrons
will result in these reducible backgrounds. Here we have scaled the cross-
sections by $0.1$ to mimic the electron misidentification rate. Requiring a
tight electron identification criteria will help in reducing these
backgrounds.

The top-jet candidate is a highest mass large radius jet, satisfying a top-
mass window (chosen rather liberally to be between 125–225 GeV) requirement.
The large-radius jet is also required to contain a b-tagged jet with $\Delta
R<1$. While any of the standard top-tagging techniques [26, 27] or
requirements on jet substructure observables can be used to increase the
purity of the top-jet selection, we leave that for the experimental analysis.

Since there is no real electron in multijet and hadronic $t\overline{t}$
background events, we have considered the jets farthest from the top jet
candidate as the lepton-jet. Then the invariant mass of the top partner is
reconstructed from four-momenta of the lepton-jet and top jet candidates. This
is the key observable for the search.

Kinematic selections are used based on signal characteristics to reduce the
background contributions. Fig. 4 shows lepton-jet and top jet $p_{\mathrm{T}}$
distributions, and based on these, a 200 GeV requirement is applied on both.
Additionally based on Fig. 5, a $\Delta\phi>1.5$ requirement is applied
between the lepton-jet and top jet candidate, as they are expected to be more
back-to-back than most background processes. After all the above kinematic
requirements, we are still left with a significant background, as can be seen
in the top partner mass distribution in reconstructed VLT mass distribution on
the right of Fig. 5.

Figure 4: Distributions of lepton-jet $p_{\mathrm{T}}$ (left) and the top jet
candidate $p_{\mathrm{T}}$ (right) for three representative signal points and
dominant background processes

Figure 5: Distributions of $\Delta\phi$ between the lepton-jet and hadronic
top jet and VLT mass after all kinematic requirements for three representative
signal points and dominant background processes

Then in Fig. 6, $m/$$p_{\mathrm{T}}$ for signals and backgrounds is compared,
and requiring the ratio to be less than $0.01$ essentially keeps only the
signal, as can be seen in the right figure.

Figure 6: Distributions of lepton-jet $m/p_{T}$ ratio before (right) and
reconstructed VLT mass after the $m/p_{T}<0.01$ requirement for three
representative signal points and dominant background processes

A detailed study on the effect of these kinematic requirement on signal and
background was performed and summarised in Table 1 for the signal points.

Requirement | Signal efficiency reduction for TP mass in $\%$:
---|---
| 1 TeV | 3 Tev | 5 TeV
Lepton multiplicity | 97 | 98 | 98
Jet multiplicity | 93 | 94 | 92
Top mass window | 75 | 79 | 71
B-jet multiplicity | 68 | 75 | 68
lepton-jet $p_{\mathrm{T}}$ | 64 | 73 | 67
Top jet $p_{\mathrm{T}}$ | 64 | 73 | 67
B-jet containment | 57 | 57 | 41
Lepton and top jet separation | 56 | 56 | 40
$m/$$p_{\mathrm{T}}$ | 17 | 29 | 27
Table 1: Effect of kinematic requirements on leptonic channel signal points.
Each requirement is mentioned earlier.

While the requirements enforced decrease the signal significantly, the
$m/$$p_{\mathrm{T}}$ requirement essentially makes it a zero background
search. The different impact of b-jet containment and $m/$$p_{\mathrm{T}}$
requirement on different signals is due to how boosted the signal is. After
all selections, about a thousand signal events remain for VLT mass of 1 TeV,
and about ten for VLT mass of 3 TeV.

###  3.3 Analysis with the top quark decaying leptonically

The signal topology in leptonic channel is two electrons being identified as
one as a part of a high $p_{\mathrm{T}}$, a low mass lepton-jet, a top quark
decaying leptonically, and at least another jet. Depending on lepton flavour
from top quark decay, two scenarios are possible, termed electron and muon
channels. At least two jets, with at least one of them b-tagged is required.

In both cases, the top quark is reconstructed by using the pseudotop method
[28]. The algorithm starts with the reconstruction of the neutrino four-
momentum. While the $x$ and $y$ components of the neutrino momentum are set to
the corresponding components of the missing transverse momentum, the $z$
component is calculated by imposing the $W$ boson mass constraint on the
invariant mass of the charged-lepton–neutrino system. If the resulting
quadratic equation has two real solutions, the one with the smaller value of
$|p_{z}|$ is chosen. If the discriminant is negative, only the real part is
considered. The leptonically decaying $W$ boson is reconstructed from the
charged lepton and the neutrino. The leptonic top quark is reconstructed from
the leptonic $W$ and the b-tagged jet closest in $\Delta R$ to the charged
lepton. We will refer it to as the leptonic top candidate.

In the muon channel, the muon is always used to reconstruct the leptonic top.
In the electron channel, a possible ambiguity can arise, as there are three
electrons, two of them are expected to be overlapping, and the third from the
top quark. We cannot a priori assume that the leading electron is from the
dark photon decay, or the electron closest to the b-tagged jet is from the top
quark decay, as a large fraction of events have two b-tagged jets, the second
one from the initial quark. However, we have found that the electron pair with
the highest invariant $p_{\mathrm{T}}$ comes from the dark photon about 99.5%
of the time, so we use this pair as the single merged electron seeding the
lepton-jet, as seen by the detector. Then the remaining electron is used for
leptonic top reconstruction. Then the invariant mass of the top partner is
reconstructed from four-momenta of the lepton-jet and leptonic top candidates.

As in the hadronically decaying top quark scenario above, we need to be
careful about lepton multiplicity when considering the backgrounds. For the
muon channel, in order to be consistent with the experimental signature, we
require at least one electron and at least one muon. The largest background is
the dileptonic mixed flavour $t\overline{t}$ process, which is an irreducible
background. Since mis-reconstruction of muons as jets are relatively rare as
compared to electrons, we do not have to worry about background that does not
contain a real muon. The semileptonic $t\overline{t}$ process with a muon will
be a reducible background, where a jet from leptonic top can mimic the lepton-
jet. As before, for this case, we have loosened the electron requirement, and
applied a normalisation factor of 0.1.

For the electron channel, we start by requiring at least three electrons, and
no muons. However, then the merged lepton is used, so the effective
requirement is two. The largest background is the dileptonic $t\overline{t}$
process with both top quarks decaying to electrons, which is an irreducible
background. The semileptonic $t\overline{t}$ process with an electron will be
a reducible background. where a jet from hadronic top can mimic the lepton-jet
or the leptonic top. As before, for this case, we have loosened the electron
requirement, and applied an extra normalisation factor of 0.1.

The other significant backgrounds can be $W/Z$ boson (decaying to electrons)
with jets. As the $Z$-boson mass is much higher than the dark photon mass, the
electrons rarely end up overlapping, and the $b$-jet requirement essentially
gets rid of almost all the $W$+jets contribution. We have not explicitly
considered $\tau$ decay modes of the top quark as the hadronic decay mode will
be equivalent to the fully hadronic signature considered, and the leptonic
decay modes will be similar to the electron and muon channels.

The kinematic requirements are inline with those applied in hadronic case,
with requirements of lepton-jet $p_{\mathrm{T}}$ and leptonic top candidate
$p_{\mathrm{T}}$ of 200 GeV. Most kinematic distributions are similar to the
hadronic channel ones shown above, so we did not repeat them. The distribution
of them is shown in Fig. 7.

Figure 7: Distributions of lepton-jet $p_{\mathrm{T}}$ (top row) and the
leptonic top candidate $p_{\mathrm{T}}$ (bottom row) for muon (left) and
electron (right) channels for three representative signal points and dominant
background processes

Similarly the b-tagged jet is required to be with $\Delta R<1$ of the leptonic
top candidate, and a $\Delta\phi>2.5$ requirement is applied between the
lepton-jet and leptonic top candidate, the latter distribution is shown in
Fig. 8. A loose minimum mass requirement of 100 GeV is applied for the
leptonic top candidate. Finally the same $m/$$p_{\mathrm{T}}$ requirement as
before is applied, and it again helps to massively reduce all backgrounds, as
can be seen in Fig. 9.

Figure 8: Distributions of $\Delta\phi$ between the lepton-jet and the
leptonic top candidate for the muon channel (left) and the electron channel
(right) for three representative signal points and dominant background
processes

Figure 9: Distributions of reconstructed VLT mass before (top row) and after
the $m/p_{T}<0.01$ requirement, for muon (left) and electron (right) channels
for three representative signal points and dominant background processes

A detailed study on the effect of these kinematic requirement on signal and
background was performed and summarised in Table 2 separately for electron and
muon channels, as defined above. The initial drop is due to one of the leptons
falling below the kinematic thresholds, and while the $m/$$p_{\mathrm{T}}$
requirement does reduce the efficiencies drastically, it also eliminates
almost all of the background, as seen above. We can also consider a
requirement on missing transverse momentum, but this is always better to leave
for a detector level analysis. Similarly, a requirement of about 100 GeV on
the leading electron $p_{\mathrm{T}}$ keeps almost all of the signal and will
help in reducing backgrounds, but this is better optimised using the potential
mis-reconstructed electrons at the detector level. After all selections, about
a thousand signal events remain for VLT mass of 1 TeV, and about ten for VLT
mass of 3 TeV.

Requirement | Signal efficiency reduction for TP mass in $\%$:
---|---
| 1 TeV | 3 TeV | 5 TeV
| El | Mu | El | Mu | El | Mu
Lepton multiplicity | 70 | 82 | 88 | 92 | 92 | 94
Jet multiplicity | 62 | 72 | 84 | 88 | 88 | 92
lepton-jet $p_{\mathrm{T}}$ | 60 | 68 | 82 | 88 | 88 | 92
Top jet $p_{\mathrm{T}}$ | 58 | 66 | 82 | 88 | 88 | 92
Top mass minimum | 58 | 64 | 82 | 86 | 88 | 92
B-jet containment | 54 | 60 | 80 | 84 | 86 | 90
Lepton and top separation | 52 | 58 | 78 | 82 | 84 | 88
$m/$$p_{\mathrm{T}}$ | 16 | 18 | 38 | 40 | 54 | 56
Table 2: Effect of kinematic requirements on leptonic channel signal
points.Each requirement is mentioned earlier.

##  4 Conclusions

A maverick top partner model, decaying to a dark photon was suggested in Ref.
[1]. A phenomenological exploration of the model has been performed, and a
search strategy has been proposed exploiting the unique signal topology. We
show that for a set of kinematic selections, both in hadronic and leptonic
decay channel of the SM top quark, almost all background can be eliminated,
leaving enough signal events for the search to be viable at the LHC upto VLT
mass of 3 TeV.

## Acknowledgements

We thank the authors of the maverick top partner paper, specifically Ian M.
Lewis and Samuel D. Lane for providing us with model files to cross check
ours. We thank Peter Loch for illuminating discussion on applicability of jet
mass calibration and suggesting the use of mass over transverse momentum
ratio. DK is funded by National Research Foundation (NRF), South Africa
through Competitive Programme for Rated Researchers (CPRR), Grant No: 118515.
MMF is funded by the Department of Science and Technology (DOST) - Accelerated
Science and Technology Human Resource Development Program (ASTHRDP)
Postdoctoral Research Fellowship. SS thanks University of Witwatersrand
Research Council for Sellschop grant and NRF for grant-holder linked bursary.
KDP thanks the National Astrophysics and Space Science Programme for their
ongoing financial support. HVDS thanks SA-CERN programme for excellence
scholarship.

## References

  * [1] J. H. Kim, S. D. Lane, H.-S. Lee, I. M. Lewis and M. Sullivan,  _Searching for Dark Photons with Maverick Top Partners_ ,  Phys. Rev. D 101(3), 035041 (2020),  10.1103/PhysRevD.101.035041,  1904.05893.
  * [2] S. Weinberg,  _The Making of the standard model_ ,  Eur. Phys. J. C 34, 5 (2004),  10.1140/epjc/s2004-01761-1,  hep-ph/0401010.
  * [3] L. Baudis,  _The Search for Dark Matter_ (2018),  10.1017/S1062798717000783,  1801.08128.
  * [4] G. Arcadi, M. Dutra, P. Ghosh, M. Lindner, Y. Mambrini, M. Pierre, S. Profumo and F. S. Queiroz,  _The waning of the WIMP? A review of models, searches, and constraints_ ,  Eur. Phys. J. C 78(3), 203 (2018),  10.1140/epjc/s10052-018-5662-y,  1703.07364.
  * [5] M. Fabbrichesi, E. Gabrielli and G. Lanfranchi,  _The Dark Photon_ (2020),  10.1007/978-3-030-62519-1,  2005.01515.
  * [6] B. Holdom,  _Two U(1)’s and Epsilon Charge Shifts_ ,  Phys. Lett. B 166, 196 (1986),  10.1016/0370-2693(86)91377-8.
  * [7] P. Fayet,  _Extra U(1)’s and New Forces_ ,  Nucl. Phys. B 347, 743 (1990),  10.1016/0550-3213(90)90381-M.
  * [8] F. Del Aguila and M. Bowick,  _The possibility of new fermions with $deltai=0$ mass_,  Nuclear Physics B 224(1), 107 (1983),  https://doi.org/10.1016/0550-3213(83)90316-4.
  * [9] J. H. Kim and I. M. Lewis,  _Loop Induced Single Top Partner Production and Decay at the LHC_ ,  JHEP 05, 095 (2018),  10.1007/JHEP05(2018)095,  1803.06351.
  * [10] H. Alhazmi, J. H. Kim, K. Kong and I. M. Lewis,  _Shedding Light on Top Partner at the LHC_ ,  JHEP 01, 139 (2019),  10.1007/JHEP01(2019)139,  1808.03649.
  * [11] M. J. Dolan, J. L. Hewett, M. Krämer and T. G. Rizzo,  _Simplified Models for Higgs Physics: Singlet Scalar and Vector-like Quark Phenomenology_ ,  JHEP 07, 039 (2016),  10.1007/JHEP07(2016)039,  1601.07208.
  * [12] M. Graham, C. Hearty and M. Williams,  _Searches for dark photons at accelerators_ (2021), 2104.10280.
  * [13] O. Matsedonskyi, G. Panico and A. Wulzer,  _On the Interpretation of Top Partners Searches_ ,  JHEP 12, 097 (2014),  10.1007/JHEP12(2014)097,  1409.0100.
  * [14] T. Sjöstrand, S. Ask, J. R. Christiansen, R. Corke, N. Desai, P. Ilten, S. Mrenna, S. Prestel, C. O. Rasmussen and P. Z. Skands,  _An Introduction to PYTHIA 8.2_ ,  Comput. Phys. Commun. 191, 159 (2015),  10.1016/j.cpc.2015.01.024,  1410.3012.
  * [15] R. D. Ball, V. Bertone, S. Carrazza, L. Del Debbio, S. Forte, A. Guffanti, N. P. Hartland and J. Rojo,  _Parton distributions with QED corrections_ ,  Nucl. Phys. B 877, 290 (2013),  10.1016/j.nuclphysb.2013.10.010,  1308.0598.
  * [16] A. Alloul, N. D. Christensen, C. Degrande, C. Duhr and B. Fuks,  _FeynRules 2.0 - A complete toolbox for tree-level phenomenology_ ,  Comput. Phys. Commun. 185, 2250 (2014),  10.1016/j.cpc.2014.04.012,  1310.1921.
  * [17] ATLAS Collaboration,  _Search for single production of vector-like quarks decaying into $Wb$ in $pp$ collisions at $\sqrt{s}=13$ TeV with the ATLAS detector_,  JHEP 05, 164 (2019),  10.1007/JHEP05(2019)164,  1812.07343.
  * [18] ATLAS Collaboration,  _Search for pair- and single-production of vector-like quarks in final states with at least one $Z$ boson decaying into a pair of electrons or muons in $pp$ collision data collected with the ATLAS detector at $\sqrt{s}=13$ TeV_,  Phys. Rev. D 98(11), 112010 (2018),  10.1103/PhysRevD.98.112010,  1806.10555.
  * [19] CMS Collaboration,  _Search for single production of a vector-like T quark decaying to a Z boson and a top quark in proton-proton collisions at $\sqrt{s}$ = 13 TeV_,  Phys. Lett. B 781, 574 (2018),  10.1016/j.physletb.2018.04.036,  1708.01062.
  * [20] CMS Collaboration,  _Search for single production of vector-like quarks decaying to a top quark and a W boson in proton-proton collisions at $\sqrt{s}=$ 13 TeV_,  Eur. Phys. J. C 79, 90 (2019),  10.1140/epjc/s10052-019-6556-3,  1809.08597.
  * [21] CMS Collaboration,  _Search for Light Resonances Decaying into Pairs of Muons as a Signal of New Physics_ ,  JHEP 07, 098 (2011),  10.1007/JHEP07(2011)098,  1106.2375.
  * [22] ATLAS Collaboration,  _A search for prompt lepton-jets in $pp$ collisions at $\sqrt{s}=$ 8 TeV with the ATLAS detector_,  JHEP 02, 062 (2016),  10.1007/JHEP02(2016)062,  1511.05542.
  * [23] CMS Collaboration,  _A search for pair production of new light bosons decaying into muons in proton-proton collisions at 13 TeV_ ,  Phys. Lett. B 796, 131 (2019),  10.1016/j.physletb.2019.07.013,  1812.00380.
  * [24] M. Cacciari, G. P. Salam and G. Soyez,  _The anti- $k_{t}$ jet clustering algorithm_,  JHEP 04, 063 (2008),  10.1088/1126-6708/2008/04/063,  0802.1189.
  * [25] C. Bierlich _et al._ ,  _Robust Independent Validation of Experiment and Theory: Rivet version 3_ ,  SciPost Phys. 8, 026 (2020),  10.21468/SciPostPhys.8.2.026,  1912.05451.
  * [26] R. Kogler _et al._ ,  _Jet Substructure at the Large Hadron Collider: Experimental Review_ ,  Rev. Mod. Phys. 91(4), 045003 (2019),  10.1103/RevModPhys.91.045003,  1803.06991.
  * [27] S. Marzani, G. Soyez and M. Spannowsky,  _Looking inside jets: an introduction to jet substructure and boosted-object phenomenology_ , vol. 958,  Springer,  10.1007/978-3-030-15709-8 (2019), 1901.10342.
  * [28] ATLAS Collaboration,  _Differential top-antitop cross-section measurements as a function of observables constructed from final-state particles using pp collisions at $\sqrt{s}=7$ TeV in the ATLAS detector_,  JHEP 06, 100 (2015),  10.1007/JHEP06(2015)100,  1502.05923.


# Real-Time Formal Verification of Autonomous Systems With An FPGA

Minh Bui, Michael Lu, Reza Hojabr, Mo Chen, Arrvindh Shriraman All the authors
are with the School of Computing Science, Simon Fraser University.
{minh_bui_3, mla233, shojabro, mochen<EMAIL_ADDRESS>
###### Abstract

Hamilton-Jacobi reachability analysis is a powerful technique used to verify
the safety of autonomous systems. This method is very good at handling non-
linear system dynamics with disturbances and flexible set representations. A
drawback to this approach is that it suffers from the curse of dimensionality,
which prevents real-time deployment on safety-critical systems. In this paper,
we show that a customized hardware design on a Field Programmable Gate Array
(FPGA) could accelerate 4D grid-based Hamilton-Jacobi (HJ) reachability
analysis up to 16 times compared to an optimized implementation and 142 times
compared to MATLAB ToolboxLS on a 16-thread CPU. Our design can overcome the
complex data access pattern while taking advantage of the parallel nature of
the HJ PDE computation. Because of this, we are able to achieve real-time
formal verification with a 4D car model by re-solving the HJ PDE at a
frequency of 5Hz on the FPGA as the environment changes. The latency of our
computation is deterministic, which is crucial for safety-critical systems.
Our approach presented here can be applied to different systems dynamics, and
moreover, potentially leveraged for higher dimensions systems. We also
demonstrate obstacle avoidance with a robot car in a changing environment.

##  I Introduction

Autonomous systems are becoming more prevalent in our lives. Examples of these
systems include self-driving cars, unmanned aerial vehicles, rescue robots,
etc. One key factor that will allow wider adoption of autonomous systems is
the guaranteed safety of these systems. Despite tremendous progress in
autonomous system research in areas such as motion planning, perception, and
machine learning, deployment of these systems in environments that involve
interactions with humans and other robots remains limited due to the potential
danger these robotic systems can cause. Formal verification methods can help
autonomous robots reach their untapped potential.

Hamilton-Jacobi (HJ) reachability analysis is a formal verification approach
that provides guaranteed safety and goal satisfactions to autonomous systems
under adversarial disturbances. There are many ways to do reachability
analysis, solving the HJ PDE is one way to characterize sets of safe states
and synthesizes optimal controllers, which involves calculating Backward
Reachable Tube (BRT) that describes a set of states the system must stay out
of in order to avoid obstacles. HJ reachability analysis has been successfully
applied in practical applications such as aircraft safe landing [1], multi-
vehicle path planning, multi-player reach avoid games [2]. The appeal of this
particular method is that it’s very powerful in handling control and
disturbances, nonlinear system dynamics, and flexible set representations.

The main downside to HJ reachability is that it’s solved on a multi-
dimensional grid with the same number of dimensions as the number of state
variables and scales exponentially with the number of dimensions. This
prevents HJ formulation to be applied on real-time systems where safety is
increasingly demanded. While 3D or smaller systems could be computed quickly
with multi-core CPUs, practical systems that usually involve 4 to 5 system
components can take several minutes to hours to compute. There have been
researches that proposed decomposing high dimensional systems into smaller
tractable sub-systems that can exactly compute [3] or overapproximate the BRT
in certain cases [4]. However, that challenge of applying HJ formulation on
real-time systems remains, as some systems cannot be decomposed further than
four dimensions, and over-approximation is introduced if projection methods
are used.

In this paper, we expand the limit of the number of dimensions for which we
could directly compute the BRT in _real time_ through the use of FPGA. We
would argue that customized hardware accelerators could complement well with
those decomposition methods in making higher dimensional systems provably safe
in real-time. As general-purpose computer no longer double its performance
every two years due to the end of Moore’s law, we have seen examples of
successful hardware accelerations in other areas such as machine learning’s
training/inference [5, 6, 7], robot’s motion planning[8].

In this paper, our contributions are as follows:

  * •

We prototype a customized hardware design on FPGA that accelerates HJ
reachability analysis to 16x compared to state-of-the-art implementation and
142x compared to [9] on 16-thread CPU for 4D system

  * •

We demonstrate that the system could meet real-time requirement of
guaranteeing safety in changing environments by re-computing BRT at 5Hz

  * •

Demonstrate obstacle avoidance with a robot car driving in an environment in
which new obstacles are introduced during run time at 5Hz.

##  II PRELIMINARIES

###  II-A Hamilton-Jacobi Reachability Analysis

Let $s\leq 0$ be time and $z\in\mathbb{R}^{n}$ be the state of an autonomous
system. The evolution of the system state over time is described by a system
of ordinary differential equations (ODE) below.

$\dot{z}=\derivative{z(s)}{s}=f(z(s),u(s),d(s))$ (1)

where $u(\cdot)$ and $d(\cdot)$ denote the control and disturbance function
respectively. The system dynamics $f$ are assumed to be uniformly continuous,
bounded and Lipschitz continuous in $z$ for fixed $u$ and $d$. Given
$u(\cdot)$ and $d(\cdot)$, there exists a unique trajectory that solves
equation (1).

The trajectory or solution to equation (1) is denoted as
$\zeta(s;z,t,u(\cdot),d(\cdot)):[t,0]\rightarrow\mathbb{R}^{n}$ , which starts
from state $z$ at time $t$ under control $u(\cdot)$ and disturbances
$d(\cdot)$. $\zeta$ satisfies (1) almost everywhere with initial condition
$\zeta(t;z,t,u(\cdot),d(\cdot))=z$.

In reachability analysis, we begin with a system dynamics described by an ODE
and a target set that represents unsafe states/obstacles [10]. We then solve a
HJ PDE to obtain Backward Reachable Tube (BRT), defined as follows:

$\displaystyle\bar{\mathcal{A}}=\\{z:\exists\gamma\in\Gamma,\forall
u(\cdot)\in\mathbb{U},\exists s\in[t,0],$ (2)
$\displaystyle\zeta(s;z,t,u(\cdot),d(\cdot))\in\mathcal{T}\\}$

In HJ reachability analysis, a target set
$\mathcal{T}\subseteq\mathcal{R}^{n}$ is represented by the implicit surface
function $V_{0}(z)$ as $\mathcal{T}=\\{z:V_{0}(z)\leq 0\\}$. The BRT is then
the sub-level set of a value function $V(z,s)$ defined as below.

$\displaystyle
V(z,s)=\min_{d(\cdot)}\max_{u(\cdot)\in\mathbb{U}}\min_{s\in[t,0]}V_{0}(\zeta(0;z,t,u(\cdot),d(\cdot)))$
(3)

We assume disturbance is applied with non-anticipative strategies[11]. In a
zero-sum differential game, the control input and disturbances have opposite
objectives.

The value function $V(z,s)$ can be obtained as the viscosity solution of this
HJ PDE:

$\begin{gathered}\min\\{D_{s}V(z,s)+H(z,\nabla V(z,s)),V(z,0)-V(z,s)\\}=0\\\
V(z,0)=l(z),s\in[t,0]\\\ H(z,\nabla
V(z,s))=\min_{\gamma[u](\cdot)}\max_{u(\cdot)}\nabla
V(z,s)^{T}f(z,u)\end{gathered}$ (4)

We compute the HJ PDE until it converges. Numerical toolboxes based on level
set methods such as [9] are used to obtain a solution on a multi-dimensional
grid for the above equation.

###  II-B Basic Numerical Solution

Let us store the value function on a multi-dimensional grid, with the
numerical solution of the value function denoted as $V$. Let $N_{d}$ be the
grid size on the $d$th axis ($1\leq d\leq 4$). We also let $x_{d,i}$ denote
the state of grid $i$ in dimension $d$. In our approach throughout this paper,
we will adopt the central differencing scheme for approximating derivatives in
dimension $d$, which is defined as follows:

$\begin{gathered}D_{d}^{-}V(x_{d,i})=\dfrac{V(x_{d,i})-V(x_{d,i-1})}{\Delta
x_{d}},\\\ D_{d}^{+}V(x_{d,i})=\dfrac{V(x_{d,i+1})-V(x_{d,i})}{\Delta
x_{d}},\\\
D_{d}V(x_{d,i})=\dfrac{D_{d}^{+}V(x_{d,i})+D_{d}^{-}V(x_{d,i})}{2}\end{gathered}$
(5)

The two terms $D_{d}^{-}$ and $D_{d}^{+}$ are the left and right
approximations respectively. Note that for grid points at each end of each
dimension (i.e $i=N_{d}-1$, $i=0$), (5) is computed with extrapolated points.
The basic algorithm for solving (4) on-grid for 4D systems is then described
as follows:

Algorithm 1 Value function solving procedures

1:$V_{0}[N_{1}][N_{2}][N_{3}][N_{4}]\leftarrow l(z)$

2://Compute Hamiltonian term, and max, min deriv

3:for $i=0:N_{1}-1$; $j=0:N_{2}-1$; $k=0:N_{3}-1$; $l=0:N_{4}-1$ do

4: Compute (5) for  $1\leq d\leq 4$

5: $minDeriv\leftarrow min(minDeriv,D_{d}V(x))$

6: $maxDeriv\leftarrow max(maxDeriv,D_{d}V(x))$

7: $\displaystyle u_{opt}\leftarrow\arg\max_{u\in\mathbb{U}}\nabla
V(z,s)^{\top}f(z,u)$

8: $\dot{x}\leftarrow f(z,u_{opt})$

9: $H_{i,j,k,l}\leftarrow\nabla V(z,s)^{\top}\dot{x}$

10:end for

11:// Compute dissipation and add to H

12:for $i=0:N_{1}-1$; $j=0:N_{2}-1$; $k=0:N_{3}-1$; $l=0:N_{4}-1$ do

13:
$\alpha_{d}(x)\leftarrow\max_{p\in[minDeriv,maxDeriv]}\absolutevalue{\dfrac{\partial
H(x,p)}{\partial p_{d}}}$

14: $H_{i,j,k,l}\leftarrow
H_{i,j,k,l}-\Sigma_{d=1}^{4}\alpha_{d}(x)\dfrac{D_{d}^{+}\check{(}x)-D_{d}^{-}\check{(}x)}{2}$

15: $\alpha_{d}^{max}\leftarrow max(\alpha_{d}^{max},\alpha_{d})$

16:end for

17://Compute stable integration time step

18:$\Delta
t\leftarrow(\Sigma_{d=1}^{4}\dfrac{\absolutevalue{\alpha_{d}^{max}}}{\Delta
x_{d}})^{-1}$

19:$V_{t+1}\leftarrow H\Delta{t}+V_{t}$

20:$V_{t+1}\leftarrow min(V_{0},V_{t+1})$

21:$\epsilon\leftarrow\absolutevalue{V_{t+1}-V_{t}}$

22:if $\epsilon<threshold$ then

23: $V_{t}\leftarrow V_{t+1}$

24: Go to line 3

25:end if

The above algorithm loops through the 4D array three times. In the first grid
iteration, the Hamiltonian terms, maximum and minimum derivative is determined
(lines 3-9). In the next grid iteration, the dissipation is computed and added
to the Hamiltonian in order to make the computation stable. At the same time,
the maximum alphas in all dimensions defined in line 13 are computed. These
$\alpha_{d}^{max}$ are used to determine the step bound $\Delta t$. In the
third grid iteration (line 19), each grid point is integrated for a length of
$\Delta t$.

Figure 1: 9 memory accesses (yellow + green colored grid) within each
iteration for computing derivatives in all 4 directions as in line 3
(algorithm 2)

In certain cases, $\alpha_{d}(x)$ in line 13 is the same as computing the
absolute value of $\dot{x}$, which has been computed in line 8. In addition,
in a lot of cases, $\alpha_{d}^{max}$ stays the same across different time
iterations. We also observed that $\Delta t$ depends only on grid
configuration and $\alpha_{d}^{max}$. So instead of re-computing $\Delta t$
every time and then loop through the 4D grid array again, we could pre-compute
$\Delta t$ and re-use it for all the time iterations. Combining these ideas
together, throughout this paper, we will use the following algorithm with one
grid looping, which is more computationally efficient:

Algorithm 2 Value function solving procedures

1:$V_{0}[N_{1}][N_{2}][N_{3}][N_{4}]\leftarrow l(z)$

2:for $i=0:N_{1}-1$; $j=0:N_{2}-1$; $k=0:N_{3}-1$; $l=0:N_{4}-1$ do

3: Compute (5) for  $1\leq d\leq 4$

4: $\displaystyle u_{opt}\leftarrow\arg\max_{u\in\mathbb{U}}\nabla
V(z,s)^{\top}f(z,u)$

5: $\dot{x}\leftarrow f(z,u_{opt})$

6: $H_{i,j,k,l}\leftarrow\nabla V(z,s)^{\top}\dot{x}$

7: $H_{i,j,k,l}\leftarrow
H_{i,j,k,l}-\Sigma_{d=1}^{4}\absolutevalue{\dot{x_{d}}}\dfrac{D_{d}^{+}(x)-D_{d}^{-}(x)}{2}$

8: $V_{t+1,(i,j,k,l)}\leftarrow
H_{i,j,k,l}\Delta{t}_{precomputed}+V_{t,(i,j,k,l)}$

9: $V_{t+1,(i,j,k,l)}\leftarrow min(V_{0,(i,j,k,l)},V_{t+1,(i,j,k,l)})$

10:end for

11:$\epsilon\leftarrow\absolutevalue{V_{t+1}-V_{t}}$

12:if $\epsilon<threshold$ then

13: $V_{t}\leftarrow V_{t+1}$

14: Go to line 2

15:end if

###  II-C Field Programmable Gate Arrays (FPGA)

FPGA are configurable intergrated circuits that are programmed for specific
applications using hardware description language (HDL).

Figure 2: System overview on FPGA (Right). The initial value array is first
transferred from DRAM to FPGA’s on-chip memory. The memory buffer then
distributes data to the 4 PEs to concurrently compute the new value function
at 4 consecutive grid points. The output from PE is then written back to DRAM.
Each fully pipelined PE outputs one grid point every clock cycle (Left).
Inside the PE, there are hardware components that sequentially solve algorithm
2

Computing platforms such as CPUs, GPUs, and FPGAs have a memory component and
computing cores. Compute cores must request and receive all the necessary data
from the memory component before proceeding with the computation. If the
memory component cannot provide all data accesses the application requires to
proceed at once, cores have to stall and wait, slowing down the computation.

Figure 3: Pipelining schedule of a single PE. The PE’s operation is an
assembly line where multiple grid points could be processed at the same time
at different stages. Each stage is physical hardware that computes specific
parts of algorithm 2. At a particular stage and a particular cycle, the PE is
busy computing a certain part of algorithm 2 for the grid point at the indices
shown. Note that for simplicity, the indices shown here are for a single PE
only.

Efficient systems need to have both fast computing cores and fast data
distributions from the memory. Depending on the application, the memory access
and computing pattern will vary. General-purpose CPU/GPU are often architected
towards a reasonable performance for a wide variety of applications, but
unoptimized for any particular application. FPGA chip, on the other hand,
provides programmable digital circuits to design customized computing core and
memory blocks. Thus, one can leverage knowledge about the details of the
computing workload to design an efficient system accordingly with FGPA. With
FPGA, one could control and achieve a higher degree of parallelism from the
digital hardware level at the cost of programmability.

###  II-D Problem Description

A key observation of algorithm 2 is that each new grid point $V_{t+1}$ could
be computed independently with each other within one time iteration and
therefore, in parallel. We could then leverage a high degree of parallelism on
FPGA by having many cores to update as many grid points concurrently as
possible.

However, before that, two challenges must be addressed. Firstly, memory blocks
need to efficiently distribute data to compute cores. In order for a loop
computation to proceed, each of these cores needs up to 9 data inputs (Fig 2.)
and a memory design needs to satisfy this. Secondly, a four-dimensional grid
takes up tens of megabytes in memory and therefore cannot be fully fit to
FPGA’s on-chip memory for fast access.

In this paper, our goal is twofold. First, we will discuss our hardware design
that can solve the above challenges and maximize parallel computation of
algorithm 2 while efficiently making use of FPGA’s on-chip memory. Next, we
will show that this enables low latency of computation on FPGA which could be
deployed in real-time systems.

##  III Solving the HJ PDE Using FPGAs

Before going into details of the design, we will introduce some terminologies
that will be relevant throughout the next section.

In digital systems, time is discretized into the unit of a _clock cycle_ ,
which is the amount of time it takes for an operation such as computing,
loading, and storing to proceed. Each clock cycle typically is a few
nanoseconds. Dynamic Random Access Memory (DRAM) is a type of memory that sits
outside of the FPGA, which has higher memory capacity but takes a lot more
clock cycles to access.

Our custom hardware comprised two main components: on-chip memory buffer, and
processing elements (PE) or computing cores (shown in Fig 2). The memory
buffer is on-chip storage, providing access to all the grid points a PE needs
to compute a new value function. Each PE is a digital circuit that takes 9
grid points from the memory buffer to compute a new value function at a
particular grid point according to algorithm 2 (line 3-10). In the following
subsections, we will go into the details of each component.

###  III-A Indexed Processing Element (PE)

The PE has the following target design objectives: (1) increase compute
throughput (defined as the number of output generated per second) through
pipelining, (2) reduce the computation time of each PE, (3) and ensure the
correctness of result while minimizing data transfer between DRAM and FPGA.

In our design, we use 4 PEs (as shown in figure 2). Each PE has an index $idx$
with $0\leq idx\leq 3$ associated with it and computes the grid point
$V_{t+1}(i,j,k,l+idx)$. At the beginning of the computation of algorithm 2,
each PE takes as input a grid index $(i,j,k,l)$ and its 8 neighbours to start
computing $V_{t+1}(i,j,k,l)$ according to algorithm 2 (line 2-10).

To increase computation throughput, each PE is fully pipelined. Similar to an
assembly line, the PE operation is divided into multiple stages taking a few
clock cycles to complete (Fig. 3). Each stage within the pipeline is physical
hardware that has a computation corresponding to one of the lines in algorithm
2 (line 3-10) for a particular index $i,j,k,l$. Every clock cycle, the result
from previous stages will be loaded to the next stage, following the
sequential order of algorithm 2. At any time during operations, the processing
element is computing different intermediate components for multiple indices
concurrently (explained in Fig.3).

To ensure that the computation is correct, inside each of the PE, there are
indices counters to keep track of loop variable $i,j,k,l$, with the inner loop
variable incrementing by one every clock cycle. These indices are used to
correctly address the state vectors during system dynamics computation. To
avoid accessing external DRAM we store these 4 state/position vectors $x$ or
any fixed non-linear functions such as $\cos(\cdot)$ and $\sin(\cdot)$ of
these states as a lookup table stored in on-chip memory, as state vectors
depend only on grid configuration and do not change with the environment. Each
PE will have its own look-up table to avoid communications between PEs. Having
this data on-chip will only require a few kilobytes of memory and no need to
access DRAM throughout the computation.

Figure 4: Four lines of memory buffer supply all the grid data to the four
PEs. Each of the rectangle blocks is a FIFO queue synthesized as Block RAM
(BRAM). The overhead notation is the size of the FIFO queue with
$N_{1},N_{2},N_{3},N_{4}$ as the four grid dimensions. Note that the queue’s
size depends only on three dimensions. Every clock cycle, new grid points
streamed from DRAM start entering each buffer line (left-hand side) and grid
points at the end of the lines are discarded (right-hand side).

###  III-B On-Chip Memory Buffer

The memory buffer has the following key design objectives: (1) minimizing the
amount of on-chip memory usage and external DRAM accesses while (2)
concurrently providing 9 grid points to each PE every clock cycle.

One problem of working with a high-dimensional grid is that the whole grid can
take up tens of megabytes and therefore cannot be fully fit to a state-of-the-
art FPGA’s on-chip memory. Instead of storing everything on-chip, in our
design, grid points are streamed continuously from DRAM into an on-chip memory
buffer (shown in Fig.2) and can be re-used many times for spatial derivatives
computation in 4 dimensions before being thrown away. From the grid
dimensions, we could compute the maximum reuse distance beyond which a grid
point can be safely discarded as no longer needed. This maximum reuse distance
is equal to the minimum size of on-chip memory buffer, which is dependent only
on $N-1$ dimensions [12] and can be fitted to an FPGA’s on-chip memory. Our
memory buffer structure is implemented as First In First Out (FIFO) queue data
structure. Every clock cycle, a new grid point supplied from DRAM will start
entering the FIFO queue while the grid point reaching at the end of the FIFO
queue will be discarded (shown in Fig. 4).

FPGA on-chip memory buffers are composed of standard Blocks of Random Access
Memory (BRAM). Each BRAM has two-ports and at most two reads can be requested
concurrently in the same clock cycle. If all 9 grid points (shown in Fig. 1)
are stored in the same BRAM at the same time, a PE would then have to wait for
5 clock cycles before performing the computation. One way to increase the
number of accesses per clock cycle is to duplicate the data in multiple BRAMs,
but this would not work well for multidimensional arrays since these array
copies easily exceed FPGA on-chip memory. A different technique would be
_memory banking_ , which is to partition the memory on-chip into multiple BRAM
that could concurrently deliver data to the PE, allowing the PE to start to
compute new value function for a grid point in one clock cycle.

To allow concurrent access for multiple PEs, we adopted the parallel memory
buffer microarchitecture from [12]. Corresponding to the number of PEs, our
on-chip storage structure is made of 4 line buffers. Each of these line
buffers is a sequence of BRAM connected acting in a queue fashion: a grid
point moves towards the end of the line every clock cycle. The two endpoints
of each BRAM (shown in Fig 4) provide tapping points that are connected as
inputs to the PEs. The number of PEs, therefore, is mainly limited by the DRAM
bandwidth.

We also made modifications to the execution flow in [13] to accommodate for
computing values function at the boundary. Once each of the buffer lines is
half full, all the processing elements can start computing a new value
function.

###  III-C Fixed-Point Representation

Computing a new value function based on algorithm 2 involves multiple addition
operations on floating-point numbers. At the hardware level, the addition of
floating-point numbers is as computationally expensive as fixed-point
multiplication, which would take up lots of resources and chip’s area.
Instead, we use fixed-point representations for our data to reduce the burden
on the hardware. We will show in the next section that this has little impact
on the correctness of the computation if the radix point is chosen carefully
for the grid configuration.

##  IV EXPERIMENT & RESULT

###  IV-A Experiment setup

In this section, we demonstrate that our system can meet the real-time
requirement through an obstacle avoidance demonstration in a changing
environment.

We used a Tamiya TT02 model RC car[14] controlled by an on-board Nvidia Jetson
Nano microcontroller inside a $4$m $\times$ $6$m room. We use the following
extended Dubins car model for its dynamics:

$\begin{split}\dot{x}&=v\cos(\theta)\\\ \dot{y}&=v\sin(\theta)\\\
\dot{v}&=a\\\ \dot{\theta}&=v\frac{\tan(\delta)}{L}\end{split}$ (6)

where $a\in\left[-1.5,1.5\right]$,
$\delta\in\left[-\frac{\pi}{18},\frac{\pi}{18}\right]$, and $L=0.3$m. The
control inputs are the acceleration $a$ and the steering angle $\delta$. We
use a grid size of $60\times 60\times 20\times 36$ with resolutions of $0.1$m,
$0.067$m, $0.2$m/s and $0.17$ rad for $x$-position, $y$-position, speed and
angle, respectively.

Inside the room, we use orange cones as obstacles and a motion capture system
is used to accurately track the car’s state and the position of the obstacles.
We initialize the initial value function as follows:

$V_{0}(x,y,v,\theta)=\sqrt{(x-x_{o})^{2}+(y-y_{o})^{2}}-R$ (7)

where $x_{o}$ and $y_{o}$ are the obstacle’s positions and R is the radius of
the cone. Obstacle’s positions can be obtained from the motion capture system.
Each of the cones has a radius of $0.08$m but is set as $0.75$m to account for
the model mismatch between the car and the dynamics used.

For the experiment, we considered three different environments, with different
cone placements, set up inside the room as shown in Fig. 5. For each
environment, a user manually controls the car and tries to steer into the
cones.

$V(x,y,v,\theta)<0.15$ (8)

Given the car’s state, when (8) is satisfied, the car is near the boundary of
a BRT so optimal control computed from the value function is applied to safely
avoid the cone. The optimal control is obtained from the value function as
follows:

$u_{opt}=\arg\max_{u\in\mathbb{U}}\nabla
V(x,y,v,\theta,s)^{\top}f(x,y,v,\theta,u)$ (9)

(a) Environment 1

(b) Environment 2

(c) Environment 3

Figure 5: Different BRTs are used as the placement of cones change over time
which limits where the RC car can be as it drives around the room.

We pre-compute the BRTs with a horizontal time of $0.5$s for three
environments using optimized_dp[15] and demonstrate safety by correctly
loading the value functions as the environment changes. We choose to pre-
compute the BRTs in order to emulate having an FPGA on-board without extra
latency resulted from communication with a remote AWS instance. For all
environments, the maximum time step to make the integration stable is
$0.007497$s. Initially, the room had a single cone but changed over time to
different cone placements. The BRT of a new environment could not be used
until 200ms after the environment has changed, which is longer than the time
taken to compute the same BRT on an FPGA. A video of these experiments can be
found at
https://www.youtube.com/playlist?list=PLUBop1d3Zm2vgPL4Hxtz8JufnIPmvrwlC

###  IV-B Hardware Correctness

We use fixed-point data representations for hardware computation. In
particular, we use 32 bits with 5 bits to represent the integer part
(including sign) and 27 bits for the decimal part. With this choice, the
precision of our computation is $2^{-27}=7.45\times 10^{-9}$ and the range of
our computation is from $-16$ to $16$. The area we use for the experiment is
$4$m $\times$ $6$m, hence the largest absolute distance is the diagonal of
$7.2$m. Therefore, the number of integer bits is enough to represent all
possible values in the solution $V$, which has the physical interpretation of
minimum distance to collision over time, given (3) and the choice of $V_{0}$
in (7).

We choose to synthesize and implement our design on AWS F1 FPGA because of its
flexibility and availability. To correctly input data to the FPGA, we first
generate an initial value array based on the obstacles’ positions and radius
described by (7). Then this value array is converted from floating-point to
fixed-point number correctly based on the bit choice discussed above.
Afterward, the value array is passed to the FPGA for the HJ PDE solving
procedure to start.

For all three experiment, we verified the correctness of BRT generated by our
hardware with the toolbox at [15] by comparing the maximum error between
corresponding grid points. The toolbox uses 32-bit floating-point numbers. The
numerical error resulting from the different representations is shown in table
below for the three environments in table I.

TABLE I: ERROR COMPARISON

| Env. 1 | Env. 2 | Env. 3
---|---|---|---
Error | $1.68\times 10^{-6}$ | $1.78\times 10^{-6}$ | $1.37\times 10^{-6}$

These negligible errors are due to precision difference between fixed-point
and floating point number. Even though the computation is repeated for many
iterations, the maximum error does not grow dramatically over time. We believe
that is because of the convergence property of BRT. As time grows, the rate of
changes in the grid values also slows down leading to stable discrepancy
between the correct floating point and fixed-point values.

###  IV-C Computational speed and Resources Usage

To measure the speed up for all three environments, we compare the computation
time on AWS FPGA running at 250MHz against [15] and [9] running on a 16-thread
Intel(R) Core(TM) i9-9900K CPU at 3.60GHz. The latency here is the time it
takes to compute the BRT. For FPGA, latency can be computed by multiplying the
clock cycles with the clock period. The result is summarized in the table
below.

TABLE II: FPGA

|  Clock cycles |  Period | Iterations | Latency
---|---|---|---|---
Env. 1 | 44155209 | 4 ns | 67 | 0.176s
Env. 2 | 44155209 | 4 ns | 67 | 0.176s
Env. 3 | 44155209 | 4 ns | 67 | 0.176s

TABLE III: optimized_dp[15]

|  Latency | Iterations | FGPA speed up
---|---|---|---
Env. 1 | 3.35 s | 67 |  $\times$18.9
Env. 2 | 2.99 s | 67 |  $\times$17
Env. 3 | 3.42 s | 67 |  $\times$19.4

TABLE IV: ToolboxLS[9]

|  Latency | Iterations | FPGA speed up
---|---|---|---
Env. 1 | 25.11 s | 70 |  $\times$142
Env. 2 | 25.14 s | 70 |  $\times$142
Env. 3 | 25.18 s | 70 |  $\times$142

It can be observed that the latency of computation on FPGA is fixed and
deterministic for all three environments while the latency on CPUs varies even
though the computation remains the same. With the lower latency of $0.176$s,
we are able to update the value function at a frequency of $5.68$Hz. The
resources usage of our design for 4 PEs is shown in the table below.

|  LUT | BRAM | DSP
---|---|---|---
Used | 26319 | 519 | 598
Available | 111900 | 1680 | 5640
Utilization | 14.03% | 30.89% | 10.6%

On an FPGA, arithmetic operations on numbers are implemented using Digital
Signal Processing (DSP) hardware or Look Up Table (LUT) that perform logical
functions. Our design does not significantly consume most of the available
resources and could be scaled up to a larger grid size.

##  V CONCLUSION

This paper introduces a novel customized hardware design on FPGA that allows
HJ reachability analysis to be computed $16$x faster than state-of-the-art
implementation on a 16-thread CPU. Because of that, we are able to solve the
HJ PDE at a frequency of 5Hz. The latency of our computation on FPGA is
deterministic for all computation iterations, which is crucial for safety-
critical systems. Our design approach presented here can be applied to system
dynamics and potentially higher dimensional systems. Finally, we demonstrate
that at 5Hz, a robot car can safely avoid obstacles and guarantee safety.

## References

  * [1] A. K. Akametalu, C. J. Tomlin, and M. Chen, “Reachability-based forced landing system,” Journal of Guidance, Control, and Dynamics, vol. 41, no. 12, pp. 2529–2542, 2018.
  * [2] M. Chen, Q. Hu, C. Mackin, J. F. Fisac, and C. J. Tomlin, “Safe platooning of unmanned aerial vehicles via reachability,” in 2015 54th IEEE Conference on Decision and Control (CDC), pp. 4695–4701, 2015.
  * [3] M. Chen, S. L. Herbert, and C. J. Tomlin, “Exact and efficient hamilton-jacobi guaranteed safety analysis via system decomposition,” in 2017 IEEE International Conference on Robotics and Automation, ICRA 2017, Singapore, Singapore, May 29 - June 3, 2017, pp. 87–92, IEEE, 2017.
  * [4] A. Li and M. Chen, “Guaranteed-safe approximate reachability via state dependency-based decomposition,” in 2020 American Control Conference (ACC), pp. 974–980, 2020.
  * [5] N. P. Jouppi, C. Young, N. Patil, D. Patterson, G. Agrawal, R. Bajwa, S. Bates, S. Bhatia, N. Boden, A. Borchers, R. Boyle, P.-l. Cantin, C. Chao, C. Clark, J. Coriell, M. Daley, M. Dau, J. Dean, B. Gelb, T. V. Ghaemmaghami, R. Gottipati, W. Gulland, R. Hagmann, C. R. Ho, D. Hogberg, J. Hu, R. Hundt, D. Hurt, J. Ibarz, A. Jaffey, A. Jaworski, A. Kaplan, H. Khaitan, D. Killebrew, A. Koch, N. Kumar, S. Lacy, J. Laudon, J. Law, D. Le, C. Leary, Z. Liu, K. Lucke, A. Lundin, G. MacKean, A. Maggiore, M. Mahony, K. Miller, R. Nagarajan, R. Narayanaswami, R. Ni, K. Nix, T. Norrie, M. Omernick, N. Penukonda, A. Phelps, J. Ross, M. Ross, A. Salek, E. Samadiani, C. Severn, G. Sizikov, M. Snelham, J. Souter, D. Steinberg, A. Swing, M. Tan, G. Thorson, B. Tian, H. Toma, E. Tuttle, V. Vasudevan, R. Walter, W. Wang, E. Wilcox, and D. H. Yoon, “In-datacenter performance analysis of a tensor processing unit,” in Proceedings of the 44th Annual International Symposium on Computer Architecture, ISCA ’17, (New York, NY, USA), p. 1–12, Association for Computing Machinery, 2017.
  * [6] Y. Chen, T. Krishna, J. S. Emer, and V. Sze, “Eyeriss: An energy-efficient reconfigurable accelerator for deep convolutional neural networks,” IEEE Journal of Solid-State Circuits, vol. 52, no. 1, pp. 127–138, 2017.
  * [7] S. Han, X. Liu, H. Mao, J. Pu, A. Pedram, M. A. Horowitz, and W. J. Dally, “Eie: Efficient inference engine on compressed deep neural network,” in 2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA), pp. 243–254, 2016.
  * [8] S. Murray, W. Floyd-Jones, Y. Qi, G. Konidaris, and D. Sorin, “The microarchitecture of a real-time robot motion planning accelerator,” pp. 1–12, 10 2016.
  * [9] I. Mitchell, “The flexible, extensible and efficient toolbox of level set methods,” J. Sci. Comput., vol. 35, pp. 300–329, 06 2008.
  * [10] M. Chen and C. J. Tomlin, “Hamilton–Jacobi Reachability: Some Recent Theoretical Advances and Applications in Unmanned Airspace Management,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 1, no. 1, pp. 333–358, 2018.
  * [11] S. Bansal, M. Chen, S. Herbert, and C. J. Tomlin, “Hamilton-jacobi reachability: A brief overview and recent advances,” in 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp. 2242–2253, IEEE, 2017.
  * [12] Y. Chi, J. Cong, P. Wei, and P. Zhou, “Soda: Stencil with optimized dataflow architecture,” in 2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pp. 1–8, 2018.
  * [13] J. Cong, P. Li, B. Xiao, and P. Zhang, “An optimal microarchitecture for stencil computation acceleration based on non-uniform partitioning of data reuse buffers,” in 2014 51st ACM/EDAC/IEEE Design Automation Conference (DAC), pp. 1–6, 2014.
  * [14] NVIDIA-AI-IOT, “Jetracer.”  Available at https://github.com/NVIDIA-AI-IOT/jetracer.
  * [15] M. Bui, “Optimized dynamic programming,” 2020.  Available at https://github.com/SFU-MARS/optimized_dp.