My Internship at Knexus Research

I interned at Knexus Research for 2 months from June 1, 2019 to Aug 9, 2019. The internship was very fruitful, and I managed to improve my software development, research, and teamwork skills. I also managed to explore a lot of Washington D.C.

The internship brief was for an AI intern to work on a narrative generation system. My lab does a lot of work in this area, and although I hadn’t personally done any research work in it; I was familiar with the general concept due to a course I had taken under my advisor (CSC 791: Generative Methods). The internship did not seem like a traditional S/W intern role, and it was in an AI-related field, so I decided to apply.

The Knexus interview process was unique and felt much more appropriate in terms of testing skills required for the role than the typical whiteboard coding interview prevalent in S/W jobs. The first round was stereotypical - a couple of problems presented in a LeetCode-like interface with a limited time to solve them. Having practiced for this type of thing, I was able to clear it relatively easily.

The second round was the most interesting to me. I was given access to a private GitLab repository with a toy Python codebase implementing the API for a simple card game. I was asked to write the functionality for the game logic. This involved reading the rules, understanding the existing API, and all the software dev stuff like writing tests, ensuring clean code, providing adequate documentation, doing version control correctly, etc.

The logic of the rules was easy enough to implement - no fancy algorithms or data structures required. Making sure my code was simple and easy to read was a much more exciting challenge. I’m used to the competitive programming one-and-done style of code, and having this interview test me on code readability and organization was nice.

I managed to clear this round as well and pass most test cases (I was later informed I missed a couple for empty lists). A face-to-face round followed where I was asked about my skills and interests, and I soon had the offer letter, which I accepted.

Skipping over the hassles of the CPT approval process and the search for adequate housing, I moved to DC a week before the internship was due to my lodging in the heart of DC. The apartments are usually snapped up by UG Congressional interns looking to work in the White House, so as an engineering intern working quite a distance away (National Harbor is almost 12 mi away, and a 1.5-hour journey by metro+bus), I was very out of place. I had friendly roommates though.

On the first day, I was given a tour of the facilities, was given my equipment, met with my mentors and the rest of the team, and was explained the goals of the project. We were to develop a children’s story generator - an AI system which could dynamically come up with varied and interesting stories for children, and whose output could be controlled via user input (where the user would most likely be a parent). Our team of 3 had been assembled to contribute to the project in unique ways - while I was brought on as the software developer, responsible for writing the code for the system, Julia Sufrin, a Humanities graduate from Wesleyan, was brought on for her expertise in narrative theory. Her knowledge of the theoretical side of narratives would help us develop a computational system to generate narratives. Next, Zohreh Dannenhauer, a PhD in AI planning systems, was brought on to inform the implementation of our final system. Our mentors envisioned the solution to involve planning in some capacity, and so her knowledge would be invaluable. I later found out that they had interview processes different from mine, and which matched the contributions they were intended to make to the project.

Our team got to know each other, and we started to lay the ground work for the project. We had daily meetings with our mentors, Justin Karneeb and Dr. Michael Floyd, on progress, roadblocks and direction. My first proposal was to re-purpose existing planning-based narrative generation systems for use in our system. Zohreh researched the planning literature for examples of these systems while Julia looked through the narrative generation literature for work regarding children’s stories specifically, so that we may have some insight into the features we want our system to have.

The field of narrative theory attempts to break down existing stories to detect patterns, templates, tropes and conventions that are used. For example, Joseph Campbell’s template of the Hero’s Journey¹ describes a pattern found in many myths and legends across cultures. Aristotle’s dramatic structure² describes how a play should be structured in terms of causal chains. Freytag’s pyramid³ describes the arc involved in the protagonist overcoming their adversary. All these patterns informed how we wanted to structure the stories produced by our system (which at this point we decided to name Grackle, after a bird found commonly in Julia’s hometown, and which makes a lot of noise).

The field of narrative generation is obviously concerned with automatically generating narratives. The planning approach to narrative generation was introduced by James Meehan in his Tale-Spin paper.⁴ The environment and characters of a story are described in a planning formalism like PDDL, along with the actions they could possible take, and a planner is used to find a path to a goal state. The resulting plan is the basis for the final story and is converted into natural language text by a hypothetical system known as a discourse generator. Of course, it could be converted into a story in any medium such as film, comic strip or audio, not just text.

The most current narrative generation system we could find was Glaive, by Stephen Ware. It improved the narrative generation process by allowing conflicts - differences between individual character goals, to occur. It worked out of the box and was straightforward to use.

We attempted to create simple domains inspired by popular children’s books like Peppa Pig and Curious George. Julia dissected for us patterns in these stories which we could use as templates, while Zohreh leveraged her experience to translate these patterns into error-free PDDL. I worked on writing these PDDL files while attempting to tie the disparate patterns into a working system which met our criteria.

Julia figured that children’s stories usually involved a main character going out of home on a journey, learning something, and returning home. They also had unique, immutable personality traits that manifested in the way they responded to events. We developed the idea of modelling character personality traits which would govern which actions they choose in response to events. These stories also involved exchanging of objects, where a character would obtain an object and use it later in the story. Zohreh came up with a clever way of implementing this in PDDL such that a planner follows a similar path.

I then hit upon what would become the final design of our system. I envisioned each story as a series of quests, where each quest would be a somewhat self-contained episode involving our main character who gains an object from each quest, and who must give an object to participate in other quests. By building a chain of quests where each quest is connected to the other by the object which must be exchanged, we can construct a story. This also made use of our disparate stories which we could use as a quest bank.

Julia suggested some improvements to the model to ensure the story seemed more believable (some quests need not give any item, there must be an overarching conflict to solve etc.) while Zohreh prototyped a simple version in PDDL. I worked on dynamically generating PDDL files to form the quest bank, while developing the framework for Grackle.

Development progressed rapidly at this point. I worked on implementing the software while accommodating extensions and new features suggested by my teammates. Julia worked on providing templates for new quests, improvements to our quest model, and language for our discourse generator. Zohreh and I worked to expand our quest model from a linear chain to a story graph, and I came up with an algorithm to dynamically generate a random story graph and incorporated it in Grackle. She also worked on some experimental features like the mutable personality traits (to represent the protagonist’s growth) which didn’t make the final system.

We struggled with coming up with a useful evaluation metric for our system. Narrative generation papers we found tend to not evaluate the quality of the generated output, and human evaluation would have been a bit cumbersome to do effectively, given that we needed to use children as our test subjects. Our mentors advised we forego a rigorous evaluation given that we aimed to only develop a prototype, so we settled on merely demoing it on our mentor’s daughter and showcasing her response.

Our final presentation consisted of a full system technical and theoretical description to the rest of the employees at Knexus, and a demo of the system. The response was encouraging, and we received some useful feedback regarding the system and its output.

Overall, I greatly enjoyed my time at Knexus. I learned a lot from my mentors and teammates, especially given how diverse their backgrounds and experiences were. I sharpened my software development skills in Python, having developed an application and tests with 500+ LOC and learned about git flow and good version control practices that I’ve begun using on personal projects ever since. I liked working on the story graph generation algorithm as it was a fun diversion from software dev tasks. I learned the importance of good communication considering different, and even non-CS backgrounds, since I had to communicate with a Humanities graduate, and a PhD steeped in a different dev environment than I was used to. I learned the importance of good presentation from my mentors who encouraged me to develop a GUI for our final system demo, instead of the terminal-based application I was planning to use.

And I explored a lot of Washington D.C.

1. Campbell, Joseph. The hero with a thousand faces. Vol. 17. New World Library, 2008. ↩

2. Aristotle. “The Poetics of Aristotle.” Translated by S. H. Butcher, The Poetics of Aristotle, by Aristotle, www.gutenberg.org/files/1974/1974-h/1974-h.htm. ↩

3. Freytag, Gustav. Die technik des dramas. S. Hirzel, 1894. ↩

4. Meehan, James R. “TALE-SPIN, An Interactive Program that Writes Stories.” Ijcai. Vol. 77. 1977. ↩