UserPreferences

Natural Language Interaction with Robots

1. Natural Language Interaction with Robots

This is a page about our research in Natural Language Interaction with Robots. It is a project for Alden's combined thesis in Computer Science and Linguistics. Hopefully, it will contain lots of stuff soon.

1.1. Abstract

Natural language communication with robots has obvious uses in almost all areas of life. Computer-based natural language interaction is an active area of research in Computational Linguistics and AI. While there have been several NL systems built for specific computer applications, NL interaction with robots remains largely unexplored. Our research focuses on implementing a natural language interpreter for commands and queries given to a small mobile robot. Out goal is to implement a complete system for natural language understanding in this domain, and as such consists of three main parts: a system for parsing a subset of English our robot is to understand, a semantic analyzer used to extract meaning from the natural language, and a first-order logic engine, used by the robot for storage and deduction of facts. Using such a system we will be able to demonstrate that a mobile robot is capable of understanding NL commands and queries and responding to them appropriately.

1.2. Papers

Here are some papers from around that have to do with natural language interpretation and also some imperative semantics:

1.3. My Paper v.4 (4/27)

Here is draft 4 and a short 8-page version.

1.4. My Paper v.3 (4/17)

Here is draft 3 and a short 7-page version.

1.5. My Paper (3/12)

Here is draft 2!

1.6. My Paper (12/21)

Here is the current draft of my first semester write-up.

1.7. Notes

1.7.1. Ok some of the last code (3/4)

Here we have code which can parse and analyze sentences including prepositions (plus the embedded declaratives that were part of the last update).

This code can understand stuch sentences as "turn left if you see a wall to your right." Here are some example interactions: This has the robot find a corner: 

 >>> do you see a wall
 No
 >>> move until you see a wall
 >>> turn right until you don't see a wall to your right
 >>> do you see a wall to your front
 No
 >>> move until you see a wall to your front

This makes the robot spin around until it find a bright light: 

 >>> do you see a bright light
 No
 >>> turn left until you see a bright light

This makes the robot beep the first time it sees a wall: (and find the wall) 

 >>> beep if you see a wall
 >>> move to a wall

This makes the robot beep every time it sees a wall and also turn around so that it's not facing the wall 

 >>> beep whenever you see a wall
 >>> turn right for 180 degrees whenever you see a wall

This makes the robot avoid walls (the last command gets it going) 

 >>> turn right until you can't see a wall whenever you see a wall to your left
 >>> turn left until you can't see a wall whenever you see a wall to your right
 >>> turn right whenever you see a wall to your front
 >>> move for 60 seconds

This makes the robot follow a light (slowly) 

 >>> turn right until you see a light to your front whenever you see a light to your right
 >>> turn left until you see a light to your front whenever you see a light to your left
 >>> turn until you see a light

We can also ask the robot things: 

 >>> do you see a wall to your right
 No
 >>> turn right until you see a wall
 >>> do you see a wall to your right
 Yes!
 >>> do you see a light to your left
 Yes!
 >>> turn right until you can't see a light
 >>> do you see a wall to your front
 Yes
 >>> turn for 180 degrees
 >>> do you see a light to your front
 Yes!
 >>> do you see a wall
 No

We can also ask about the line sensors ("do you see a line"), but they are quite flaky.

1.7.2. More Code! (2/14)

1.7.3. Logical Engines (1/31)

Here are two python programs that are supposed to do logical inference and stuff:

1.7.4. For Myro v. 0.5.9 (11/14)

These are now updated for the most recent myro.

for some reason, "turnoff your right light" has no effect. It's exactly the same as the left light, but it just doesn't work. It's weird

1.7.5. Even More (11/13)

It now takes duration type prepositions and adverbs, ie

Also, it now understands simple contextual commands:

for "again" it gets the most recent non-contextual command and does it again. For "move again" it finds the most recent non-contextual move command and does it again. Here are the new files (I don't think these work with the newest myro--it's just an issue about the types of commands--myro is changing quickly, so when the commands become stable I'll update this stuff:

cool

1.7.6. More Semantic Analysis (11/1)

I've explanded the number of objects and verbs in the world. Now it will parse the following:

I'll keep expanding the objects. The big thing left is parsing AdvPs, which shouldn't be too bad. I really want to get a working logical engine, because then sentences like 'beep when you see a wall' would come out fine I think with the structure I've set up. The 'you see a wall' sentence would be a separate logical thingy, but it should be completely compartmented.

1.7.7. Semantic Analysis! (10/29)

Ok now we have a symantic analyzer. There's no pretty picture for this one, since it's so incredibly weird and complicated, but it does seem to work a little. I've built the major analysis structure, and I have to fill in meanings for words. Also, I need to exend the "obj" class so that commands like "turnon your left light" will work. I think I know how to do this, and hopefully it won't be too much work. Running the symAnalyzer.py file brings up a command request. Currently, it understands 'move', 'go', 'move to the wall', 'go to the wall' and that's it. Since the crappy interface I real quick wrote up waits for the robot to stop doing things before it askes for another command, you can't tell it 'go' or 'move' because it'll never stop waiting (and crash python). In other words, it currently understands only 2 commands, but it understands them the "right way" ie it parses and builds up a layer from the parse tree. Once I spend a little time on building up the meanings of verbs and stuff that number should increase dramatically. Here's the code:

So that's pretty cool.

1.7.8. More Robot Stuff (10/11)

So I wrote up a bunch of python classes that give us some structure and hopefully build up a subsumption brain. The code is a little long, so I'll just include a link here:

Also, I made up a little schematic to show what the heck is going on here:

http://students.haverford.edu/awalker/CSling/brain_diagram2.jpg

Here's a description of some of the things in the diagram and in the code:

1.7.8.1. Brain:
The brain is made up of layers. Every time the brain is asked for its command, it goes through (in reverse order, so older = more powerful) and polls each layer in turn and asks "what do you want to do?" The current layer being asked has access to the current command that the brain would output (ie the cumulative command so far). In this way, the layer can decide to simply override the current commands, modify them to try to accomplish stuff at once, or just leave them alone. The brain is connected to the scribbler through the nerves object, which is where it gets senses and sends its commands
1.7.8.2. Layers :
Each layer is made up of blocks. When a layer is called, it calls its first block (I could have put the first block in the linked list straight into the brain, but I thought it might be a good idea to have an extra structure between them in case we needed things in the future).
1.7.8.3. Blocks:
The block is sort of the atom of movement. When a block is constructed, it's given a function and a next block (which might be null). The function must take three arguments (maybe 4 in the future if I make each function have properties modifyable (like speed) from outside), the senses, the current command, and the next block. The block outputs what the function outputs. A typical example (which is implemented in the code) is to have a "until" block. This block is constructed with a function which looks at the IR sensors. If they're off, it calls the next block in the list and simply returns whatever it returns. If the IR sensors are on, it ignores the next block, passes on whatever commands came in, and kills itself (its layer). This block could be given any block as its sub-block, but I gave it a movement block, which has a function which simply returns a command to move forward without caring about anything. In this way, the robot moves forward (the until block keeps calling the move block) until it sees at wall (at which point the until block kills itself (and its sub-block)).
1.7.8.4. Nerves:
1.7.8.5. Senses (sensors object) :
I made this because getting data from the robot is really slow. This data object gets reset every iteration. After being reset, it's passed around to the different layers as they make commands. If it's asked for a particular sensor data, it asks the robot for it and remembers it. The next time it's asked for that data, it doesn't bother asking the robot. Obviously, it has to be reset every iteration, but it's effective for speeding things up as much as possible

1.7.9. Robot Stuff (10/8)

1.7.9.1. Move to the wall code

This is a interesting piece of code that might scale: 

def move(speed) :
    return (lambda : (r.motors(speed, speed-.1), True))

def rotate(speed) :
    return (lambda : (r.rotate(speed), True))

def see(what, where='non') :
    if what == 'IR' :
        if where == 'left' :
            return (lambda : (r.readIR(0) == 0))
        elif where == 'right' :
            return (lambda : (r.readIR(1) == 0))
        elif where == 'straight' :
            return (lambda : (r.readIR(0) == 0 and r.readIR(1) == 0))
        else:
            return (lambda : (r.readIR(0) == 0 or r.readIR(1) == 0))
    elif what == 'line' :
        currentLine = (r.readLine(0) == 0 and r.readLine(1) == 0)
        return (lambda : (r.readLine(0) == 0 and r.readLine(1) == 0) != currentLine)
    else :
        return False

def until(action, cond) :
    action()
    while not cond() :
        continue
    r.stop()

def whil(action, cond) :
    if cond() :
        action()
        while cond() :
            continue
        r.stop()


def face(left, straight, right, nil):
    print [left(), straight(), right(), nil()]
    if  straight():
        return
    if nil():
        print "nothin.."
        until(move(.4), lambda: not nil())
        if straight() :
            return
    if right() :
        print "to the right"
        until(rotate(-.3), straight)
        return
    if left() :
        print "to the left"
        until(rotate(.3), straight)
        return

def IRface() :
    face(see('IR', 'left'), see('IR', 'straight'), see('IR', 'right'), lambda:(not see('IR')()))


def follow():
    while True:
        IRface()
        time.sleep(.5)
        continue

until(move(.5), see('IR'))

This will cause the robot to move forward until it sees something with its IR sensors, or move forward while something else. The follow command is built up of smaller commands, and basically comes down to: if you see something to the right, turn right until you see something in front of you, and likewise for left. It's pretty slow to respond because of the lag time, but it works alright. The until, whil commands work pretty well. I'm trying to translate the sentences at the bottom into similar commands.

I haven't tried anything with multithreading or anything. It seems like maybe there should be a clock or something and every time it ticks each layer gets to do something based on the outputs of all the other layers or something. Maybe we wouldn't need multithreading. Probably not with this subsumption stuff--we'd just have a list of functions to call to see what commands they would generate. Something like that.

1.7.9.2. Facts
Here are some random helpful facts about the Scribbler. They're about right for my computer, although I'm not sure how consistent they are across robots/computers:

(my robot has a bug where the forward(1) actually drives the right wheel faster, so my recorded speeds are for r.motors(1,.9) and r.motors(.5,.3)) 

r.rotate(1), time.sleep(.055), r.stop()
gives just about a quarter turn

1.7.10. Subordinating Prepositions And Nouns (10/1)

1.7.10.1. Sub. Preps.
It seems like maybe the conditionals in commands should really be where the pluses are. They would control the flow of commands. Also, for the subordinating prepositions, they seem to have pretty well defined meanings:

If conditionals take the place of the pluses, then I think contexual commands can be just like regular commands in layers and stuff. They would be instantiated, immediately make a command which does something (like kill a layer, etc), and then die. However, this way, they can also be embedded in conditionals, like "stop moving when you see a light." The conditional would block the command until see(me, light) (or something) was true, and it would then allow it and kill the layer right off. The "Whenever" subordinating preposition would be special, I think, and remain. Then you could do something like "Go faster whenever it's bright." Assuming, of course, that it could parse "when it's bright."

1.7.10.2. Nouns

I think all the nouns should just be a list of all the sets they're a member of (all the adjectives that can refer to them), and then semantic analysis of the DP would mean an intersection of sets. This doesn't handle prepositions, however.

1.7.11. Another grammar that contains simple declaratives (9/29)

Here's another grammar which contains a declarative sentence (DS) part. I'll make up productions for a Q (query) soon so it won't have just C (command). Anyway with this grammar you can see "move forward until you see the wall." Of course, it sill needs a semantic analyzer.... 
ISDSProds = '''
    C -> IS
    DS -> DP DVP
    IS -> VP
    DVP -> DV | DV VPP | DV DP | DV AdvP VPP | DV AdvP | Adv DV | Adv VPP |
           Adv DV AdvP VPP | Adv DV AdvP
    VP -> V | V VPP | V DP | V AdvP DP VPP | V DP VPP | V AdvP DP | V AdvP VPP |
          V AdvP | Adv V | Adv VPP | Adv V AdvP VPP | Adv V AdvP
    DP -> NP | D NP
    NP -> N | AP NP | N NPP | AP NP NPP | NumP NP
    AP -> A
    AdvP -> Adv AdvP |
    NPP -> P DP
    VPP -> P DP | SubP DS
    NumP -> Num
    Num -> '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '10' | '20' | '45' |
           '30' | '90' | '180' | '360' | '270' | "one" | "two" | "three" | "four" |
           "five" | "six" | "seven" | "eight" | "nine" | "ten"
    Adv -> "quickly" | "slowly" | "carefully" | "right" | "left" | "straight" | "back" |
           "backwards" | "forward" | "forwards" | "around"
    N -> "I" | "you" | "room" | "light" | "dark" | "lights" | "yourself" | "sound" | "beep" |
         "song" | "wall" | "box" | "line" | "note" |"seconds" | "feet" | "inches" | "degrees"
    D -> "the" | "your" | "a" | "an" | "that" |
    A -> "right" | "left" | "center" | "high" | "low" | "black" | "white" | "dark"
    P -> "to" | "until" | "for" | "along" | "toward" | "towards" | "from" | "into"
    SubP -> "after" | "if" | "unless" | "until" | "when" | "whenever"
    V -> "face" | "spin" | "move" | "go" | "turn" | "turnon" | "play" | "light" | "blink" | "beep"
    DV -> "face" | "spin" | "move" | "go" | "turn" | "turnon" | "play" | "light" | "blink" | "beep" |
          "say" | "hear" | "see" | "is"
    '''

1.7.12. An Actual Grammar! (9/28)

I made a grammar to convince myself that the semantic analysis would be possible to make these module things. Here is the (python - nltk_lite) grammar: 

productions = '''IS -> VP
    VP -> V | V PP | V DP | V AdvP PP | V AdvP | Adv V | Adv PP | Adv V AdvP PP | Adv V AdvP
    DP -> NP | D NP
    NP -> N | AP NP | N PP | AP NP PP | NumP NP
    AP -> A
    AdvP -> Adv AdvP |
    PP -> P DP
    NumP -> Num
    Num -> '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '10' | '20' | '45' | '30' |
           '90' | '180' | '360' | '270' | "one" | "two" | "three" | "four" | "five" | "six" |
           "seven" | "eight" | "nine" | "ten"
    Adv -> "quickly" | "slowly" | "carefully" | "right" | "left" | "straight" | "back" |
           "backwards" | "forward" | "forwards" | "around"
    N -> "light" | "dark" | "lights" | "yourself" | "sound" | "beep" | "song" | "wall" | "box" |
         "line" | "note" |"seconds" | "feet" | "inches" | "degrees"
    D -> "the" | "your" | "a" | "an" | "that" |
    A -> "right" | "left" | "center" | "high" | "low" | "black" | "white" | "dark"
    P -> "to" | "until" | "for" | "along" | "toward" | "towards" | "from" | "into"
    V -> "move" | "go" | "turn" | "turnon" | "play" | "light" | "blink" | "beep"
    '''

1.7.13. A Picture! (9/27)

http://students.haverford.edu/awalker/CSling/diagram2.jpg

Here is a possible schematic for a subsumption intelligence. Note that all the modules have access to all the sensors, and each module produces commands which flow down. I'm not sure (noted by the gray lines) whether a module would have access to the commands being passed down the bus. Also, the bus is really three buses, one for each output device (lights, motors, sound). The pluses notate some way of combining the commands passing down. Also, the conditionals, which I think come mostly from prepositional phrases, can block or allow commands to pass. Also, if any piece of a command (a layer) dies, the whole command dies. In this way, a conditional like (to the wall) can stop the command. The avoid layer would be the only thing which is there at startup. The other two layers where what I hope the sequence of commands "Beep when you see a wall", "Move to the wall" would produce. After it finds the wall, it would kill the top layer and go back to just two. A contexual command like "Stop beeping" would kill the second layer.

1.7.14. A Grammar (9/27)

Here's a quick grammar for parsing simple imperatives. I did this because I was thinking about putting layers together for the intelligence without representation idea, and I was wondering what pieces of the sentence fit where. I'm trying to make a diagram of what the layered "intelligence" would be.

Anyway I think the V will be a layer (function) taking DP as an argument and being modified by AdvP. It will then be blocked/facilitated by PP (I'll try to make a diagram). I think maybe the PP is going to have to decide whether it wants to modify the verb function of just block it. I would prefer if there were no modification, but then I'm not sure how "Move along the line" would work.

1.7.15. Intelligence Without Representation (9/26)

This seems like a very good way to represent intelligence. The questions is whether to represent the entire state of the robot as a single layered decomposition of activities or have each command be its own layered system.

1.7.16. Arguments to Commands (Alden - 9/24)

Each command has an argument about condition on doing the command. It seems to make sense to have the prepositional/adverbial phrase generate a lambda function which is just called every so often. For instance:

(I never finished writing this, but I think you get the point)

1.7.17. Commands It Should Understand (Alden - 9/22)

1.7.17.1. Movement:

Move ("go" can go wherever "move" is"): 

  Move forward                               -   r.forward(.5)
  Move back                                  -   r.backward(.5)
  Move backwards                             -   r.backward(.5)
  Move right                                 -   r.turnRight(.2); r.stop(); r.forward(.5)
  Move left
  Move forward a little                      - r.forward(.5); r.stop();
  *Move forward as far as you can
  *Move forward until you can’t
  Move forward until you can't move forward  - until(move(.5), stalled)
  Move forward two feet                      - duration(move(.5), 2 feet)
  Move forward for 4 seconds                 - duration(move(.5), 4 seconds)
  Move forward slowly                        - move(.2)
  Move forward quickly                       - move(1)
  Move forward slowly for two feet           duration(move(.2), 2 feet)
  Move                                       - move(.5)
  Move to the line                           - until(move(.5), see('line'))
  Move into the black box                    - until(move(.5), see('line'))
  Move into the white box                    - until(move(.5), see('line'))
  *Move forward until I tell you to stop
  Move to the wall                           - until(move(.5), see('IR'))
  Move forward to the wall                   - until(move(.5), see('IR'))
  Move until you can see the wall            - until(move(.5), see('IR'))
  Move forward until you hit the wall        - until(move(.5), stall)
  Move forward along the line                - ? (complicated)
  Move backwards along the line              - ?
  Move towards the light                     - ? (the light sensors are weird and finicky)
  Move forward into the dark                 - ?
  *Move alongside the wall
  *Move along the wall until you see another wall
  Quickly move forward to the wall           - until(move(1), see('IR'))

All summarized by: Move(direction, speed, condition_on_moving)

Turning: 

  Turn right                                     - r.rotate(-1), time.sleep(.055), r.stop()
  Turn left                                      - r.rotate(1), time.sleep(.055), r.stop()
  Turn right for 2 seconds                       - duration(r.rotate(-.5), 2 seconds)
  *Turn directly right
  Turn right 90 degrees                          - r.rotate(-1), time.sleep(.055), r.stop()
  Turn right a little                            - r.rotate(-.5), r.stop()
  Turn right until you see the wall              - until(rotate(-.5), see('IR', 'straight'))
  *Turn left until you find the brightest light
  *Turn to follow the wall
  Turn around                                    - duration(rotate(.5), .5 seconds)
  Turn back                                      - duration(rotate(.5), .5 seconds)
  *Turn all the way around
  *Turn halfway around
  *Turn and face the other direction
  *Turn in a circle
  *Turn right a lot
  *Turn right some
  *Turn to face the wall
  Turn until you face the wall                   - duration(rotate(.5), .5 seconds)
  Turn right slowly                              - r.rotate(-.3)
  Turn right quickly                             - r.rotate(-1)
  Slowly turn around                             - duration(rotate(.3), 5 seconds)
  Turn slowly right                              - r.rotate(-.3)
  *Turn on a dime

Turn(direction, speed, condition_on_turning)

Turn is really just two commands of the following: Move(wheel, direction, speed, condition_on_moving)

1.7.18. Non-Movement:

Lights: 
  Turn on your left light                       -  r.setLED(0,1)
  Turn on your lights                           -  for i in range(0,3): r.setLED(i,1)
  Light your lights                             -  for i in range(0,3): r.setLED(i,1)
  *Turn your right light on
  Turn off your lights                          -  for i in range(0,3): r.setLED(i,0)
  *Turn your lights off
  Blink your lights                             -  for j in range(0,10): time.sleep(.1), for i in range(0,3): r.setLED(i,1)
  Turn on your lights when you see the wall     -  when(lambda:for i in range(0,3): r.setLED(i,1), see('IR', 'straight'))
  Turn on your lights until you see the wall    -  until(lambda:for i in range(0,3): r.setLED(i,1), see('IR', 'straight'))
  *Display a binary 6 on your lights
  *Turn on your left light if you see an object to your left

Combinations of: SetLight(state, light, condition)

Sound: 

  Play a song
  Play an A
  *Make a beep when you see the wall
  Beep when you see the wall
  *Beep for 2 seconds when you stop moving

Combinations of: Sound(hertz, condition)

1.7.18.1. Contextual:
It seems like commands fall into one of three categories:

Contextual commands seem as though they can only modify waiting or executing commands, with the priority given to executing commands. I imagine using multithreading of some kind would simulate this effectively or more easily? Also, every time the state of the robot changes (its logical database of facts about itself), every command would have to check to see if their condition function was changed. Also, ideally, if you asked it to run into a wall, it would ask you if you were sure or something.

General:

Movement:

1.7.18.2. Rachel's Spam

For my CS380 class I am attempting to affect the results of the Bryn Mawr Google-type search engine. I would like to increase the ranking of some of my spam-type [WWW]sites. As it is now [WWW]they don't even show up in the search engine! I don't think they are getting crawled. By the way, this is [WWW]Rachel Heaton, though the previous link has nothing to do with me. Anyway, please forgive my spamming the wiki and let it stay until November 14, 2006. Thanks Alden!