Marcus L Endicott BSc MCI is available for consultation on this topic at patreon.com/mendicott

State Machine & Dialog Systems

State Machines: The Discrete Engine Driving Dialog Interaction

State machines are integral components underlying many dialog systems, enabling them to model conversational flow, interpret user intent, and manage interactions. A state machine refers to a system with a finite number of stable states and defined transitions between those states dictated by inputs and the current state. They are useful for representing systems that exhibit complex yet structured behavior.

In dialog systems, state machines play an essential role in tracking discourse state, coordinating dialogue policy, and guiding system responses. Simple dialog systems may rely on frame-based approaches and slot-filling driven by a state machine. More advanced systems integrate state machines with neural and statistical models for enhanced flexibility.

State machines have several key advantages for dialog systems:

  1. They provide formal models for mapping out conversational workflows, states like greetings and information provision, and transition logic. This helps dialog designers structure coherent dialog policies and system behavior.
  2. State machines enable managing multi-turn conversations by retaining session state. This allows tracking user intents and requests across multiple exchanges.
  3. They allow integrating domain knowledge and task workflows into the dialog manager through states and transition rules. This facilitates goal-oriented interactions.
  4. State machines help coordinate output and responses by triggering actions associated with states. This provides a control mechanism for dialog systems.

Recent research has led to innovations like probabilistic state machines with data-driven transitions for better scalability and language-independence. Reinforcement learning helps optimize policies and produce human-like conversations. Incremental processing facilitates real-time turn-taking. And multi-modal state machines integrate different input events into a unified interaction workflow.

Applications of state machine-based dialog systems include goal-oriented scenarios like form-filling, transactions, and queries. They also enable social dialog agents and conversational assistants. When paired with virtual characters, they facilitate lifelike interactions spanning information provision, questioning, and chitchat ability.

In summary, state machines enable organizing dialog systems into coherent structures tracking user intent, managing discourse history, providing responses, and coordinating interaction flow. Advancements focus on statistically-learned transitions, neural representations, and multi-modal integration to enhance conversational ability. These systems aim to sustain engaging information-seeking and social dialog at scale.

Wikipedia:

See also:

100 Best Amazon Sumerian Tutorials | 100 Best Amazon Sumerian Videos | 100 Best State Machine Videos | 100 Best Unity3d Dialog System Videos | Augmented Transition Network & Dialog Systems | Behavior Analyzers | Multi-agent System Development Kit (MASDK) | Robot Control Schemes | SceneMaker

  • Aggarwal, M., Arora, A., & Sodhani, S. (2018). Improving Search Through A3C Reinforcement Learning Based Conversational Agent. In International Conference on Neural Information Processing (pp. 213-223). Springer, Cham.
  • Albertengo, G., & Di Vittorio, R. (2018). Chatbot integration within Sitecore Experience Platform.
  • Anantaram, C., Sangroya, A., Saini, P., & Rawat, M. (2018). Automatic Extraction of Domain Specific Latent Beliefs in Customer Complaints to Help Tailor Chatbots. In Workshops at the Thirty-Second AAAI Conference on Artificial Intelligence.
  • Baudart, G., Dolby, J., Duesterwald, E., & Hirzel, M. (2018). Protecting chatbots from toxic content. In Proceedings of the 2nd Workshop on Abusive Language Online (pp. 92-97).
  • Baudart, G., Hirzel, M., Mandel, L., & Shinnar, A. (2018). Reactive chatbot programming. In Proceedings of the 5th ACM SIGPLAN International Workshop on Reactive and Event-Based Languages and Systems (pp. 22-29).
  • Baumann, T. (2018). Attentive Speaking. From Listener Feedback to Interactive Adaptation.
  • Bickmore, T., Trinh, H., Asadi, R., & Olafsson, S. (2018). Safety First: Conversational Agents for Health Care. In Studies in Conversational UX Design. Springer.
  • Buoncompagni, L., Ghosh, S., & Moura, M. (2018). A Scalable Architecture to Design Multi-modal Interactions for Qualitative Robot Navigation. In International Conference of the Italian Association for Artificial Intelligence (pp. 494-508). Springer, Cham.
  • Buschmeier, H. (2018). Attentive Speaking. From Listener Feedback to Interactive Adaptation.
  • Celikyilmaz, A., He, X., & Deng, L. (2018). Deep learning in conversational language understanding. In Deep Learning in Natural Language Processing (pp. 127-152). Springer, Singapore.
  • Chhabra, A., Saini, P., Sangroya, A., & Goyal, V. (2018). Learning Latent Beliefs and Performing Epistemic Reasoning for Efficient and Meaningful Dialog Management. arXiv preprint arXiv:1805.04678.
  • Cutugno, F., & Rossi, S. (2018). A Scalable Architecture to Design Multi-modal Interactions for Qualitative Robot Navigation. In International Conference of the Italian Association for Artificial Intelligence (pp. 494-508). Springer, Cham.
  • Daniel, F., Baez, M., Casati, F., & Svetlana, N. (2018). Crowdsourcing for Reminiscence Chatbot Design. In Conference on Human Factors in Computing Systems.
  • Deng, L., & Liu, Y. (Eds.). (2018). Deep learning in natural language processing. Springer.
  • Dziri, N. (2018). Response Generation For An Open-Ended Conversational Agent (Doctoral dissertation).
  • Emam, S. S., & Miller, J. (2018). Inferring Extended Probabilistic Finite-State Automaton Models from Software Executions. ACM Transactions on Software Engineering and Methodology, 27(3), 1-37.
  • Ernst, G. (2018). Permugram Language Models. University of Jena.
  • Fadhil, A. (2018). Can a Chatbot Determine My Diet?: Addressing Challenges of Chatbot Application for Meal Recommendation. arXiv preprint arXiv:1802.09100.
  • Fernández-Rodicio, E., Castro-González, Á., González Mollineda, R. A., & Martinez, F. J. (2018). Composable Multimodal Dialogues Based on Communicative Acts. In International Conference on Social Robotics (pp. 601-612). Springer, Cham.
  • Flokstra, J., Bruijnes, M., op den Akker, H. J., van Waterschoot, J., Dosis, A., Logan, V., … & Visser, T. (2018). Flipper 2.0: A Pragmatic Dialogue Engine for Embodied Conversational Agents. In Proceedings of the 18th International Conference on Intelligent Virtual Agents (pp. 131-137).
  • Gao, Y., Yang, F., Frisk, M., Hernandez, D., & Peters, C. A. (2018). Social Behavior Learning with Realistic Reward Shaping. arXiv preprint arXiv:1808.02144.
  • Gaudl, S. E. (2018). Agile Behaviour Design: A Design Approach for Structuring Game Characters and Interactions. arXiv preprint arXiv:1803.01631.
  • Ghosh, S., Buoncompagni, L., & Moura, M. (2018). A Scalable Architecture to Design Multi-modal Interactions for Qualitative Robot Navigation. In International Conference of the Italian Association for Artificial Intelligence (pp. 494-508). Springer, Cham.
  • Green Jr, N. L., & Lehman, J. F. (2018). An Integrated Architecture for Discourse: Generation, Interpretation, and Recipe Acquisition.
  • Griol, D., & Callejas, Z. (2018). Increasing the Role of Data Analytics in m-Learning Conversational Applications. In Software Data Engineering for Network eLearning Environments (pp. 109-129). IGI Global.
  • Grossman, J., Lin, Z., Sheng, H., Wei, J. T., & Williams, J. J. (2018). MathBot: Transforming Online Resources for Learning Math into Conversational Interactions.
  • Götzer, J. (2018). Engineering and user experience of chatbots in the context of damage recording for insurance companies.
  • Han, T. (2018). Learning to Interpret and Apply Multimodal Descriptions.
  • Hasler, E., Orr, R., & Tappe, H. (2018). Learning complex grammars with gated recursive units. arXiv preprint arXiv:1807.07511.
  • Hunter, A. (2018). Towards a framework for computational persuasion with applications in behaviour change. Argument & Computation, 9(2), 89-126.
  • Iosif, E., Klasinas, I., Athanasopoulou, G., Potamianos, A., & Narayanan, S. (2018). Speech understanding for spoken dialogue systems: From corpus harvesting to grammar rule induction. Computer Speech & Language, 47, 272-297.
  • Janarthanam, S. (2017). Hands-on chatbots and conversational UI development: Build chatbots and voice user interfaces with ChatFuel, Dialogflow, Microsoft Bot Framework, Lex, Alexa Skills, and Google Actions. Packt Publishing Ltd.
  • Jiang, C. (2018). The Performance Optimization of LTE Multimedia Broadcast Multicast Services Based on RObust Header Compression (Doctoral dissertation).
  • Joseph, A. C., & Srivastava, S. R. (2018). Stack Automata-Based Framework for Behavior Modeling of Virtual Agents. In Proceedings of First International Conference on Smart Systems, Innovations and Computing (pp. 539-550). Springer, Singapore.
  • Kawahara, T. (2018). Spoken dialogue system for a human-like conversational robot ERICA. In Proceedings of the IWSDS.
  • Khatri, C., Hedayatnia, B., Venkatesh, A., Nunn, J., Pan, Y., Liu, H., … & Gabriel, R. (2018). Advancing the state of the art in open domain dialog systems through the alexa prize. arXiv preprint arXiv:1812.10757.
  • Khatri, C., Venkatesh, A., Hedayatnia, B., Ram, A., Prasad, R., Cheng, M., … & Gabriel, R. (2018). Alexa prize: State of the art in conversational AI. AI Magazine, 39(4), 40-60.
  • Khouzaimi, H., Laroche, R., & Lefèvre, F. (2018). A methodology for turn-taking capabilities enhancement in Spoken Dialogue Systems using Reinforcement Learning. Computer Speech & Language, 47, 98-126.
  • Kim, S., Salter, D., DeLuccia, L., Son, K., & Amer, M. R. (2018). SMILEE: Symmetric Multi-modal Interactions with Language-gesture Enabled (AI) Embodiment. In Proceedings of the 19th ACM International Conference on Multimodal Interaction (pp. 567-571).
  • Lara-Cabrera, R., González-Fierro, M., Buisán, D., & Camús, A. (2018). Dialogue system based on topic identification for robot Pepper. In International Work-Conference on the Interplay Between Natural and Artificial Computation (pp. 497-506). Springer, Cham.
  • Larionov, G., Kaden, Z., Dureddy, H. V., & Rigoll, G. (2018). Tartan: A retrieval-based socialbot powered by a dynamic finite-state machine architecture. arXiv preprint arXiv:1809.10730.
  • Lehman, J., & Green, N. (2018). An integrated architecture for generating discourse: interpretation, acquisition and generation. In Proceedings of the Thirteenth Workshop on Innovative Use of NLP for Building Educational Applications (pp. 188-198).
  • Litman, D. J., Strik, H., & Lim, G. S. (2018). Speech technologies and the assessment of second language speaking: Approaches, challenges, and opportunities. Language Assessment Quarterly, 15(4), 375-389.
  • Liu, B. (2018). Learning Task-Oriented Dialog with Neural Network Methods.
  • Luz, S. (2018). Partitioning POMDPs for multiple input types, and their application to dialogue managers.
  • Mallios, S. (2018). Virtual Doctor: An Intelligent Human-Computer Dialogue System for Quick Response to People in Need.
  • Mastrogiovanni, F. (2018). A Scalable Architecture to Design Multi-modal Interactions for Qualitative Robot Navigation. In AI* IA 2018–Advances in Artificial Intelligence (pp. 264-277). Springer, Cham.
  • Mathews, A. P. (2018). Automatic Image Captioning with Style (Doctoral dissertation, Australian National University).
  • Mensio, M., Rizzo, G., & Morisio, M. (2018). Multi-turn qa: A rnn contextual approach to intent classification for goal-oriented systems. In Companion of the The Web Conference 2018 on The Web Conference 2018 (pp. 487-494).
  • Miao, N., Zhou, H., Mou, L., Yan, R., & Li, L. (2018). CGMH: Constrained Sentence Generation by Metropolis-Hastings Sampling. arXiv preprint arXiv:1811.10996.
  • Mislevics, A., Grundspenkis, J., & Rollande, R. (2018). A Systematic Approach to Implementing Chatbots in Organizations–RTU Leo Showcase. In International Baltic Conference on Databases and Information Systems (pp. 32-46). Springer, Cham.
  • Morrison, H. M., & Martens, C. (2018, April). How Was Your Weekend? A Generative Model of Phatic Conversation. In Thirty-First International Flairs Conference.
  • Nguyen, D. C. (2018). Learning socio-communicative behaviors of a humanoid robot by demonstration (Doctoral dissertation).
  • Nikitina, S., Daniel, F., Baez, M., & Casati, F. (2018). Crowdsourcing for Reminiscence Chatbot Design. arXiv preprint arXiv:1805.12346.
  • Nixon, M., DiPaola, S., & Bernardet, U. (2018, July). An Eye Gaze Model for Controlling the Display of Social Status in Believable Virtual Humans. In 2018 IEEE Conference on Computational Intelligence and Games (CIG) (pp. 1-8). IEEE.
  • Odriozola, I., Hernaez, I., & Navas, E. (2018). An on-line VAD based on Multi-Normalisation Scoring (MNS) of observation likelihoods. Expert Systems with Applications, 97, 353-366.
  • Ohlenbusch, M., Bartner, N. F., Vöge, S., & Gollhofer, A. (2018). Installation and Control of Building Automation Systems Using Human-Robot-Interaction. In International Conference on Methods and Models in Automation and Robotics (MMAR) (pp. 1030-1035). IEEE.
  • Pandey, M. (2018, June). Machine learning and systems for building the next generation of EDA tools. In Proceedings of the 23rd Asia and South Pacific design automation conference (pp. 573-578).
  • Park, Y., Kang, S., & Seo, J. (2018). An Efficient Framework for Development of Task-Oriented Dialog Systems in a Smart Home Environment. Sensors, 18(5), 1581.
  • Pecune, F., Chen, J., Matsuyama, Y., & Cassell, J. (2018, June). Field trial analysis of socially aware robot assistant. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (pp. 1851-1858). International Foundation for Autonomous Agents and Multiagent Systems.
  • Perera, I., Allen, J., Teng, C. M., & Galescu, L. (2018). A Situated Dialogue System for Learning Structural Concepts in Blocks World. In Proceedings of the 19th Annual SIGdial Meeting on Discourse and Dialogue (pp. 370-380).
  • Petrenko, S. A. (2018). Possible Scientific-Technical Solutions to the Problem of Giving Early Warning. In Big Data Technologies for Monitoring of Computer Networks (pp. 3-26). Springer, Cham.
  • Plch, T. (2018). Belieavable decision making in large scale open world games for ambient characters (Doctoral Dissertation, Charles University).
  • Prabhumoye, S., Tsvetkov, Y., Salakhutdinov, R., & Black, A. W. (2018). Style transfer through back-translation. arXiv preprint arXiv:1804.09000.
  • Ranzenberger, T., Hacker, C., & Gallwitz, F. (2018, September). Integration of a Kaldi speech recognizer into a speech dialog system for automotive infotainment applications. In Proc. Elektronische Sprachsignalverarbeitung (ESSV) (pp. 200-206).
  • Reshmi, S., & Balakrishnan, K. (2018). Empowering Chatbots With Business Intelligence By Big Data Integration. International Journal of Advanced Research in Computer Science, 9(2).
  • Reshmi, S., & Balakrishnan, K. (2018). Enhancing Inquisitiveness of Chatbots Through NER Integration. In 2018 International Conference on Advances in Computing, Communications and Informatics (ICACCI) (pp. 1270-1276). IEEE.
  • Rioja del Rio, H., Odriozola, I., Sagüés, C., Lleida Solano, E., Huerta, J. M., & Miguel Sánches, A. (2018). An on-line VAD based on Multi-Normalisation Scoring (MNS) of observation likelihoods. EHU.
  • Ripoll Galán, L. (2018). ScripTale: generation of procedural narrative (Bachelor’s thesis, Universitat Politècnica de Catalunya).
  • Roemmele, M. (2018). Neural networks for narrative continuation. arXiv preprint arXiv:1806.04093.
  • Saeed, A. A., & D?nciulescu, D. (2018). Modern interfaces for knowledge representation and processing systems based on markup technologies. International Journal of Information and Software Technology, 104, 72-83.
  • Saju, C. J., & Ravimaran, S. (2018). Efficient Extraction of Named Entities from New Domains Using Big Data Analytics. Journal of Computational and Theoretical Nanoscience, 15(8-9), 2780-2785.
  • Sangroya, A., Anantaram, C., Saini, P., & Rawat, M. (2018). Extracting Latent Beliefs and using Epistemic Reasoning to Tailor a Chatbot. In Twenty-Seventh International Joint Conference on Artificial Intelligence.
  • Santos, T. P., Rocha, A. P., Cardoso, A., & Oliveira, E. (2018). Towards a Custom Data-Driven Natural Language Generation for a Social Robot. In International Joint Conference on Neural Networks (IJCNN) (pp. 1-8). IEEE.
  • Sawada, K. (2018). A Statistical Approach To Speech Synthesis And Image Recognition Based On Hidden Markov Models (Doctoral dissertation).
  • Shah, P., Hakkani-Tür, D., Tur, G., Rastogi, A., Bapna, A., Nayak, N., & Heck, L. (2018). Building a conversational agent overnight with dialogue self-play. arXiv preprint arXiv:1801.04871.
  • Sidner, C. L., Bickmore, T., Nooraie, B., Rich, C., Pera, M. S., & Lesh, N. (2018). Creating new technologies for companionable agents to support isolated older adults. ACM Transactions on Interactive Intelligent Systems (TiiS), 8(3), 1-45.
  • Sinha, S., Agrawal, S. S., & Jain, A. (2018). Continuous density hidden markov model for hindi speech recognition. GSTF Journal on Computing (JoC), 5(1).
  • Skantze, G., & Schlangen, D. (2009, March). Incremental dialogue processing in a micro-domain. In Proceedings of the 12th Conference of the European Chapter of the ACL (EACL 2009) (pp. 745-753).
  • Smith, J. E. (2018). Space-time algebra: a model for neocortical computation. In Proceedings of the 45th Annual International Conference on the Architecture of Computing Systems (pp. 1-8).
  • Srivastava, S. R., & Joseph, A. C. (2018). Stack Automata-Based Framework for Behavior Modeling of Virtual Agents. In Proceedings of First International Conference on Smart Systems, Innovations and Computing (pp. 539-550). Springer, Singapore.
  • Sticht, M. (2018). Proof Search in Multi-Agent Dialogues for Modal Logic.
  • Valente, M. T., Paixão, K., Hafner, D., Tran, D., Irpan, A., et al. (2018). CSIndexbr: Exploring the Brazilian Scientific Production in Computer Science. arXiv preprint arXiv:1809.09429.