However, a few new twists were added to the 1995 competition. First, a complete topological map of the environment was not available. Instead, a set of instructions, for example, "turn third left" and "go past foyer," would guide the robot through the hallways toward a goal room. Second, it would be possible that the instructions contained an error, such as directing the robot toward a nonexistent hallway or room. Third, the information provided in the instructions only specified a number of "openings" that had to be detected before turning into another hallway or entering the goal room. Only the nature of the last opening of every instruction could be inferred (a hallway in the case of a turn instruction or a doorway in the case of an enter instruction), but the intermediate openings could be of any type. The lack of a more qualitative description of the environment limited the capabilities of the probabilistic navigation algorithm on the robot, which could only be used as a sophisticated feature counter (figure 1).

Many human social exchanges and coordinated activities critically involve dialogue interactions. Hence, we need to develop natural humanlike dialogue-processing mechanisms for future robots if they are to interact with humans in natural ways. In this article we discuss the challenges of designing such flexible dialoguebased robotic systems. We report results from data we collected in human interaction experiments in the context of a search task and show how we can use these results to build more flexible robotic architectures that are starting to address the challenges of task-based humanlike natural language dialogues on robots. As a result, the ability of future social and service robots to interact with humans in natural ways (Scheutz et al. 2007) will critically depend on developing capabilities of humanlike dialoguebased natural language processing (NLP) in robotic architectures.

Turning to align itself with the hallway, it begins to move toward the near door of the goal room, which is just a few feet in front. This run should be easy, so the robot thinks. DERVISH plans to use another hallway. DERVISH's brain is an on-board MACINTOSH Later, when the robot finally reaches the node just outside the goal room, the enterroom module is called. This simple procedure aligns the robot with the doorway and then moves a prespecified distance into the room.

We stare intensely at the robot with one eye, keeping the other one out for any surprises. It looks for the door and slowly starts moving into the room. Our minds seem to be sharing the same thought--" YODA, don't fail us now." We decided that the Office Navigation event in the robot competition was to be our first milestone in working toward this goal. It would provide us a context in which to direct our efforts.