Overhearing, Plan Recognition and the YOYO Algorithm - Research Paper Example

Running Head: Overhearing, Plan Recognition and the YOYO algorithm Overhearing, Plan Recognition and the YOYO algorithm - Converting Tacit Knowledge to Explicit in organizations Research Proposal (Style: APA) Writer ID #: 19714 Order No. 323725 11 November 2009 Table of Contents: Introduction 2 Objectives of the Study and Research Questions 6 Brief Literature Review 8 The Research Design and Methodology 16 Research Ethics 17 Research Time Table 17 Table of Figures: S.No. Word Hyperlink Figure 1 Overhearing Architecture (Aiello and Busetta et al. 2001. p.177) Figure 2 Most Active versus Most Important communications that are overheard and plotted (Source: Gutnik and Kaminka. 2006. p.298) Figure 3 Overhearing strategies plotted as a function of the value of conversation types (Gutnik and Kaminka. 2006. p.299) Table of Tables: S.No. Word Hyperlink Table 1 Research Time Table Introduction In the modern era of stringent global competition, businesses are finding it increasingly difficult to sustain their competitive advantages in the marketplaces. Off late business owners have realized the immense benefits of knowledge management practices to sustain competitive advantages and hence have invested in tools and techniques to capture, organize, disseminate and reuse knowledge related to their businesses. However, one of the major challenges in implementation of knowledge management is that companies have ended up compiling huge repositories of information but have not been able to convert them into effective knowledge management systems. In this context the application of Artificial Intelligence technologies in knowledge management has been recognized as a major area of research especially in the areas of tacit to explicit knowledge conversion, speech to text conversion and information indexing, knowledge retrieval from text/data mining, intelligent knowledge search engines, etc. [Liebowitz, J. 2001. p.1-6] A research by Kaminka and Pynadath (2002. p.83-91) presented techniques of on-line monitoring of teams using a method of "overhearing" whereby their communication exchanges during business transactions are captured in computer systems and the learning of the agents are captured under three categories - No Learning, On-Line Learning and Using Previously Learned Predictions. They called the system as "Overseer" that can be effectively used to compare the performance gaps between novice agents and expert agents. The system could be used for performance evaluations of individuals as well as groups carrying out business transactions in any domain of the world. The researchers deployed two different hierarchies in the system - A team hierarchy and a plan hierarchy. The team hierarchy comprises of people fitting into the roles required to deliver tasks defined in the plan hierarchy. Hence, every individual in a role is expected to "execute a plan". They modeled the ground operations of an international airport whereby the human agents were allowed to query about the status of a plan and the future course of the plan in progress thus dealing with obstacles coming on the way of a plan. They querying was normally carried out by people in higher hierarchies and the plan reporting carried out by people in lower hierarchies. The learning about steps taken for plan executions were recorded in a plan library. They developed a probabilistic model of quantitative evaluation of the plan by plotting a time series of the plan state variables whereby all plans are represented by a set of Boolean random variables in such a way that the variable is true only if an agent is able to execute it at time "t". Thereafter the performance "belief" about an agent was plotted as a probability distribution with Markov property over all the variables within the set and was termed as Dynamic Belief Network (DBN). The start of a plan is overheard through initiation messages by the reporter and termination of plan overheard through termination messages by the reporter when the status of the plan is queried by the higher up. Hence, the system was dependent upon the truthfulness of the reporters and, to some extent, the knowledge of their social interactions. They designed an algorithm called YOYO that depends upon the plan hierarchy to predict the following plan that the agents are expected to choose. Decision making by overhearing agent conversations was introduced by Aiello and Busetta et al. (2001. p.177-178) which is presented in its simplest form in the figure below: Figure 1: Overhearing Architecture (Aiello and Busetta et al. 2001. p.177) In this model, the third agent acting as the over hearer possesses good knowledge about the two agents collaborating and hence can value add to the collaboration process. In this model, the over hearer agent possesses a built in parser using Java based BDI platform that collects the keywords from the conversation after it is converted to text and then logs the keywords in a log database. The keywords are then matched with a knowledge database such that additional information pertaining to the keywords can be fetched and suggested to the collaborating agents. One simple example is - proposing additional search parameters to the collaborators that may be trying to search for some information. Kaminka and Pynadath used their work to develop the over-hearing system with performance evaluation YOYO algorithm using the Plan Recognition Bayesian Networks developed by Charnaik and Goldman et al. (1993. p.60-61) which recognizes the probability of a plan as "1" if at least one of the plans in the plan hierarchy network is true. Becerra-Fernandez (2000. p.315-320) presented a research on application of artificial intelligence in finding experts in a large organization that can contribute to a purpose - like solving a problem, contribution to a project, consultation, etc. The system presented by the author correlates subject matter knowledge recorded in a knowledge management system with the communications over E-Mails and textual versions of recorded speech pertaining to the subject matter and converts then into relational information after carrying out essential cleansing. The search interface of the system can be used to locate people in the organization that can be chosen for the purpose. The authors discussed a number of people finder KM tools that can be used effectively for the purpose. I propose to build further on the over-hearing technique and the YOYO algorithm to carry out research on the systems and methodologies that uses plan recognition. I intend to present a system of plan recognition that can be implemented in business process management in the back-office of an organization - like loan processing system of a bank. To present the system, I will carry out literature review on the existing overhearing techniques, the YOYO algorithm application areas, Plan recognition techniques and relationship building among information stored in tables. I will present the flow diagrams of this system and scenario based applications in knowledge based industries. Objectives of the Study and Research Questions Organizational knowledge management is not an old concept given that empirical theories are evident only in the past two decades. It is the realization of the differences between information and knowledge that has given way to artificial intelligence for development of knowledge management frameworks. The business process re-engineering efforts of organizations to sustain and enhance competitive advantages have made the business strategists realize the fact that an in-depth knowledge of the existing processes and their contribution to the business is critical to carry out effective re-engineering of the processes. Such knowledge needs to be generalized and reusable such that their mapping with the business performance can be carried out. Also, it is essential to find out and analyze the conversion of business processes into actions taken by process agents when executing business tasks. This conversion will help to understand the most appropriate actions under given conditions to achieve best performance from the process. Artificial Intelligence experts have developed methods to capture the actions from the tacit minds of agents such that they can be generalized and stored in relational databases and used for decision making (Liebowitz. 2001. p.1-6). One such innovation is the "Plan Recognition" which is a recent technique of analyzing the plan of an agent in executing a task such that a repository of plans is created and the most suitable plan can be selected to execute a process. I intend to contribute to the plan recognition technology by enhancing the YOYO algorithm to further develop the performance measurement of agents. In this context, following are the objectives of my research: (a) To study the empirical theories and generalizations related to Plan Recognition methods. (b) To analyze the algorithms developed in the past that have contributed to Plan recognition methods (c) To recommend enhancements in the YOYO algorithm pertaining to the performance measurement of agents in Plan recognition. I propose the following Research question for my dissertation: "What are the gaps in the YOYO algorithm and how can they be filled to ensure better performance measurement of single hierarchy multi-agent systems using plan recognition technique" I propose to use interpretive method of qualitative research based on the "grounded theory" approach which I have presented in the "research design and methodology" section. Brief Literature Review Gray & Altmann (2001. p.387-391) presented cognitive modeling of human - computer interactions that is focused on modeling human behavior when interacting with machines and execute tasks. They discussed three major applications of cognitive modeling related to human tasks. The first model called CPM GOMS (Critical Path Method - Goals - Operators - Methods - Selection) was targeted to analyze tasks in terms of goals, steps used to perform the task (called operators) and operational methods to achieve the goals (sequence of operators). The model verified the interaction of human skills and the task routine to analyze the overall performance. Another model discussed by the authors was focused on reducing the human errors after the machine successfully completed a task. The model was known as "post-completion error" that was developed using a programmable model called CAPS. The performance of business transactions can be substantially improved by virtue of "memory elements" in the machine that helps human beings to reduce their errors when interacting with the automata systems. The third cognitive model that the authors discussed corresponds with the information access when a process is being executed. For example, a help file referred or a data file accessed to execute steps of the transaction. The authors argued that the memory of the human beings carrying out the transaction pertaining to the location of a helpful illustration is also a skill that develops over time. Hence, experienced people access information faster than the amateurs and hence take lesser time in completing the transactions. The indexing and search techniques developed for helping the human processors have effectively resulted in accelerating the development of their information access skills. The cognitive models to study human behavior in a semi-automation environment can be of two types - Generative models and Descriptive models. The Generative models can be viewed as executable scripts (like computer programs) which can generate the outputs based on some inputs provided to the processor. Such programs can result in measurable outcomes of the human behavior when executing tasks and hence can generate results that are close to reality. These models can also be used to analyze the effects of intermediate steps - like what a human operator might be thinking about the next step. These models mature more and more as their knowledge of circumstantial human behavior increases. (Gray & Altmann. 2001. p.387-391) Plan recognition is essentially a generative cognitive modeling area and YOYO is one such generative model. The descriptive models, on the other hand, can be used to effectively describe the human behavior under given circumstances (inputs) but cannot regenerate the behavior. Hence, they can be used for theoretical strategy formation but not suitable for action research. I hereby present brief literature review on plan recognition and the application of overhearing in plan recognition. In the end of this analysis, I present the YOYO algorithm that uses overhearing to execute plan recognition in business process management systems. Plan Recognition is not a new problem. It was viewed as the intersection between psychology and artificial intelligence by Schmidt and Sridharan et al (1978. p.45-83) who were the first to recognize plan recognition as a problem of artificial intelligence. They defined plan recognition as an application of artificial intelligence to human psychology pertaining to intentions, beliefs and goals of the human actors when performing tasks. They explained that in plan recognition, artificial intelligence is used to develop an experimental paradigm in which the performance of human actors are investigated by capturing their psychological attributes. In the psychological research areas, the inputs to an investigative model and the corresponding outputs can be explained mathematically which forms the baseline of the semantic analysis structures that can be used by artificial intelligence to develop mathematical and statistical models. Mulder and Voorbraak (2003. p.47-61) recognized the following applications of plan recognition: (a) Psychological Modeling (b) Automated paraphrasing and summarizing applications (c) Auto-pilot or Auto-driver systems (d) Natural language understanding explaining utterances of human beings (e) Intelligent human-computer interfacing (f) Reverse engineering of program codes by recognizing the plan behind a piece of code such that goals and effects can be recognized (g) Multi-agent co-ordination for collaborative action planning (h) Tactical Plan recognition - like defining attack and defense strategies in a war fought by military forces Overhearing techniques have been recently employed to study plan recognition. As explained by Gutnik and Kaminka (2006. p.289-302), overhearing is an appropriate technique to study plan recognition in multi agent hierarchical organizational systems. The overhearing is carried out by virtue of systems that are plugged into the communication systems of the group of agents. The output can be used for variety of applications - extending help to agents, identifying their training needs, measuring their performance, assessing gaps in the process effectiveness, identification of wastes and duplications, etc. The overhearing technique has proved to be an effective tool in business process management and enhancements in multi agent systems. However, it has some disadvantages as well. In practical implementation scenarios, every conversation cannot be overheard and linked with the action database especially in large scale multi agent systems. In such systems, it is wise to assume that overhearing resources are limited and hence only the useful subset of communications should be overheard and analyzed through intelligent sampling processes such that plan recognitions can be carried out. In such over hearings, it is important to determine the following attributes of the communications: (a) General specifications of the conversations that can be directly mapped with the actions required by the business processes (b) The overall overhearing strategies that are suitable for such conversations (c) qualitative and quantitative analysis of the overhearing outcomes Gutnik and Kaminka (2006. p.289-302) proposed two broad categories overhearing strategies in such organizations: (a) Overhearing the conversations of most important agents in the organizational system: This category of over hearing shall ensure that the highly valuable communications can be captured that are key to enhancement of the overall efficiency (b) Overhearing the conversations of the most talkative agents in the organizational system: This category of over hearing shall ensure that high volumes of communications can be captured that is key to development of rich action databases. The authors discovered that the first strategy results in a parabolic curve when plotted as per communication volumes whereas the second strategy maintains linearity. This behavior is shown in the figure below: Figure 2: Most Active versus Most Important communications that are overheard and plotted (Source: Gutnik and Kaminka. 2006. p.298) They modeled the conversations in hierarchical organizations using the following four parameters: (a) Conversation distribution: The distribution of conversations depends upon the hierarchy of the organization. In pyramidal organizations for example, the agents that communicate the most are those that are placed at the bottom of the hierarchy. (b) Conversation topics: The agents normally communicate on the topics that are directly or indirectly related to their responsibilities in the organization. (c) Conversation groups: Agents normally communicate with peers or with agents at one level above or below in the organization. Hence, communications that bypass hierarchies are seldom tracked. (d) Conversation roles: The agents at higher levels in the hierarchies communicate with high value content whereas agents at lower levels exhibit mass communication characteristics. The authors emphasized that the trade off of benefits between value of conversations and volume of conversations depends upon the over hearing strategy of the organization. This trade off can be understood by plotting the overhearing strategy as a function of value of conversation types (ratio of value of most active conversations to most important conversations) as shown in figure 3. The value of conversations can be taken as a finite number having a range depending upon the overall framework of overhearing comprising of - efficient overhearing strategies, strategies comparison, value of information and number of over-hearers deployed. Figure 3: Overhearing strategies plotted as a function of the value of conversation types (Gutnik and Kaminka. 2006. p.299) The YOYO algorithm developed by Kaminka, Gal A. and Pynadath, David V. (2002. p.83-95) is targeted to address some of the significant problems in multi-agent overhearing. They discovered that all agents do not communicate always and many a times they understand each other's state by observing certain report screens rather than talking. They realized than when the state of the agent is reported, the communication is normally carried out by one agent while others are in listening mode. Hence, the researchers resorted to report based monitoring whereby the voice reports provided by agents related to their state are captured and their next step is predicted using plan recognition. The key contributions of the researchers are: (a) Plan recognition representation using linear time probabilistic distributions along with the associated algorithms (b) Knowledge of social procedures and interactions among the team to address the unavailable observations and predict future observations. (c) The YOYO algorithm that exploits the knowledge of team hierarchy and models them into a single structure instead of modeling each agent separately. The YOYO algorithm transitions the state of the entire team to the next level if no messages are received. However, if messages are received they are collected and together used as evidence of different plans that may be implied from these messages. YOYO uses a single plan hierarchy and hence all team members are represented together. Hence, accuracy of YOYO depends upon close co-ordination among the agents otherwise the model may fail in loosely connected agent hierarchies. One such example of closely coordinating multiple agent system is ground staff operations of an airport. YOYO can be an excellent algorithm to carry out plan recognitions in Japanese style lean management systems where every deliverable is considered as achievement of the team and not of the individual. Hence, either the entire team transitions to the next level or no-one does. I propose to develop YOYO applicability in closely connected business process management systems and also discover ways to address scenarios when some of the agents in the team transition to next state while others remain in the same state. I am not sure at this stage, but I visualize breaking a large team into smaller teams having agents with similar roles such that every sub-team uses a single plan hierarchy used by the YOYO algorithm. The Research Design and Methodology I propose to conduct qualitative research with a mixed approach of positivism and interpretation. But I do not propose to start with hypotheses rather I have started with research questions. My proposed research is design based with the following stages: Step 1: Setting the Context of the Research Step 2: Formation of Research Objectives and Research Questions. Step 3: Literature review of broad subject areas related to the subject matter Step 4: Literature review of the specific papers that are related to the research problem Step 5: Modification of the YOYO algorithm and finalizing the new form of YOYO algorithm to address the gaps Step 6: Critical Discussions Step 7: Conclusions Step 8: Generalizations [Educational Researcher. 2003 p.5-9] Research Ethics I do not visualize any ethical issues in my research. However, I would like to declare that I will abide by the ethical guidelines of the University and abide by the science pledge commitment. I also declare that the entire content would be written by me originally and wherever the concepts are taken from sources, they would be cited within the text as well as included in the references section at the end of the dissertation. Research Time Table Following is the proposed time table for this research: Table 1: Research Time Table S. No. Activity Target date for Completion 1 Setting the Context of the Research Completed on October 20, 2009 2 Formation of Research Objectives and Research Questions. Completed on November 9, 2009 3 Literature review of broad subject areas related to the subject matter 4 Literature review of the specific papers that are related to the research problem 5 Modification of the YOYO algorithm and finalizing the new form of YOYO algorithm to address the gaps 6 Critical Discussions 7 Conclusions 8 Generalizations Reference List: Aiello, Marco and Busetta, Paolo et al. (2002). Ontological Overhearing. Intelligent Agents VIII. p.177-178. SpringerLink. Becerra-Fernandez, I. (2000). The role of artificial intelligence technologies in the implementation of People-Finder knowledge management systems. Knowledge Based Systems. Vol.13. p.315-320. Elsevier Science Limited. Charnaik, Eugene and Goldman, Robert P. (1993). A Bayesian Model of Plan Recognition. Artificial Intelligence. Vol. 64. p.60-61. Elsevier Science Limited. Design-Based Research: An Emerging Paradigm for Educational Inquiry. The Design-Based Research Collective. Educational Researcher. 2003, Vol. 32 (1): p.5-9, American Educational Research Association. Geib, Christopher W. and Goldman, Robert P. (2009). A probabilistic plan recognition algorithm based on plan tree grammars. Artificial Intelligence. Vol. 173: p.1101-1132. Elsevier Science Limited. Gray, W. D., & Altmann, E. M. (2001). Cognitive modeling and human-computer interaction. In W. Karwowski (Ed.), International encyclopedia of ergonomics and human factors. Vol. 1: p.387-391. Taylor & Francis, Ltd. New York. Gutnik, Gery and Kaminka, Gal A. (2006). Experiments in Selective Overhearing of Hierarchical Organizations. F. Dignum, R. van Eijk, and R. Flores (Eds.). Springer-Verlag Berlin Heidelberg. p.289-301. Retrieved from Springer Link. Kaminka, Gal A. and Pynadath, David V. (2002). Monitoring Teams by Overhearing: A Multiagent Plan Recognition Approach. Journal of Artificial Intelligence Research. Vol.17. p.83-130. Liebowitz, J. (2001). Knowledge management and its link to artificial intelligence. Expert Systems with Applications. Vol.20. p.1-6. Pergamon. Elsevier Science Limited. Mulder, Frank and Voorbraak, Frans. (2003). A formal description of tactical plan recognition. Information Fusion. Vol. 4: p.47-61. Elsevier Science Limited. Schmidt, C.F. and Sridharan, N.S. et al. (1978). The Plan Recognition Problem: An Intersection of Psychology and Artificial Intelligence. Artificial Intelligence. Vol.11: p.45-83. North-Holland Publishing Company. Retrieved from Springer Link. End of Document Read More