Quagents and Natural Language


What part of "Drop your weapon and raise your hands" don't you understand?

Reading

Chapter 22 is probably adequate, but you might have fun adding some content from Chapter 23. James Allen's book Natural Language Understanding has some sections you might find interesting, such as 3.3 on tops-down parsing and 9.2 on semantic grammars. In fact, they are on the course's electronic reserves waiting for you.

You might enjoy reading about the approach the CSUG robot team took to dealing with natural language input. (Don't get your hopes up, there may not be enough details to be helpful but we could always ask Tom and Dasun to come in and explain more.) Here are Mabel 2002 and Mabel 2003 and a similar Mabel 2003 Jnl UG Research .

Assignment

This is a team assignment. Teams of two or three are OK. Make sure there is a chance for each team member to shine! This assignment seems to break up nicely into fairly independent parts.

We want to do Quagent version of the Textbook's idea in Chapter 22 about ordering the agent in the Wumpus world around, possibly asking it questions, and perhaps having it respond in natural language to things it sees or experiences.

All the NLU processing (parsing, semantic interpretation, generation) will take place at the Quagent level, not the bot level. So your Quagent's NLU-understanding code will take as input NL sentences from you and will produce as output quagent-protocol orders for your bot(s). Likewise your quagent program may want to turn quagent perceptions (which it may have to ask the bot for) into natural language.

It is quite possible to hack together something that works pretty well but that does not demonstrate knowledge of current NLU theory and practice. On the other hand, much of NLU theory and practice is about fairly complex issues of language in which the context is not as constrained as ours. Generally your goal is to exhibit as much NLU expertise as you can while doing the most sophisticated an general (i.e. impressive) communication you can with your quagent. So there are points, if you will, for style and content.

I'd like to see a formal grammar for your interface, a parsing algorithm (either written by you or found and used by you -- say from a Java library, code you find on the web, whatever), and a way to hook the parse to semantics that you then use to generate the protocol messages to the bot. Sophistication, generality, elegance, and power are what we want. If you want to explore some cool topic like resolving pronoun reference (like what does "it" mean in one of the sentences below), great! OR another fun idea is to have the quagent come back with a question if it doesn't understand something. As usual, there is an enormous literature out there that can help, but also as usual the text should be close to providing enough information. Let us know if you feel you need more, and let the class know thru BB if you find an especially useful reference.

Entirely off the top of my head, it seems that the following sort of inputs and outputs are reasonable. Y is you, Q is quagent

Y: Move 10. Q: OK. [bot moves]
Y: Please drop the tofu. Q: OK.
Y: Put down the tofu. Q: Yeah, yeah, it's always something...
Y: Please go straight ahead 10 then left 5. Pick up the Tofu. Q. Whatever.
Y: Move 10 if you hold a head. Q: OK.
Y: Now Bot5, if your wealth is greater than 100, go ahead 10, otherwise tell me your wealth. Q: OK [Bot5 moves].
Y: Now drop it. Q. Don't understand.
Y: Now drop it. Q. Drop what? [better, eh?]
Y: Now drop it. Q. Sir, yes sir! (drops tofu) [best but not easy...we're beyond simple sentence understanding at this point.]
Y. Can you move ahead 20 and tell me what you see? Q. Cain't see diddly.
Y. Can you move ahead 20 and tell me what you see? Q. I see Gold, tofu, and kryptonite.
Y: What are you holding right now? Q. I'm holding nothing.
Y: Turn left 90 unless you're holding gold. Q: OK.
Y: (to Bot1) Go take the gold from Bot2. (to Bot2) Please give your gold to Bot1. Qs: No problemo.
Y: Show me the view from over by the box. Q: Here you go. [view from bot is displayed].
Y: No, no, please turn 60 right instead. Q: Like this? [new view is displayed].

You're aiming for a natural and usable interface to one or more bots using natural language in a way that illustrates generalizable concepts that will scale to more concepts, more complex syntax, and possibly even some memory about the conversation so far.

Reserve Reading!

I have had two sections of James Allen's book Natural Language Understanding scanned into your CSC242 course reserves. One is on top-down parsing and the other on semantic grammars. I think that combination of techniques is quite promising for this domain.

Free Code!

If you're feeling brave you may want to try the chart parser whose code is in A tar file . It is based on Allen's book, which you may want to borrow or acquire somehow. The development parallels the book, and the javadoc refers to the text. There's a README.txt with the barest possible overview. The author (George Ferguson) went to some trouble to make the javadoc pretty detailed, with stuff from the book, but javadoc doesn't have any high-level organization aside from the classes.

As noted in the toplevel TODO.txt, the parser is almost able to handle gaps (linguistic movement).

What you really need for actual NLU is the semantic features, which this code doesn't provide at all (it would be the next thing to add, but it's actually quite complicated, especially to work out proper representations of the SEM features in Java as opposed to Lisp).

AND there's another, more complete version: James' Lisp version (freely available to go with the book) does more, at some cost in readability. It is pointed to from his web site but seems to be in A tar.gz file . It comes with an online manual.

On the other hand, maybe a simple language would be adequate... maybe something as simple as a programming language? Real NLU people would never consider this seriously, but a simple country boy like I wonders why not something like a parser-generator tool like lex, yacc, or more modernly yylex and bison, for example? (Well, besides the pop-ups, I mean.) I don't know just what's right or wrong with this idea. "That's the glory of it."

As George Ferguson observes, "You'll only get a recursive-descent LR(1) parser out of yacc/bison (or something like that). The standard approach in NLU is chart parsing, which is effectively a form of dynamic programmiing (not that it's usually described that way). James' book has a good description of several parsing formalisms (FSMs, recursive descent, etc.)

Trying to program semantic rules (what bison/yacc call "actions") in C for manipulating NL semantic structures (or even syntactic ones, for that matter), would be what I would call painful (to say nothing of distracting). If you really want bison/yacc, at least find the program that does it for java. I forget what it's called, but I used it in a project once and it was great. Let's see... "java_cup" and "jlex":

They are at: CUP and JLex .

Don't forget Java StringTokenizer for simple command parsing.

What to Hand In

Send CB a (strictly private and confidential) review of the performance of each of your teammates if there is anything special that I should know. Thats brown@cs.rochester.edu .

Here are some project Computing Resource and Project Grading Guidelines we all will be following.

Make sure we can tell who did what in the project. Provide a thorough and thoughtful write-up of your work, formally describing the environment and the actions available to your quagent, and your goals and methods for communicating with it. Make sure your readers appreciate the quagent's full linguistic capabilities -- don't sell yourselves short. Examples, lists, explicit grammars, etc, all are useful. Don't forget the references section.

Aim for the goal that your project is so well-conceived, well-done, and well-reported that your report will take its place in the 242 Hall of Fame. I am hoping for ingenious, compelling experiments and conclusions. Transcripts of "conversations" or examples of the most complex order-giving and order-taking behavior are good.

Create a PDF document of your writeup and upload it to BB.

Write in good scientific style in the form of a computer science technical report. You may find useful this set of advice on writing and homework. There are some example writeups of student projects on the Main Assignment Page .

---
242 Home Page

This page is maintained by Nature Lover

Last update: 1.9.04.