For my “Computing Practice and Theory” project, I chose to continue some of the work with Prolog and EBNF grammar parsing that I had begun in the “Computability” program.  Specifically, I wanted to study more about Natural Language Understanding– the process of gleaning intended meaning from natural language.

As Natural Language Processing can be a bit dry, I decided to put a fun spin on the project; I designed and implemented a small command grammar for a Scribbler II robot.  The Scribbler II is a simple educational robot which has a python-based interface library called Myro available.

My program, tentatively titled “ScribPro”, is a hybrid python/prolog application that allows control of a Scribbler via natural language.  All communication with the robot is transmitted over Bluetooth.  The python component handles initialization, messaging to & from Prolog, code execution, and both fetching and sanitization of user input.  I was learning python on the fly as I did this project, so the final python component is pretty messy… but by the end of the quarter I felt that I have achieved basic competency.  I am very glad that I learned it; the ability to use python quickly create simple programs or prototype has already proven itself invaluable.

The Prolog component handles the bulk of the parsing work.  It reads the sentence fed to it from the python component, determines whether or not it is a successful parse, and if it is, converts the parse tree into a functor which it passes back to python.  The validity of a parse is determined according to a grammar.  Early on in the project, I tried to write a very abstract grammar using only the rules of the English language, and quickly realized that it was beyond the scope of this project.  This dilemma is one that anyone trying to do natural language parsing inevitably encounters: English is a messy language!  In order to overcome this and make a usable program within a ten-week timeframe, I chose to severely bound the words and sentential forms that my program would recognize.  Limiting the scope of my grammar to natural language units that are applicable to robot control made the project feasible.

While the final grammar never grew quite as complex as I would’ve liked, I am pretty happy with how the project turned out.  The robot is able to parse & execute a variety of movement-based commands — from plain English!

Not only is the robot able to handle simple sentences such as “Please go forward”, it can handle fairly complex compound sentences such as:

• “Spin in a circle to the left two times.”
• “Go forward four point five feet and turn left, then wait nine hundred milliseconds, turn around and beep once.”
• “Scoot forward until you reach the wall, then move backwards two inches, turn around and beep.”

Beyond the basic text mode, there is an optional voice input mode that taps into the Microsoft Speech Engine.  It is pretty fun to vocally order the robot around!

The fact that I was using two programming languages in tandem (prolog & python) presented some significant initial difficulties in the project.  A good portion of my final code revolves around passing messages back and forth between the two.  The tradeoff was worth it, however– had I been forced to implement my program in a single language, it would have been quite a bit messier.  There is something to be said for using the right tool for the job.  By the end of the project, I gained a substantial amount of confidence in my own ability to multiple languages within a single project.  No doubt this will come in handy in the future.

Here is a diagram of the program flow and component design of my final program:

I now feel confident that I have a handle on the basics of natural language parsing using grammars, and believe that I could implement such a system again in a much shorter timeframe, with a more elegant end result.

If I were to revise this project, I would attempt to abstract the code-generation side to be a level higher.  Right now, the code generated from a successful parse is extremely Scribbler-specific… which I would like to rectify.  I could conceivably create my own generic set of common robotics-related functions which the parser would invoke, rather than having it call specific Myro functions.  I would then implement the ability to map these generic functions to model-specific ones via config files; essentially allowing the parser to be used for other types of robots with ease.

Overall, I had quite a bit of fun with this project, whilst still managing to feel like I challenged myself.  I look forward to further independent research into Prolog, as I feel that logic programming is a valuable yet underutilized programming paradigm.  I also look forward to further tinkering with more advanced robotics projects.

Past weekly blog updates can be found at the following links:

• Week 1: Project Proposal – First Draft
• Week 2: Revised Project Proposal
• Week 3: Final Project Proposal
• Week 4: My Scribbler II Has Arrived!
• Week 4: A Sample Vocab List
• Week 5: Adventures In Integration
• Week 6: Finishing the Python/Prolog Interface
• Week 7: Scribby’s First Steps
• Week 8: You Can Walk The Walk, Now Talk The Talk
• Week 9: Cleaning House (And Code) — includes the full grammar definition.

My final code can be found here:

• scribpro.py – Python Main Program Executable
• nlp.pl – Prolog Natural Language Parsing Component

(Please be forgiving of the code, as I am an undergrad and was learning by doing for most of it.  There are approximately a million things I would change if I could do it all over again.)

If anyone reading this has any questions or is working on a related project, I’d love to hear from you!