Conversation Kit

A directed graph model for conversational UIs

Created as a spare time project by P. Daniel Tyreus - @tyreus

• Minimal dependencies
• Well documented
• Clear, concise API designed to be extended and customized
• Redux-style state management for predictability and easier testing.

Introduction

Conversation kit aims to provide a flexible structure for processing conversations
between a human user and a chat bots ands voice agents. This project
takes the approach of modeling a conversation as a directed graph.
The nodes of the graph (or vertices if you prefer) are the conversation snippets
spoken by the bot. The edges of the graph represent the flow of the conversation based on
the interpreted intent of user by connecting one node to another.

Below is an example of a specialized form of a directed graph conversation known
as a dialog tree. In this case each
node spoken by the bot requires a response from the user. Each edge directs the
conversation to the next node based on the response chosen.

Conversations can quickly get more complicated, with loops and multi-level flow. Below
is an example of the conversation graph for a chatbot to log allergy symptoms.

Installation

The artifacts are available on Maven Central

<dependency>
  <groupId>com.conversationkit</groupId>
  <artifactId>conversation-kit</artifactId>
  <version>2.0.1</version>
</dependency>

Directed Conversations

Conversation kit takes a more generalized approach to modeling conversations. A
DirectedConversationEngine starts with an initial state that specifies a start
node. The engine accepts a message from a user and delegates to a natural language
understanding (NLU) system to determine the user’s intent. The DirectedConversationEngine
then looks at all the outbound edges from the start node and picks
the first one that matches the intent and returns true for it’s validate() method. The engine
then proceeds to the target node for the matching edge and waits for the next user input.

//handle an incoming message from a user
MessageHandlingResult result = engine.handleIncomingMessage("hello").get();
//get the node that the conversation has progressed to
ConversationNode currentNode = index.getNodeById(engine.getState().getCurrentNodeId());

You would then check to see what action the current node is set to perform or
what messages it should send. This will depend on the node implementation, but
a simple example to get a list of messages for the bot to respond with might look like:

for (JsonValue message : currentNode.getMetadata().get("message").asArray()) {
    String m = message.asString();
    //send m
}

JSON Conversation Graphs

This project uses JSON Graph Format to store the
graph representation of conversations. Conversation Kit provides some classes
for reading JSON in this format and creating the internal graph representation.
You can use format you prefer by writing your own JsonGraphBuilder implementation.

Conversation State

The conversation state is a data store designed to persist a user’s progress
through a conversation, help customize the messages sent by the bot to the
user, and to save data from user responses during the conversation. In many
cases the implementation will be backed by a database or other permanent
storage.

Conversation Kit ships with an abstract IConversationState
implementation that shows
how the state can easily be stored using HashMap.

Redux

I writing and using version 1 of this framework I realized that state management
quickly became non-trivial in larger applications. While updating Conversation Kit
for version 2, I became inspired by a number of other projects
I was working on that were using Redux or a derivative for
state management. Redux is traditionally used in front end code to build graphical user
interfaces (GUI). At it’s core it features a predictable, centralized container for application
state. While a conversational user interface is somewhat different from a GUI, it
can still benefit tremendously from Redux-style store.

Redux in Java

Redux is primarily a JavaScript library and I could not find an implementation I liked
in Java. I suspect this is because Redux relies heavily on functional programming
concepts which were not as widely supported in Java when Redux was becoming popular. Java 8
has nice support for functional programming. Redux has a fairly small API, so I
wrote my own implementation
for this project. I may pull that out into a separate project at some point.

Typed State

The implementation I wrote is fairly consistent with the JavaScript version. The main
difference is that I wanted to use a typed state instead of a JavaScript object (or Java HashMap) for the
external API. This just means that the Store constructor must take an additional
argument of a Function that
accepts a HashMap and returns the typed state.

Application State

By default the Redux implementation only handles the conversation state. There is no
requirement for the rest of your application to interact with it. However, since it
is useful to have a centralized state, you can easily add additional state slices
and reducer functions to the store. See
ConversationGraphTest
for a complete example on how to construct a typed state with multiple reducers.

Nodes

A conversation node is a vertex on the directed conversation graph containing
content for the bot to present to the user. Each node has
zero or more outbound edges and zero or more inbound edges. The conversation
traverses the graph between nodes by looking at the user’s intent and choosing
the first matching edge at each vertex.

Each node contains a conversation snippet represents a small bit of dialog in a conversation.
In the case of a chat bot, this might represent a block of text sent as one
message. The content is stored in the metadata field of the node as JSON. The
structure will be highly implementation dependent and is designed to be completely
flexible. For a voice assistent, the metadata might store the link to an audio file.
For a Facebook Messenger bot, one node might hold the JSON representing a button and
another some text.

Creating a node from the JSON is the responsibility of a JsonNodeBuilder.

@FunctionalInterface
public interface JsonNodeBuilder<N extends IConversationNode> {
    public N nodeFromJson(Integer id, String type, JsonObject metadata) throws IOException;
}

In the case of a Dialog Tree, a
DialogTreeNodeBuilder takes JSON that looks something like
the following and creates a DailogTreeNode from it.

{
    "id": "1",
    "type": "DialogTree",
    "label": "1",
    "metadata": {
        "message": ["Hello I'm a test bot.", "How are you feeling today?"]
    }
}

DialogTreeNode

A dialog tree is a type of branching conversation often seen in adventure
video games. The user is given a choice of what to say and makes subsequent
choices until the conversation ends. The responses to the user are scripted
based on the choices made. A Dialog Tree would be a choice to model a
conversation when your UI does not allow free-form responses, like a
questionnaire.

A DialogTreeNode is a restricted implementation of
IConversationNode that
holds a text string to represent the displayed conversation snippet and
retrieves a list of allowed responses from the outbound edges. There is a
working example of how to model, build, and use a Dialog Tree in the
DialogTreeTest.

ConversationNode

A ConversationNode is a more general implementation of IConversationNode. Most
likely you will want to use or extend this for your node implementation. See
DirectedConversationEngineTest.

Edges

A conversation edge is a directed connection between two nodes on the
conversation graph. Each edge has exactly one start node and one end node,
but a node frequently has multiple outbound edges. The conversation
implementation will look at each outbound edge from a node in sequence to decide which
edge to use to continue traversing the conversation graph.

public interface IConversationEdge<S extends IConversationState> {
    public Integer getEndNodeId();
    public String getIntentId();
    public boolean validate(I intent, S state);
    public List<Object> getSideEffects(I intent, S state);
}

After the DirectedConversationEngine determines a user’s intent from a message,
it evaluates the outbound edges for the current node to move the conversation to
the next node. The engine iterates over each outbound edge to find the first to

1. Match the intent’s ID with getIntentId()
2. Return true from validate(I intent, S state);

Once a match is found, the engine dispatches the side effect actions to the
internal Redux store from getSideEffects(I intent, S state).

Validation Function

Use the validate function for cases where there are multiple edges with the same
intent or the intent requires preconditions in the state. For example, consider an
agent that takes food orders. There could be an intent to order a burger (i.e. ORDER_BURGER). The node could
have two outbound edges with the intent ORDER_BURGER, one to handle ordering a cheeseburger
and the other to handle ordering a hamburger. In this case, both statements

• “I would like a cheeseburger.”
• “Let me have a regular burger.”

would match the ORDER_BURGER intent. But the validate function on each edge could
look at the intent slots to only return true for the type of burger it is looking for.

Another way of achieving the same result in this case would be to have two different
intents ORDER_HAMBURGER and ORDER_CHEESEBURGER. But slot filling is a pretty
handy feature of most NLU engines and the validate function lets you apply logic to
the conversation flow based on slot values.

A second use case for validate is to make sure that a precondition in the state
is met before proceeding along an edge. For example, if there are no burgers ready yet,
the state could have a key burgers_ready:false. In this case all ORDER_BURGER edges
may want to return false for validate to direct the user to order something different.

Side Effects

Side effects are another concept borrowed from Redux. Side effects represent any
actions that should be taken by the application as a result of matching an intent
and moving the conversation to the next node. Side effects are dispatched to the
Redux store and should be an instance of Action. A common side effect is to update
the state with the results of the previous intent. From the above example, the edge
matching ORDER_BURGER might dispatch a CHEESEBURGER_ORDER_RECEIVED action. The reducer
could then update the state for the user from current_order:['fries','coke'] to
current_order:['fries','coke','cheeseburger'].

Any side effect that is an instance of Action is processed synchronously. In other
words the state will be updated before the engine proceeds to the next conversation
node. Conversation kit also supports asynchronous actions using the CompletableFutureMiddleware.
If the instance of the side effect is a Future, the action will be handled by the
middleware and processed asynchronously. This
is useful for longer running tasks that don’t necessarily need to finish to let the
conversation proceed.

Natural Language Understanding / Intent Processing

The edges on the conversation graph are matched to the interpreted purpose (i.e. intent) of
the user’s last message. Determining intent from an utterance is in the domain of Natural
Language Understanding (NLU). Conversation kit does not provide sophisticated NLU capabilities. Instead
it is designed to integrate with any external NLU service. To use any third party
NLU service, extend IntentDetector and pass an instance of
the class to the DirectedConversationEngine.

NLU Services

There are several well-known vendors who offer Natural Language Understanding as a service.

• Microsoft Cognitive Services Language Understanding (LUIS)
• Amazon Web Services Lex
• Google Dialogflow
• Facebook’s wit.ai

All of the commercial NLU systems use some type of advanced deep learning technology to
provide the language understanding. For testing and prototyping purposes,
Conversation Kit includes a RegexIntentDetector. This is a very primitive NLU that
just relies on RegEx matching to determine intent. The RegexIntentDetector is not
intended for production use.

For production use, conversation-kit has modules for Lex and DialogFlow.

Putting It All Together

For an example of a conversation graph with all nodes, edges, and side effects all loaded from a JSON file, see
ConversationGraphTest.

If you have questions or suggestions, you can contact me
on Twitter.