Term Project Final Reportcsce 4613 Artificial Intelligence Fall 2009

Term Project – Final ReportCSCE 4613 Artificial Intelligence – Fall 2009

University of Arkansas – CSCE Department

CSCE 4613 Artificial Intelligence – Preliminary Report – Fall 2009

Workflow Expansion & DBMS Logging

Michael Laflamme, Daniel Starling, & Nam Truong

Abstract

The current workflow implementation consists of a monolithic logic architecture. This project contains a few distinct subprojects, namely: rewriting the Prolog decision-making and C++ pathfinding components, design and integration of database logging, and streamlining of the C# code which allows the individual components to communicate. Regarding the Prolog in particular, the goal is to split agent logic into independent agents, all of which concurrently attempt to resolve a problem leading to the conclusion of the workflow.

1. Introduction

1.1 Problem

There is little research regarding the integration of computing with medical workflows and the analytic aid that software can provide in proceeding through a workflow and recording the results. In addition, there is no widely-used method of representing medical workflows, of automating the collection of a record of workflow steps, or of querying and mining past workflow outcomes for events of interest (after action reports).

A medical workflow can be characterized in such a way that it is possible to represent it with a rule-based decision engine (e.g. Prolog) and log the outcome of the operation using a Database Management System (DBMS). By representing and modeling a workflow with Prolog, we can carry out simulated procedures that mimic real life's random circumstances (e.g. varying dose levels for a patient, or patient death) and allow the decision engine to formulate a new path of action based on rules. By logging the activities that take place during the workflow, we can monitor for events as they occur, such as “What percentage of operations required 3 stents?” or “What are some predictors of a bad patient outcome in operation X?”

1.2 Objective

By expanding on past research at the University of Arkansas (UofA), we hope to build a foundation for creating arbitrary medical workflows with exceptional conditions, taking into account different roles, and the ability to query for information from workflows that were carried out in the past.

In more detail, this project is exploring:

-How to break big workflows into much smaller, more modular subtasks

-How to add variation to workflows (randomization)

-How to represent exception and exception handling in workflows

-How to represent different roles and coordinate problem-solving processes to result in a workflow

-How to monitor a workflow for interesting events in progress

-How to log the results of the workflow in an external database

-How to optimize the database to more readily yield useful statistics

-How to add additional workflows

-How to replay workflows logged in the database

1.3 Context

Our project is carried out in the context of Second Life (SL), a 3D virtual world where human participants (known as “avatars”) can create 3D objects and attach logic to them that makes them “smart” and interactive. The workflow project takes place in UofA's area of SL that is dedicated to designing the hospital of the future—one largely reliant on RFID tags to spatially track inventory/items and give them identity.

This environment suggests the notion that “Everything is Alive” (EiA), which is an ongoing UofA project [1]. This is an umbrella idea under which the workflow project falls. In it, we presume that objects have identity, and that many of them can even tell us information about themselves (thanks to a built-in computing capacity). By supposing that pervasive computing already exists, we can assume that many aspects of medical workflows can be carried out under automation, underlining the importance of characterizing these workflows in a way that a computer can understand and remember.

1.4 Potential Impact

At its current stage of development, workflows could be analyzed to optimize equipment, staff, and timing for any implemented operation. If the agents move beyond simply enacting a scene to actively solving problems, then the workflow itself is a tool used in generating optimal solutions where an agent has complete knowledge of past workflows, and can act according in the current workflow based on the interaction of logic and known desirable outcomes. Moving to the realm of science fiction, workflows could be used to control smart entities in the real world. For example, a robot doctor could be continually updated by a workflow that runs many generations of agents susceptible to natural selection, with spider entities bridging the gap between the real and the virtual. In this way, problems in the real world can be solved with precision and speed greater than that of any one person.

Workflows can also be used for educational and entertainment purposes, neither of which are necessarily distinct. Instead of describing an operation to a patient, a doctor can just show the patient the procedure, without the gory details. One or more users can replace digital agents and have specific roles in the workflow, with possible errors and unforeseen situations arising not unlike that of the real world. Finally, workflows can be used just for entertainment's sake. Did you ever want to perform an open heart bypass?

2. Related Work

2.1 Key Technologies

Our project (and the all-encompassing EiA project) is developed within the virtual world known as Second Life. SL differs from other similar games in that it fully supports scripting and object creation/manipulation by players, which gives us the freedom to model currently developing technologies as they might exist within a decade or two (or perhaps even longer). This allows us to focus on researching real-world applications for such technologies before they even come into prevalence.

A primary focus of the EiA project is varying applications for RFID systems, especially in the area of inventory management. This aspect in particular is of interest to our project, as inventory control is inherently connected to workflow efficiency.

By creating virtual workflows such that AI agents can solve them, we are essentially designing the very same thing for real-world applications. If a logic-based program can successfully complete the workflow by following a set of rules (or steps, as one might view them in an actual workflow), then humans should be able to utilize the same process to solve the same problem.

On the broader subject of workflows in general, the Workflow Management Coalition (WfMC) is an organization which oversees the development and standardization of workflows, mainly through a language of their own creation—XPDL—which (according to WfMC) is “the leading process…design format for storing the visual diagram and process syntax of business process models.” [4]

We make extensive use of custom HTTP web services, a byproduct of our integration into other UofA SL hospital projects (e.g. tracking virtual items through RFID) and need to speak with programming-enabled objects inside of Second Life. To carry out workflows in Second Life, we also require a customized pathfinding system to navigate the 3D environment. In fact, expanding on a previous pathfinding project is a peripheral goal of the workflow project for this semester.

Prolog threading capability is crucial to this project as it allows the main Prolog engine

to evaluate agent communication concurrently. Similarly, sockets allow for inter-process communication. The SWI C# library (see [5]) allows for the main Prolog process to call C# subroutines directly.

2.2 Related Work

Clark discussed the implementation of multi-agent systems in Qu-Prolog. The Prolog component of this project implements a multi-agent system through the use of multiple threads and multiple processes-- the difference being multiple processes do not share the global database. Clark states that in situations where an agent wishes to send a message without knowing the destination identity, "it is better to use a communications server that routes messages based on content rather than destination identification". That is, the sole form of agent to agent communication in this project is broadcast communication via changes to the global database. To enable the various processes to interact with the threads in the main system, sockets, a form of inter-process communication is used. Lastly, to enable Prolog to C# interaction, a message queue associated with a thread is used.

Because agents in a multi-agent system cannot have knowledge of everything in the system, the system itself or a mechanism in the system must narrow or hide knowledge appropriately. Clark uses a bid arbitration thread to regulate the actions of agents in their auction scenario. In this project, the system regulates the modification of the world state.

There are different approaches to exception handling of workflows, but at the core, exceptions must be triggered, identified, and passed around until a resolution is found. Han and Klein suggest a Java/C++ approach to handling exceptions. First, an individual agent must recognize that something out of the ordinary has occurred during the course of the workflow- “Something is wrong”. This general triggering of an exception must be made more specific for optimal resolution-- that is, the agent must narrow down the exception to a single case - “Something is wrong. The patient has died”. Klein suggests an inheritable approach by traversing an exception tree, where at each node certain characteristics must be met for more specificity of exceptions. The mechanism for dealing with the exception must first suspend the current workflow, and allow for communication between agents. Again, a Java/C++ approach is suggested by passing an exception up the caller-callee tree until some agent has the tools to deal

with the exception. At the top (in this case, the global Prolog database), methods independent of the caller-callee relationship can be implemented.

2.3 Related EiA Projects

Our workflow project relates to several other EiA projects, e.g.;

• Mirror Worlds project – Our project could allow us to monitor real-life medical workflows as they are carried out by observing a reflection of them in a virtual environment. We could also replay past workflows in this same manner.
• Ontology project – Parts of our project assume that certain supplies are needed to complete the medical operation workflow. This might require associating items with a particular set of workflows, and viewing a workflow as a recipe with a list of ingredients and a set of steps. The information gathered is also crucial to the logic of the agents in the workflow, in that agents can deal with exceptions based not on logic alone, but also on past outcomes.
• Smart Devices – In order to avoid burdening medical professionals with error-prone data entries to record the status of a medical workflow (which would preferably happen in real-time), we need devices (wheelchairs, pill bottles, etc.) to recognize when they're being used and report it.
• Pathfinding project – Our workflow project will be renovating and expanding on a previous project that allows us to represent a hospital as a model (this model is independent of Second Life, as if we were modeling it after something in real life) and then determine how to get from point A to point B within it. A hospital “hypervisor” program might use this technology to move items around a hospital.

3. Architecture

3.1 Requirements or Use Cases

• A pathfinding system that can determine an optimal route for avatarbots to take when acting out a particular medical workflow

◦Need to use the existing pathfinding system that already accounts for the complexities of avatarbots interacting with Second Life

◦Must automate the task of importing the Second Life hospital model into our internal representation, and then optimize the algorithm used for pathfinding so that avatarbots can better avoid items.

• Avatars (agents) play roles (surgeon, patient, nurse, etc.) in a workflow. Each agent has a set of responsibilities and their own internal model of a workflow. As the workflow proceeds, it must coordinate the agents to “solve the problem” and execute the procedure. Agents must exhibit:
• Autonomy – The agent has, and resolves its individual tasks. Actions of one agent do not directly affect other agents, but instead through some intermediary--in this case, the Prolog database.
• Locality – An individual cannot know everything in the system. The system hide information from some agents while giving it to others.
• Decentralization – The system is not the controlling agent but merely a reflection of actions by agents.
• Exception handling – Each agent must be able to communicate exceptions and if appropriate deal with the exception specific to his domain.
• Random behavior – Each agent must have failure probabilities for a chosen number of actions.
• The C# interface must not have any logic related to agents nor the system, but merely act as a translation unit from the Prolog database to language, SL, DBMS, C++, etc, can understand.

3.2 Architecture or Design Space

Our project consists of primary 3 components and one extra project (a pathfinding component). These components are:

1. At its base, the Prolog component was responsible for housing all agent logic, and the current world state. The primary goal this semester was to split the workflow logic, that is each agent possessing his own logic that was separate and cannot be entirely known by other agents. Two primary sub-components were necessary to achieve a multi-agent system. The first obvious component- agents that can independently interact with other entities, and the second- a system that housed the current world state, dictated communication rules, and interacted with the C# interface.

A first attempt of this goal was thought to be achievable by utilizing the meta-programming capabilities of Prolog-- that is, allowing a system to uniquely process some request by compiling the relevant logic. For example, given two agents A, B, and a system, communication between the two agents would proceed by first having the system consult the agent that was expected to begin the exchange. In Prolog, this can be achieved by merely using consult/1, or use_module/1,2, the advantages of adding modules instead of full files being the hidden nature of goal execution in modules-- the system can execute the module without having access or knowledge of its logic. Once added to the database, A would process his unique logic and attempt to communicate with B by passing a name and message to the system. The system would recognize the name of B, retract the logic of A, assert the logic of B, and so on.

This approach has problems. First, one could recognize that multiple retractions and assertions are not necessary-- that is, A and B could have separately named methods, ie a_resolve, b_resolve, and the system can call that unique method appropriately without having to worry about functors clashing, however this would necessitate the system breaking atoms apart and concatenating the appropriate prefix or postfix so as to allow the correct functor to be evaluated. At the time, this author thought this action to be undesirable, as the sheer number of functors meant for every agent communication, the system would have to keep track of the source, the destination, and the method, and break apart/ append atoms appropriately. Perhaps in a future project, one could look into achieving this same idea by using the module system. Each agent would only have one globally visible functor, and all communication would have to be routed to this functor, thus lessening the the system's role of atom manipulation.

Because the author choose to keep all agent methods identical-- that is, agents A and B both have the same "resolve" method, then multiple assertions and retractions are necessary. There is a major problem with this approach. Consider communication between A and B. At any time, only the logic of a single agent is allowed to be in the database, thus the system adds A to the database, A processes his logic accordingly and tells the system he needs to talk to B. The system retracts all of A's functor and asserts all of B's functor. The problem then lies in the fact that A is not yet done processing. By calling the system, A is still waiting to evaluate whether the call was true. The system retracts the very functor that A is still in, and replacing that with B's exact named functor, thus producing situations in which A begins execution of his own logic, but ends by mistakenly executing B's logic. One could explore allowing agents not to call the system directly but just assert facts into the database, thus allowing the functor to end, and avoiding the problem outlined above, however, this author decided to go in a different direction once this problem was encountered.

One could avoid the problem of database consistency all together by allowing each agent to maintain his own database-- that is, for every agent, there is a separate Prolog process running. This is achieved by allowing the C# interface to start a process for each individual agent, and a core process for the system. Inter-process communication was achieved through sockets. The system, acting as a server, would accept incoming requests from the agents, where the agent spoke first, identifying himself. Each agent is connected to this server, but not between each other. Every agent is placed into a polling cycle. At the top of the cycle, the agent asks the server for the current state of the world. A very simple world state was implemented for this project, where a state is the last action performed by some agent-- the beginning state is null. The agent takes this state, processes it, and sends appropriate data back to the system. The system retracts it's current world state and asserts this new state. The new world state then is then polled by some other agent or in some cases the same agent and becomes the catalyst for that agent action.